View abstract

Session III.1 - Numerical Linear Algebra

Monday, June 19, 14:00 ~ 14:30

Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Singular Value Approximation

Cameron Musco

University of Massachusetts Amherst, USA   -   This email address is being protected from spambots. You need JavaScript enabled to view it.

Given a matrix $A \in \mathbb{R}^{n \times n}$ which is normalized so that its entries are bounded in magnitude by $1$, it is well-known that randomly sparsifying $A$ to be supported on a subset of just $\tilde{O}(n/\epsilon^2)$ of its entries, yields an approximation $A_S$ with $\| A - A_S\|_2 \le \epsilon n$ with high probability, where $\|\cdot\|_2$ is the spectral norm. We show that for positive semidefinite (PSD) matrices, no randomness is needed at all in this statement. Namely, there exists a fixed subset of $\tilde{O}(n/\epsilon^2)$ entries that acts as a $universal\, sparsifier$: $\| A - A_S\|_2 \le \epsilon n$ holds simultaneously for every bounded entry PSD matrix. One can view this result as a significant extension of a spectral graph expander nearly matching the Ramanujan bound.

We leverage the existence of such universal sparsifiers to give the first $deterministic\, algorithms$ for several central linear algebraic problems, including singular value and singular vector approximation and positive semidefiniteness testing, that run in faster than matrix multiplication time on worst-case input matrices. This partially addresses a significant gap between randomized and deterministic algorithms for fast linear algebraic computation. We also extend our results to non-PSD matrices and to deterministic algorithms that approximate $A$ with a non-sparse matrix. We prove lower bounds showing that many of our results are nearly optimal.

Joint work with Rajarshi Bhattacharjee (University of Massachusetts Amherst), Gregory Dexter (Purdue University), Archan Ray (University of Massachusetts Amherst) and David P. Woodruff (Carnegie Mellon University).

View abstract PDF