Near-Optimal Algorithms for Linear Algebra in the Current Matrix
  Multiplication Time
  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.
