{"id":"arxiv/2605.09755","url":"https://arxiv.org/abs/2605.09755","tags":["math.NA","cs.DS","cs.LG","stat.ML"],"score":0,"title":"Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation","domain":"math.NA","source":"arxiv","authors":["Shabarish Chenakkod","Michał Dereziński"],"reviews":0,"subject":"math.NA","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-10","reactions":{}}