Randomized algorithms for low-rank matrix factorizations: sharp performance bounds

DOI10.1007/S00453-014-9891-7zbMATH Open1315.68283arXiv1308.5697OpenAlexW2061844057WikidataQ114229331 ScholiaQ114229331MaRDI QIDQ2345951FDOQ2345951

Authors: Rafi Witten, Emmanuel J. Candès 

Publication date: 21 May 2015

Published in: Algorithmica (Search for Journal in Brave)

Abstract: The development of randomized algorithms for numerical linear algebra, e.g. for computing approximate QR and SVD factorizations, has recently become an intense area of research. This paper studies one of the most frequently discussed algorithms in the literature for dimensionality reduction---specifically for approximating an input matrix with a low-rank element. We introduce a novel and rather intuitive analysis of the algorithm in Martinsson et al. (2008), which allows us to derive sharp estimates and give new insights about its performance. This analysis yields theoretical guarantees about the approximation error and at the same time, ultimate limits of performance (lower bounds) showing that our upper bounds are tight. Numerical experiments complement our study and show the tightness of our predictions compared with empirical observations.

Full work available at URL: https://arxiv.org/abs/1308.5697

Recommendations

• Randomized algorithms for the low-rank approximation of matrices
• A fast randomized algorithm for the approximation of matrices
• Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
• Subspace Iteration Randomization and Singular Value Problems
• Fast monte-carlo algorithms for finding low-rank approximations

zbMATH Keywords

dimension reductionmatrix approximationrandom matrixrandomized linear algebrapass efficient algorithm

Mathematics Subject Classification ID

Randomized algorithms (68W20) Analysis of algorithms (68W40)

Cites Work

• Matrix Analysis
• Title not available (Why is that?)
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Non-asymptotic theory of random matrices: extreme singular values
• A limit theorem for the norm of random matrices
• Condition Numbers of Gaussian Random Matrices
• A randomized algorithm for principal component analysis
• The smallest eigenvalue of a large dimensional Wishart matrix
• A randomized algorithm for the decomposition of matrices
• A fast randomized algorithm for the approximation of matrices

Cited In (14)

• Regularized Linear Inversion with Randomized Singular Value Decomposition
• Lectures on randomized numerical linear algebra
• Lower bounds for matrix factorization
• Lower bounds for matrix factorization
• Statistical Inference, Learning and Models in Big Data
• Randomized subspace iteration: analysis of canonical angles and unitarily invariant norms
• Accurate low-rank approximations via a few iterations of alternating least squares
• Recursions on the marginals and exact computation of the normalizing constant for Gibbs processes
• Randomized Projection for Rank-Revealing Matrix Factorizations and Low-Rank Approximations
• Randomized Spectral Clustering in Large-Scale Stochastic Block Models
• On two random models in data analysis
• Literature survey on low rank approximation of matrices
• Random perturbation of low rank matrices: improving classical bounds
• Randomized local model order reduction

This page was built for publication: Randomized algorithms for low-rank matrix factorizations: sharp performance bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2345951)