# Learning-Based Low-Rank Approximations

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

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Oct 2019.

## Built on by (most cited first, 30 of 41)

- [Learning to Optimize: A Primer and A Benchmark](https://mlsanity.com/paper/2103.12828/) (2021)
- [Instance-Optimal Compressed Sensing via Posterior Sampling](https://mlsanity.com/paper/2106.11438/) (2021)
- [Generalization Bounds for Data-Driven Numerical Linear Algebra](https://mlsanity.com/paper/2206.07886/) (2022)
- [Online Algorithms with Multiple Predictions](https://mlsanity.com/paper/2205.03921/) (2022)
- [A Survey on Approximate Edge AI for Energy Efficient Autonomous Driving Services](https://mlsanity.com/paper/2304.14271/) (2023)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Algorithm Configuration for Structured Pfaffian Settings](https://mlsanity.com/paper/2409.04367/) (2024)
- [Double Coverage with Machine-Learned Advice](https://mlsanity.com/paper/2103.01640/) (2021)
- [Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programming](https://mlsanity.com/paper/2309.00203/) (2023)
- [Improved Frequency Estimation Algorithms with and without Predictions](https://mlsanity.com/paper/2312.07535/) (2023)
- [Learning Based Proximity Matrix Factorization for Node Embedding](https://mlsanity.com/paper/2106.05476/) (2021)
- [Improved Generalization Bound and Learning of Sparsity Patterns for Data-Driven Low-Rank Approximation](https://mlsanity.com/paper/2209.08281/) (2022)
- [Provably data-driven projection method for quadratic programming](https://mlsanity.com/paper/2509.04524/) (2025)
- [Cherry-Picking Gradients: Learning Low-Rank Embeddings of Visual Data via Differentiable Cross-Approximation](https://mlsanity.com/paper/2105.14250/) (2021)
- [Learning-Augmented Search Data Structures](https://mlsanity.com/paper/2402.10457/) (2024)
- [Learning-Based Algorithms for Graph Searching Problems](https://mlsanity.com/paper/2402.17736/) (2024)
- [Learning Low-Rank Feature for Thorax Disease Classification](https://mlsanity.com/paper/2404.18933/) (2024)
- [Diffusion on Graph: Augmentation of Graph Structure for Node Classification](https://mlsanity.com/paper/2503.12563/) (2025)
- [DiffRed: Dimensionality Reduction guided by stable rank](https://mlsanity.com/paper/2403.05882/) (2024)
- [Optimal Algorithms for Augmented Testing of Discrete Distributions](https://mlsanity.com/paper/2412.00974/) (2024)
- [Learning-Augmented Frequent Directions](https://mlsanity.com/paper/2503.00937/) (2025)
- [Changing Base Without Losing Pace: A GPU-Efficient Alternative to MatMul in DNNs](https://mlsanity.com/paper/2503.12211/) (2025)
- [Better Private Distribution Testing by Leveraging Unverified Auxiliary Data](https://mlsanity.com/paper/2503.14709/) (2025)
- [Provably Data-driven Multiple Hyper-parameter Tuning with Structured Loss Function](https://mlsanity.com/paper/2602.02406/) (2026)
- [Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming](https://mlsanity.com/paper/2605.19052/) (2026)
- [Learning-Augmented Sketches for Hessians](https://mlsanity.com/paper/2102.12317/) (2021)
- [Low-rank Tensor Learning with Nonconvex Overlapped Nuclear Norm Regularization](https://mlsanity.com/paper/2205.03059/) (2022)
- [On Approximability of ℓ22 Min-Sum Clustering](https://mlsanity.com/paper/2412.03332/) (2024)
- [Learning-Augmented Streaming Algorithms for Correlation Clustering](https://mlsanity.com/paper/2510.10705/) (2025)
- [Learning Sparsity and Randomness for Data-driven Low Rank Approximation](https://mlsanity.com/paper/2212.08186/) (2022)

## Abstract (arXiv)

We introduce a "learning-based" algorithm for the low-rank decomposition problem: given an n × d matrix A, and a parameter k, compute a rank-k matrix A' that minimizes the approximation loss |A-A'|F. The algorithm uses a training set of input matrices in order to optimize its performance. Specifically, some of the most efficient approximate algorithms for computing low-rank approximations proceed by computing a projection SA, where S is a sparse random m × n "sketching matrix", and then performing the singular value decomposition of SA. We show how to replace the random matrix S with a "learned" matrix of the same sparsity to reduce the error. Our experiments show that, for multiple types of data sets, a learned sketch matrix can substantially reduce the approximation loss compared to a random matrix S, sometimes by one order of magnitude. We also study mixed matrices where only some of the rows are trained and the remaining ones are random, and show that matrices still offer improved performance while retaining worst-case guarantees. Finally, to understand the theoretical aspects of our approach, we study the special case of m=1. In particular, we give an approximation algorithm for minimizing the empirical loss, with approximation factor depending on the stable rank of matrices in the training set. We also show generalization bounds for the sketch matrix learning problem.