Fast computation of low rank matrix approximations

DOI10.1145/380752.380858zbMath1311.94032OpenAlexW2086486316MaRDI QIDQ5176019

Frank McSherry, Demetrios 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

Mathematics Subject Classification ID

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

Related Items (32)

Randomized numerical linear algebra: Foundations and algorithms ⋮ A randomized algorithm for a tensor-based generalization of the singular value decomposition ⋮ Far-field compression for fast kernel summation methods in high dimensions ⋮ Tensor Bernstein concentration inequalities with an application to sample estimators for high-order moments ⋮ Low-rank decomposition meets kernel learning: a generalized Nyström method ⋮ A fast SVD-hidden-nodes based extreme learning machine for large-scale data analytics ⋮ \textit{ScreeNOT}: exact MSE-optimal singular value thresholding in correlated noise ⋮ Random perturbation of low rank matrices: improving classical bounds ⋮ Dense fast random projections and Lean Walsh transforms ⋮ A note on element-wise matrix sparsification via a matrix-valued Bernstein inequality ⋮ Tensor sparsification via a bound on the spectral norm of random tensors: Algorithm 1. ⋮ Separating populations with wide data: a spectral analysis ⋮ On using prototype reduction schemes to optimize kernel-based nonlinear subspace methods. ⋮ Random walk with restart: fast solutions and applications ⋮ Sampling based succinct matrix approximation ⋮ Effective implementation to reduce execution time of a low-rank matrix approximation problem ⋮ Noisy random graphs and their laplacians ⋮ Generalized low rank approximations of matrices ⋮ Generalized low rank approximations of matrices ⋮ Recognizing linear structure in noisy matrices ⋮ Diffusion representations ⋮ A way for low ranking matrices and its stochastic computations using Monte Carlo method ⋮ Stochastic Algorithms in Linear Algebra - beyond the Markov Chains and von Neumann - Ulam Scheme ⋮ Stochastic boundary methods of fundamental solutions for solving PDEs ⋮ Less is More: Sparse Graph Mining with Compact Matrix Decomposition ⋮ Frequent Directions: Simple and Deterministic Matrix Sketching ⋮ Column subset selection via sparse approximation of SVD ⋮ Recovering PCA from Hybrid-$(\ell_1,\ell_2)$ Sparse Sampling of Data Elements ⋮ Singular value decomposition of large random matrices (for two-way classification of microarrays) ⋮ Matrix estimation by universal singular value thresholding ⋮ Unnamed Item ⋮ Unnamed Item

Cites Work

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

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