# Non-Convex Compressed Sensing with Training Data

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 66 references that are in the map.
- First posted on arXiv 20 Jan 2021.

## Builds on (most cited first, 30 of 37)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [Learning both Weights and Connections for Efficient Neural Networks](https://mlsanity.com/paper/1506.02626/) (2015)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Deep Image Prior](https://mlsanity.com/paper/1711.10925/) (2017)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Learning Structured Sparsity in Deep Neural Networks](https://mlsanity.com/paper/1608.03665/) (2016)
- [Compressed Sensing using Generative Models](https://mlsanity.com/paper/1703.03208/) (2017)
- [Variational Dropout Sparsifies Deep Neural Networks](https://mlsanity.com/paper/1701.05369/) (2017)
- [Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data](https://mlsanity.com/paper/1808.01204/) (2018)
- [Qualitatively characterizing neural network optimization problems](https://mlsanity.com/paper/1412.6544/) (2014)
- [A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks](https://mlsanity.com/paper/1810.02281/) (2018)
- [Towards moderate overparameterization: global convergence guarantees for training shallow neural networks](https://mlsanity.com/paper/1902.04674/) (2019)
- [Spurious Local Minima are Common in Two-Layer ReLU Neural Networks](https://mlsanity.com/paper/1712.08968/) (2017)
- [An Overview of Neural Network Compression](https://mlsanity.com/paper/2006.03669/) (2020)
- [Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture](https://mlsanity.com/paper/1511.03607/) (2015)
- [Compressed Sensing with Deep Image Prior and Learned Regularization](https://mlsanity.com/paper/1806.06438/) (2018)
- [Neural Proximal Gradient Descent for Compressive Imaging](https://mlsanity.com/paper/1806.03963/) (2018)
- [Deep Compressed Sensing](https://mlsanity.com/paper/1905.06723/) (2019)
- [Compressive sensing with un-trained neural networks: Gradient descent finds the smoothest approximation](https://mlsanity.com/paper/2005.03991/) (2020)
- [Simple, Efficient, and Neural Algorithms for Sparse Coding](https://mlsanity.com/paper/1503.00778/) (2015)
- [Global Guarantees for Enforcing Deep Generative Priors by Empirical Risk](https://mlsanity.com/paper/1705.07576/) (2017)
- [Modeling Sparse Deviations for Compressed Sensing using Generative Models](https://mlsanity.com/paper/1807.01442/) (2018)
- [Algorithmic Guarantees for Inverse Imaging with Untrained Network Priors](https://mlsanity.com/paper/1906.08763/) (2019)
- [No bad local minima: Data independent training error guarantees for multilayer neural networks](https://mlsanity.com/paper/1605.08361/) (2016)
- [Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method](https://mlsanity.com/paper/1511.04777/) (2015)
- [Deep Networks for Compressed Image Sensing](https://mlsanity.com/paper/1707.07119/) (2017)
- [New Algorithms for Learning Incoherent and Overcomplete Dictionaries](https://mlsanity.com/paper/1308.6273/) (2013)

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

- [Learning Trees of ℓ0-Minimization Problems](https://mlsanity.com/paper/2302.02548/) (2023)

## Abstract (arXiv)

Efficient algorithms for the sparse solution of under-determined linear systems Ax = b are known for matrices A satisfying suitable assumptions like the restricted isometry property (RIP). Without such assumptions little is known and without any assumptions on A the problem is NP-hard. A common approach is to replace ℓ1 by ℓp minimization for 0 < p < 1, which is no longer convex and typically requires some form of local initial values for provably convergent algorithms. In this paper, we consider an alternative, where instead of suitable initial values we are provided with extra training problems Ax = Bl, l=1, dots, p that are related to our compressed sensing problem. They allow us to find the solution of the original problem Ax = b with high probability in the range of a one layer linear neural network with comparatively few assumptions on the matrix A.