Fast computation of low-rank matrix approximations

DOI10.1145/1219092.1219097zbMath1311.94031MaRDI QIDQ3546324

Frank McSherry, Demetrios Achlioptas

Publication date: 21 December 2008

Published in: Journal of the ACM (Search for Journal in Brave)

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

Mathematics Subject Classification ID

68W40: Analysis of algorithms

15A18: Eigenvalues, singular values, and eigenvectors

94A20: Sampling theory in information and communication theory

Related Items

Unnamed Item, Unnamed Item, Randomized algorithms in numerical linear algebra, Tensor sparsification via a bound on the spectral norm of random tensors: Algorithm 1., Clustering subgaussian mixtures by semidefinite programming, Literature survey on low rank approximation of matrices, Analyzing Multiple‐Probe Microarray: Estimation and Application of Gene Expression Indexes, Recovering PCA from Hybrid-$(\ell_1,\ell_2)$ Sparse Sampling of Data Elements, Weighted community detection and data clustering using message passing, Non‐negative residual matrix factorization: problem definition, fast solutions, and applications, Unnamed Item, Randomized Spectral Clustering in Large-Scale Stochastic Block Models, Subsampling Algorithms for Semidefinite Programming, Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCA, Fast and Accurate Proper Orthogonal Decomposition using Efficient Sampling and Iterative Techniques for Singular Value Decomposition, Randomized numerical linear algebra: Foundations and algorithms, Comparison of matrix norm sparsification, Detection thresholds in very sparse matrix completion, Quantum-inspired canonical correlation analysis for exponentially large dimensional data, Dimension reduction and construction of feature space for image pattern recognition, Descriptive matrix factorization for sustainability. Adopting the principle of opposites, Convergence analysis of iterated best response for a trusted computation game, User-friendly tail bounds for sums of random matrices, A novel coupling of noise reduction algorithms for particle flow simulations, Randomized interpolative decomposition of separated representations, Territorial design optimization for business sales plan, Randomized LU decomposition, Exemplar-based low-rank matrix decomposition for data clustering, An improvement of the parameterized frequent directions algorithm, Reducing uncertainty of dynamic heterogeneous information networks: a fusing reconstructing approach, A note on element-wise matrix sparsification via a matrix-valued Bernstein inequality, Second order accurate distributed eigenvector computation for extremely large matrices, Randomized LU decomposition using sparse projections, GraphLSHC: towards large scale spectral hypergraph clustering, Spectral estimation from simulations via sketching, Far-field compression for fast kernel summation methods in high dimensions, A note on linear function approximation using random projections, Column subset selection problem is UG-hard, Quantum context-aware recommendation systems based on tensor singular value decomposition, A remark on the spectra of random graphs with given expected degrees, Low-Rank Matrix Approximations Do Not Need a Singular Value Gap