Fast computation of low rank matrix approximations

By Dimitris Achlioptas, Frank McSherry. Symposium on the Theory of Computing, 2001

356 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mathematics, Computational Mechanics

View Paper: https://www.semanticscholar.org/paper/9fe4e58bcf31d528a30f15bd0b180fbe298f91ef

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mathematics

In Computational Mechanics

Citations in the corpus

Matrix approximation and projective clustering via volume sampling (2006, methodology): “The problem of efficiently finding an approximation to this subspace has received much attention in the past decade [19, 15, 1 , 14, 16].”
Numerical linear algebra in the streaming model (2009, methodology): “A 1-pass algorithm was proposed by Achlioptas and McSherry [1], whose error estimate includes an additive term of ‖A‖; that is, their results are not low relative error.”
A randomized algorithm for a tensor-based generalization of the singular value decomposition (2007, background): “Recent work in the randomized algorithms literature has focused on algorithms for extremely large linear algebra problems [18,19,48,7,2,1,8,9,10,11,12,14,15,42,6].”
Algorithm 971: An Implementation of a Randomized Algorithm for Principal Component Analysis (2017, background): “However, the spectral norm is generally preferable for big data subject to noise, as argued by McSherry and Achlioptas [2007].”
SketchOGD: Memory-Efficient Continual Learning (2023, unknown): “…setting of one-pass learning. b) Matrix approximation: Many approaches have been proposed for approximating or compressing a matrix, including techniques based on sparsification and quantization [26], column selection [27], dimensionality reduction [28] and approximation by submatrices [29].”
User-Friendly Tail Bounds for Sums of Random Matrices (2010, background): “We have encountered these issues in a wide range of problems from computational mathematics: smoothed analysis of Gaussian elimination [51]; semidefinite relaxation and rounding of quadratic maximization problems [38, 50]; construction of maps for dimensionality reduction [1]; matrix approximation b”
Relative-Error CUR Matrix Decompositions (2007, methodology): “The primary focus of their work was in introducing methods to accelerate orthogonal iteration and Lanczos iteration methods, and their analysis relied heavily on ideas from random matrix theory [2, 1].”
Spectral Sparsification of Graphs (2008, methodology): “nd Aethe adjacency matrix of the sampled graph Ge. This procedure guarantees that E h Ae i = A. Sampling procedures of this form were examined by Benczur and Karger [BK96] and Achlioptas and McSherry [AM01]. Achlioptas and McSherry analyze the approximation obtained by such a procedure through a bou”
An Introduction to Matrix Concentration Inequalities (2015, unknown): “This approach was proposed in [3, 4], and the papers [2, 105] contain recent innovations.”
Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication (2006, methodology): “Note that the construction of the matrices S and R by the ElementwiseMatrixMultiplication algorithm may be viewed as adding carefully constructed random matrices E and D such that S = A + E and R = B + D; see [2] and [1] for a discussion.”
Simple and deterministic matrix sketching (2012, background): “Sparser matrices are stored more efficiently and can be multiplied faster by other matrices [4][2][15].”
Tighter Low-rank Approximation via Sampling the Leveraged Element (2014, background): “[1] considered a different approach based on entrywise sampling and quantization for low rank approximation and has given additive error bounds.”
TAIL BOUNDS FOR ALL EIGENVALUES OF A SUM OF RANDOM MATRICES (2011, methodology): “We mention in particular the work of Achlioptas and McSherry on randomized sparsification of matrices [AM01, AM07], that of Meckes on the norms of random matrices [Mec04], and that of Alon, Krivelevich and Vu [AKV02] on the concentration of the largest eigenvalues of random symmetric matrices, all…”