Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation
Guy Bresler, Alina Harbuzova · 2025
Read Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation by Guy Bresler, Alina Harbuzova (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-02802.txt.
Introduction
Guy Bresler and Alina Harbuzova prove that two classic hard problems in high-dimensional statistics are, in computing terms, the same problem, in a paper from 2025. Both models hide a faint signal inside noise. One works through data covariance; the other through a symmetric matrix. Each had been studied on its own for years.
The authors give the first average-case reduction that turns instances of the sparse covariance problem into instances of the sparse Wigner problem. The key is a new symmetry property of the Gram-Schmidt process, which strips dependence from the noise while keeping the signal intact. Because reductions carry hardness with them, results for one model now transfer to the other. The equivalence closes a long gap between the two literatures.
Catalog record
| CREATOR | Guy Bresler, Alina Harbuzova |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 199 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-02802