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 (42)

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

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