Authors:Igor Ciril1;Jérôme Darbon2 andYohann Tendero3
Affiliations:1Institut Polytechnique des Sciences Avancées, France;2Brown University, United States;3Université Paris-Saclay, France
Keyword(s):Basis Pursuit, Compressive Sensing, Inverse Scale Space, Sparsity, $\ell^1$ Regularized Linear Problems, Non-smooth Optimization, Maximal Monotone Operator, Phase Transition.
RelatedOntology Subjects/Areas/Topics:Computer Vision, Visualization and Computer Graphics ;Image and Video Coding and Compression ;Image Formation and Preprocessing ;Image Formation, Acquisition Devices and Sensors ;Image Generation Pipeline: Algorithms and Techniques
Abstract:This paper considers l1-regularized linear inverse problems that frequently arise in applications. One strikingexample is the so called compressive sensing method that proposes to reconstruct a high dimensional signalu P Rn from low dimensional measurements Rm Q b Au, m ! n. The basis pursuit is another example. Formost of these problems the number of unknowns is very large. The recovered signal is obtained as the solutionto an optimization problem and the quality of the recovered signal directly depends on the quality of thesolver. 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 observethis transition phase. This paper proposes a simple algorithm that computes an exact l1 minimizer under theconstraints 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 literature is exhibited. Thesecomparisons illustrate that our algorithm compares advantageously: the aforementioned transition phase isempirically observed with a much better quality.(More)
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 P Rn from low dimensional measurements Rm Q b Au, m ! n. 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 literature is exhibited. These
comparisons illustrate that our algorithm compares advantageously: the aforementioned transition phase is
empirically observed with a much better quality.