Spring 2010 Seminar Series

DATE: February 18th
LOCATION: E51-376
TIME: 4:15pm
Reception immediately following in the ORC Conference Room, E40-106

SPEAKER:
Alexandre d'Aspremont

TITLE
Subsampling, Spectral Methods & Semidefinite Programming

ABSTRACT
We show how subsampling techniques can be used to approximate eigenvectors of large matrices and discuss applications in dimensionality reduction and ranking. We then use these results to reduce the per iteration complexity of first order algorithms for semidefinite programming. The subsampling ratio explicitly controls the algorithm's granularity, i.e. the tradeoff between cost per iteration and total number of iterations. In this setting, the method's total computational cost is also directly proportional to the complexity (i.e. rank) of the solution.