Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation
Abstract
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 computational equivalence result between two well-studied high-dimensional statistics models. Our approach leverages a new perturbation equivariance property for Gram-Schmidt orthogonalization, enabling removal of dependence in the noise while preserving the signal.
Cite
Text
Bresler and Harbuzova. "Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation." Proceedings of Thirty Eighth Conference on Learning Theory, 2025.Markdown
[Bresler and Harbuzova. "Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation." Proceedings of Thirty Eighth Conference on Learning Theory, 2025.](https://mlanthology.org/colt/2025/bresler2025colt-computational/)BibTeX
@inproceedings{bresler2025colt-computational,
title = {{Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation}},
author = {Bresler, Guy and Harbuzova, Alina},
booktitle = {Proceedings of Thirty Eighth Conference on Learning Theory},
year = {2025},
pages = {594-595},
volume = {291},
url = {https://mlanthology.org/colt/2025/bresler2025colt-computational/}
}