Robust Without Trying: Testing Nonnegative LP Recovery Against Adversarial Measurements

Many sensing problems try to recover a mostly-zero, nonnegative signal, such as which of thousands of DNA targets are present in a sample, from far fewer measurements than unknowns. A classic way to do this is to solve a linear program, an optimization with a linear objective and linear constraints, that finds the nonnegative signal with the smallest total mass consistent with the measurements. Theory says this works under conditions on the sensing matrix. Those conditions cannot be checked for any real matrix, and the key theory paper reports no experiments at all. A separate, purely theoretical line of work shows that the fast iterative methods practitioners actually use can be broken by a "semi-random adversary": someone who adds extra measurements that are correct but deliberately correlated. That work proposes a new nearly-linear-time algorithm to fix the problem, and it too has no experiments.

This note proposes the missing experiments, organized around one simple observation. In the noiseless case, the linear program is automatically immune to the semi-random adversary. Adding correct measurements can only shrink the set of feasible signals, so if the program recovered the truth before, it still does afterwards. The same argument gives a per-instance check that can be computed. It is a dual certificate: a single extra linear program whose solution proves that the recovered signal is the program's unique answer. Nobody has measured how much this free robustness is worth, how fast it fades with noise, how it compares in wall-clock time and accuracy with the fast methods the adversary breaks, or whether the certificate predicts success on realistic microarray-like sensing matrices. Those are the questions here.

Core Claim

Consider measurements $b = Ax^* + \xi$, where $A$ is an $M \times N$ sensing matrix with $M \ll N$, $x^* \ge 0$ has at most $k$ nonzeros, and $\xi$ is noise. The nonnegative relaxation studied in Linear Program Relaxation of Sparse Nonnegative Recovery in Compressive Sensing Microarrays is

$$\min_{x \ge 0} \ \mathbf{1}^\top x \quad \text{subject to} \quad Ax = b .$$

Qin et al. prove two things: sparse solutions sit at vertices of the feasible set, and the program recovers $x^*$ under a nonnegative restricted property defined through restricted isometry and orthogonality constants. Computing those constants is NP-hard, and the paper contains no numerical experiments.

The relevant per-instance object is easy to write down. A candidate solution $\hat{x}$ with support $S$ is the unique optimum if the columns of $A_S$ are linearly independent and there is a dual vector $y$ satisfying

$$(A^\top y)_i = 1 \ \text{for } i \in S, \qquad (A^\top y)_j \le 1 - \gamma \ \text{for } j \notin S, \quad \gamma > 0 .$$

The largest achievable $\gamma$ can be found with one linear program. Call it the certificate margin.

Now suppose a semi-random adversary appends rows $R$ to a well-behaved matrix $G$, and all the new measurements are correct. Any certificate $y$ for $G$ extends to $[G; R]$ by giving the new rows zero dual weight. This yields a concrete, testable prediction. In the noiseless case, the success curve of the linear program on $[G; R]$ should lie on or above its curve on $G$ alone, for every adversary. Methods that rank coordinates by correlation with the measurements carry no such guarantee, and Semi-Random Sparse Recovery in Nearly-Linear Time proves they can be broken. The open empirical questions are how large the gap is in practice, how much of the advantage survives noise and sensor nonlinearity, and whether the linear program's running time is actually the obstacle that motivates nearly-linear-time alternatives.

Research Program

The first component is an adversary suite that can be reproduced. Since no semi-random benchmark exists in the literature, it must be built. The base matrix $G$ will come in three types. The first is i.i.d. Gaussian. The second is binary probe-affinity matrices modeled on the [3,4,7] Hamming-code designs and the 70-spot calibration chip in Compressive Sensing DNA Microarrays. The third is a near-square Gaussian regime: dimension 64 with 30 nonzeros, the setting where Randomly aggregated least squares for support recovery and Refined least squares for support recovery report that correlation-based methods break down.

Adversaries will append correct measurements of three kinds. Duplicated rows overweight a few directions. Decoy-amplifying rows place large weight on a chosen set of inactive coordinates while touching the true support lightly, which inflates correlation scores on the decoys. Correlated block rows mimic the cross-hybridization patterns seen on physical chips. Each adversary is parameterized by how many rows it adds relative to the size of $G$.

The second component is a head-to-head benchmark with noise and nonlinearity layered on top. In the noisy case, equality constraints become a residual constraint measured in the $\ell_1$ norm, which keeps the problem a linear program. The extension argument above no longer holds exactly, because adversarial rows bring their own noise. The study measures how quickly the guarantee erodes. It also tests one targeted remedy: per-row residual budgets, which keep adversarial rows from absorbing the noise allowance. For nonlinearity, readouts pass through the saturating hybridization curves documented by Sheikholeslami et al. This directly tests whether Qin et al.'s linear model survives realistic chip physics.

The third component turns the certificate margin into a diagnostic. Its predictive value for exact support recovery will be measured across all regimes. The aim is a usable replacement for the uncomputable restricted constants, one a chip designer could compute before fabricating a probe set.

The fourth component, which is secondary and has an explicit fallback, is an attempt to implement the short-flat algorithm from Semi-Random Sparse Recovery in Nearly-Linear Time. That paper relies on an abstract "step oracle" for its updates. The implementation will realize this oracle with an off-the-shelf approximate solver and will record its cost and accuracy. If no faithful implementation is achievable, the documented obstacles become a result in their own right. This mirrors Ene and Nguyen's own admission in A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint that their algorithm cannot be run in practice.

Baselines

The do-nothing reference is the linear program run on the clean matrix $G$ alone, with adversarial rows discarded. This is an oracle that knows which rows are adversarial. The noiseless prediction is that the program on $[G; R]$ matches or beats this curve. Any shortfall points to a numerical or implementation failure that must be found before other conclusions are trusted.

The simplest competitor is one-shot top-$k$ correlation: compute $A^\top b$ and keep the $k$ largest entries. Exact Recovery of Sparse Binary Vectors from Generalized Linear Measurements proves this optimal for sparse binary signals under Gaussian sensing. It is the strongest argument that heavier machinery is unnecessary, and it is the method decoy rows are designed to fool. It will receive the true $k$, which favors it.

Iterative hard thresholding, from Iterative hard thresholding for compressed sensing, will be run with a nonnegativity projection, the true $k$, and a step-size grid. Orthogonal matching pursuit will be run alongside it. These are the fast methods the semi-random paper proves brittle, and this study would be the first to measure that brittleness. Refined least squares, from Refined least squares for support recovery, is the strongest existing method in the near-square regime. The file reports only qualitative results for it: "a 100% success rate with significantly fewer equations than competing methods" in the 64-dimensional, 30-sparse Gaussian setting. No reported numeric result was found on Lacuna for any method on a semi-random benchmark. The semi-random paper's own algorithm is included if the fourth component succeeds.

All methods see identical matrices and measurements and run on the same CPU. Each tunable method receives the same grid budget: about twenty configurations, chosen on held-out instances. The linear program uses a standard open-source dual simplex or interior-point solver with default settings.

An ablation isolates the key ingredient, namely solving a global optimization over all constraints rather than scoring coordinates locally. In the ablation, the linear program is truncated to its first few interior-point iterations and then thresholded to $k$ entries. The proposal wins if two things hold. First, under adversaries that push top-$k$, hard thresholding, and matching pursuit below 50% exact recovery at a given measurement count, the full program stays within a few points of its clean-$G$ curve. Second, its wall-clock time remains within a small constant factor of refined least squares at the scales tested.

Why not just…?

Why not just run nonnegative least squares, or a nonnegative Lasso, and skip the theory? These are serious threats, because nonnegativity alone already imposes much of the needed structure. They will be included as baselines under the same tuning budget. Nonnegative least squares is a convex program over the same feasible set, so in the noiseless case it may inherit some of the same robustness. If it matches the linear program everywhere, the conclusion is that the robustness belongs to global convex fitting rather than to the $\ell_1$ objective, and the paper will report it that way.

Why not just reweight or normalize rows and then run hard thresholding? Duplicate rows are easy to detect. Decoy-amplifying rows are not: they are correct measurements, and their harm comes from the correlation structure they add, which row-norm equalization does not remove. The study will run hard thresholding after row normalization and after leverage-based row downweighting. If this cheap fix closes the gap on every adversary family, the practical message changes to "preprocess, then iterate," and that will be stated.

Why not just use subsampled least-squares ensembles, which already handle hard regimes? Refined least squares draws random row subsets. When adversarial rows make up a large share of the matrix, most subsets contain them, so the method has no structural protection. It also solves many inversions per peeling step. The benchmark measures both its accuracy as the adversarial fraction grows and its running time as $N$ scales.

Why not use swap or pipage rounding to steer toward the sparsest vertex, as Qin et al.'s open problem seems to invite? In the noiseless nonnegative problem, a simplex solve already returns a vertex. Moving a fractional point along directions that preserve $Ax = b$ until a coordinate hits zero is essentially a simplex pivot. Rounding therefore adds no information, and the real question is whether the linear program's vertex is the true signal. The certificate answers that question per instance. Rounding would matter only under extra budget constraints, which these problems lack.

Proposed Experiments

The decisive experiment is a set of phase-transition maps. Each map plots measurement ratio $M/N$ against sparsity ratio $k/M$, showing exact support recovery over 100 trials per cell. Maps are produced for every combination of base matrix, adversary family, and adversarial fraction, at $N$ = 64, 1,000, and 20,000.

The first check is the noiseless monotonicity prediction. The linear program should be no worse on $[G; R]$ than on $G$, while top-$k$, hard thresholding, and matching pursuit should degrade as the adversarial fraction grows. If the fast methods do not degrade, the semi-random concern is largely theoretical, and that is itself a publishable answer.

The second check sweeps noise level at fixed adversarial fraction. It reports both relative $\ell_2$ error and support recovery to locate where the free robustness ends, and whether per-row residual budgets extend it.

The third check measures the certificate margin's area under the ROC curve for predicting exact recovery. It is computed separately on Gaussian, binary Hamming-style, and saturating-nonlinearity matrices. The target is above 0.9 on linear models, and the study will report how far the score falls under saturation.

The fourth check records wall-clock time against $N$ for every method on sparse binary matrices. This settles whether the linear program's cost is a real practical barrier, or whether, like the galactic constant in Ene and Nguyen's analysis, the motivation for nearly-linear-time alternatives does not hold up under measurement.