Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910207494324224 |
|---|---|
| author | Chenakkod, Shabarish Dereziński, Michał |
| author_facet | Chenakkod, Shabarish Dereziński, Michał |
| contents | The power method is one of the most fundamental tools for extracting top principal components from data through low-rank matrix approximation. Yet, when the target rank is large, the cost of matrix multiplication associated with this procedure becomes a major bottleneck. We develop an algorithmic and theoretical framework for accelerating the power method using fast sketching, which is a popular paradigm in randomized linear algebra. Our framework leads to simple and provably efficient methods for singular value decomposition, low-rank factorization, and Nyström approximation, which attain strong numerical performance on benchmark problems. The key novelty in our analysis is the use of regularized spectral approximation, a property of fast sketching methods which proves more flexible in generalizing power method guarantees than traditional arguments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_09755 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation Chenakkod, Shabarish Dereziński, Michał Numerical Analysis Data Structures and Algorithms Machine Learning The power method is one of the most fundamental tools for extracting top principal components from data through low-rank matrix approximation. Yet, when the target rank is large, the cost of matrix multiplication associated with this procedure becomes a major bottleneck. We develop an algorithmic and theoretical framework for accelerating the power method using fast sketching, which is a popular paradigm in randomized linear algebra. Our framework leads to simple and provably efficient methods for singular value decomposition, low-rank factorization, and Nyström approximation, which attain strong numerical performance on benchmark problems. The key novelty in our analysis is the use of regularized spectral approximation, a property of fast sketching methods which proves more flexible in generalizing power method guarantees than traditional arguments. |
| title | Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation |
| topic | Numerical Analysis Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2605.09755 |