Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication

By Petros Drineas, R. Kannan, Michael W. Mahoney. 2006

531 citations recorded by the source corpus.

Subfields: Computational Mathematics, Computational Theory and Mathematics, Statistics and Probability

How researchers see this paper

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

In Computational Mathematics

In Computational Theory and Mathematics

In Statistics and Probability

Citations in the corpus

Parseval Networks: Improving Robustness to Adversarial Examples (2017, methodology): “Provided the rows are carefully sampled, the procedure is an accurate Monte Carlo approximation of the regularizer loss function (Drineas et al., 2006).”
GIANT: Globally Improved Approximate Newton Method for Distributed Optimization (2017, methodology): “…S 1 , · · · , S m ∈ n s be independent uniform sampling matrices with s = Θ( R Besides uniform sampling, other sketching methods such as leverage score sampling (Drineas et al., 2006b), Gaussian projection (Johnson and Lindenstrauss, 1984), Rademacher random variables (Achlioptas, 2003),…”
A randomized algorithm for a tensor-based generalization of the singular value decomposition (2007, methodology): “Sampling probabilities of the form (9) (with β = 1 and where A (i) is the i th column of the matrix A and | A (i) | is its Euclidean length) are optimal in a sense made precise in [10].”
Subgradient and sampling algorithms for l1 regression (2005, methodology): “The probabilities used in the sampling technique is similar in flavor to that used in some recent randomized approximation algorithms for numerical linear algebra.[DK01, DKM ] One dierence from those algorithms is that the sampling is done independently for each input point, rather than picking eac”
On the Nyström Method for Approximating a Gram Matrix for Improved Kernel-Based Learning (2005, methodology): “…between recent work on Nyström-based kernel methods (Williams and Seeger, 2001; Williams, Rasmussen, Schwaighofer, and Tresp, 2002; Fowlkes, Belongie, Chung, and Malik, 2004) and the low-rank approximation algorithm of Frieze, Kannan, and Vempala (1998); Drineas, Kannan, and Mahoney (2004b).”
Spectral Curvature Clustering (SCC) (2009, methodology): “2More precisely, a scaling constant needs to be used in front of the sum in order to have the right magnitude (see Drineas et al. 2006, Sect.”
Low-Rank Approximation and Regression in Input Sparsity Time (2012, methodology): “However, in the applications we are aware of, such as coresets for regression [Dasgupta et al. 2009], ε is typically constant (in the applications of this, a general ε > 0 can be achieved by oversampling [Drineas et al. 2006a; Dasgupta et al. 2009]).”
Tail inequalities for sums of random matrices that depend on the intrinsic dimension (2012, methodology): “This scheme was originally proposed and analyzed by Drineas et al. (2006), where the error measure used was the Frobenius norm; here, we analyze the spectral norm error.”
Sub-Sampled Newton Methods II: Local Convergence Rates (2016, unknown): “Hence, we can use approximate matrix multiplication results as a fundamental primitive in RandNLA [33, 18], to probabilistically control the error in approximation of ∇F (x) by g(x), through uniform sampling of the columns and rows of the involved matrices above.”
Improved Approximation Algorithms for Large Matrices via Random Projections (2006, methodology): “The complexity of the procedure is a factor log(m+p) higher than that of the column-row sampling approach [23].”
An improved approximation algorithm for the column subset selection problem (2008, unknown): “ Vρ−kΣρ−k −Γ+Γ||2 ≤ ||Σ ρ−kV T −kS1D1D1S T 1 Vρ− kΣρ−k −Γ||2 + Σ2 ρ− 2 ≤ ||Σρ−kV T ρ−kS1D1D1S T 1 Vρ−kΣρ−k −Γ||F + Σ2 ρ−k 2 . Given our construction of S1 and D1 and applying eqn. (9) of Theorem 1 of [13] with β = 1/2 and δ = 0.1, we get that with probability at least 0.9, Σ ρ−kV T ρ−kS1D1D1S T 1 Vρ”
Fast Randomized Kernel Methods With Statistical Guarantees (2014, methodology): “It is known that is the optimal sampling distribution in terms of minimizing the expected error E (cid:107) ΨΨ (cid:62) − Ψ SS (cid:62) Ψ 2 F ; see [13].”
Faster least squares approximation (2007, methodology): “ the sampling probabilities are uniform and do not depend on the norms of the columns of (HDUA) T or the rows of Hb⊥. However, we can still apply the results of Table 1 (second row) in 12 page 150 of [11]. More speciﬁcally, since we condition on eqn. (23) holding, the rows of HDUA (which of course c”
Random Matrices: the Distribution of the Smallest Singular Values (2009, unknown): “Quantitatively, we have Lemma 5.3 (Correlation between distances).”
Fast Randomized Kernel Ridge Regression with Statistical Guarantees (2015, methodology): “Recall that Kii = ‖φ(xi)‖ 2 F , so our procedure is akin to sampling according to the squared lengths of the data vectors, which has been extensively used in different contexts of randomized matrix approximation [21, 17, 19, 8, 2].”