Beyond Low Rank: Fast Low-Rank + Diagonal Decomposition with a Spectral Approach
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_ | 1866917156763992064 |
|---|---|
| author | Yeon, Kingsley Anitescu, Mihai |
| author_facet | Yeon, Kingsley Anitescu, Mihai |
| contents | Low-rank plus diagonal (LRPD) decompositions provide a powerful structural model for large covariance matrices, simultaneously capturing global shared factors and localized corrections that arise in covariance estimation, factor analysis, and large-scale kernel learning. We introduce an alternating low-rank then diagonal (Alt) algorithm that provably reduces approximation error and significantly outperforms gradient descent while remaining cheaper than majorization-minimization methods~\cite{sun2016majorization}. To scale to large matrices, we develop a randomized LRPD variant that combines fixed-rank Nystrom sketching~\cite{tropp2017fixed} for the low-rank component with Diag++ stochastic diagonal estimation~\cite{baston2022stochastic}. This hybrid algorithm achieves machine precision decomposition error using a number of matrix-vector products far smaller than the ambient dimension, and comes with rigorous non-asymptotic error bounds. On synthetic data, it exactly recovers LRPD structured matrices with high efficiency, and on real-world S&P 500 stock return covariances, where the spectrum decays slowly and strong sector structure exists, it achieves substantially lower error than pure low-rank approximations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_17120 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Beyond Low Rank: Fast Low-Rank + Diagonal Decomposition with a Spectral Approach Yeon, Kingsley Anitescu, Mihai Numerical Analysis 65F60, 65F10, 65W20, 68W25 Low-rank plus diagonal (LRPD) decompositions provide a powerful structural model for large covariance matrices, simultaneously capturing global shared factors and localized corrections that arise in covariance estimation, factor analysis, and large-scale kernel learning. We introduce an alternating low-rank then diagonal (Alt) algorithm that provably reduces approximation error and significantly outperforms gradient descent while remaining cheaper than majorization-minimization methods~\cite{sun2016majorization}. To scale to large matrices, we develop a randomized LRPD variant that combines fixed-rank Nystrom sketching~\cite{tropp2017fixed} for the low-rank component with Diag++ stochastic diagonal estimation~\cite{baston2022stochastic}. This hybrid algorithm achieves machine precision decomposition error using a number of matrix-vector products far smaller than the ambient dimension, and comes with rigorous non-asymptotic error bounds. On synthetic data, it exactly recovers LRPD structured matrices with high efficiency, and on real-world S&P 500 stock return covariances, where the spectrum decays slowly and strong sector structure exists, it achieves substantially lower error than pure low-rank approximations. |
| title | Beyond Low Rank: Fast Low-Rank + Diagonal Decomposition with a Spectral Approach |
| topic | Numerical Analysis 65F60, 65F10, 65W20, 68W25 |
| url | https://arxiv.org/abs/2512.17120 |