Fetching the paper…
Reading the bibliography…
We provide fast algorithms for overconstrained $\ell_p$ regression and related problems: for an $n\times d$ input matrix $A$ and vector $b\in\mathbb{R}^n$, in $O(nd\log n)$ time we reduce the problem $\min_{x\in\mathbb{R}^d} \|Ax-b\|_p$ to the same problem with input matrix $\tilde A$ of dimension $s \times d$ and corresponding $\tilde b$ of dimension $s\times 1$.
Extremum problems with inequalities as subsidiary conditions
F. John · 1948
Earlier work this paper cites.
On minimum volume ellipsoids containing part of a given ellipsoid
M. J. Todd · 1982
Earlier work this paper cites.
Algorithmic Theory of Numbers, Graphs, and Convexity
L. Lovász · 1986
Earlier work this paper cites.
Uncertainty principles and signal recovery
D. Donoho and P. Stark · 1989
Earlier work this paper cites.
A stable and efficient algorithm for the rank-one modification of the symmetric eigenproblem
M. Gu and S. C. Eisenstat · 1994
Earlier work this paper cites.
Uncertainty principles and ideal atomic decomposition
D. Donoho and X. Huo · 2001
Earlier work this paper cites.
Sparse representations in unions of bases
R. Gribonval and M. Nielsen · 2003
Earlier work this paper cites.
A bound on the deviation probability for sums of non-negative random variables
A. Maurer · 2003
Earlier work this paper cites.
Topics in Sparse Approximation
J. A. Tropp · 2004
Earlier work this paper cites.
Subgradient and sampling algorithms for ℓ 1 \ell_{1} regression
K. Clarkson · 2005
Earlier work this paper cites.
A fast random sampling algorithm for sparsifying matrices
S. Arora, E. Hazan, and S. Kale · 2006
Cited alongside, same era.
Stable distributions, pseudorandom generators, embeddings, and data stream computation
P. Indyk · 2006
Cited alongside, same era.
Uncertainty principles, extractors, and explicit embeddings of ℓ 2 \ell_{2} into ℓ 1 \ell_{1}
P. Indyk · 2007
Cited alongside, same era.
Fast dimension reduction using Rademacher series on dual BCH codes
N. Ailon and E. Liberty · 2008
Cited alongside, same era.
Relative-error CUR matrix decompositions
P. Drineas, M. W. Mahoney, and S. Muthukrishnan · 2008
Cited alongside, same era.
80 million tiny images: A large data set for nonparametric object and scene recognition
A. Torralba, R. Fergus, and W. T. Freeman · 2008
Cited alongside, same era.
Blendenpik: Supercharging LAPACK’s least-squares solver
H. Avron, P. Maymounkov, and S. Toledo · 2010
Later among the works it cites.
Faster least squares approximation
P. Drineas, M. W. Mahoney, S. Muthukrishnan, and T. Sarlós · 2010
Later among the works it cites.
Ancestry informative markers for fine-scale individual assignment to worldwide populations
P. Paschou, J. Lewis, A. Javed, and P. Drineas · 2010
Later among the works it cites.
Randomized algorithms for matrices and data
M. W. Mahoney · 2011
Later among the works it cites.
Subspace embeddings for the ℓ 1 \ell_{1} -norm with applications
C. Sohler and D. P. Woodruff · 2011
Later among the works it cites.
Improved analysis of the subsampled randomized Hadamard transform
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
N. Ailon and B. Chazelle · 2009
Cited alongside, same era.
Sampling algorithms and coresets for ℓ p \ell_{p} regression
A. Dasgupta, P. Drineas, B. Harb, R. Kumar, and M. W. Mahoney · 2009
Cited alongside, same era.
CUR matrix decompositions for improved data analysis
M. W. Mahoney and P. Drineas · 2009
Cited alongside, same era.
J. A. Tropp · 2011
Later among the works it cites.
Fast approximation of matrix coherence and statistical leverage
P. Drineas, M. Magdon-Ismail, M. W. Mahoney, and D. P. Woodruff · 2012
Closest in time.
Sparser Johnson-Lindenstrauss transforms
D. M. Kane and J. Nelson · 2012
Closest in time.
The L1-norm best-fit hyperplane problem
J. P. Brooks and J. H. Dulá · 2013
Closest in time.