Practical sketching algorithms for low-rank matrix approximation

Abstract

This paper describes a suite of algorithms for constructing low-rank approximations of an input matrix from a random linear image of the matrix, called a sketch. These methods can preserve structural properties of the input matrix, such as positive-semidefiniteness, and they can produce approximations with a user-specified rank. The algorithms are simple, accurate, numerically stable, and provably correct. Moreover, each method is accompanied by an informative error bound that allows users to select parameters a priori to achieve a given approximation quality. These claims are supported by numerical experiments with real and synthetic data.

References in corpus (1)

• Sketching as a Tool for Numerical Linear Algebra

Cited by in corpus (19)

• Scalable Semidefinite Programming
• Randomized resolvent analysis
• Subspace-Orbit Randomized Decomposition for Low-rank Matrix Approximation
• Faster quantum and classical SDP approximations for quadratic binary optimization
• Improved Fixed-Rank Nyström Approximation via QR Decomposition: Practical and Theoretical Aspects
• Matrix completion with deterministic pattern - a geometric perspective
• Randomized Truncated SVD Levenberg-Marquardt Approach to Geothermal Natural State and History Matching
• Low-rank nonnegative tensor approximation via alternating projections and sketching
• Wavelet-based resolvent analysis of non-stationary flows
• Sketching for low-rank nonnegative matrix approximation: Numerical study
• A Fast Randomized Algorithm for Computing an Approximate Null Space
• Randomized low-rank approximation for symmetric indefinite matrices
• Low-rank approximation of parameter-dependent matrices via CUR decomposition
• Probabilistic methods for approximate archetypal analysis
• Randomized Compression of Rank-Structured Matrices Accelerated with Graph Coloring
• Accuracy and Stability of CUR decompositions with Oversampling
• Principled interpolation of Green's functions learned from data
• One-Pass Sparsified Gaussian Mixtures
• Sketching sparse low-rank matrices with near-optimal sample- and time-complexity using message passing