Practical Sketching Algorithms for Low-Rank Matrix Approximation

DOI10.1137/17M1111590zbMath1379.65026arXiv1609.00048OpenAlexW3100283647MaRDI QIDQ4598337

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

Publication date: 20 December 2017

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

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

zbMATH Keywords

sketching dimension reduction randomized algorithm numerical experiment numerical linear algebra matrix approximation streaming algorithm subspace embedding single-pass algorithm

Mathematics Subject Classification ID

Related Items

Exploiting low-rank structure in semidefinite programming by approximate operator splitting, Pass-efficient methods for compression of high-dimensional turbulent flow data, Low-Rank Tucker Approximation of a Tensor from Streaming Data, Randomized numerical linear algebra: Foundations and algorithms, Randomized Spectral Clustering in Large-Scale Stochastic Block Models, A Nonlinear Matrix Decomposition for Mining the Zeros of Sparse Data, Randomized quaternion QLP decomposition for low-rank approximation, Screening for a reweighted penalized conditional gradient method, Scalable \textit{in situ} compression of transient simulation data using time-dependent bases, Randomized QLP decomposition, Improved Variants of the Hutch++ Algorithm for Trace Estimation, Efficient Randomized Algorithms for the Fixed-Precision Low-Rank Matrix Approximation, Subspaces Analysis for Random Projection UTV Framework, Sketching for a low-rank nonnegative matrix approximation: numerical study, Contour Integral Methods for Nonlinear Eigenvalue Problems: A Systems Theoretic Approach, Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions, An efficient randomized QLP algorithm for approximating the singular value decomposition, Randomized algorithms for the computation of multilinear rank-\((\mu_1,\mu_2,\mu_3)\) approximations, Robust Recovery of Low-Rank Matrices and Low-Tubal-Rank Tensors from Noisy Sketches, Pass-efficient randomized LU algorithms for computing low-rank matrix approximation, Streaming Tensor Train Approximation, An efficient randomized fixed-precision algorithm for tensor singular value decomposition, Randomized Low-Rank Approximation for Symmetric Indefinite Matrices, An Improved Analysis and Unified Perspective on Deterministic and Randomized Low-Rank Matrix Approximation, Practical sketching algorithms for low-rank Tucker approximation of large tensors, Principled interpolation of Green's functions learned from data, Numerical strategies for recursive least squares solutions to the matrix equation AX = B, Solving trust region subproblems using Riemannian optimization, Revisiting Spectral Bundle Methods: Primal-Dual (Sub)linear Convergence Rates, Pass-efficient truncated UTV for low-rank approximations, Approximate distance-comparison-preserving symmetric encryption, Practical Sketching Algorithms for Low-Rank Matrix Approximation, Low-rank nonnegative tensor approximation via alternating projections and sketching, A fast randomized algorithm for computing an approximate null space, The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection, Randomized Nyström Preconditioning, Randomized Low-Rank Approximation of Monotone Matrix Functions, Learning to Forecast Dynamical Systems from Streaming Data, Randomized Discrete Empirical Interpolation Method for Nonlinear Model Reduction, XT<scp>race</scp>: Making the Most of Every Sample in Stochastic Trace Estimation, Randomized Subspace Iteration: Analysis of Canonical Angles and Unitarily Invariant Norms, Memory-Efficient Structured Convex Optimization via Extreme Point Sampling, FANOK: Knockoffs in Linear Time, Pass-Efficient Randomized Algorithms for Low-Rank Matrix Approximation Using Any Number of Views, Low-Rank Independence Samplers in Hierarchical Bayesian Inverse Problems, Distributed estimation of principal eigenspaces, Random projections for conic programs, A non-Euclidean gradient descent method with sketching for unconstrained matrix minimization, An efficient randomized algorithm for computing the approximate Tucker decomposition, Generalized Conditional Gradient with Augmented Lagrangian for Composite Minimization, Single-pass randomized algorithms for LU decomposition, Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation, Randomized Sketching Algorithms for Low-Memory Dynamic Optimization, An Implicit Representation and Iterative Solution of Randomly Sketched Linear Systems, Scalable Semidefinite Programming, Unnamed Item, Convergence rate of block-coordinate maximization Burer-Monteiro method for solving large SDPs, On the Convergence of Projected-Gradient Methods with Low-Rank Projections for Smooth Convex Minimization over Trace-Norm Balls and Related Problems, Unnamed Item, Perturbations of CUR Decompositions, Sublinear Cost Low Rank Approximation via Subspace Sampling, Proof methods for robust low-rank matrix recovery, Single-pass randomized QLP decomposition for low-rank approximation, Why Are Big Data Matrices Approximately Low Rank?, ISLET: Fast and Optimal Low-Rank Tensor Regression via Importance Sketching

Uses Software

Algorithm 971

Cites Work