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

DOI10.1145/1536414.1536446MaRDI QIDQ5172715zbMATH OpenOpenAlexFDO

Authors

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

low rank matrix approximationnoncommutative Khintchine inequalitysingular value decompositionstructurally random matrix

Mathematics Subject Classification ID

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

Recommendations

• Adaptive Sampling and Fast Low-Rank Matrix Approximation
• Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
• Fast monte-carlo algorithms for finding low-rank approximations
• Fast low rank approximations of matrices and tensors
• Fast computation of low rank matrix approximations

Cited in

(29)

• A simple spectral algorithm for recovering planted partitions
• Low-rank and sparse matrices fitting algorithm for low-rank representation
• Effective implementation to reduce execution time of a low-rank matrix approximation problem
• Novel alternating update method for low rank approximation of structured matrices
• Multiplicative Approximations of Random Walk Transition Probabilities
• Fast low rank approximations of matrices and tensors
• Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering
• Adaptive Sampling and Fast Low-Rank Matrix Approximation
• Tensor sparsification via a bound on the spectral norm of random tensors: Algorithm 1.
• Literature survey on low rank approximation of matrices
• Low Rank Approximation of a Sparse Matrix Based on LU Factorization with Column and Row Tournament Pivoting
• Optimal bounds for Johnson-Lindenstrauss transformations
• Low-Rank Updates and a Divide-And-Conquer Method for Linear Matrix Equations
• Why Are Big Data Matrices Approximately Low Rank?
• Fast computation of low rank matrix approximations
• Subspace Iteration Randomization and Singular Value Problems
• Low-Rank Matrix Approximation Using Point-Wise Operators
• Tighter low-rank approximation via sampling the leveraged element
• A Fast Majorize–Minimize Algorithm for the Recovery of Sparse and Low-Rank Matrices
• Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces
• Fast Estimation of Approximate Matrix Ranks Using Spectral Densities
• Relative errors for deterministic low-rank matrix approximations
• The approximate rank of a matrix and its algorithmic applications
• Low-rank approximation of a matrix: novel insights, new progress, and extensions
• Fast and Accurate Proper Orthogonal Decomposition using Efficient Sampling and Iterative Techniques for Singular Value Decomposition
• Faster least squares approximation
• Turning big data into tiny data: coresets for unsupervised learning problems
• Fast multiple rank-constrained matrix approximation
• Generalizing random butterfly transforms to arbitrary matrix sizes

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5172715)