An Algorithm Solving Compressive Sensing Problem Based on Maximal Monotone Operators
Tendero, Yohann (Institut Polytechnique des Sciences Avancées)
Ciril, Igor (Institut Polytechnique des Sciences Avancées)
Darbon, Jérôme (Brown University. Division of Applied Mathematics)
Serna, Susana (Universitat Autònoma de Barcelona. Departament de Matemàtiques)

Data:	2021
Resum:	The need to solve ℓ1 regularized linear problems can be motivated by various compressive sensing and sparsity related techniques for data analysis and signal or image processing. These problems lead to nonsmooth convex optimization in high dimensions. Theoretical works predict a sharp phase transition for the exact recovery of compressive sensing problems. Our numerical experiments show that state-of-the-art algorithms are not effective enough to observe this phase transition accurately. This paper proposes a simple formalism that enables us to produce an algorithm that computes an ℓ1 minimizer under the constraints A=u b up to the machine precision. In addition, a numerical comparison with standard algorithms available in the literature is exhibited. The comparison shows that our algorithm compares advantageously with other state-of-the-art methods, both in terms of accuracy and efficiency. With our algorithm, the aforementioned phase transition is observed at high precision.
Drets:	Aquest document està subjecte a una llicència d'ús Creative Commons. Es permet la reproducció total o parcial, la distribució, la comunicació pública de l'obra i la creació d'obres derivades, fins i tot amb finalitats comercials, sempre i quan es reconegui l'autoria de l'obra original.
Llengua:	Anglès
Document:	Article ; recerca ; Versió acceptada per publicar
Matèria:	Compressive sensing ; Inverse scale space ; Maximal monotone operator ; Nonsmooth optimization ; Phase transition ; Sparse solution recovery ; ℓ1 minimization
Publicat a:	SIAM Journal on Scientific Computing, Vol. 43, Issue 6 (January 2021) , p. A4067-A4094, ISSN 1095-7197

DOI: 10.1137/19M1260670

Postprint 29 p, 973.5 KB

El registre apareix a les col·leccions:
Articles > Articles de recerca
Articles > Articles publicats