In compressed sensing a sparse vector is approximately retrieved from an underdetermined equation system Ax = b. Exact retrievalwouldmean solving a large combinatorial problem which is well known to be NP-hard. For b of the form Ax0 + ϵ, where x0 is the ground truth and ϵ is noise, the 'oracle solution' is the one you get if you a priori know the support of x0, and is the best solution one could hope for. We provide a non-convex functional whose global minimum is the oracle solution, with the property that any other local minimizer necessarily has high cardinality. We provide estimates of the type ||◯ - x0||2 ≤ C||ϵ||2 with constants C that are significantly lower than for competing methods or theorems, and our theory relies on soft assumptions on the matrix A, in comparison with standard results in the field. The framework also allows to incorporate a priori information on the cardinality of the sought vector. In this case we show that despite being non-convex, our cost functional has no spurious local minima and the global minima is again the oracle solution, thereby providing the first method which is guaranteed to find this point for reasonable levels of noise, without resorting to combinatorial methods.

Original languageEnglish
Article number115014
JournalInverse Problems
Issue number11
Publication statusPublished - 2020 Nov

Subject classification (UKÄ)

  • Computational Mathematics


  • Compressed sensing
  • Non-convex optimization
  • Nonsmooth optimization
  • Regularization


Dive into the research topics of 'An unbiased approach to compressed sensing'. Together they form a unique fingerprint.

Cite this