An unbiased approach to compressed sensing

Research output: Contribution to journalArticle

Abstract

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.

Details

Authors
Organisations
External organisations
  • Chalmers University of Technology
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Computational Mathematics

Keywords

  • Compressed sensing, Non-convex optimization, Nonsmooth optimization, Regularization
Original languageEnglish
Article number115014
JournalInverse Problems
Volume36
Issue number11
Publication statusPublished - 2020 Nov
Publication categoryResearch
Peer-reviewedYes