Fetching the paper…
Reading the bibliography…
The aim of this paper is two-fold: firstly, to present subspace embedding properties for $s$-hashing sketching matrices, with $s\geq 1$, that are optimal in the projection dimension $m$ of the sketch, namely, $m=\mathcal{O}(d)$, where $d$ is the dimension of the subspace.
LSQR: an algorithm for sparse linear equations and sparse least squares
C. C. Paige and M. A. Saunders · 1982
Earlier work this paper cites.
Extensions of Lipschitz mappings into a Hilbert space
W. B. Johnson and J. Lindenstrauss · 1984
Earlier work this paper cites.
Numerical methods for least squares problems
A. Björck · 1996
Earlier work this paper cites.
Matrix computations
G. H. Golub and C. F. Van Loan · 1996
Earlier work this paper cites.
Benchmarking optimization software with performance profiles
E. D. Dolan and J. J. Moré · 2002
Earlier work this paper cites.
Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
N. Ailon and B. Chazelle · 2006
Earlier work this paper cites.
Sampling algorithms for l2 regression and applications
P. Drineas, M. W. Mahoney, and S. Muthukrishnan · 2006
Earlier work this paper cites.
Numerical optimization
J. Nocedal and S. J. Wright · 2006
Earlier work this paper cites.
Improved approximation algorithms for large matrices via random projections
T. Sarlos · 2006
Earlier work this paper cites.
A fast randomized algorithm for overdetermined linear least-squares regression
V. Rokhlin and M. Tygert · 2008
Earlier work this paper cites.
Using perturbed Q R QR factorizations to solve linear least-squares problems
H. Avron, E. Ng, and S. Toledo · 2009
Earlier work this paper cites.
Blendenpik: supercharging Lapack’s least-squares solver
H. Avron, P. Maymounkov, and S. Toledo · 2010
Earlier work this paper cites.
Algorithm 915, SuiteSparseQR: multifrontal multithreaded rank-revealing sparse QR factorization
T. A. Davis · 2011
Earlier work this paper cites.
The University of Florida sparse matrix collection
T. A. Davis and Y. Hu · 2011
Earlier work this paper cites.
Randomized algorithms for matrices and data
M. W. Mahoney · 2011
Earlier work this paper cites.
Improved analysis of the subsampled randomized Hadamard transform
J. A. Tropp · 2011
Earlier work this paper cites.
An almost optimal unrestricted fast Johnson-Lindenstrauss transform
N. Ailon and E. Liberty · 2013
Cited alongside, same era.
Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
X. Meng and M. W. Mahoney · 2013
Cited alongside, same era.
OSNAP: faster numerical linear algebra algorithms via sparser subspace embeddings
J. Nelson and H. L. Nguyen · 2013
Cited alongside, same era.
Sparsity lower bounds for dimensionality reducing maps
J. Nelson and H. L. Nguyen · 2013
Cited alongside, same era.
LSRN: a parallel iterative solver for strongly over- or underdetermined systems
X. Meng, M. A. Saunders, and M. W. Mahoney · 2014
Cited alongside, same era.
Lower bounds for oblivious subspace embeddings
J. Nelson and H. L. Nguyen · 2014
The state-of-the-art of preconditioners for sparse linear least-square problems
N. Gould and J. Scott · 2017
Later among the works it cites.
Householder QR factorization with randomization for column pivoting (HQRRP)
P.-G. Martinsson, G. Quintana Ortí, N. Heavner, and R. van de Geijn · 2017
Later among the works it cites.
An empirical evaluation of sketching for numerical linear algebra
Y. Dahiya, D. Konomis, and D. P. Woodruff · 2018
Later among the works it cites.
Fully understanding the hashing trick
C. Freksen, L. Kamma, and K. G. Larsen · 2018
Later among the works it cites.
Error estimation for randomized least-squares algorithms via the bootstrap
M. Lopes, S. Wang, and M. Mahoney · 2018
Later among the works it cites.
A randomized least squares solver for terabyte-sized dense overdetermined systems
C. Iyer, H. Avron, G. Kollias, Y. Ineichen, C. Carothers, and P. Drineas · 2019
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Sketching as a tool for numerical linear algebra
D. P. Woodruff · 2014
Cited alongside, same era.
Toward a unified theory of sparse dimensionality reduction in Euclidean space
J. Bourgain, S. Dirksen, and J. Nelson · 2015
Cited alongside, same era.
The state-of-the-art of preconditioners for sparse linear least-squares problems: the complete results
N. Gould and J. Scott · 2015
Cited alongside, same era.
Randomized iterative methods for linear systems
R. M. Gower and P. Richtárik · 2015
Cited alongside, same era.
P.-G. Martinsson · 2015
Cited alongside, same era.
Nearly tight oblivious subspace embeddings by trace inequalities
M. B. Cohen · 2016
Cited alongside, same era.
Later among the works it cites.
Understanding sparse JL for feature hashing
M. Jagadeesan · 2019
Later among the works it cites.
Faster Least Squares Optimization
J. Lacotte and M. Pilanci · 2019
Later among the works it cites.
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip
N. Loizou · 2019
Later among the works it cites.
Stable sparse subspace embedding for dimensionality reduction
L. Chen, S. Zhou, and J. Ma · 2020
Later among the works it cites.
Least-squares regressions via randomized Hessians
N. Kahale · 2020
Later among the works it cites.
Optimal Randomized First-Order Methods for Least-Squares Problems
J. Lacotte and M. Pilanci · 2020
Later among the works it cites.
Extending and Improving Learned CountSketch
S. Liu, T. Liu, A. Vakilian, Y. Wan, and D. P. Woodruff · 2020
Later among the works it cites.
Convergence analysis of inexact randomized iterative methods
N. Loizou and P. Richtárik · 2020
Later among the works it cites.
Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares
M. A. Iwen, D. Needell, E. Rebrova, and A. Zare · 2021
Closest in time.