Title: OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings
Speaker: Huy Le Nguyen, Princeton University
Date: Tuesday, February 19, 2013 2:00pm
Location: Hill Center, Room 124, Rutgers University, Busch Campus, Piscataway, NJ
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 Jelani Nelson (IAS).
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math