 |
Conference papers
A Simple and Exact Algorithm to Solve l1 Linear Problems: Application to the Compressive Sensing Method
Abstract : This paper considers l1-regularized linear inverse problems that frequently arise in applications. One striking
example is the so called compressive sensing method that proposes to reconstruct a high dimensional signal
u from low dimensional measurements b=Au. The basis pursuit is another example. For most of these problems the number of unknowns is very large. The recovered signal is obtained as the solution to an optimization problem and the quality of the recovered signal directly depends on the quality of the
solver. Theoretical works predict a sharp transition phase for the exact recovery of sparse signals. However,
to the best of our knowledge, other state-of-the-art algorithms are not effective enough to accurately observe
this transition phase. This paper proposes a simple algorithm that computes an exact l1 minimizer under the constraints Au=b. This algorithm can be employed in many problems: as soon as A has full row rank. In addition, a numerical comparison with standard algorithms available in the iterature is exhibited. These comparisons illustrate that our algorithm compares advantageously: the aforementioned transition phase is empirically observed with a much better quality.
https://hal.telecom-paris.fr/hal-02287733
Contributor : Telecomparis Hal <>
Submitted on : Friday, September 13, 2019 - 5:17:39 PM
Last modification on : Tuesday, September 21, 2021 - 2:16:04 PM
Contributor : Telecomparis Hal <>
Submitted on : Friday, September 13, 2019 - 5:17:39 PM
Last modification on : Tuesday, September 21, 2021 - 2:16:04 PM
Links full text
