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

singular value decompositionalgorithmstreamingmatrix sketching\textsc{FrequentDirections}covariance sketching

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

• 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?)
• 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 Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
• Fast approximation of matrix coherence and statistical leverage
• Fast computation of low rank matrix approximations
• Fast monte-carlo algorithms for finding low-rank approximations
• Faster least squares approximation
• Finding repeated elements
• 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)

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

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)