# A Validation Approach to Over-parameterized Matrix and Image Recovery

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 56 references that are in the map.
- First posted on arXiv 21 Sep 2022.

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

- [Deep Image Prior](https://mlsanity.com/paper/1711.10925/) (2017)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [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)
- [Implicit Bias of Gradient Descent on Linear Convolutional Networks](https://mlsanity.com/paper/1806.00468/) (2018)
- [Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced](https://mlsanity.com/paper/1806.00900/) (2018)
- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015)
- [Robust Training under Label Noise by Over-parameterization](https://mlsanity.com/paper/2202.14026/) (2022)
- [Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?](https://mlsanity.com/paper/1812.10004/) (2018)
- [Global Optimality of Local Search for Low Rank Matrix Recovery](https://mlsanity.com/paper/1605.07221/) (2016)
- [Implicit Regularization for Optimal Sparse Recovery](https://mlsanity.com/paper/1909.05122/) (2019)
- [Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction](https://mlsanity.com/paper/2106.15013/) (2021)
- [Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees](https://mlsanity.com/paper/1509.03025/) (2015)
- [Early Stopping for Deep Image Prior](https://mlsanity.com/paper/2112.06074/) (2021)
- [Global Optimality in Low-rank Matrix Optimization](https://mlsanity.com/paper/1702.07945/) (2017)
- [Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorization](https://mlsanity.com/paper/2203.02839/) (2022)
- [Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence](https://mlsanity.com/paper/1904.10020/) (2019)
- [On the computational and statistical complexity of over-parameterized matrix sensing](https://mlsanity.com/paper/2102.02756/) (2021)
- [Robust Recovery via Implicit Bias of Discrepant Learning Rates for Double Over-parameterization](https://mlsanity.com/paper/2006.08857/) (2020)
- [Harnessing Structures in Big Data via Guaranteed Low-Rank Matrix Estimation](https://mlsanity.com/paper/1802.08397/) (2018)
- [Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery](https://mlsanity.com/paper/2109.11154/) (2021)
- [Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterization](https://mlsanity.com/paper/2202.08788/) (2022)
- [Self-Validation: Early Stopping for Single-Instance Deep Generative Priors](https://mlsanity.com/paper/2110.12271/) (2021)
- [General Low-rank Matrix Optimization: Geometric Analysis and Sharper Bounds](https://mlsanity.com/paper/2104.10356/) (2021)
- [Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recovery](https://mlsanity.com/paper/2102.02969/) (2021)
- [A nearly linearly convergent first-order method for nonsmooth functions with quadratic growth](https://mlsanity.com/paper/2205.00064/) (2022)

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

- [Guaranteed Nonconvex Factorization Approach for Tensor Train Recovery](https://mlsanity.com/paper/2401.02592/) (2024)
- [Fast and Accurate Estimation of Low-Rank Matrices from Noisy Measurements via Preconditioned Non-Convex Gradient Descent](https://mlsanity.com/paper/2305.17224/) (2023)
- [Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descent](https://mlsanity.com/paper/2502.00463/) (2025)
- [Implicit Regularization Makes Overparameterized Asymmetric Matrix Sensing Robust to Perturbations](https://mlsanity.com/paper/2309.01796/) (2023)
- [Robust Low-rank Tensor Train Recovery](https://mlsanity.com/paper/2410.15224/) (2024)
- [Image Reconstruction via Deep Image Prior Subspaces](https://mlsanity.com/paper/2302.10279/) (2023)
- [Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensing](https://mlsanity.com/paper/2303.14244/) (2023)
- [Structured Variational D-Decomposition for Accurate and Stable Low-Rank Approximation](https://mlsanity.com/paper/2506.08535/) (2025)

## Abstract (arXiv)

This paper studies the problem of recovering a low-rank matrix from several noisy random linear measurements. We consider the setting where the rank of the ground-truth matrix is unknown a priori and use an objective function built from a rank-overspecified factored representation of the matrix variable, where the global optimal solutions overfit and do not correspond to the underlying ground truth. We then solve the associated nonconvex problem using gradient descent with small random initialization. We show that as long as the measurement operators satisfy the restricted isometry property (RIP) with its rank parameter scaling with the rank of the ground-truth matrix rather than scaling with the overspecified matrix rank, gradient descent iterations are on a particular trajectory towards the ground-truth matrix and achieve nearly information-theoretically optimal recovery when it is stopped appropriately. We then propose an efficient stopping strategy based on the common hold-out method and show that it detects a nearly optimal estimator provably. Moreover, experiments show that the proposed validation approach can also be efficiently used for image restoration with deep image prior, which over-parameterizes an image with a deep network.