Do Sparse-Recovery Signal Thresholds Survive Real Feature Matrices?

Theory for sparse estimation, the problem of finding which few of many features actually matter from noisy data, makes a sharp prediction. Whether you can find all the relevant features depends less on the total signal strength than on how strong the weakest relevant feature is. If one true coefficient sits near the noise floor, recovery needs many more samples, and the required count can be written down in closed form. Nearly every paper that proves such a law checks it only on simulated data with independent Gaussian features. Meanwhile, papers that select features on real data report prediction accuracy and never ask how strong the selected features were. As a result, nobody knows whether these "weakest link" thresholds describe what happens on the correlated, non-Gaussian feature matrices practitioners actually use.

This proposal tests that directly. We keep the real feature matrices from public benchmarks, such as spoken-letter spectra, breast-cancer gene expression, mouse proteomics and single-cell RNA counts. Into each matrix we plant sparse coefficient vectors whose smallest entry, and the spread of entry sizes, we control exactly. We then measure, for each planted feature, the coefficient size at which standard algorithms start detecting it. Because we plant the truth, recovery can be scored exactly while every other property of the data stays real. The question is whether a per-feature version of the textbook threshold, computed from the real matrix, predicts these empirical detection points. If it does not, we want to know whether the failure comes from correlation alone or from something beyond correlation.

Core Claim

We conjecture that on real feature matrices, the minimum detectable magnitude is not a single number for the whole problem. Each feature has its own threshold, set by how much of that feature's variation is not explained by the other relevant features. Concretely, for a planted support $S$ of size $s$ in a matrix with $p$ columns and $n$ rows, noise standard deviation $\sigma$, and $v_j(S)$ the residual variance of standardized column $j$ after regressing it on the other columns in $S$, we predict feature $j$ is detected once its coefficient exceeds

$$\tau_j = c\,\sigma\sqrt{\frac{2\log(p-s)}{n\,v_j(S)}},$$

where $c$ is one constant per algorithm, fitted once and then held fixed across datasets. With independent Gaussian columns, $v_j = 1$ and this reduces to the $\sqrt{\log p / n}$ scale in Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting, which derives necessary and sufficient sample sizes in terms of the minimum magnitude for Gaussian designs. The ratio of smallest to average coefficient size is the quantity Resolution Limits of Sparse Coding in High Dimensions uses to bound sample complexity. In our formula it enters only through which features fall below their own $\tau_j$.

A falsifiable consequence follows. The fraction of the support recovered should be predicted by counting planted features with $|\beta_j| > \tau_j$. That count gives a partial-recovery curve, a quantity Fletcher et al. explicitly leave open.

This threshold governs missed true features. False alarms on inactive columns are governed separately by how strongly inactive columns correlate with the support, so we score both sides. We do not claim the formula covers false alarms.

Relation to Prior Work

Several papers motivate the gap. Fletcher et al. validate their bounds only with Gaussian Monte Carlo heatmaps. Average case analysis of Lasso under ultra sparse conditions derives replica-method predictions for Lasso's true and false positives when the support is tiny, and matches them to simulations with Gaussian matrices, though its motivating genomics data is never used. Stability and Risk Bounds of Iterative Hard Thresholding shows a fast-rate regime under a strong-signal condition, again only on synthetic logistic regression. Greedy-pursuit guarantees for orthogonal matching pursuit (A Sharp Condition for Exact Support Recovery With Orthogonal Matching Pursuit) and orthogonal least squares (Sparse recovery via Orthogonal Least-Squares under presence of Noise.) give minimum-magnitude conditions through restricted-isometry constants. Those constants cannot be computed on real matrices, so their tightness there is unknown.

We reuse all of these as the algorithms and predictions under test. We do not prove new bounds. The contribution is that the measurement matrix is no longer idealized.

Other papers constrain the design. Signal Strength Estimation in Logistic Regression Using Data Splitting is the closest work that touches real data, a single-cell RNA dataset. It estimates a global signal strength, proves its mapping only for Gaussian features, and reports degradation at very low signal. That is exactly the regime of the weakest coordinate we target, so we treat it as a competitor, not a tool. Feature Selection using Stochastic Gates and SAND: One-Shot Feature Selection with Additive Noise Distortion work on real benchmarks but report accuracy and concordance. They cannot say whether a feature they missed was weak or simply absent.

Finally, The Empirical Validation Gap frames the general failure mode: proofs with idealized assumptions that go untested against real workloads. We treat our study as one concrete instance.

We also address a tension in the literature head on. Fletcher et al. and Wainwright locate the hardest signals at vanishing minimum magnitude. Donoho et al. show that for message-passing reconstruction error, the least-favorable signals have very large amplitudes, because big entries interfere with thresholding. These are different error criteria, but on correlated real matrices the two effects can combine: a strong feature correlated with a weak one could mask it. Our planting design separates the two effects.

Research Program

The feature matrices come from ISOLET (7,797 × 617 spectral features), METABRIC (221 clinical and genomic features), mice protein expression (77 proteins), the single-cell glucocorticoid dataset (2,400 cells × 600 genes), and row subsamples of HAR70. We also use MADELON's 500 columns as a reference, since 480 of them are synthetic noise. For each matrix we subsample rows to sweep $n$ and standardize columns. We draw supports either uniformly or deliberately among highly correlated clusters. We assign coefficient profiles at fixed minimum magnitude:

  • equal magnitudes;
  • geometric spread, giving a low minimum-to-average ratio;
  • three-point mixtures in the style of Johnstone;
  • profiles where a strong coefficient is placed on a column highly correlated with the weakest one.

Responses are generated with Gaussian noise and, separately, with noise resampled from the residuals of a real-response fit.

The algorithms run on each instance are:

  • marginal correlation thresholding;
  • Lasso, tuned by both cross-validation and the oracle support-size rule;
  • orthogonal matching pursuit;
  • orthogonal least squares;
  • iterative hard thresholding;
  • stochastic gates as the nonlinear-capable method.

For each planted feature we fit a logistic detection curve in $|\beta_j|$ and read off the 50% point. That point is the empirical threshold, compared against $\tau_j$.

Baselines

The naive reference is the global-SNR predictor. It assigns every feature the same threshold, derived from total signal energy as if all coefficients were equal. If it predicts per-feature detection as well as our formula, the weakest-link view adds nothing on real data.

The standard theoretical reference is the independent-Gaussian threshold of Wainwright and Fletcher et al. with $v_j = 1$, applied to the real matrix after standardization. It represents what a practitioner would conclude by trusting the published law as written.

The strongest existing predictor is the replica theory of Okajima et al., which gives quantitative true-positive and false-positive counts for Lasso as a function of samples, magnitude and regularization. We evaluate it with each dataset's $n$, $p$, $s$ and planted magnitudes, so it receives exactly the instances and noise draws our formula receives, with no extra tuning beyond its own regularization input.

On real-design recovery thresholds, no reported result was found on Lacuna for any of these predictors. All published comparisons are synthetic. The closest real-data numbers in the file measure prediction rather than support. Stochastic gates reach a concordance index of 0.633 with 2 features on METABRIC, versus 0.580 with 44 features for Cox-Lasso (Feature Selection using Stochastic Gates). SAND reaches about 92.6% accuracy on ISOLET (SAND). These are not comparable targets, which is part of the motivation.

The key ablation replaces each real matrix with Gaussian rows drawn from its own empirical covariance, then reruns everything. This isolates whether real-data deviations come from correlation, which $v_j$ captures, or from non-Gaussian structure such as heavy tails, sparsity of counts or outlying cells, which it does not. A second ablation drops $v_j$ but keeps the support-wide mutual coherence. This tests whether the per-feature quantity is what matters, rather than a global coherence summary.

Our formula beats the baselines if it reduces the median absolute log-ratio between predicted and empirical thresholds by at least half relative to the Gaussian reference. It must do so on at least four of the five real matrices, with a single fitted constant per algorithm. We will also report where it loses.

Why not just…?

Why not just simulate correlated Gaussian designs, such as Toeplitz covariance, instead of using real matrices? This is a real threat, and the matched-covariance ablation settles it. If Gaussian rows with each dataset's covariance reproduce the real-matrix detection curves, then the gap is purely covariance. The honest conclusion would be that correlated-Gaussian theory suffices, and the paper becomes a recipe for plugging in $v_j$. If the curves differ, which is plausible for count-valued single-cell data, real matrices carry structure that synthetic correlation studies miss.

Why not just evaluate feature selectors on real benchmarks by accuracy, as SAND and stochastic gates do? Accuracy cannot reveal whether a weak feature was missed, because the true support is unknown. The METABRIC result makes this concrete: 2 selected features versus 44 with modest differences in concordance index. That says little about which support is correct. Planting is the only way to score recovery exactly while keeping the real matrix.

Why not just estimate signal strength from real data with the data-splitting method of Li and Liu? That method recovers a single global strength. It is proven for Gaussian features and degrades at low signal, so it cannot locate the weakest coordinate. We include its estimate as an extra global predictor alongside the naive baseline to show this directly.

Why not just tune the threshold by cross-validation? Cross-validation optimizes prediction, not support recovery. Accelerating Cross-Validation in Multinomial Logistic Regression with ℓ1-Regularization reports that literal cross-validation becomes unstable at the small regularization values where weak signals live. We run cross-validated Lasso as one of the tested algorithms, so its weak-feature miss rate is measured rather than assumed.

Decisive Checks

The first check is calibration of per-feature thresholds against the Gaussian and replica predictions across all five real matrices, together with the matched-Gaussian ablation.

The second check is the partial-recovery curve. The predicted fraction recovered, obtained by counting features above $\tau_j$, should track the observed fraction across sample sizes. If it does, that is the first empirical answer to the partial-recovery question Fletcher et al. leave open.

The third check is the interference experiment. Holding the weakest coefficient fixed, we raise the amplitude of a strong coefficient on a correlated column. If the weak feature's detection rate falls, then on real matrices the weakest-link and large-amplitude views both hold at once, and a corrected threshold must include an interference term. If it does not fall, the weakest-link view alone describes real data.

Either outcome is informative. Each reports, for the first time, how far published signal-strength laws can be trusted outside the Gaussian simulations they were proven for.