Distinguishability and Recovery for a Doubly Sparse Spiked Wigner Model

Ioana Dumitriu; JD Flynn; Zhichao Wang

stat.MLOct 16, 2026

Distinguishability and Recovery for a Doubly Sparse Spiked Wigner Model

Authors: Ioana Dumitriu, JD Flynn, Zhichao Wang

Organizations: University of California, San Diego · University of California, Berkeley

Abstract

We study distinguishability and recovery of a sparse rank-one signal in a spiked Wigner model with independently sparse noise through a variety of algorithms and parameter regimes. The signal and noise have separate sparsity parameters, while the signal-to-noise ratio (SNR) remains of constant order as the matrix size grows. For sub-Gaussian noise and spikes whose nonzero coordinates are bounded away from zero, a leave-one-out quadratic thresholding procedure (a generalization of Ding et al., 2024) identifies the support. Sign synchronization yields exact recovery for a Rademacher spike, and spectral refinement yields strong recovery. The quadratic thresholding search parameter gives an explicit tradeoff between signal sparsity, noise sparsity, and computational cost. We also study extensions to sub-Gaussian spike priors through diagonal and quadratic thresholding. For Rademacher spikes with continuous nonzero noise, we develop an identical search algorithm that exploits unblurred signal entries, the existence of which permits distinguishability; connectivity of the graph they reveal provides a sufficient condition for exact recovery. These guarantees do not require moment assumptions on the continuous noise distribution. Together with our previous PCA results (Dumitriu et al., 2026), our analysis covers almost the entire space of parameters and regimes for distinguishing and recovering in our doubly sparse spiked Wigner model.

Figures & tables

$np\to\infty$	Small-Ball	Rademacher	Lower Bounded
	Sub-Gaussian
Distinguishability	PCA ( $\theta>1,q\gg\log(n)/n$ )
	Diagonal Thresholding
	( $q\gg np^{2}\log(nq)$ )	( $q\gtrsim np^{2}\log(nq)$ )
	Quadratic Thresholding ( $q\gtrsim p\log(n)$ )
		Identical Search ( $1-q\gtrsim 1/(np)^{2}$ )

Table 1: Distinguishing and Recovering under varying spike assumptions for Model 2.1 under

np\to\infty

. For spike assumptions, see Assumptions 3 and 1 , 4 , and 2 , respectively. All four use Assumption 5 . The noise follows Assumption 7 for PCA, DT, and QT, and Assumption 6 for IS. All four use Assumption 8 .

Doubly Sparse Distinguishability
$1-q\ll 1/n^{2}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	QT
$1-q\gtrsim 1/n^{2}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	QT	IS
$1-q\gtrsim\frac{(\log n)^{2}}{n^{2}}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	IS , QT	IS
$1-q\gtrsim\frac{\log n}{n}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	IS , QT	IS
$1-q\gtrsim\tau^{-2}$	IS , $\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	IS , $\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	IS , QT	IS
$q\gtrsim\Theta(1)$	IS , $\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	IS , $\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	IS , QT	IS

Table 2: Distinguishability results for Identical Search ( IS ), polynomial-time and nonpolynomial-time Quadratic Thresholding (

\textbf{QT}_{p}

/ QT ), linear-time Diagonal Thresholding (

\textbf{DT}_{l}

), and PCA (Pink Shaded Region). Assumptions and axis details in Section 3.4 .

Doubly Sparse Recovery
$1-q\ll\frac{\log n}{n}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	QT
$1-q\gtrsim\frac{\log n}{n}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	QT	IS
$1-q\gtrsim\frac{\log(\frac{n}{\log n})}{n/\log n}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	IS , QT	IS
$1-q\gtrsim\frac{\log(\sqrt{\frac{n}{\log n}})}{\sqrt{n/\log n}}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	IS , $\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	IS , QT	IS
$1-q\gtrsim\frac{\log\tau}{\tau}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	IS , $\textbf{QT}_{p}$ , $\textbf{DT}_{l}$ ,	IS , $\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	IS , QT	IS
$q\gtrsim\Theta(1)$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	IS , $\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	IS , $\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	IS , QT	IS

Table 3: Recovery results for Identical Search ( IS ), polynomial-time and nonpolynomial-time Quadratic Thresholding (

\textbf{QT}_{p}

/ QT ), linear-time Diagonal Thresholding (

\textbf{DT}_{l}

), and PCA (Pink Shaded Region). Assumptions and axis details in Section 3.4 .

Panel of Figure 1 — Figure 1: Sparse spike and dense noise: $p=8/n$ , $q=1$ , Rademacher prior, 100 trials per point. (a) Exact-recovery probability of QT ( $l=2$ ) for different $\theta$ , one curve per $n$ . (b) Correlation results for each of the four methods at $n=10^{4}$ for different $\theta$ .

prior	method	theory	$\theta=0.8$	$\theta=1$	$\theta=1.2$	$\theta=1.5$	$\theta=2$
Rademacher	PCA (corr)	$\circ$ needs $np\to\infty$	0.15	0.29	0.42	0.60	0.76
	QT (exact)	$\checkmark$ Thm 4 .1(a) exact	0.96	1.00	1.00	1.00	1.00
	DT (supp)	$\checkmark$ Thm 4 .1(c) support, $\theta\geq 1$	0.90	0.95	1.00	1.00	1.00
	IS (exact)	$\times$ $q=1$	0.00	0.00	0.00	0.00	0.00
lower bounded	PCA (corr)	$\circ$ needs $np\to\infty$	0.14	0.30	0.46	0.62	0.79
	QT (supp)	$\checkmark$ Thm 4 .2(a) support, $\theta\geq 1.2$	0.00	0.34	0.93	0.99	0.99

Table 4: Sparse spike and dense noise (

p=8/n

q=1

) at

n=10^{4}

, 100 trials. “theory”:

\checkmark

a theorem guarantees the metric,

\times

its condition fails,

\circ

no guarantee.

Panel of Figure 2 — Figure 2: Bounded expected support, $p=5/n$ , $q=1$ , Rademacher prior. (a) Squared PCA correlation against $\theta_{\rm eff}=\theta K/5$ for $\theta\in\{0.8,1,1.2\}$ and $n\in\{10^{3},\dots,2\cdot 10^{4}\}$ (200 trials each), with the BBP curve $1-1/\lambda^{2}$ . (b) Fixed support size $K$ : mean squared correlation against $n$ ; thin lines: BBP limits.

Panel of Figure 3 — Figure 3: QT sparsity scaling: $p=c/\sqrt{n\log n}$ , $q=1$ , $l=2$ , Rademacher prior, 100 trials per point. (a) Exact-recovery probability against $R_{\rm QT}=q\theta^{2}l/(np^{2}\log n)=2\theta^{2}/c^{2}$ , all $(c,\theta)$ pooled, one curve per $n$ . (b) The same at $\theta=1.5$ against $c$ ; the vertical line is $c=\theta/3$ .

Panel of Figure 4 — Figure 4: Identical Search. (a) Success rates at $n=2\cdot 10^{4}$ for $p=1/2$ , $q=5/n$ (100 trials). (b) Exact recovery on the noise-free graph $G(K,1-q)$ , $1-q=\alpha\log K/K$ , 500 trials; thin lines $\exp(-K^{1-\alpha})$ , the connectivity limit used in Theorem 21 ; vertical line: its threshold $\alpha=1$ . (c) Total error of the full-knowledge test, $1-q=s/K^{2}$ , 2000 planted and 100 null trials.

prior	method	theory	$\theta=0.3$	$\theta=0.5$	$\theta=0.8$	$\theta=1$	$\theta=1.2$
Rademacher	PCA (corr)	$\times$ $nq\not\gg\log n$	0.01	0.01	0.01	0.01	0.01
	QT (exact)	$\times$ $q\not\gtrsim p\log n$	0.00	0.00	0.00	0.00	0.00
	DT (supp)	$\times$ Thm 15 (remark) empty interval	0.00	0.00	0.00	0.00	0.00
	IS (exact)	$\checkmark$ Thm 3 .1(d) exact	1.00	1.00	1.00	1.00	1.00

Table 5: Dense spike and very sparse noise (

p=1/2

q=5/n

) at

n=2\cdot 10^{4}

, 100 trials.

prior	method	theory	$\theta=0.5$	$\theta=0.8$	$\theta=1$	$\theta=1.2$	$\theta=1.5$
Rademacher	PCA (corr)	$\checkmark$ weak iff $\theta>1$	0.02	0.04	0.17	0.55	0.75
	QT (exact)	$\times$ $q\not\gtrsim p\log n$	0.00	0.00	0.00	0.00	0.00
	DT (supp)	$\times$ Thm 15 (remark) window empty	0.00	0.00	0.00	0.00	0.00
	IS (exact)	$\times$ $q=1$	0.00	0.00	0.00	0.00	0.00

Table 6: Dense spike and dense noise (

p=q=1

) at

n=10^{4}

, 100 trials.

Figure 11

Figure 12

Figure 13

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Doubly Sparse Distinguishability
$1-q\ll 1/n^{2}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}^{L}$	QT
$1-q\gtrsim 1/n^{2}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}^{L}$	QT	IS
$1-q\gtrsim\frac{(\log n)^{2}}{n^{2}}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}^{L}$	IS , QT	IS
$1-q\gtrsim\frac{\log n}{n}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	IS , $\textbf{QT}_{p}$ , $\textbf{DT}_{l}^{L}$	IS , QT	IS
$1-q\gg\frac{\log n}{n}$	$\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	IS , $\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	IS , $\textbf{QT}_{p}$ , $\textbf{DT}_{l}^{L}$	IS , QT	IS
$1-q\gtrsim\tau^{-2}$	IS , $\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	IS , $\textbf{QT}_{p}$ , $\textbf{DT}_{l}$	IS , $\textbf{QT}_{p}$ , $\textbf{DT}_{l}^{L}$	IS , QT	IS

Appendix

Table 7: Distinguishability results extended from Table 2 to include results for Assumption 1 . See A.2 for details on notation.

Doubly Sparse Recovery
$1-q\ll\frac{\log n}{n}$	$\textbf{QT}_{p}^{L}$ $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ $\textbf{DT}_{l}^{L}$	$\textbf{QT}_{(p)}$ $\textbf{DT}_{l}^{L}$	$\textbf{QT}_{p}^{L}$ $\textbf{DT}_{l}^{L}$	$\textbf{QT}^{L}$
$1-q\gtrsim\frac{\log n}{n}$	$\textbf{QT}_{p}^{L}$ $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ $\textbf{DT}_{l}^{L}$	$\textbf{QT}_{(p)}$ $\textbf{DT}_{l}^{L}$	$\textbf{QT}_{p}^{L}$ $\textbf{DT}_{l}^{L}$	$\textbf{QT}^{L}$	IS
$1-q\gtrsim\frac{\log(\frac{n}{\log n})}{n/\log n}$	$\textbf{QT}_{p}^{L}$ $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ $\textbf{DT}_{l}^{L}$	$\textbf{QT}_{(p)}$ $\textbf{DT}_{l}^{L}$	$\textbf{QT}_{p}^{L}$ $\textbf{DT}_{l}^{L}$	IS $\textbf{QT}^{L}$	IS
$1-q\gtrsim\frac{\log(\sqrt{\frac{n}{\log n}})}{\sqrt{n/\log n}}$	$\textbf{QT}_{p}^{L}$ $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ $\textbf{DT}_{l}^{L}$	$\textbf{QT}_{(p)}$ $\textbf{DT}_{l}^{L}$	IS $\textbf{QT}_{p}^{L}$ $\textbf{DT}_{l}^{L}$	IS $\textbf{QT}^{L}$	IS
$1-q\gtrsim\frac{\log(\sqrt[3]{\frac{n}{\log n}})}{\sqrt[3]{n/\log n}}$	$\textbf{QT}_{p}^{L}$ $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ $\textbf{DT}_{l}^{L}$	IS $\textbf{QT}_{(p)}$ $\textbf{DT}_{l}^{L}$	IS $\textbf{QT}_{p}^{L}$ $\textbf{DT}_{l}^{L}$	IS $\textbf{QT}^{L}$	IS
$1-q\gtrsim\frac{\log(\sqrt[4]{\frac{n}{\log n}})}{\sqrt[4]{n/\log n}}$	$\textbf{QT}_{p}^{L}$ $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ $\textbf{DT}_{l}$	$\textbf{QT}_{p}$ $\textbf{DT}_{l}$	IS , $\textbf{QT}_{p}$ $\textbf{DT}_{l}^{L}$	IS $\textbf{QT}_{(p)}$ $\textbf{DT}_{l}^{L}$	IS $\textbf{QT}_{p}^{L}$ $\textbf{DT}_{l}^{L}$	IS $\textbf{QT}^{L}$	IS

Appendix

Table 8: Recovery results extended from Table 3 to include results for Assumption 1 . See A.2 for details on notation.

Sparse Recovery

Sparse recovery reconstructs signals or models with few active components from limited, noisy, or indirect measurements.

See all 75 papers

Sep 1, 2025

The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements

We consider the problem of support recovery for sparse binary signals from noisy linear measurements. For sparse Gaussian measurement matrices we identify sufficient conditions on the minimal sample size for maximum-likelihood recovery in the high-SNR regime

ds/p \to \infty

, where

p

denotes the signal dimension,

s

the number of non-zero components of the signal, and

d

the expected number of non-zero components per row of measurement. Combined with known lower bounds, this yields an information-theoretic threshold of order

s\log(p/s) / \log(ds/p)

, making explicit the price of measurement sparsity. In particular, we highlight a regime where the sample-complexity loss from measurement sparsity is logarithmic while the computational gain is nearly linear. Second, we study recovery after sparsifying an originally dense Gaussian design: the observations are generated from the dense design, while estimation uses an independently sparsified design and a rescaled response. In the proportional regime

s=αp

d=ψp

, we prove that, for every fixed target error level

δ

and every slack

\varepsilon>0

, a sample size of order

p/ψ^2

is sufficient for support recovery for arbitrarily small

ψ

Youssef Chaabouni, David Gamarnik

Massachusetts Institute of Technology

Sparse Recovery Sample Complexity

Ask PDF

May 30, 2026

Easy, robust approximate message passing for planted spike models

We present a simple and efficient algorithm for robust approximate message passing (AMP) in the spiked matrix setting. In particular, let

\varepsilon

be a sufficiently small constant, and suppose that

X \in \mathbb R^{n \times n}

is a Gaussian matrix with a planted rank-

1

spike, and

E \in \mathbb R^{n \times n}

is an adversarially chosen matrix supported on an

\varepsilon n \times \varepsilon n

principal minor. Let

v_{\mathrm{AMP}}(X)

be the output of an AMP iteration on the uncorrupted matrix

X

. We give a procedure that, given access only to the corrupted matrix

Y = X + E

, computes a vector

v_{\mathrm{ALG}}(Y)

which is

\tilde{O}(\sqrt{\varepsilon})

-close to

v_{\mathrm{AMP}}(X)

, for any of a class of AMP iterations which includes sparse Principal Component Analysis (PCA), non-negative PCA, and

\mathbb Z_2

synchronization. Our algorithm consists of a spectral pre-processing step combined with a robust spectral initialization procedure; given these inputs, we prove that (perhaps surprisingly) AMP is robust out-of-the-box.

Misha Ivkov, Tselil Schramm

*Stanford University. · †Stanford University.

Random Matrix Theory Principal Component Analysis Adversarial Robustness Approximate Message Passing Spectral Methods

Ask PDF

Oct 28, 2025

Robustness to Sparse Adversarial Corruption in Arbitrary Linear Measurements: Beyond Exact Recovery

Recovery from linear measurements under sparse adversarial corruption is typically formulated as an exact-recovery problem: one seeks structural conditions on

\mathbf{A}

(e.g., restricted isometry property) guaranteeing unique recovery of

\mathbf{x}^\star

from

\mathbf{y} = \mathbf{A}\mathbf{x}^\star + \mathbf{e}

with

\|\mathbf{e}\|_0 \leq q

. However, these guarantees provide no guidance once exact recovery fails. This limitation obscures simple robustness phenomena -- for instance, repeated rows in

\mathbf{A}

can preserve nontrivial information about

\mathbf{x}^\star

under sparse corruption. In this paper, we study what information about

\mathbf{x}^\star

can be uniformly recovered from

\mathbf{y} = \mathbf{A}\mathbf{x}^\star + \mathbf{e}

for arbitrary

\mathbf{A}\in\mathbb{R}^{m\times n}

and any

q

-sparse

\mathbf{e}

. We show that the robust information is precisely

\mathbf{x}^\star + \ker(\mathbf{U})

, where

\mathbf{U}

is the orthogonal projection onto the intersection of rowspaces of all submatrices of

\mathbf{A}

obtained by deleting

2q

rows. This clarifies how the row structure of

\mathbf{A}

governs whether a

q

-sparse corruption allows exact, partial, or only trivial recovery. We further prove every

\mathbf{x}

minimizing

\|\mathbf{y} - \mathbf{A} \mathbf{x}\|_0

belongs to

\mathbf{x}^\star + \ker(\mathbf{U})

, yielding a constructive approach to recover this set. For i.i.d. Gaussian matrices, we establish a sharp phase transition between exact and trivial recovery. We sketch two applications: robust network tomography and signal reconstruction from oversampled DCT.

Vishal Halder, Alexandre Reiffers-Masson, Abdeldjalil Aïssa-El-Bey +1

IMT Atlantique, Lab-STICC, CNRS UMR 6285, Brest, France · Department of Computer Science and Automation, Indian Institute of Science, Bengaluru, India

Sparse Recovery Adversarial Robustness Corruption Robustness Inverse Problems

Ask PDF

Abstract

Sparse Recovery

Explore similar work

The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements

Easy, robust approximate message passing for planted spike models

Robustness to Sparse Adversarial Corruption in Arbitrary Linear Measurements: Beyond Exact Recovery