Thresholding gradient methods in Hilbert spaces: support identification and linear convergence

¹ CNRS, École Normale Supérieure (DMA), 75005 Paris, France.
² LCSL, Istituto Italiano di Tecnologia and Massachusetts Institute of Technology, Cambridge, MA 02139, USA.
³ DIBRIS, Università degli Studi di Genova, 16146 Genova, Italy.
⁴ Dipartimento di Matematica, Università degli Studi di Genova, 16146 Genova, Italy.

^* Corresponding author: guillaume.garrigos@ens.fr

Received: 3 December 2017
Accepted: 6 March 2019

Abstract

We study the ℓ¹ regularized least squares optimization problem in a separable Hilbert space. We show that the iterative soft-thresholding algorithm (ISTA) converges linearly, without making any assumption on the linear operator into play or on the problem. The result is obtained combining two key concepts: the notion of extended support, a finite set containing the support, and the notion of conditioning over finite-dimensional sets. We prove that ISTA identifies the solution extended support after a finite number of iterations, and we derive linear convergence from the conditioning property, which is always satisfied for ℓ¹ regularized least squares problems. Our analysis extends to the entire class of thresholding gradient algorithms, for which we provide a conceptually new proof of strong convergence, as well as convergence rates.