Column Thresholding for Sparse Spiked Wigner Models: Improved Signal Strength Requirements

We study the sparse spiked Wigner model, where the goal is to recover an $s$-sparse unit vector $\boldsymbol{u} \in \mathbb{R}^d$ from a noisy observation $\boldsymbol{Y} = \beta \boldsymbol{u} \boldsymbol{u}^\top + \boldsymbol{W}$. While the information-theoretic threshold is $\beta = \widetilde{\Omega}(\sqrt{s})$, existing polynomial-time algorithms require $\beta = \widetilde{\Omega}(s)$, yielding a substantial computational-statistical gap. We propose a column thresholding method that attains the $\widetilde{\Omega}(\sqrt{s})$ scaling for both estimation and support recovery under the non-uniformity condition $|| \boldsymbol{u} ||_\infty = \Omega(1)$. This condition is not merely technical: it explicitly rules out uniform spikes, for which planted-clique-based hardness results apply, and identifies a concrete class of non-uniform spikes where the required signal strength can be reduced. Building on this initializer, we further develop a truncated power method that iteratively refines the estimate with provable linear convergence.

We study the recovery of an unknown sparse signal from a noisy matrix observation in the spiked Wigner model, a classical model in high-dimensional statistics. Existing efficient algorithms typically require stronger signals than what is theoretically necessary, and this gap is believed to be unavoidable for uniformly distributed sparse signals. We show that this barrier can be bypassed for a natural class of non-uniform sparse signals. Our column-thresholding method succeeds at lower signal strength than existing efficient approaches, and an iterative refinement procedure further improves estimation and support recovery. These results clarify when efficient recovery is possible at weaker signal levels in the spiked Wigner model. Rather than resolving the hardest uniform case, our work identifies a structured non-uniform setting where the computational barrier can be overcome.