Parameterized Complexity of Matrix Factorization Problems
David P. Woodruff
IBM Almaden Research Center
Talk
David P. Woodruff is a prominent researcher at IBM Almaden. He graduated his Ph.D. at MIT in 2007 under the supervision of Piotr Indyk. He is the recipient of numerous awards, including the “Presburger Award from EATCS”, the “IBM Pat Goldberg Award”, and the “IBM Master Inventor Award” (with more than 20 U.S. Patents). Also, he is recognized for “Outstanding IBM Research Division Accomplishments” and he is a member of the “IBM Academy of Technology”. He has a strong record of publications in prestigious conferences such as STOC, FOCS, SODA, ICALP, PODS and NIPS. Most recently, he wrote an excellent book “Sketching as a Tool for Numerical Linear Algebra” summarizing a rapidly emerging subfield of TCS which has many applications in machine learning.
This will be an overview talk on several NP-hard variants of low rank approximation, including non-negative low rank approximation, weighted low rank approximation, and ell_1-low rank approximation. These problems have important applications in machine learning and numerical linear algebra. I will discuss various ways of coping with hardness for these problems, such as via approximation, parameterized complexity, and through bicriteria solutions.
Parts of this talk are based on my work with Ilya Razenshteyn, and Zhao Song (STOC '16) and with Zhao Song and Peilin Zhong (STOC '17).