Computer Science/Discrete Mathematics Seminar II

An “oblivious subspace embedding” (OSE) is a distribution over matrices S such that for any low-dimensional subspace $V$, with high probability over the choice of $S$, $\|Sx\|_2$ approximately equals $\|x\|_2$ (up to $1 + \epsilon$ multiplicative error) for all $x$ in $V$ simultaneously. Sarlos in 2006 pioneered the use of OSE’s for speeding up algorithms for several numerical linear algebra problems. Problems that benefit from OSE’s include: approximate least squares regression, low-rank approximation, approximating leverage scores, and constructing good preconditioners.

We give a class of OSE distributions we call “oblivious sparse norm-approximating projections” (OS-NAP) that yield matrices S with few rows that are also extremely sparse, yielding improvements over recent work in this area by Clarkson and Woodruff. In particular, we show $S$ can have $O(d^2)$ rows and $1$ non-zero entry per column, or even $O(d^{1+ \gamma} )$ rows and $O_\gamma (1)$ non-zero entries per column for any desired constant $\gamma > 0$. When applying the latter bound for example to the approximate least squares regression problem of finding $x$ to minimize $\| Ax-b \|_2$ up to a constant factor, where $A$ is $n \times d$ for $n \gg d$, we obtain an algorithm with running time $O(nnz(A) +d \omega + \gamma )$. Here $nnz(A)$ is the number of non-zero entries in $A$, and $\omega$ is the exponent of square matrix multiplication.

Our main technical result is essentially a Bai-Yin type theorem in random matrix theory and is likely to be of independent interest: i.e. we show that for any $U$ in $R^{n \times d}$ with orthonormal columns and random sparse $S$ with appropriately chosen entries and sufficiently many rows, all singular values of $SU$ lie in the interval $[1- \epsilon ,1 + \epsilon ]$ with good probability.

Joint work with Huy Lê Nguyễn (Princeton).