5th Year Master of Science in Computer Science Thesis Presentation

— 4:00pm

Location:
In Person and Virtual - ET - Traffic21 Classroom, Gates Hillman 6501 and Zoom

Speaker:
YUCHENG DAI , Master's Student, Computer Science Department, Carnegie Mellon University
https://www.linkedin.com/in/yuchengdai

On Algorithms for Weighted Low Rank Approximation

In this thesis we focus on the problem of Weighted Low Rank Approximation, which is a fundamental problem in theoretical computer science, machine learning and optimization. We introduce an approximation algorithm running in Ov(nnz(A) + n · poly( k/wε2 ) ) time based on row sampling of the original matrix, where all weights in the weight matrix are within a ratio of w. Our algorithm is relative error, improving upon prior additive error algorithms that were also not row sampling algorithms and had slower running time. We also show nearly matching lower bounds on the number of rows any algorithm must sample.

Thesis Committee:

David P. Woodruff (Chair)
Richard Peng

Additional Information

In Person and Zoom Participation. See announcement.

Add event to Google
Add event to iCal