Computer Science Thesis Proposal April 10, 2023 1:00pm — 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/ 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 Add event to Google Add event to iCal
