[cs-talks] Cameron Musco's visit, Oct. 4th
Crovella, Mark E
crovella at bu.edu
Tue Oct 3 12:59:41 EDT 2017
From: Charalampos Tsourakakis<ctsourak at bu.edu<mailto:ctsourak at bu.edu>>
Date: Tue, Oct 3, 2017 at 10:16 AM
Subject: Cameron Musco's visit, Oct. 4th
To: cs-talks at cs.bu.edu<mailto:cs-talks at cs.bu.edu>, nosman at bu.edu<mailto:nosman at bu.edu>
Cameron Musco<http://www.cameronmusco.com/> from MIT will be visiting us tomorrow 10/4, and will give a talk at the Hariri Seminar room from 2 to 3. If you would like to meet with him, please sign up here<https://docs.google.com/spreadsheets/d/1foCoevcVx4Z5k1XD66l7t2qVtC5H4ZzGWSllG54Qvz0/edit?usp=sharing>.
Title: Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices
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...
More information about the cs-talks