Fast computation of low-rank matrix approximations

DOI10.1145/1219092.1219097zbMath1311.94031OpenAlexW1970950689MaRDI 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

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

Related Items

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