A fast and efficient algorithm for low-rank approximation of a matrix
From MaRDI portal
Publication:5172715
DOI10.1145/1536414.1536446zbMath1304.65140MaRDI QIDQ5172715
No author found.
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.1536446
singular value decomposition; low rank matrix approximation; noncommutative Khintchine inequality; structurally random matrix
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
68W20: Randomized algorithms
Related Items
Tensor sparsification via a bound on the spectral norm of random tensors: Algorithm 1., Literature survey on low rank approximation of matrices, Optimal Bounds for Johnson-Lindenstrauss Transformations, Subspace Iteration Randomization and Singular Value Problems, Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces, Fast and Accurate Proper Orthogonal Decomposition using Efficient Sampling and Iterative Techniques for Singular Value Decomposition, Faster least squares approximation, A simple spectral algorithm for recovering planted partitions, Effective implementation to reduce execution time of a low-rank matrix approximation problem, Multiplicative Approximations of Random Walk Transition Probabilities, Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering