Sparse regularization on thin grids I: the Lasso. (13th March 2017)

• Record Type: Journal Article
• Authors: Duval, Vincent; Peyré, Gabriel
• Is Part Of: Inverse problems. Volume 33:Number 5(2017:May)
• Publication Date: 2017-03-13
• Subjects: sparsity -- deconvolution -- L1 norm -- compressed sensing -- convex optimization -- space of measures; Inverse problems (Differential equations) -- Periodicals; 515.357
• DOI: 10.1088/1361-6420/aa5e12
• Languages: English
• ISSNs: 0266-5611

Abstract

Abstract: This article analyzes the recovery performance in the presence of noise of sparse ℓ 1 regularization, which is often referred to as the Lasso or Basis-Pursuit. We study the behavior of the method for inverse problems regularization when the discretization step size tends to zero. We assume that the sought after sparse sum of Diracs is recovered when there is no noise (a condition which has been thoroughly studied in the literature) and we study what is the support (in particular the number of Dirac masses) estimated by the Lasso when noise is added to the observation. We identify a precise non-degeneracy condition that guarantees that the recovered support is close to the initial one. More precisely, we show that, in the small noise regime, when the non-degeneracy condition holds, this method estimates twice the number of spikes as the number of original spikes. Indeed, we prove that the Lasso detects two neighboring spikes around each location of an original spike. While this paper is focussed on cases where the observations vary smoothly with the spikes locations (e.g. the deconvolution problem with a smooth kernel), an interesting by-product is an abstract analysis of the support stability of discrete ℓ 1 regularization, which is of an independent interest. We illustrate the usefulness of this abstract analysis to analyze for the first time the support instability of compressed sensing recovery.