Subgradient and sampling algorithms for l1 regression

By Kenneth L. Clarkson. ACM-SIAM Symposium on Discrete Algorithms, 2005

89 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/66487fcc8fa499c52d1896fc0db35a69b59c9d59

How researchers see this paper

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

Citations in the corpus

Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression (2012, background): “In spite of their low-degree polynomial-time solvability, (cid:96) p regression problems have been the focus in recent years of a wide range of random sampling and random projection algorithms, largely due to a desire to develop improved algorithms for large-scale data applications [3, 24, 10].”
Agnostically learning halfspaces (2005, background): “L1 linear regression is a well-studied problem [ 7 ], and the minimizing polynomial p for the RHS of (3) can be obtained in poly(n d ) time using linear programming.”
Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions (2009, methodology): “Randomized algorithms for l1 regression are described in [28].”
Sketching as a Tool for Numerical Linear Algebra (2014, background): “The first efficient algorithm for finding a wellconditioned basis is due to Clarkson [25], who achieved a running time of O(nd5 log n)+poly(d).”
Low rank approximation with entrywise l1-norm error (2017, methodology): “, [29] and references therein) of the concatenated matrix [U ∗,A] give a distribution for which the optimalV for the latter problem is a (1+ε )-approximation to the former problem; see also earlier work on `1-leverage scores [21, 31] which have poly(d ) rows and the same (1 + ε )-approximation guara”
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.”