Fast monte-carlo algorithms for finding low-rank approximations

2004/11/01 by Alan Frieze, Ravi Kannan, Santosh Vempala · 512 citations
Computer Science · Engineering · Mathematics · #Algorithm #Combinatorics #Discrete mathematics #Hankel matrix #Low-rank approximation #Mathematical analysis #Mathematics #Matrix (chemical analysis) #Matrix norm #Matrix polynomial #Monte Carlo method #Polynomial #Polynomial matrix #Randomized algorithm #Rank (graph theory) #Singular value #Singular value decomposition #Sparse and Compressive Sensing Techniques #Statistics #Stochastic Gradient Optimization Techniques #Tensor decomposition and applications #Time complexity

paper · doi:10.1145/1039488.1039494

published in Journal of the ACM 51(6), 1025-1041 (Association for Computing Machinery)

openalex publication_date 2004/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/25

Abstract

We consider the problem of approximating a given m × n matrix A by another matrix of specified rank k , which is smaller than m and n . The Singular Value Decomposition (SVD) can be used to find the "best" such approximation. However, it takes time polynomial in m, n which is prohibitive for some modern applications. In this article, we develop an algorithm that is qualitatively faster, provided we may sample the entries of the matrix in accordance with a natural probability distribution. In many applications, such sampling can be done efficiently. Our main result is a randomized algorithm to find the description of a matrix D * of rank at most k so that holds with probability at least 1 − δ (where |·| F is the Frobenius norm). The algorithm takes time polynomial in k ,1/ϵ, log(1/δ) only and is independent of m and n . In particular, this implies that in constant time, it can be determined if a given matrix of arbitrary size has a good low-rank approximation.

Citations

• Authoritative sources in a hyperlinked environment

Cited by

• Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations
• Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions
• Learning Large-scale Network Embedding from Representative Subgraph
• Numerically Safe Gaussian Elimination with No Pivoting
• Improved SVRG for quadratic functions
• Quantum Algorithms for Unsupervised Machine Learning and Neural Networks
• Sparse sketches with small inversion bias
• Quantum-Inspired Classical Algorithm for Principal Component Regression
• A Multi-criteria Approach for Fast and Outlier-aware Representative Selection from Manifolds
• On Subspace Approximation and Subset Selection in Fewer Passes by MCMC Sampling
• Sublinear Time Low-Rank Approximation of Distance Matrices
• The structure of global conservation laws in Galerkin plasma models
• Regular Partitions and Their Use in Structural Pattern Recognition
• Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
• Low-rank Approximation of a Matrix: Novel Insights, New Progress, and Extensions
• The Singular Value Decomposition, Applications and Beyond
• On Recovering the Best Rank-r Approximation from Few Entries
• Effective Resistances, Statistical Leverage, and Applications to Linear Equation Solving
• Randomized Rank-Revealing UZV Decomposition for Low-Rank Approximation of Matrices
• Low Rank Matrix Approximation in Linear Time
• Low Rank Approximation and Regression in Input Sparsity Time
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra
• Study of Compressed Randomized UTV Decompositions for Low-Rank Matrix Approximations in Data Science
• Subsampling Algorithms for Semidefinite Programming
• Randomized LU decomposition
• Quantum Machine Learning For Classical Data
• A quantum-inspired algorithm for approximating statistical leverage scores
• Filter Sketch for Network Pruning
• Deterministic matrix sketches for low-rank compression of high-dimensional simulation data
• Regularized Linear Inversion with Randomized Singular Value Decomposition
• A quantum-inspired classical algorithm for recommendation systems
• Computational time-reversal imaging with a small number of random and noisy measurements
• MACH: Fast Randomized Tensor Decompositions
• On the approximation of a matrix
• Distributed Low Rank Approximation of Implicit Functions of a Matrix
• Optimal Sampling Algorithms for Block Matrix Multiplication
• Fast and Near-Optimal Matrix Completion via Randomized Basis Pursuit
• Quantum Machine Learning Algorithm for Knowledge Graphs
• Quantum-Inspired Classical Algorithm for Slow Feature Analysis
• A Randomized Kaczmarz Algorithm with Exponential Convergence
• Matrix Completion from Noisy Entries
• Latent Network Summarization: Bridging Network Embedding and Summarization
• Metro maps of plant disease dynamics--automated mining of differences using hyperspectral images. [europepmc]
• Quantum machine learning: a classical perspective. [europepmc]
• Randomized methods to characterize large-scale vortical flow networks. [europepmc]
• Coresets for the Average Case Error for Finite Query Sets. [europepmc]
• Evaluating dimensionality reduction for genomic prediction. [europepmc]

Related

• Fast Monte-Carlo Low Rank Approximations for Matrices
• Fast and stable randomized low-rank matrix approximation
• Low-rank Approximation of a Matrix: Novel Insights, New Progress, and Extensions
• A Rank Revealing Randomized Singular Value Decomposition (R3SVD)\n Algorithm for Low-rank Matrix Approximations
• Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions