Frequent Directions: Simple and Deterministic Matrix Sketching

DOI10.1137/15M1009718zbMath1348.65075arXiv1501.01711OpenAlexW1485437584MaRDI QIDQ2821796

Mina Ghashami, Jeff M. Phillips, Edo Liberty, 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

algorithmsingular value decompositionstreamingmatrix sketching\textsc{FrequentDirections}covariance sketching

Mathematics Subject Classification ID

Related Items (18)

Active Subspace of Neural Networks: Structural Analysis and Universal Attacks ⋮ Accelerating patch-based low-rank image restoration using kd-forest and Lanczos approximation ⋮ Randomized numerical linear algebra: Foundations and algorithms ⋮ Randomized Quaternion Singular Value Decomposition for Low-Rank Matrix Approximation ⋮ One-pass additive-error subset selection for \(\ell_p\) subspace approximation and \((k, p)\)-clustering ⋮ Randomized algorithms for orthogonal nonnegative matrix factorization ⋮ Unnamed Item ⋮ Learning to Forecast Dynamical Systems from Streaming Data ⋮ Literature survey on low rank approximation of matrices ⋮ Improved Algorithms for Time Decay Streams ⋮ Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering ⋮ An improvement of the parameterized frequent directions algorithm ⋮ Communication-Efficient Distributed Eigenspace Estimation ⋮ Structural results on matching estimation with applications to streaming ⋮ Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item

Uses Software

• Caltech-UCSD Birds

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Faster least squares approximation
• Sums of random Hermitian matrices and an inequality by Rudelson
• Spectral norm of products of random and deterministic matrices
• On the largest principal angle between random subspaces
• Finding repeated elements
• On randomized one-round communication complexity
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Latent semantic indexing: A probabilistic analysis
• A note on element-wise matrix sparsification via a matrix-valued Bernstein inequality
• Sequential Karhunen-Loeve basis extraction and its application to images
• A sparse Johnson
• Improved Practical Matrix Sketching with Guarantees
• Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
• Mergeable summaries
• Randomized algorithms for the low-rank approximation of matrices
• Non-asymptotic theory of random matrices: extreme singular values
• Low-Rank Approximation and Regression in Input Sparsity Time
• Sparser Johnson-Lindenstrauss Transforms
• Sampling from large matrices
• Adaptive Sampling and Fast Low-Rank Matrix Approximation
• A Fast Random Sampling Algorithm for Sparsifying Matrices
• Relative-Error $CUR$ Matrix Decompositions
• Strong converse for identification via quantum channels
• Communication Complexity
• Numerical linear algebra in the streaming model
• Fast computation of low rank matrix approximations
• Relative Errors for Deterministic Low-Rank Matrix Approximations
• Fast monte-carlo algorithms for finding low-rank approximations
• Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
• Near Optimal Column-Based Matrix Reconstruction
• On differentially private low rank approximation
• Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering

This page was built for publication: Frequent Directions: Simple and Deterministic Matrix Sketching