# Learning Sparsity and Randomness for Data-driven Low Rank Approximation

arXiv: https://arxiv.org/abs/2212.08186 · HTML: https://mlsanity.com/paper/2212.08186/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 19 references that are in the map.
- First posted on arXiv 15 Dec 2022.

## Builds on (most cited first, 9 of 9)

- [A PAC Approach to Application-Specific Algorithm Selection](https://mlsanity.com/paper/1511.07147/) (2015)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [Learning-Based Low-Rank Approximations](https://mlsanity.com/paper/1910.13984/) (2019)
- [Generalization Bounds for Data-Driven Numerical Linear Algebra](https://mlsanity.com/paper/2206.07886/) (2022)
- [Learning the Positions in CountSketch](https://mlsanity.com/paper/2007.09890/) (2020)
- [Hyperspectral Image Dataset for Benchmarking on Salient Object Detection](https://mlsanity.com/paper/1806.11314/) (2018)
- [Sparse Linear Networks with a Fixed Butterfly Structure: Theory and Practice](https://mlsanity.com/paper/2007.08864/) (2020)
- [Improved Generalization Bound and Learning of Sparsity Patterns for Data-Driven Low-Rank Approximation](https://mlsanity.com/paper/2209.08281/) (2022)
- [Tensor-Based Sketching Method for the Low-Rank Approximation of Data Streams](https://mlsanity.com/paper/2209.14637/) (2022)

## Abstract (arXiv)

Learning-based low rank approximation algorithms can significantly improve the performance of randomized low rank approximation with sketch matrix. With the learned value and fixed non-zero positions for sketch matrices from learning-based algorithms, these matrices can reduce the test error of low rank approximation significantly. However, there is still no good method to learn non-zero positions as well as overcome the out-of-distribution performance loss. In this work, we introduce two new methods Learning Sparsity and Learning Randomness which try to learn a better sparsity patterns and add randomness to the value of sketch matrix. These two methods can be applied with any learning-based algorithms which use sketch matrix directly. Our experiments show that these two methods can improve the performance of previous learning-based algorithm for both test error and out-of-distribution test error without adding too much complexity.