# Linear Recursive Feature Machines provably recover low-rank matrices

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 56 references that are in the map.
- First posted on arXiv 9 Jan 2024.

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

- [Intrinsic Dimensionality Explains the Effectiveness of Language Model Fine-Tuning](https://mlsanity.com/paper/2012.13255/) (2020)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Implicit Regularization in Deep Matrix Factorization](https://mlsanity.com/paper/1905.13655/) (2019)
- [Implicit Regularization in Matrix Factorization](https://mlsanity.com/paper/1705.09280/) (2017)
- [Kernel and Rich Regimes in Overparametrized Models](https://mlsanity.com/paper/2002.09277/) (2020)
- [On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization](https://mlsanity.com/paper/1802.06509/) (2018)
- [Implicit Bias of Gradient Descent on Linear Convolutional Networks](https://mlsanity.com/paper/1806.00468/) (2018)
- [A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks](https://mlsanity.com/paper/1810.02281/) (2018)
- [A Rewriting System for Convex Optimization Problems](https://mlsanity.com/paper/1709.04494/) (2017)
- [Neural Networks can Learn Representations with Gradient Descent](https://mlsanity.com/paper/2206.15144/) (2022)
- [The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks](https://mlsanity.com/paper/2202.08658/) (2022)
- [Implicit Regularization in Deep Learning May Not Be Explainable by Norms](https://mlsanity.com/paper/2005.06398/) (2020)
- [Neural Networks Efficiently Learn Low-Dimensional Representations with SGD](https://mlsanity.com/paper/2209.14863/) (2022)
- [A Theoretical Analysis on Feature Learning in Neural Networks: Emergence from Inputs and Advantage over Fixed Features](https://mlsanity.com/paper/2206.01717/) (2022)
- [Implicit Bias of Large Depth Networks: a Notion of Rank for Nonlinear Functions](https://mlsanity.com/paper/2209.15055/) (2022)
- [Flat minima generalize for low-rank matrix recovery](https://mlsanity.com/paper/2203.03756/) (2022)
- [Bottleneck Structure in Learned Features: Low-Dimension vs Regularity Tradeoff](https://mlsanity.com/paper/2305.19008/) (2023)
- [Mechanism of feature learning in convolutional neural networks](https://mlsanity.com/paper/2309.00570/) (2023)
- [The Flip Side of the Reweighted Coin: Duality of Adaptive Dropout and Regularization](https://mlsanity.com/paper/2106.07769/) (2021)

## Built on by (most cited first, 16 of 16)

- [Emergence in non-neural models: grokking modular arithmetic via average gradient outer product](https://mlsanity.com/paper/2407.20199/) (2024)
- [Average gradient outer product as a mechanism for deep neural collapse](https://mlsanity.com/paper/2402.13728/) (2024)
- [xRFM: Accurate, scalable, and interpretable feature learning models for tabular data](https://mlsanity.com/paper/2508.10053/) (2025)
- [Residual Connections Harm Generative Representation Learning](https://mlsanity.com/paper/2404.10947/) (2024)
- [Feature learning as alignment: a structural property of gradient descent in non-linear neural networks](https://mlsanity.com/paper/2402.05271/) (2024)
- [Convergent Evolution: How Different Language Models Learn Similar Number Representations](https://mlsanity.com/paper/2604.20817/) (2026)
- [The Weight Gram Matrix Captures Sequential Feature Linearization in Deep Networks](https://mlsanity.com/paper/2605.06258/) (2026)
- [Learning Multi-Index Models with Hyper-Kernel Ridge Regression](https://mlsanity.com/paper/2510.02532/) (2025)
- [Precise asymptotics of reweighted least-squares algorithms for linear diagonal networks](https://mlsanity.com/paper/2406.02769/) (2024)
- [The Features at Convergence Theorem: a first-principles alternative to the Neural Feature Ansatz for how networks learn representations](https://mlsanity.com/paper/2507.05644/) (2025)
- [Tucker Diffusion Model for High-dimensional Tensor Generation](https://mlsanity.com/paper/2604.00481/) (2026)
- [Q3R: Quadratic Reweighted Rank Regularizer for Effective Low-Rank Training](https://mlsanity.com/paper/2511.04485/) (2025)
- [Local EGOP for Continuous Index Learning](https://mlsanity.com/paper/2601.07061/) (2026)
- [Breaking Data Symmetry is Needed For Generalization in Feature Learning Kernels](https://mlsanity.com/paper/2604.00316/) (2026)
- [DANCE: Doubly Adaptive Neighborhood Conformal Estimation](https://mlsanity.com/paper/2602.20652/) (2026)
- [K-Inverse-RFM: A Modified RFM that Bridges the Gap to Neural Networks for Data-Corrupted Mathematical Tasks](https://mlsanity.com/paper/2607.00329/) (2026)

## Abstract (arXiv)

A fundamental problem in machine learning is to understand how neural networks make accurate predictions, while seemingly bypassing the curse of dimensionality. A possible explanation is that common training algorithms for neural networks implicitly perform dimensionality reduction - a process called feature learning. Recent work posited that the effects of feature learning can be elicited from a classical statistical estimator called the average gradient outer product (AGOP). The authors proposed Recursive Feature Machines (RFMs) as an algorithm that explicitly performs feature learning by alternating between (1) reweighting the feature vectors by the AGOP and (2) learning the prediction function in the transformed space. In this work, we develop the first theoretical guarantees for how RFM performs dimensionality reduction by focusing on the class of overparametrized problems arising in sparse linear regression and low-rank matrix recovery. Specifically, we show that RFM restricted to linear models (lin-RFM) generalizes the well-studied Iteratively Reweighted Least Squares (IRLS) algorithm. Our results shed light on the connection between feature learning in neural networks and classical sparse recovery algorithms. In addition, we provide an implementation of lin-RFM that scales to matrices with millions of missing entries. Our implementation is faster than the standard IRLS algorithm as it is SVD-free. It also outperforms deep linear networks for sparse linear regression and low-rank matrix completion.