An unbiased approach to compressed sensing
(2020) In Inverse Problems 36(11).- 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... (More)
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.
(Less)
- author
- Carlsson, Marcus LU ; Gerosa, Daniele LU and Olsson, Carl LU
- organization
- publishing date
- 2020-11
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Compressed sensing, Non-convex optimization, Nonsmooth optimization, Regularization
- in
- Inverse Problems
- volume
- 36
- issue
- 11
- article number
- 115014
- publisher
- IOP Publishing
- external identifiers
-
- scopus:85096810854
- ISSN
- 0266-5611
- DOI
- 10.1088/1361-6420/abbd7f
- language
- English
- LU publication?
- yes
- id
- 0a032c7a-e17b-4fd7-a7fd-552e0e847d42
- date added to LUP
- 2021-01-14 16:06:44
- date last changed
- 2022-05-12 17:37:29
@article{0a032c7a-e17b-4fd7-a7fd-552e0e847d42,
abstract = {{<p>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. </p>}},
author = {{Carlsson, Marcus and Gerosa, Daniele and Olsson, Carl}},
issn = {{0266-5611}},
keywords = {{Compressed sensing; Non-convex optimization; Nonsmooth optimization; Regularization}},
language = {{eng}},
number = {{11}},
publisher = {{IOP Publishing}},
series = {{Inverse Problems}},
title = {{An unbiased approach to compressed sensing}},
url = {{http://dx.doi.org/10.1088/1361-6420/abbd7f}},
doi = {{10.1088/1361-6420/abbd7f}},
volume = {{36}},
year = {{2020}},
}