Sampling algorithms for l2 regression and applications

By Petros Drineas, Michael W. Mahoney, S. Muthu Muthukrishnan. ACM-SIAM Symposium on Discrete Algorithms, 2006

410 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Statistics and Probability

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

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 Statistics and Probability

Citations in the corpus

A randomized algorithm for a tensor-based generalization of the singular value decomposition (2007, background): “…indices of the columns that have been chosen in the ﬁrst (cid:8) − 1 rounds form the multiset { S 1 , S 2 , . . . , S (cid:8) − 1 } (where the multiset of columns S i were chosen in the i th round) and let matrix whose columns are the columns of A with indices in { S 1 , S 2 , . . . , S (cid:8) −…”
A unified framework for approximating and clustering data (2011, methodology): “Efficient approximation algorithms for the regression problem are given by Clarkson [12] for z = 1, Drineas, Mahoney, and Muthukrishnan [17] for z = 2, and Dasgupta et al.”
PCA-Correlated SNPs for Structure Identification in Worldwide Human Populations (2007, background): “[34,35] proved that if a small number of columns is picked in independent identical random trials, where in each trial the j-th column of A is picked with probability proportional to pj, then the top k left singular vectors of the selected columns are very close to the top k left singular vectors of”
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),…”
Faster least squares approximation (2007, methodology): “Remark: In prior work [8, 9], nonuniform sampling probabilities were computed to satisfy (25) with β = 1.”
Relative-Error CUR Matrix Decompositions (2007, methodology): “Note that an immediate generalization of the results of [29] to the generalized 2 regression problem considered in this section would involve sampling probabilities of the form (24)”
Improved Approximation Algorithms for Large Matrices via Random Projections (2006, methodology): “In [29, 30, 31] these results are then applied to products arising from the singular value decomposition of the input.”
A statistical perspective on algorithmic leveraging (2013, methodology): “This is the basic algorithmic leveraging algorithm that was originally proposed in (Drineas et al., 2006), and it’s solution will be denoted by β̃LEV .”
Low-Rank Approximation and Regression in Input Sparsity Time (2012, background): “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]).”
Sketching as a Tool for Numerical Linear Algebra (2014, background): “This is called Leverage Score Sampling [42, 46, 45, 43], which will be discussed later in the chapter.”
A Sharper Generalization Bound for Divide-and-Conquer Ridge Regression (2019, background): “Although the theories in (Avron, Clarkson, and Woodruff 2016; Clarkson and Woodruff 2013; Drineas, Mahoney, and Muthukrishnan 2006; Drineas et al. 2011) showed that this approximate solution, denote ˜ w , is not far from the ERM solution w erm in the (cid:96) 2 norm sense, it magniﬁes either the…”
The Fast Johnson--Lindenstrauss Transform and Approximate Nearest Neighbors (2009, methodology): “Sarlós [40] recently discovered that the FJLT can be used to improve a result by Drineas, Mahoney, and Muthukrishnan [17] on fast approximate 2-regression.”
Sub-Sampled Newton Methods I: Globally Convergent Algorithms (2016, background): “, sampling with respect to approximate leverage scores [21, 20].”