mlsanityData to 14 Oct 2026

Non-Convex Compressed Sensing with Training Data

arXiv 2101.08310 ↗First posted 20 Jan 2021cs.LG cs.NA math.NAcited by 1

Not on the map. Why?

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.

Key facts. Cited by 1 paper 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

37 of 66 references.

References · 37

  1. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  2. 2015Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Codingcited by 2,329
  3. 2015Learning both Weights and Connections for Efficient Neural Networkscited by 2,031
  4. 2016Understanding deep learning requires rethinking generalizationcited by 1,674
  5. 2017Deep Image Priorcited by 1,098
  6. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  7. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 574
  8. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 566
  9. 2016Learning Structured Sparsity in Deep Neural Networkscited by 541
  10. 2017Compressed Sensing using Generative Modelscited by 339
  11. 2017Variational Dropout Sparsifies Deep Neural Networkscited by 265
  12. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 261
25 more
  1. 2014Qualitatively characterizing neural network optimization problemscited by 188
  2. 2018A Convergence Analysis of Gradient Descent for Deep Linear Neural Networkscited by 184
  3. 2019Towards moderate overparameterization: global convergence guarantees for training shallow neural networkscited by 176
  4. 2017Spurious Local Minima are Common in Two-Layer ReLU Neural Networkscited by 104
  5. 2020An Overview of Neural Network Compressioncited by 59
  6. 2015Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picturecited by 49
  7. 2018Compressed Sensing with Deep Image Prior and Learned Regularizationcited by 47
  8. 2018Neural Proximal Gradient Descent for Compressive Imagingcited by 46
  9. 2019Deep Compressed Sensingcited by 46
  10. 2020Compressive sensing with un-trained neural networks: Gradient descent finds the smoothest approximationcited by 39
  11. 2015Simple, Efficient, and Neural Algorithms for Sparse Codingcited by 37
  12. 2017Global Guarantees for Enforcing Deep Generative Priors by Empirical Riskcited by 37
  13. 2018Modeling Sparse Deviations for Compressed Sensing using Generative Modelscited by 33
  14. 2019Algorithmic Guarantees for Inverse Imaging with Untrained Network Priorscited by 32
  15. 2016No bad local minima: Data independent training error guarantees for multilayer neural networkscited by 30
  16. 2015Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Methodcited by 24
  17. 2017Deep Networks for Compressed Image Sensingcited by 23
  18. 2013New Algorithms for Learning Incoherent and Overcomplete Dictionariescited by 22
  19. 2014Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Methodcited by 22
  20. 2018A Provably Convergent Scheme for Compressive Sensing under Random Generative Priorscited by 15
  21. 2014Local Identification of Overcomplete Dictionariescited by 7
  22. 2014More Algorithms for Provable Dictionary Learningcited by 6
  23. 2019Restricted Isometry Property under High Correlationscited by 5
  24. 2013Sparse Matrix Factorizationcited by 3
  25. 2020A Relaxation Argument for Optimization in Neural Networks and Non-Convex Compressed Sensingcited by 2

Built on by

Cited by year

Citing papers per year: 2023: 1.

1 paper.

  1. 2023Learning Trees of ℓ0-Minimization Problemscited by 0