Featured event

Lines of blue blurred letters falling, credit iStock

SILO Seminar: Yash Deshpande

Event Details

When: May 15, 2015, 12:30 PM

Location: 3rd Floor Orchard View Room , Discovery Building

Contact: 608-316-4401, hstampfli@wisc.edu

Yash Deshpande

Yash Deshpande

Covariance thresholding, kernel random matrices and sparse PCA

In Sparse Principal Component Analysis (PCA) we wish to reconstruct a low-rank matrix from noisy observations, under sparsity assumptions on the factors recovered. Johnstone and Lu (2004) formalized these assumptions in the ‘spiked covariance model’, wherein we observe $n$ i.i.d. samples from a $p$ dimensional Gaussian distribution $N(0, I + b v v^t)$. The population principal component $v$ is called the ‘spike’ and is assumed to be sparse in a certain basis. Johnstone and Lu also proposed a simple scheme that consistently estimates the support of $v$ provided its size is smaller than $\sqrt{n/\log p}$. Despite a considerable amount of work over the past ten years, there was no computationally efficient scheme that improved over this guarantee. We analyze Covariance Thresholding, a simple algorithm proposed by Krautgamer, Nadler and Vilenchik (2013) and prove that it recovers supports up to size $\sqrt{n}$. Under a certain complexity conjecture, it is impossible to significantly improve this guarantee.  The main technical component in our analysis involves a new bound on the spectral norm of kernel random matrices.
This is joint work with Andrea Montanari.

Speaker:  Yash Deshpande, Ph.D. Student, Stanford University

SILO is a lecture series with speakers from the UW faculty, graduate students or invited researchers that discuss mathematical related topics. The seminars are organized by WID’s Optimization research group.

SILO’s purpose is to provide a forum that helps connect and recruit mathematically-minded graduate students. SILO is a lunch-and-listen format, where speakers present interesting math topics while the audience eats lunch.