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+eps 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” (OSNAP) 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 x d for n » 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 x 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-eps, 1+eps] with good probability.
Joint work with Huy Lê Nguyễn (Princeton).
Speaker Biography
Jelani Nelson is a postdoctoral researcher in theoretical computer science at the Institute for Advanced Study, and will begin as an Assistant Professor of Computer Science at Harvard University in Fall 2013. Jelani’s research interests include algorithms and complexity theory, with specific focuses on algorithms for processing massive datasets and pseudorandomness.