Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation

Guy Bresler, Alina Harbuzova

In this work, we show the first average-case reduction transforming the sparse Spiked Covariance Model into the sparse Spiked Wigner Model and as a consequence obtain the first com…