Timezone: »

 
Poster
Few-Shot Data-Driven Algorithms for Low Rank Approximation
Piotr Indyk · Tal Wagner · David Woodruff

Tue Dec 07 04:30 PM -- 06:00 PM (PST) @
in Poster Session 2 »

Recently, data-driven and learning-based algorithms for low rank matrix approximation were shown to outperform classical data-oblivious algorithms by wide margins in terms of accuracy. Those algorithms are based on the optimization of sparse sketching matrices, which lead to large savings in time and memory during testing. However, they require long training times on a large amount of existing data, and rely on access to specialized hardware and software. In this work, we develop new data-driven low rank approximation algorithms with better computational efficiency in the training phase, alleviating these drawbacks. Furthermore, our methods are interpretable: while previous algorithms choose the sketching matrix either at random or by black-box learning, we show that it can be set (or initialized) to clearly interpretable values extracted from the dataset. Our experiments show that our algorithms, either by themselves or in combination with previous methods, achieve significant empirical advantage over previous work, improving training times by up to an order of magnitude toward achieving the same target accuracy.

Keywords: Optimization

Author Information

Piotr Indyk (MIT)
Tal Wagner (Microsoft Research Redmond)
David Woodruff (Carnegie Mellon University)

More from the Same Authors