An unbiased approach to compressed sensing. (23rd October 2020)

• Record Type: Journal Article
• Authors: Carlsson, Marcus; Gerosa, Daniele; Olsson, Carl
• Is Part Of: Inverse problems. Volume 36:Number 11(2020)
• Publication Date: 2020-10-23
• Subjects: compressed sensing -- regularization -- non-convex optimization -- non-smooth optimization; Inverse problems (Differential equations) -- Periodicals; 515.357
• DOI: 10.1088/1361-6420/abbd7f
• Languages: English
• ISSNs: 0266-5611

Abstract

Abstract: In compressed sensing a sparse vector is approximately retrieved from an under-determined equation system Ax = b . Exact retrieval would mean solving a large combinatorial problem which is well known to be NP-hard. For b of the form Ax 0 + ϵ, where x 0 is the ground truth and ϵ is noise, the 'oracle solution' is the one you get if you a priori know the support of x 0, 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 ‖ x ̂ − x 0 ‖ 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.