Non-Convex Compressed Sensing with Training Data

Abstract

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 ${\ell }_1$ by ${\ell }_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=B_l$, $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$.

References in corpus (16)

• Deep Image Prior
• Variational Dropout Sparsifies Deep Neural Networks
• Compressed Sensing using Generative Models
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Compressed Sensing with Deep Image Prior and Learned Regularization
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Neural Proximal Gradient Descent for Compressive Imaging
• Deep Compressed Sensing
• More Algorithms for Provable Dictionary Learning
• Sparse Matrix Factorization
• A Provably Convergent Scheme for Compressive Sensing under Random Generative Priors
• Restricted Isometry Property under High Correlations
• A Relaxation Argument for Optimization in Neural Networks and Non-Convex Compressed Sensing