Computer Science Thesis Proposal
— 2:30pm
Location:
In Person
-
Reddy Conference Room, Gates Hillman 4405
Speaker:
TAISUKE YASUDA
,
Ph.D. Student, Computer Science Department, Carnegie Mellon University
https://taisukeyasuda.github.io/
Advances in Algorithms for Matrix Approximation via Sampling and Sketching
In the past two decades, the field of randomized numerical linear algebra has been extremely successful in developing algorithmic techniques for the problem of matrix approximation, in which large matrices are approximated by much smaller ones. This problem is fundamental to many areas of mathematics and computer science, and algorithmically, matrix approximation has found applications ranging from machine learning to graph algorithms to computational geometry and beyond.
In this thesis proposal, we further develop the theory of matrix approximation algorithms from the perspective of randomized numerical linear algebra, drawing particularly heavily from techniques based on sampling and sketching. We focus on obtaining nearly optimal trade-offs for fundamental problems in this literature, and succeed in resolving such bounds for problems including oblivious ℓp subspace embeddings, ℓp Lewis weight sampling, streaming Löwner--John ellipsoid approximation, active ℓp linear regression, and entrywise low rank approximation.
Thesis Committee
David Woodruff (Chair)
Anupam Gupta
Richard Peng
Cameron Musco (University of Massachusetts Amherst)