Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915345161256960 |
|---|---|
| author | Bresler, Guy Harbuzova, Alina |
| author_facet | Bresler, Guy Harbuzova, Alina |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_02802 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation Bresler, Guy Harbuzova, Alina Statistics Theory Computational Complexity 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. |
| title | Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation |
| topic | Statistics Theory Computational Complexity |
| url | https://arxiv.org/abs/2503.02802 |