[cs-talks] Cameron Musco, TOMORROW 10/4 @ 2pm, Hariri Seminar Room

Harrington, Jacob Walter jwharrin at bu.edu
Tue Oct 3 10:41:23 EDT 2017

Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices
Cameron Musco, PhD student, Massachusetts Institute of Technology Theory of Computation Group
Wednesday, October 4th, 2 – 3pm, Hariri Seminar Room, MCS 180

I will discuss recent progress on fast algorithms for approximating positive semidefinite (PSD) matrices, which are of central importance in machine learning, optimization, and computational science in general.

In particular, I will show how new techniques in recursive leverage score sampling yield a surprising algorithmic result: we give a method for computing a near optimal k-rank approximation to any n x n PSD matrix in n * k^2 time. When k is not too large, our algorithm is sublinear -- i.e. it does not need to read all entries of the matrix. It thus bypasses a natural lower bound for general matrices and is the first method that exploits PSD structure to obtain provably faster runtimes.

I will also discuss connections between our work and recent advances on faster nonlinear kernel methods in machine learning. I'll highlight future research directions in this area and computational lower bounds that rule out certain further improvements.

Joint work with David Woodruff. To appear, FOCS'17. Manuscript available at: https://arxiv.org/abs/1704.03371<https://urldefense.proofpoint.com/v2/url?u=https-3A__arxiv.org_abs_1704.03371&d=DwMFaQ&c=WO-RGvefibhHBZq3fL85hQ&r=j1RHBAhJA8mdSrMx2sdK3sCGMxNeIT8PUVQ5psYnByI&m=XUWUgR45slpQIXvWgOW-halj8jtMzV_pl4jnjOVD2Hs&s=XlBPYCm6YwjsEoMhuNK2OnXZArvLe2ouK0xtp-tyQd4&e=>.

Bio: Cameron Musco is a final year Ph.D. student in MIT's Theory of Computation Group, advised by Nancy Lynch. He studies algorithms, focusing on randomized methods for linear algebra with applications in machine learning and data analysis. He is also interested in understanding randomized computation and algorithmic robustness by studying computation in biological systems.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/cs-talks/attachments/20171003/2e241dbb/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Cameron Musco Talk.pdf
Type: application/pdf
Size: 146547 bytes
Desc: Cameron Musco Talk.pdf
URL: <http://cs-mailman.bu.edu/pipermail/cs-talks/attachments/20171003/2e241dbb/attachment.pdf>

More information about the cs-talks mailing list