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

CREATORGuy Bresler, Alina Harbuzova
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE199 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-02802

Browse the full library · About the Tower of Babel