State Evolution for Decimated Message Passing in Sparse Regression

Many hard estimation problems are solved in practice by decimation. The procedure estimates everything, permanently fixes the few variables it is most confident about, simplifies the problem, and repeats. It works well empirically. In sparse regression, a decimation method guided by least-squares estimates reported zero false positives on a gene-expression study where the Lasso reported 131 An adaptive shortest-solution guided decimation approach to sparse high-dimensional linear regression. We have almost no theory that says when fixing variables one batch at a time should beat estimating them all at once. A separate body of theory, the asymptotic decoupling principle, explains why large random regression problems behave like many independent one-dimensional problems. Under it, each coordinate's estimate looks like the true value plus Gaussian noise of a known size. That size is tracked across iterations by a scalar recursion called state evolution. The theory assumes a fixed problem. It does not describe what happens when variables are removed from the problem mid-run.

This note proposes to close that gap for sparse linear regression. Decimation is driven by Approximate Message Passing (AMP), an iterative estimator whose per-coordinate outputs obey the decoupling principle. We derive a two-level state evolution that tracks the effective noise across both inner message-passing iterations and outer decimation rounds. The derivation yields a sharp and partly negative prediction: decimation should help only insofar as it amounts to changing the scalar denoiser, the one-dimensional shrinkage rule AMP applies to each coordinate. If the prediction holds, it explains when decimation is worth its cost and supplies a cheaper static substitute. If it fails, it pinpoints where decoupling breaks.

Core Claim

The setting is $y = Ax + w$, with $A$ an $M \times N$ random design. Suppose decimation pins coordinate $i$ based only on its own decoupled observation $r_i = x_i + \sigma Z_i$. An example rule pins it when $|r_i|$ exceeds a threshold $\tau_k$ at round $k$. Then the coordinates left active form a population whose distribution is the previous prior conditioned on a local event. We conjecture that interference on the remaining coordinates stays asymptotically Gaussian after this selection. The file flags this as an open question (Gap 4), and it is the crux of the project. If it holds, round $k$ is described by three updated quantities. The first is a new effective prior:

$$p_{k+1}(x) \propto p_k(x)\,\Pr\big(|x + \sigma_k Z| \le \tau_k\big).$$

Here $p_k$ is the distribution of still-active coordinates, $\sigma_k$ is the converged effective noise level at round $k$, and $Z$ is standard Gaussian. The second is a new aspect ratio $\delta_{k+1} = M/N_{k+1}$, where $N_{k+1}$ is the number of active coordinates. The third is an inflated noise floor:

$$\sigma_{w,k+1}^2 = \sigma_{w,k}^2 + \frac{1}{M}\sum_{i \text{ pinned at } k} (\hat{x}_i - x_i)^2.$$

The added term is the energy of errors made on pinned coordinates. After their columns are subtracted from $y$, those errors act as extra measurement noise. Standard state evolution is then run inside each round with these quantities.

The substantive consequence concerns the case where AMP already uses the Bayes-optimal denoiser for the true prior on a Gaussian design. There, decimation cannot lower asymptotic mean squared error, because it only moves information around. The gains ASSD observes must therefore come from three sources. The first is denoiser mismatch, for example Lasso-style soft thresholding or a misspecified prior. The second is finite-size effects. The third is design structure outside the regime where decoupling holds. We will test each source separately.

The technical difficulty is that pinned estimates depend on $y$, and hence on the unpinned columns. The added noise is therefore not independent of the remaining design. We will write decimation as AMP whose denoiser returns a frozen value once a coordinate is pinned. That is a coordinate-wise denoiser with memory of its own past iterates. We will attempt a proof of state evolution for it using the conditioning argument of The dynamics of message passing on dense graphs, with applications to compressed sensing, which established the fixed-matrix case.

Relation to Prior Work

The closest work is The Decimation Scheme for Symmetric Matrix Factorization. It recovers the columns of an extensive-rank symmetric factorization one at a time, both with a decimated AMP and with replica fixed-point equations for each step. It removes whole rank-one components rather than individual coordinates. Its analysis is replica-based and non-rigorous, and it covers only the symmetric model. We decimate coordinates in a regression design, where selection conditions the remaining prior; nothing analogous arises when a factor column is subtracted. We aim for a rigorous state evolution rather than a replica ansatz.

ASSD An adaptive shortest-solution guided decimation approach to sparse high-dimensional linear regression supplies the algorithmic template and the empirical motivation. It is the method we reuse and explain, but it has no theory. It also pays for repeated pseudoinverses, and the authors say it takes several seconds where VAMP takes under a second.

The static AMP analyses constrain the proposal: they are the null hypothesis decimation must beat. Asymptotic Statistical Analysis of Sparse Group LASSO via Approximate Message Passing predicts true-positive and false-discovery proportions for a static group penalty. A power analysis for model-X knockoffs with ℓp-regularized statistics predicts power and false discovery proportion for one-shot thresholded Lasso with knockoffs. Both are exact for i.i.d. Gaussian designs and neither shrinks the system.

Vector Approximate Message Passing extends decoupling to right-orthogonally invariant designs. We use it as the inner engine for non-i.i.d. designs, where the same two-level recursion should apply with its state evolution in place of AMP's.

Research Program

The work has four parts. First, derive the two-level recursion for i.i.d. Gaussian designs. Include both fixed-fraction batch rules, which pin the top $\rho$ fraction of active coordinates, and threshold rules. Attempt the proof sketched above. Second, build decimated AMP and decimated VAMP. After each round, pinned columns are subtracted and the next round is warm-started, so the cost stays at matrix-vector products plus one SVD for VAMP. Pinned values are refit by least squares on the pinned support at the end. Third, derive the static equivalent. This is a single AMP run whose denoiser is the composition implied by the recursion's sequence of conditioned priors. It is the object that tests whether decimation reduces to a change of denoiser. Fourth, study the regimes where the theory should fail: strongly correlated Gaussian designs and the real genomic data. The aim is to measure whether ASSD's advantage over VAMP persists there once both use the same guidance quality. A generalized-linear extension using GAMP Binary linear classification and feature selection via generalized approximate message passing is a stretch goal, not a core deliverable.

Baselines

The naive reference is static AMP with soft thresholding, equivalently the Lasso, with the penalty tuned by cross-validation. It is the same estimator decimation starts from, so any gain is attributable to the loop. On the TCGA ovarian cancer data (300 samples, 2,000 genes), the file reports 131 false positives for the Lasso An adaptive shortest-solution guided decimation approach to sparse high-dimensional linear regression.

The strongest static competitor is VAMP with an expectation-maximization–tuned Bernoulli-Gaussian prior. It is fast, provably decoupled on rotationally invariant designs, and Bayes-optimal in matched settings. The file reports 98 false positives for it on TCGA in the same paper. The strongest decimation competitor is ASSD itself, which reports 0 false positives on TCGA and only qualitative superiority on correlated synthetic designs with correlation 0.7. No reported numeric support-recovery result was found on Lacuna for that synthetic setting. We will reimplement ASSD following its described protocol, including the adaptive stopping threshold and the BIC pruning. The file does not specify how TCGA false positives were defined, so we will adopt the ASSD paper's protocol as closely as its description allows and report our reproduction of all three numbers before comparing.

Thresholded Lasso with model-X knockoffs A power analysis for model-X knockoffs with ℓp-regularized statistics is the one-shot false-discovery-control baseline. Forward stepwise selection, equivalently orthogonal matching pursuit, is the classical greedy decimation baseline.

Fairness rules apply to all methods. They see the same data splits. Each tuning parameter (penalty, prior hyperparameters, batch fraction, stopping threshold) gets the same cross-validation budget. All methods get the same final least-squares refit on their selected support, and wall-clock time is measured on the same hardware.

The key ablation compares decimated AMP against its derived static-equivalent denoiser. If the two match in mean squared error and in true-positive and false-discovery proportions, the loop itself adds nothing beyond denoiser choice. A second ablation removes the prior update, pinning and refitting while keeping the original prior. It isolates whether the conditioned prior matters.

Beating the field means one of two outcomes. The first is matching ASSD's false-discovery control at VAMP-like runtime. The second is strictly lower false discovery proportion than VAMP at equal true-positive proportion on the correlated designs.

Why not just…?

Why not just run VAMP once and threshold? In the matched i.i.d. Gaussian setting, our own theory predicts this is as good as decimation. We state this openly; it is not a threat to be argued away. The real threat is in correlated and real designs, where VAMP's 98 false positives versus ASSD's 0 on TCGA suggest decimation adds something. That comparison mixes guidance quality (least squares versus VAMP) with the loop. Decimated VAMP against static VAMP at equal tuning separates the two. If decimated VAMP does not reduce VAMP's false positives, ASSD's advantage lies in least-squares guidance rather than in decimation, and we will report that.

Why not just use a better static denoiser, or the Lasso with knockoffs? If the static-equivalent denoiser ablation matches decimation, this alternative wins on simplicity. The proposal then delivers a derived denoiser and a theory saying decimation is unnecessary, which is still a useful result. The knockoff analysis covers only i.i.d. Gaussian covariates, so its advantage on correlated designs is untested. We will run it on the same correlated designs.

Why not just use forward stepwise or orthogonal matching pursuit? These are decimation with a least-squares refit at every step. Their known weakness is irreversible early mistakes under correlation, which is the error-cascade problem listed for decimation generally. Our recursion makes a quantitative prediction here. Pinned-coordinate error energy enters the noise floor additively, so batch fraction and threshold trade speed against cascade risk along a curve we can compute. Stepwise selection sits at one fixed point on that curve.

Proposed Experiments

The decisive check is agreement between recursion and simulation on i.i.d. Gaussian designs with a Bernoulli-Gaussian signal. We will sweep $N$ from $10^3$ to $10^5$ over a grid of aspect ratios, sparsities, and noise levels, and compare predicted against empirical mean squared error and true-positive and false-discovery proportions at every decimation round. Error should shrink roughly as $1/\sqrt{N}$ if the usual concentration holds. A persistent gap would falsify the Gaussianity conjecture. We will probe that directly with Kolmogorov–Smirnov tests on the standardized residuals $r_i - x_i$ of active coordinates after each round.

The second check is the matched-prior null. In the matched Bayes setting, decimated and static Bayes AMP should reach the same mean squared error. In the Lasso-denoiser setting, the gap between decimation and static Lasso should equal the gap predicted by the static-equivalent denoiser.

The third check repeats the comparison on right-orthogonally invariant designs with controlled condition number, using decimated VAMP. It then moves to correlated Gaussian designs with correlation 0.7, following ASSD's setting, where the theory is not expected to hold exactly.

The fourth check is TCGA ovarian cancer under the reproduced ASSD protocol. We will report false positives, selected-support size, and runtime for all baselines and both ablations.

The project succeeds if the recursion tracks simulation in the decoupling regime, and if the real-data experiments settle whether decimation's benefit on correlated designs comes from the loop or from the guidance vector.