Monday, April 10, 2023, 1pm

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)

Additional Information

Event Type: Thesis Proposals
Room Number: In Person
Building: Reddy Conference Room, Gates Hillman 4405
Speaker's Name: TAISUKE YASUDA
Speaker Website: taisukeyasuda.github.io
Speaker's Professional Title: Ph.D. Student, Computer Science Department, Carnegie Mellon University
Talk Title: Advances in Algorithms for Matrix Approximation via Sampling and Sketching
Event Poster Title: Poster
Event Poster URL: www.cs.cmu.edu…
For More Information: jennsbl@cs.cmu.edu | deb@cs.cmu.edu
Affiliations: Computer Science Department (CSD)
Organization(s): SCS