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.