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
• Low-Rank Approximation and Regression in Input Sparsity Time
• 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
• Toward a unified theory of sparse dimensionality reduction in Euclidean space
• Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
• Fast linear algebra is stable
• Computational Advertising: Techniques for Targeting Relevant Ads
• 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 (76)

• Approximate distance-comparison-preserving symmetric encryption
• Fast and accurate randomized algorithms for linear systems and eigenvalue problems
• On the Convergence of Projected-Gradient Methods with Low-Rank Projections for Smooth Convex Minimization over Trace-Norm Balls and Related Problems
• Random projections for linear programming: an improved retrieval phase
• Randomized compression of rank-structured matrices accelerated with graph coloring
• Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions
• 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
• Pass-efficient truncated UTV for low-rank approximations
• Practical Sketching Algorithms for Low-Rank Matrix Approximation
• Efficient Randomized Algorithms for the Fixed-Precision Low-Rank Matrix Approximation
• 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
• Generalized Conditional Gradient with Augmented Lagrangian for Composite Minimization
• Subspaces Analysis for Random Projection UTV Framework
• Low-Rank Tucker Approximation of a Tensor from Streaming Data
• 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
• 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
• Pass-efficient methods for compression of high-dimensional turbulent flow data
• Perturbations of CUR Decompositions
• Randomized Sketching Algorithms for Low-Memory Dynamic Optimization
• 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
• Title not available (Why is that?)
• Scalable Semidefinite Programming
• Frequent directions: simple and deterministic matrix sketching
• Efficient $\widetilde{O}(n/\epsilon)$ Spectral Sketches for the Laplacian and its Pseudoinverse
• Exploiting low-rank structure in semidefinite programming by approximate operator splitting
• Improved Variants of the Hutch++ Algorithm for Trace Estimation
• Memory-Efficient Structured Convex Optimization via Extreme Point Sampling
• Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation
• Randomized quaternion QLP decomposition for low-rank approximation
• 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
• Pass-Efficient Randomized Algorithms for Low-Rank Matrix Approximation Using Any Number of Views
• Randomized Spectral Clustering in Large-Scale Stochastic Block Models
• An efficient randomized algorithm for computing the approximate Tucker decomposition
• ISLET: Fast and Optimal Low-Rank Tensor Regression via Importance Sketching
• Low-Rank Independence Samplers in Hierarchical Bayesian Inverse Problems
• Low-rank nonnegative tensor approximation via alternating projections and sketching
• FANOK: Knockoffs in Linear Time
• Randomized Subspace Iteration: Analysis of Canonical Angles and Unitarily Invariant Norms
• An efficient randomized fixed-precision algorithm for tensor singular value decomposition
• Why Are Big Data Matrices Approximately Low Rank?
• Title not available (Why is that?)
• An efficient randomized QLP algorithm for approximating the singular value decomposition
• A Nonlinear Matrix Decomposition for Mining the Zeros of Sparse Data
• 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

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)