A fast and efficient algorithm for low-rank approximation of a matrix

DOI10.1145/1536414.1536446zbMath1304.65140OpenAlexW2084439502MaRDI 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

zbMATH Keywords

singular value decompositionlow rank matrix approximationnoncommutative Khintchine inequalitystructurally random matrix

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (11)

A simple spectral algorithm for recovering planted partitions ⋮ Faster least squares approximation ⋮ Tensor sparsification via a bound on the spectral norm of random tensors: Algorithm 1. ⋮ Literature survey on low rank approximation of matrices ⋮ Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces ⋮ Effective implementation to reduce execution time of a low-rank matrix approximation problem ⋮ Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering ⋮ Optimal Bounds for Johnson-Lindenstrauss Transformations ⋮ Multiplicative Approximations of Random Walk Transition Probabilities ⋮ Subspace Iteration Randomization and Singular Value Problems ⋮ Fast and Accurate Proper Orthogonal Decomposition using Efficient Sampling and Iterative Techniques for Singular Value Decomposition

This page was built for publication: A fast and efficient algorithm for low-rank approximation of a matrix