Non-Convex Compressed Sensing with Training Data

2021/01/20 by Gerrit Welper, Welper, G.
Computer Science · Engineering · #68Q32 #94A12 #Blind Source Separation Techniques #Electrical and Bioimpedance Tomography #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.2101.08310

openalex publication_date 2021/01/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 ℓ₁ 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 = B_l, l=1, …, 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.

Citations

• Sparsest solutions of underdetermined linear systems via ℓq-minimization for 0<q⩽1
• Sparse Approximate Solutions to Linear Systems
• Long Short-Term Memory
• Iteratively reweighted least squares minimization for sparse recovery
• Stable signal recovery from incomplete and inaccurate measurements
• No bad local minima: Data independent training error guarantees for\n multilayer neural networks
• Variational Dropout Sparsifies Deep Neural Networks
• Compressed Sensing using Generative Models
• Deep Image Prior
• Neural Proximal Gradient Descent for Compressive Imaging
• Compressed Sensing with Deep Image Prior and Learned Regularization
• Learning Overparameterized Neural Networks via Stochastic Gradient\n Descent on Structured Data
• Restricted Isometry Property under High Correlations
• Deep Compressed Sensing

Related

• On the Certification of the Restricted Isometry Property
• Minimization of Transformed L₁ Penalty: Theory, Difference of Convex Function Algorithm, and Robust Application in Compressed Sensing
• Compressed Sensing of Simultaneous Low-Rank and Joint-Sparse Matrices
• Sparse Solutions of an Undetermined Linear System
• Hidden cliques and the certification of the restricted isometry property