Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation

• URL: http://arxiv.org/abs/2605.09755v1
• Date: Sun, 10 May 2026 21:05:03 GMT
• Title: Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation
• Abstract summary: We develop an algorithmic and theoretical framework for accelerating the power method using fast sketching.<n>Our framework leads to simple and provably efficient methods for singular value decomposition, low-rank factorization, and Nystrm approximation.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Split-Merge: A Difference-based Approach for Dominant Eigenvalue Problem [6.938695246282628]
  Split-Merge is an algorithm that attains accelerated convergence without requiring spectral knowledge.<n>It consistently outperforms state-of-the-art methods in both efficiency and scalability.<n>It achieves more than a $boldsymbol10times$ speedup over the classical power method.
  arXiv  Detail & Related papers  (2025-01-25T08:37:17Z)
• Faster WIND: Accelerating Iterative Best-of-$N$ Distillation for LLM Alignment [81.84950252537618]
  This paper reveals a unified game-theoretic connection between iterative BOND and self-play alignment.<n>We establish a novel framework, WIN rate Dominance (WIND), with a series of efficient algorithms for regularized win rate dominance optimization.
  arXiv  Detail & Related papers  (2024-10-28T04:47:39Z)
• The Stochastic Conjugate Subgradient Algorithm For Kernel Support Vector Machines [1.738375118265695]
  This paper proposes an innovative method specifically designed for kernel support vector machines (SVMs) It not only achieves faster iteration per iteration but also exhibits enhanced convergence when compared to conventional SFO techniques. Our experimental results demonstrate that the proposed algorithm not only maintains but potentially exceeds the scalability of SFO methods.
  arXiv  Detail & Related papers  (2024-07-30T17:03:19Z)
• A Bound on the Maximal Marginal Degrees of Freedom [0.0]
  This paper addresses low rank approximations and surrogates for kernel ridge regression.<n>We demonstrate that the computational cost of the most popular low rank approach, which is the Nystr"om method, is almost linear in the sample size.<n>The result builds on a thorough theoretical analysis of the approximation of elementary kernel functions by elements in the range of the associated integral operator.
  arXiv  Detail & Related papers  (2024-02-20T10:25:44Z)
• Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates [50.36933471975506]
  We consider the finite-sum optimization problem, where each component function is strongly convex and has Lipschitz continuous gradient and Hessian. The recently proposed incremental quasi-Newton method is based on BFGS update and achieves a local superlinear convergence rate. This paper proposes a more efficient quasi-Newton method by incorporating the symmetric rank-1 update into the incremental framework.
  arXiv  Detail & Related papers  (2024-02-04T05:54:51Z)
• An Accelerated Doubly Stochastic Gradient Method with Faster Explicit Model Identification [97.28167655721766]
  We propose a novel doubly accelerated gradient descent (ADSGD) method for sparsity regularized loss minimization problems. We first prove that ADSGD can achieve a linear convergence rate and lower overall computational complexity.
  arXiv  Detail & Related papers  (2022-08-11T22:27:22Z)
• Practical and Fast Momentum-Based Power Methods [7.223413715110717]
  The power method is a classical algorithm with broad applications in machine learning tasks, including streaming PCA, spectral clustering, and low-rank matrix approximation. A momentum-based scheme can be used to accelerate the power method, but achieving an optimal convergence rate with existing algorithms critically relies on additional spectral information that is unavailable at run-time. We provide a pair of novel momentum-based power methods, which we call the delayed momentum power method (DMPower) and a streaming variant, the delayed momentum streaming method (DMStream) Our methods leverage inexact deflation and are capable of achieving near-optimal convergence with far
  arXiv  Detail & Related papers  (2021-08-20T16:54:12Z)
• Acceleration Methods [57.202881673406324]
  We first use quadratic optimization problems to introduce two key families of acceleration methods. We discuss momentum methods in detail, starting with the seminal work of Nesterov. We conclude by discussing restart schemes, a set of simple techniques for reaching nearly optimal convergence rates.
  arXiv  Detail & Related papers  (2021-01-23T17:58:25Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  Principal component analysis (PCA) is a widely used dimension reduction technique in machine learning and statistics. Various approaches to obtain sparse principal direction loadings have been proposed, which are termed Sparse Principal Component Analysis. We present thresholding as a provably accurate, time, approximation algorithm for the SPCA problem.
  arXiv  Detail & Related papers  (2020-06-23T04:25:36Z)
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
  We introduce a framework for designing primal methods under the decentralized optimization setting where local functions are smooth and strongly convex. Our approach consists of approximately solving a sequence of sub-problems induced by the accelerated augmented Lagrangian method. When coupled with accelerated gradient descent, our framework yields a novel primal algorithm whose convergence rate is optimal and matched by recently derived lower bounds.
  arXiv  Detail & Related papers  (2020-06-11T18:49:06Z)
• Average-case Acceleration Through Spectral Density Estimation [35.01931431231649]
  We develop a framework for the average-case analysis of random quadratic problems. We derive algorithms that are optimal under this analysis. We develop explicit algorithms for the uniform, Marchenko-Pastur, and exponential distributions.
  arXiv  Detail & Related papers  (2020-02-12T01:44:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.