Algorithms for l_p Low-Rank Approximation and non-negative l_1 Column Subset Selection
Event details
| Date | 23.10.2017 |
| Hour | 11:15 › 12:15 |
| Speaker | Silvio Lattanzi, Google Zurich |
| Location | |
| Category | Conferences - Seminars |
Abstract:
The problem of low-rank approximation and column subset selection of a matrix are usually studied for the Frobenius norm. Nevertheless in practice it is often interesting to study these problems also for l_1 or l_∞. Here we introduce new algorithms for l_p Low-Rank Approximation and non-negative l_1 Column Subset Selection.
We start by considering the problem of approximating a given matrix by a low-rank matrix so as to minimize the entry-wise l_p-approximation error, for any p ≥ 1; the case p = 2 is the classical SVD problem. We obtain the first provably good approximation algorithms for this version of low-rank approximation that work for every value of p ≥ 1, including p = ∞. Our algorithms are simple, easy to implement, work well in practice, and illustrate interesting tradeoffs between the approximation quality, the running time, and the rank of the approximating matrix.
Then we consider the problems of sparse regression and column subset selection under l_1 error. For both problems, we show that in the non-negative setting it is possible to obtain tight and efficient approximations, without any additional structural assumptions. We then use this technique to obtain an efficient algorithm for column subset selection under l_1 error for non-negative matrices.
Joint work with Flavio Chierichetti, Sreenivas Gollapudi, Ravi Kumar, Rina Panigrahy, David P. Woodruff and Aditya Bhaskara.
Bio:
Silvio Lattanzi received his bachelor (2005) and master (2007) degree both with highest honors from the Computer Science department of Sapienza University of Rome. He received his PhD(2011) in Computer Science from the Computer Science department of Sapienza University of Rome, his advisor was Alessandro Panconesi. Silvio was a research scientist at Google New York from January 2011 to March 2017. Silvio is a research scientist at Google Zurich since April 2017.
The problem of low-rank approximation and column subset selection of a matrix are usually studied for the Frobenius norm. Nevertheless in practice it is often interesting to study these problems also for l_1 or l_∞. Here we introduce new algorithms for l_p Low-Rank Approximation and non-negative l_1 Column Subset Selection.
We start by considering the problem of approximating a given matrix by a low-rank matrix so as to minimize the entry-wise l_p-approximation error, for any p ≥ 1; the case p = 2 is the classical SVD problem. We obtain the first provably good approximation algorithms for this version of low-rank approximation that work for every value of p ≥ 1, including p = ∞. Our algorithms are simple, easy to implement, work well in practice, and illustrate interesting tradeoffs between the approximation quality, the running time, and the rank of the approximating matrix.
Then we consider the problems of sparse regression and column subset selection under l_1 error. For both problems, we show that in the non-negative setting it is possible to obtain tight and efficient approximations, without any additional structural assumptions. We then use this technique to obtain an efficient algorithm for column subset selection under l_1 error for non-negative matrices.
Joint work with Flavio Chierichetti, Sreenivas Gollapudi, Ravi Kumar, Rina Panigrahy, David P. Woodruff and Aditya Bhaskara.
Bio:
Silvio Lattanzi received his bachelor (2005) and master (2007) degree both with highest honors from the Computer Science department of Sapienza University of Rome. He received his PhD(2011) in Computer Science from the Computer Science department of Sapienza University of Rome, his advisor was Alessandro Panconesi. Silvio was a research scientist at Google New York from January 2011 to March 2017. Silvio is a research scientist at Google Zurich since April 2017.
Practical information
- Expert
- Free
Organizer
- Prof. Michael Kapralov
Contact
- Pauline Raffestin