Practical sketching algorithms for low-rank matrix approximation

DOI10.1137/17M1111590zbMATH Open1379.65026arXiv1609.00048OpenAlexW3100283647MaRDI QIDQ4598337FDOQ4598337

Authors: Joel A. Tropp, A. Yurtsever, Madeleine Udell, Volkan Cevher 

Publication date: 20 December 2017

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

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.

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

Recommendations

• Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
• Fast monte-carlo algorithms for finding low-rank approximations
• Fast low rank approximations of matrices and tensors
• Low-rank approximation algorithms for matrix completion with random sampling
• Fast computation of low rank matrix approximations

zbMATH Keywords

dimension reductionmatrix approximationrandomized algorithmsketchingstreaming algorithmnumerical experimentnumerical linear algebrasubspace embeddingsingle-pass algorithm

Mathematics Subject Classification ID

Cites Work

• Title not available (Why is that?)
• Improved matrix algorithms via the subsampled randomized Hadamard transform
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Latent semantic indexing: A probabilistic analysis
• Dimensionality reduction for \(k\)-means clustering and low rank approximation
• Lower bounds for oblivious subspace embeddings
• Numerical linear algebra in the streaming model
• Fast monte-carlo algorithms for finding low-rank approximations
• Turning big data into tiny data: constant-size coresets for \(k\)-means, PCA and projective clustering
• Randomized Algorithms for Matrices and Data
• Title not available (Why is that?)
• Improved analysis of the subsampled randomized Hadamard transform
• The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
• A randomized algorithm for the decomposition of matrices
• A fast randomized algorithm for the approximation of matrices
• Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
• Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
• Fast linear algebra is stable
• Sketching as a tool for numerical linear algebra
• Subspace Iteration Randomization and Singular Value Problems
• Algorithm 971
• Optimal Approximate Matrix Product in Terms of Stable Rank
• Low-Rank PSD Approximation in Input-Sparsity Time
• Practical sketching algorithms for low-rank matrix approximation
• Optimal principal component analysis in distributed and streaming models
• Online principal components analysis
• Turnstile streaming algorithms might as well be linear sketches
• Nearly tight oblivious subspace embeddings by trace inequalities

Cited In (83)

• Pass-efficient randomized algorithms for low-rank matrix approximation using any number of views
• Solving trust region subproblems using Riemannian optimization
• Title not available (Why is that?)
• Single-pass randomized QLP decomposition for low-rank approximation
• A non-Euclidean gradient descent method with sketching for unconstrained matrix minimization
• Randomized QLP decomposition
• FANOK: knockoffs in linear time
• ISLET: fast and optimal low-rank tensor regression via importance sketching
• A block bidiagonalization method for fixed-accuracy low-rank matrix approximation
• The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection
• Contour Integral Methods for Nonlinear Eigenvalue Problems: A Systems Theoretic Approach
• Improved practical matrix sketching with guarantees
• Low-rank independence samplers in hierarchical Bayesian inverse problems
• Randomized numerical linear algebra: Foundations and algorithms
• Sublinear Cost Low Rank Approximation via Subspace Sampling
• Random projections for conic programs
• Randomized algorithms for the computation of multilinear rank-\((\mu_1,\mu_2,\mu_3)\) approximations
• ALORA: affine low-rank approximations
• Pass-efficient methods for compression of high-dimensional turbulent flow data
• Perturbations of CUR Decompositions
• Randomized subspace iteration: analysis of canonical angles and unitarily invariant norms
• Scalable kernel \(k\)-means clustering with Nyström approximation: relative-error bounds
• Sketching as a tool for numerical linear algebra
• A nonlinear matrix decomposition for mining the zeros of sparse data
• Randomized Low-Rank Approximation for Symmetric Indefinite Matrices
• A fast randomized algorithm for computing an approximate null space
• Sketching for a low-rank nonnegative matrix approximation: numerical study
• Pass-efficient randomized LU algorithms for computing low-rank matrix approximation
• Extended Lanczos bidiagonalization algorithm for low rank approximation and its applications
• Title not available (Why is that?)
• Frequent directions: simple and deterministic matrix sketching
• Efficient $\widetilde{O}(n/\epsilon)$ Spectral Sketches for the Laplacian and its Pseudoinverse
• Bounded matrix low rank approximation
• Exploiting low-rank structure in semidefinite programming by approximate operator splitting
• Practical sketching algorithms for low-rank matrix approximation
• Efficient randomized algorithms for the fixed-precision low-rank matrix approximation
• Improved Variants of the Hutch++ Algorithm for Trace Estimation
• Subspaces analysis for random projection UTV framework
• Generalized conditional gradient with augmented Lagrangian for composite minimization
• Randomized quaternion QLP decomposition for low-rank approximation
• Low-rank Tucker approximation of a tensor from streaming data
• An Implicit Representation and Iterative Solution of Randomly Sketched Linear Systems
• Randomized Low-Rank Approximation of Monotone Matrix Functions
• Distributed estimation of principal eigenspaces
• Single-pass randomized algorithms for LU decomposition
• An Improved Analysis and Unified Perspective on Deterministic and Randomized Low-Rank Matrix Approximation
• Screening for a reweighted penalized conditional gradient method
• Scalable \textit{in situ} compression of transient simulation data using time-dependent bases
• Learning to Forecast Dynamical Systems from Streaming Data
• Streaming Tensor Train Approximation
• Randomized Spectral Clustering in Large-Scale Stochastic Block Models
• An efficient randomized algorithm for computing the approximate Tucker decomposition
• Randomized sketching algorithms for low-memory dynamic optimization
• Low-rank nonnegative tensor approximation via alternating projections and sketching
• An efficient randomized fixed-precision algorithm for tensor singular value decomposition
• Scalable semidefinite programming
• Why Are Big Data Matrices Approximately Low Rank?
• Streaming low-rank matrix approximation with an application to scientific simulation
• An efficient randomized QLP algorithm for approximating the singular value decomposition
• Randomized Discrete Empirical Interpolation Method for Nonlinear Model Reduction
• Convergence rate of block-coordinate maximization Burer-Monteiro method for solving large SDPs
• Proof methods for robust low-rank matrix recovery
• Approximate distance-comparison-preserving symmetric encryption
• Fast and accurate randomized algorithms for linear systems and eigenvalue problems
• Random projections for linear programming: an improved retrieval phase
• Randomized compression of rank-structured matrices accelerated with graph coloring
• Fast randomized numerical rank estimation for numerically low-rank matrices
• Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions
• On the convergence of projected-gradient methods with low-rank projections for smooth convex minimization over trace-norm balls and related problems
• XT<scp>race</scp>: Making the Most of Every Sample in Stochastic Trace Estimation
• Robust Recovery of Low-Rank Matrices and Low-Tubal-Rank Tensors from Noisy Sketches
• Broadband recursive skeletonization
• A sequential multilinear Nyström algorithm for streaming low-rank approximation of tensors in Tucker format
• A multilinear Nyström algorithm for low-rank approximation of tensors in Tucker format
• Randomized Nyström Preconditioning
• Practical sketching algorithms for low-rank Tucker approximation of large tensors
• Wavelet-based resolvent analysis of non-stationary flows
• Principled interpolation of Green's functions learned from data
• Numerical strategies for recursive least squares solutions to the matrix equation AX = B
• SketchySGD: reliable stochastic optimization via randomized curvature estimates
• Revisiting Spectral Bundle Methods: Primal-Dual (Sub)linear Convergence Rates
• Memory-efficient structured convex optimization via extreme point sampling
• Pass-efficient truncated UTV for low-rank approximations

Uses Software

• Algorithm 971

This page was built for publication: Practical sketching algorithms for low-rank matrix approximation

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