Sampling from large matrices: An approach through geometric functional analysis

By Mark Rudelson, Roman Vershynin. JACM, 2005

415 citations recorded by the source corpus.

We study random submatrices of a large matrix A. We show how to approximately compute A from its random submatrix of the smallest possible size O(rlog r) with a small error in the spectral norm, where r = ‖A‖2F/‖A‖22 is the numerical rank of A. The numerical rank is always bounded by, and is a stable relaxation of, the rank of A. This yields an asymptotically optimal guarantee in an algorithm for computing low-rank approximations of A. We also prove asymptotically optimal estimates on the spectral norm and the cut-norm of random submatrices of A. The result for the cut-norm yields a slight improvement on the best-known sample complexity for an approximation algorithm for MAX-2CSP problems. We use methods of Probability in Banach spaces, in particular the law of large numbers for operator-valued random variables.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/c77239fd517e60303fa14a64aa80a567771e01bc

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 Mechanics

In Computational Theory and Mathematics

Citations in the corpus

Simple and deterministic matrix sketching (2012, background): “Despite this algorithm’s apparent simplicity, providing tight bounds for its performance required over a decade of research [16][3][12][26][29][24][14].”
Exact Recoverability From Dense Corrupted Observations via $\ell _{1}$-Minimization (2011, result): “This result has been known in the literature [26]–[28].”
Sums of random Hermitian matrices and an inequality by Rudelson (2010, background): “While similar results have appeared in other papers [10, 12, 16], our proof is simpler and gives explicit (albeit quite large) constants.”
TAIL BOUNDS FOR ALL EIGENVALUES OF A SUM OF RANDOM MATRICES (2011, background): “uise of a lemma, due to Rudelson [Rud99], that provides an analog of the law of large numbers for sums of rank-one matrices. This result has found many applications, including column-subset selection [RV07] and the fast approximate solution of least-squares problems [DMMS11]. The NCKI and its coroll”
Low-Rank Approximation and Regression in Input Sparsity Time (2012, background): “…error [Frieze et al. 2004; Papadimitriou et al. 2000; Achlioptas and McSherry 2007; Drineas et al. 2006a, 2006b, 2006c; Drineas and Mahoney 2005; Rudelson and Vershynin 2007; Deshpande et al. 2006] or they get a bounded relative error but are slow [Deshpande and Vempala 2006; Drineas et al.…”
Spectral norm of products of random and deterministic matrices (2008, background): “We obtain P { max j=1,...,n Sj > 2(np+ log(2n))s } ≤ ne−c log(2n)s = 2−csn1−cs. Integration yields E max j=1,...,n Sj ≤ C(np+ log(2n)).”
Tail inequalities for sums of random matrices that depend on the intrinsic dimension (2012, background): “Rudelson and Vershynin (2007) also prove similar exponential tail inequalities for sums of rank-one matrices using non-commutative Khinchine moment inequalities by way of a key inequality of Rudelson (1999); the extension to higher rank random matrices is not explicitly worked out, but may be…”
Introduction to the non-asymptotic analysis of random matrices (2010, background): “It is a big program to understand what we can learn about B by seeing A, see [34, 25, 66].”
Norms of Random Submatrices and Sparse Approximation (2008, positive): “The proof of Theorem 1.1 uses a result of Rudelson–Vershynin [4] to bound the spectral norm of a random column submatrix.”
GSPBOX: A toolbox for signal processing on graphs (2014, background): “; G2 = gsp_graph_sparsify(G,epsilon); figure(100); gsp_plot_graph(G); title(’Original graph’) figure(101); gsp_plot_graph(G2); title(’Sparsified graph’) close(100); close(101); References: [11], [7], [8] 8.5.2 GSP_REPMATLINE - This function repeat the matrix A in aspeciﬁc manner Usage Ar = gsp_repma”
Improved Approximation Algorithms for Large Matrices via Random Projections (2006, methodology): “Subsequent research based on sampling entire rows or columns with probability proportional to their squared Euclidean length resulted in more practical algorithms and refined analysis both for SVD [28, 24, 49, 20] and approximate matrix products [23].”
Randomized numerical linear algebra: Foundations and algorithms (2020, methodology): “More refined analyses of empirical matrix approximation were obtained in (Rudelson and Vershynin 2007, Tropp 2015).”