Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time
Preprint
Abstract
In the numerical linear algebra community, it was suggested that to obtain nearly optimal bounds for various problems such as rank computation, finding a maximal linearly independent subset of columns (a basis), regression, or low-rank approximation, a natural way would be to resolve the main open question of Nelson and Nguyen (FOCS, 2013). This question is regarding the logarithmic factors in the sketching dimension of existing oblivious subspace embeddings that achieve constant-factor approximation. We show how to bypass this question using a refined sketching technique, and obtain optimal or nearly optimal bounds for these problems. A key technique we use is an explicit mapping of Indyk based on uncertainty principles and extractors, which after first applying known oblivious subspace embeddings, allows us to quickly spread out the mass of the vector so that sampling is now effective. We thereby avoid a logarithmic factor in the sketching dimension that is standard in bounds proven using the matrix Chernoff inequality. For the fundamental problems of rank computation and finding a basis, our algorithms improve Cheung, Kwok, and Lau (JACM, 2013), and are optimal to within a constant factor and a poly(log log(n))-factor, respectively. Further, for constant-factor regression and low-rank approximation we give the first optimal algorithms, for the current matrix multiplication exponent.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Toward a unified theory of sparse dimensionality reduction in Euclidean spaceGeometric and Functional Analysis, 2015
- Improved Matrix Algorithms via the Subsampled Randomized Hadamard TransformSIAM Journal on Matrix Analysis and Applications, 2013
- A fast randomized algorithm for overdetermined linear least-squares regressionProceedings of the National Academy of Sciences of the United States of America, 2008
- Fast linear algebra is stableNumerische Mathematik, 2007
- Improved Approximation Algorithms for Large Matrices via Random Projections2006
- Matrix approximation and projective clustering via volume sampling2006
- Adaptive estimation of a quadratic functional by model selectionThe Annals of Statistics, 2000
- Random Vectors in the Isotropic PositionJournal of Functional Analysis, 1999