mlsanityData to 7 Oct 2026

A Validation Approach to Over-parameterized Matrix and Image Recovery

arXiv 2209.10675 ↗First posted 21 Sep 2022math.OC cs.LG eess.IVcited by 8

Not on the map. Why?

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.

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

Builds on

29 of 56 references.

References · 29

  1. 2017Deep Image Priorcited by 1,097
  2. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 649
  3. 2019Implicit Regularization in Deep Matrix Factorizationcited by 402
  4. 2017Implicit Regularization in Matrix Factorizationcited by 318
  5. 2018Implicit Bias of Gradient Descent on Linear Convolutional Networkscited by 251
  6. 2018Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balancedcited by 172
  7. 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 159
  8. 2017No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysiscited by 127
  9. 2016Matrix Completion has No Spurious Local Minimumcited by 124
  10. 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
  11. 2022Robust Training under Label Noise by Over-parameterizationcited by 93
  12. 2018Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?cited by 87
17 more
  1. 2016Global Optimality of Local Search for Low Rank Matrix Recoverycited by 81
  2. 2019Implicit Regularization for Optimal Sparse Recoverycited by 78
  3. 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 77
  4. 2015Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guaranteescited by 68
  5. 2021Early Stopping for Deep Image Priorcited by 44
  6. 2017Global Optimality in Low-rank Matrix Optimizationcited by 35
  7. 2022Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorizationcited by 34
  8. 2019Low-rank matrix recovery with composite optimization: good conditioning and rapid convergencecited by 31
  9. 2021On the computational and statistical complexity of over-parameterized matrix sensingcited by 31
  10. 2020Robust Recovery via Implicit Bias of Discrepant Learning Rates for Double Over-parameterizationcited by 26
  11. 2018Harnessing Structures in Big Data via Guaranteed Low-Rank Matrix Estimationcited by 25
  12. 2021Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recoverycited by 21
  13. 2022Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterizationcited by 21
  14. 2021Self-Validation: Early Stopping for Single-Instance Deep Generative Priorscited by 15
  15. 2021General Low-rank Matrix Optimization: Geometric Analysis and Sharper Boundscited by 12
  16. 2021Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recoverycited by 10
  17. 2022A nearly linearly convergent first-order method for nonsmooth functions with quadratic growthcited by 6

Built on by

Cited by year

Citing papers per year: 2023: 4; 2024: 2; 2025: 2.

8 papers.

  1. 2024Guaranteed Nonconvex Factorization Approach for Tensor Train Recoverycited by 8
  2. 2023Fast and Accurate Estimation of Low-Rank Matrices from Noisy Measurements via Preconditioned Non-Convex Gradient Descentcited by 5
  3. 2025Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descentcited by 4
  4. 2023Implicit Regularization Makes Overparameterized Asymmetric Matrix Sensing Robust to Perturbationscited by 2
  5. 2024Robust Low-rank Tensor Train Recoverycited by 2
  6. 2023Image Reconstruction via Deep Image Prior Subspacescited by 1
  7. 2023Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensingcited by 0
  8. 2025Structured Variational D-Decomposition for Accurate and Stable Low-Rank Approximationcited by 0