Numerical linear algebra in the streaming model

DOI10.1145/1536414.1536445zbMath1304.65138OpenAlexW2059867647WikidataQ130959638 ScholiaQ130959638MaRDI QIDQ5172714

David P. Woodruff, Kenneth L. Clarkson

Publication date: 4 February 2015

Published in: Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1536414.1536445

zbMATH Keywords

matrix productlinear regressionlow-rank approximation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (37)

Pass-efficient methods for compression of high-dimensional turbulent flow data ⋮ Randomized numerical linear algebra: Foundations and algorithms ⋮ Side-constrained minimum sum-of-squares clustering: mathematical programming and random projections ⋮ Derandomizing restricted isometries via the Legendre symbol ⋮ Sublinear Estimation of Weighted Matchings in Dynamic Data Streams ⋮ Sparser Johnson-Lindenstrauss Transforms ⋮ Summary Data Structures for Massive Data ⋮ Robust Recovery of Low-Rank Matrices and Low-Tubal-Rank Tensors from Noisy Sketches ⋮ Streaming Tensor Train Approximation ⋮ Randomized algorithms in numerical linear algebra ⋮ Randomized LU decomposition ⋮ Faster least squares approximation ⋮ Streaming graph computations with a helpful advisor ⋮ Unnamed Item ⋮ Practical Sketching Algorithms for Low-Rank Matrix Approximation ⋮ Fast Metric Embedding into the Hamming Cube ⋮ A fast randomized algorithm for computing an approximate null space ⋮ Literature survey on low rank approximation of matrices ⋮ Single Pass Spectral Sparsification in Dynamic Streams ⋮ Optimal CUR Matrix Decompositions ⋮ Unnamed Item ⋮ Sketching for Principal Component Regression ⋮ Core-Sets: Updated Survey ⋮ Improved Algorithms for Time Decay Streams ⋮ Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering ⋮ Toward a unified theory of sparse dimensionality reduction in Euclidean space ⋮ Structural results on matching estimation with applications to streaming ⋮ Random projections for Bayesian regression ⋮ Multiplicative Approximations of Random Walk Transition Probabilities ⋮ Everywhere-Tight Information Cost Tradeoffs for Augmented Index ⋮ Almost Optimal Explicit Johnson-Lindenstrauss Families ⋮ Frequent Directions: Simple and Deterministic Matrix Sketching ⋮ Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation ⋮ Randomized Sketching Algorithms for Low-Memory Dynamic Optimization ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Streaming algorithms for extent problems in high dimensions

This page was built for publication: Numerical linear algebra in the streaming model