# The Nonconvex Geometry of Linear Inverse Problems

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 96 references that are in the map.
- First posted on arXiv 7 Jan 2021.

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

- [Compressed Sensing using Generative Models](https://mlsanity.com/paper/1703.03208/) (2017)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [Spurious Local Minima are Common in Two-Layer ReLU Neural Networks](https://mlsanity.com/paper/1712.08968/) (2017)
- [Best Subset Selection via a Modern Optimization Lens](https://mlsanity.com/paper/1507.03133/) (2015)
- [Sparse High-Dimensional Regression: Exact Scalable Algorithms and Phase Transitions](https://mlsanity.com/paper/1709.10029/) (2017)
- [Exact Support Recovery for Sparse Spikes Deconvolution](https://mlsanity.com/paper/1306.6909/) (2013)
- [Global Optimality in Tensor Factorization, Deep Learning, and Beyond](https://mlsanity.com/paper/1506.07540/) (2015)
- [Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs](https://mlsanity.com/paper/1804.02008/) (2018)
- [Fast and Provable ADMM for Learning with Generative Priors](https://mlsanity.com/paper/1907.03343/) (2019)
- [Superresolution without Separation](https://mlsanity.com/paper/1506.03144/) (2015)
- [Tight convex relaxations for sparse matrix factorization](https://mlsanity.com/paper/1407.5158/) (2014)
- [An Approximate Shapley-Folkman Theorem](https://mlsanity.com/paper/1712.08559/) (2017)
- [Convexity of the image of a quadratic map via the relative entropy distance](https://mlsanity.com/paper/1305.0243/) (2013)
- [A Decomposition Method for Large Scale MILPs, with Performance Guarantees and a Power System Application](https://mlsanity.com/paper/1411.1973/) (2014)
- [Refined Shapley-Folkman Lemma and Its Application in Duality Gap Estimation](https://mlsanity.com/paper/1610.05416/) (2016)
- [Sparse non-negative super-resolution -- simplified and stabilised](https://mlsanity.com/paper/1804.01490/) (2018)

## Abstract (arXiv)

The gauge function, closely related to the atomic norm, measures the complexity of a statistical model, and has found broad applications in machine learning and statistical signal processing. In a high-dimensional learning problem, the gauge function attempts to safeguard against overfitting by promoting a sparse (concise) representation within the learning alphabet. In this work, within the context of linear inverse problems, we pinpoint the source of its success, but also argue that the applicability of the gauge function is inherently limited by its convexity, and showcase several learning problems where the classical gauge function theory fails. We then introduce a new notion of statistical complexity, gaugep function, which overcomes the limitations of the gauge function. The gaugep function is a simple generalization of the gauge function that can tightly control the sparsity of a statistical model within the learning alphabet and, perhaps surprisingly, draws further inspiration from the Burer-Monteiro factorization in computational mathematics. We also propose a new learning machine, with the building block of gaugep function, and arm this machine with a number of statistical guarantees. The potential of the proposed gaugep function theory is then studied for two stylized applications. Finally, we discuss the computational aspects and, in particular, suggest a tractable numerical algorithm for implementing the new learning machine.