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

The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements
Sep 1, 2025Youssef Chaabouni, David GamarnikSparse Recovery Sample Complexity
Massachusetts Institute of Technology
Easy, robust approximate message passing for planted spike models
May 30, 2026Misha Ivkov, Tselil SchrammRandom Matrix Theory Principal Component Analysis
*Stanford University. · †Stanford University.
Robustness to Sparse Adversarial Corruption in Arbitrary Linear Measurements: Beyond Exact Recovery
Oct 28, 2025Vishal Halder, Alexandre Reiffers-Masson, Abdeldjalil Aïssa-El-Bey +1Sparse Recovery Adversarial Robustness
IMT Atlantique, Lab-STICC, CNRS UMR 6285, Brest, France · Department of Computer Science and Automation, Indian Institute of Science, Bengaluru, India

Sep 1, 2025J/K move · Enter open · S save

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

Youssef Chaabouni, David Gamarnik

Massachusetts Institute of Technology

Sparse Recovery Sample Complexity

Open paper AskPDF arXiv

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

ψ

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