Fast computation of low rank matrix approximations

DOI10.1145/380752.380858zbMATH Open1311.94032OpenAlexW2086486316MaRDI QIDQ5176019FDOQ5176019

Authors: Frank McSherry, D. Achlioptas 

Publication date: 27 February 2015

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

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

Recommendations

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

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Analysis of algorithms (68W40) Sampling theory in information and communication theory (94A20)

Cites Work

• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)

Cited In (45)

• Title not available (Why is that?)
• Generalized low rank approximations of matrices
• Fast Estimation of Approximate Matrix Ranks Using Spectral Densities
• Less is More: Sparse Graph Mining with Compact Matrix Decomposition
• Far-field compression for fast kernel summation methods in high dimensions
• Stochastic boundary methods of fundamental solutions for solving PDEs
• Low-rank approximation of a matrix: novel insights, new progress, and extensions
• Tighter low-rank approximation via sampling the leveraged element
• Quantum recommendation systems
• A randomized algorithm for a tensor-based generalization of the singular value decomposition
• Randomized numerical linear algebra: Foundations and algorithms
• Singular value decomposition of large random matrices (for two-way classification of microarrays)
• Matrix estimation by universal singular value thresholding
• Noisy random graphs and their laplacians
• A note on element-wise matrix sparsification via a matrix-valued Bernstein inequality
• Recognizing linear structure in noisy matrices
• On using prototype reduction schemes to optimize kernel-based nonlinear subspace methods.
• \textit{ScreeNOT}: exact MSE-optimal singular value thresholding in correlated noise
• Low-Rank Matrix Approximation Using Point-Wise Operators
• Separating populations with wide data: a spectral analysis
• Frequent directions: simple and deterministic matrix sketching
• Fast structured matrix computations: tensor rank and Cohn-Umans method
• A fast and efficient algorithm for low-rank approximation of a matrix
• Improving the Complexity of Block Low-Rank Factorizations with Fast Matrix Arithmetic
• Practical sketching algorithms for low-rank matrix approximation
• Random walk with restart: fast solutions and applications
• Sampling based succinct matrix approximation
• Fast low-rank modifications of the thin singular value decomposition
• Adaptive Sampling and Fast Low-Rank Matrix Approximation
• Tensor Bernstein concentration inequalities with an application to sample estimators for high-order moments
• Fast low rank approximations of matrices and tensors
• Tensor sparsification via a bound on the spectral norm of random tensors: Algorithm 1.
• Column subset selection via sparse approximation of SVD
• Low-rank decomposition meets kernel learning: a generalized Nyström method
• Generalized low rank approximations of matrices
• Stochastic algorithms in linear algebra -- beyond the Markov chains and von Neumann-Ulam scheme
• A way for low ranking matrices and its stochastic computations using Monte Carlo method
• Recovering PCA and sparse PCA via hybrid-\((\ell_1,\ell_2)\) sparse sampling of data elements
• Random perturbation of low rank matrices: improving classical bounds
• A fast SVD-hidden-nodes based extreme learning machine for large-scale data analytics
• Why Are Big Data Matrices Approximately Low Rank?
• Dense fast random projections and Lean Walsh transforms
• Fast monte-carlo algorithms for finding low-rank approximations
• Effective implementation to reduce execution time of a low-rank matrix approximation problem
• Approximating Matrix Multiplication for Pattern Recognition Tasks

This page was built for publication: Fast computation of low rank matrix approximations

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