Linear Recursive Feature Machines provably recover low-rank matrices.

Area of Science:

• Machine Learning
• Statistical Inference
• Computational Theory

Background:

• Neural networks excel at predictions, seemingly defying the curse of dimensionality.
• Feature learning, a form of dimensionality reduction, is a hypothesized reason for this success.
• The average gradient outer product (AGOP) is a statistical estimator linked to feature learning.

Purpose of the Study:

• To provide theoretical guarantees for Recursive Feature Machines (RFMs) in dimensionality reduction.
• To connect feature learning in neural networks with classical sparse recovery algorithms.
• To develop a scalable and efficient implementation of RFMs for practical applications.

Main Methods:

• Analyzing Recursive Feature Machines (RFMs) for overparameterized problems in sparse linear regression and low-rank matrix recovery.
• Demonstrating that linear RFMs (lin-RFMs) are equivalent to a variant of Iteratively Reweighted Least Squares (IRLS).
• Implementing lin-RFM to handle large-scale matrices with numerous missing entries.

Main Results:

• Theoretical guarantees are established for RFM's dimensionality reduction capabilities.
• Lin-RFMs are shown to be a variant of the IRLS algorithm.
• The developed lin-RFM implementation is faster than standard IRLS and outperforms deep linear networks.

Conclusions:

• RFMs provide explicit feature learning, offering insights into neural network behavior.
• The study bridges the gap between neural network feature learning and classical sparse recovery.
• The efficient lin-RFM implementation enables practical application in large-scale sparse recovery and matrix completion.