Frequent directions: simple and deterministic matrix sketching

DOI10.1137/15M1009718MaRDI QIDQ2821796zbMATH OpenOpenAlexFDO

Authors Mina Ghashami, Edo Liberty, Jeff M. Phillips, David P. Woodruff

Publication date 23 September 2016

Published in SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

\textsc{FrequentDirections}algorithmcovariance sketchingmatrix sketchingsingular value decompositionstreaming

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20)

Abstract: We describe a new algorithm called Frequent Directions for deterministic matrix sketching in the row-updates model. The algorithm is presented an arbitrary input matrix $Ain{R}^{nimesd}$ one row at a time. It performed $O(dimesell)$ operations per row and maintains a sketch matrix $Bin{R}^{ellimesd}$ such that for any $k<ell$ $|A^{T}A-B^{T}B{|}_{2}leq|A-A_k{|}_F^2/(ell-k)$ and $$ . Here, $A_k$ stands for the minimizer of $|A-A_k{|}_F$ over all rank $k$ matrices (similarly $B_k$) and $p{i}_{B_k}(A)$ is the rank $k$ matrix resulting from projecting $A$ on the row span of $B_k$. We show both of these bounds are the best possible for the space allowed. The summary is mergeable, and hence trivially parallelizable. Moreover, Frequent Directions outperforms exemplar implementations of existing streaming algorithms in the space-error tradeoff.

Recommendations

• scientific article; zbMATH DE number 7049775
• Improved practical matrix sketching with guarantees
• Practical sketching algorithms for low-rank matrix approximation
• Deterministic algorithms for skewed matrix products
• An improvement of the parameterized frequent directions algorithm
• On sketching matrix norms and the top singular vector
• A Distance-Preserving Matrix Sketch
• Randomized Sketching for Krylov Approximations of Large-Scale Matrix Functions
• scientific article; zbMATH DE number 3976197
• Direct methods for sparse matrices

Cites work

• A Fast Random Sampling Algorithm for Sparsifying Matrices
• A note on element-wise matrix sparsification via a matrix-valued Bernstein inequality
• A sparse Johnson-Lindenstrauss transform
• Adaptive Sampling and Fast Low-Rank Matrix Approximation
• An improved approximation algorithm for the column subset selection problem
• Communication Complexity
• Data streams: algorithms and applications.
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Dimensionality reduction for k-means clustering and low rank approximation
• Fast approximation of matrix coherence and statistical leverage
• Fast computation of low rank matrix approximations
• Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
• Fast monte-carlo algorithms for finding low-rank approximations
• Faster least squares approximation
• Finding repeated elements
• scientific article; zbMATH DE number 4023423 (Why is no real title available?)
• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• scientific article; zbMATH DE number 1947405 (Why is no real title available?)
• scientific article; zbMATH DE number 2045498 (Why is no real title available?)
• scientific article; zbMATH DE number 2079343 (Why is no real title available?)
• scientific article; zbMATH DE number 2086663 (Why is no real title available?)
• scientific article; zbMATH DE number 2109363 (Why is no real title available?)
• scientific article; zbMATH DE number 6159604 (Why is no real title available?)
• scientific article; zbMATH DE number 1424312 (Why is no real title available?)
• Improved practical matrix sketching with guarantees
• Latent semantic indexing: A probabilistic analysis
• Mergeable summaries
• Near Optimal Column-Based Matrix Reconstruction
• Non-asymptotic theory of random matrices: extreme singular values
• Numerical linear algebra in the streaming model
• On differentially private low rank approximation
• On randomized one-round communication complexity
• On the largest principal angle between random subspaces
• Randomized algorithms for the low-rank approximation of matrices
• Relative errors for deterministic low-rank matrix approximations
• Relative-Error CUR Matrix Decompositions
• Sampling from large matrices
• Sequential Karhunen-Loève basis extraction and its application to images
• Sparser Johnson-Lindenstrauss transforms
• Spectral norm of products of random and deterministic matrices
• Strong converse for identification via quantum channels
• Sums of random Hermitian matrices and an inequality by Rudelson
• Turning big data into tiny data: constant-size coresets for k-means, PCA and projective clustering

Cited in

(28)

• An improvement of the parameterized frequent directions algorithm
• Structural results on matching estimation with applications to streaming
• Accelerating patch-based low-rank image restoration using kd-forest and Lanczos approximation
• Improved practical matrix sketching with guarantees
• Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering
• Literature survey on low rank approximation of matrices
• Robust frequent directions with application in online learning
• scientific article; zbMATH DE number 7049775 (Why is no real title available?)
• Communication-efficient distributed covariance sketch, with application to distributed PCA
• Active subspace of neural networks: structural analysis and universal attacks
• Randomized Quaternion Singular Value Decomposition for Low-Rank Matrix Approximation
• MetaGrad: adaptation using multiple learning rates in online learning
• Communication-Efficient Distributed Eigenspace Estimation
• Numerical linear algebra in the streaming model
• Streaming low-rank matrix approximation with an application to scientific simulation
• Relative errors for deterministic low-rank matrix approximations
• Eigenvalues of a matrix in the streaming model
• Improved Algorithms for Time Decay Streams
• Randomized numerical linear algebra: Foundations and algorithms
• One-pass additive-error subset selection for \(\ell_p\) subspace approximation and \((k, p)\)-clustering
• Randomized algorithms for orthogonal nonnegative matrix factorization
• Learning to Forecast Dynamical Systems from Streaming Data
• Improving compressed matrix multiplication using control variate method
• A stochastic perturbation analysis of the QR decomposition and its applications
• Online randomized interpolative decomposition with \textit{a posteriori} error estimator for temporal PDE data reduction
• Turning big data into tiny data: coresets for unsupervised learning problems
• Explicable hyper-reduced order models on nonlinearly approximated solution manifolds of compressible and incompressible Navier-Stokes equations
• Algorithm-agnostic low-rank approximation of operator monotone matrix functions

Describes a project that uses

Uses Software

• Caltech-UCSD Birds

This page was built for publication: Frequent directions: simple and deterministic matrix sketching

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