Monday, March 30, 2015

Sparse Spikes Deconvolution on Thin Grids / Compressive Sensing in Electromagnetics - A Review

Gabriel Peyré let me know of the following:

Hi Igor,

A paper that might interest the CS community
The numerical section contains some findings on support (in)stability of CS with l^1.

-- best
From his blog post:
Vincent Duval and myself just released a new paper on the asymptotic performance of L1-type methods for deconvoluton, when the grid-size tends to zero. This paper extends our previous results on the subject. It basically proves that both the classical lasso/basis-pursuit method, and the less known continuous basis-pursuit method estimate twice the number of spikes. This is not so surprising because approximating arbitrary spikes locations on a quantized grid somehow necessitates this slight delocalization of the positions. An interesting feature of our analysis is that we are able to perfectly predict which of the neighboring grid points will be selected using a careful analysis of so-called dual certificates. Another interesting feature of these theoretical findings is that we provide an “abstract” analysis of L1-like methods that extend the classical results of J. J. Fuchs to the setting where the support is not necessarily stable (which is always the case for coherent inverse problems like deconvolution). This abstract analysis can be used beyond deconvolution problems. In the numerical section, we show how it can be used to assess numerically support-instability in compressed sensing reconstruction. This is a somehow under-studied problem. Indeed, the literature only focus on the case where the support is stable or only on L2 stability, never on the “gray area” where support is unstable but the method is successful when there is no noise.

Abstract : This article analyzes the recovery performance of two popular finite dimensional approximations of the sparse spikes deconvolution problem over Radon measures. We examine in a unified framework both the L1 regularization (often referred to as Lasso or Basis-Pursuit) and the Continuous Basis-Pursuit (C-BP) methods. The Lasso is the de-facto standard for the sparse regularization of inverse problems in imaging. It performs a nearest neighbor interpolation of the spikes locations on the sampling grid. The C-BP method, introduced by Ekanadham, Tranchina and Simoncelli, uses a linear interpolation of the locations to perform a better approximation of the infinite-dimensional optimization problem, for positive measures. We show that, in the small noise regime, both methods estimate twice the number of spikes as the number of original spikes. Indeed, we show that they both detect two neighboring spikes around the locations of an original spikes. These results for deconvolution problems are based on an abstract analysis of the so-called extended support of the solutions of L1-type problems (including as special cases the Lasso and C-BP for deconvolution), which are of an independent interest. They precisely characterize the support of the solutions when the noise is small and the regularization parameter is selected accordingly. We illustrate these findings to analyze for the first time the support instability of compressed sensing recovery when the number of measurements is below the critical limit (well documented in the literature) where the support is provably stable.

Giacomo Oliveri also sent me the following link to a review:

Dear Dr. Carron,

this is to kindly ask if you could consider posting the following contribution (published journal paper on the IEEE Antennas and Propagation Magazine) in your excellent Nuit Blanche blog (

Title: Compressive Sensing in Electromagnetics - A Review
Authors: Andrea MASSA, Paolo ROCCA, and Giacomo OLIVERI
Journal: IEEE Antennas and Propagation Magazine
Volume: 57
Issue: 1
Pages: 224-238
Month: February
Year: 2015
DOI: 10.1109/MAP.2015.2397092
Several problems arising in electromagnetics can be directly formulated or suitably recast for an effective solution within the compressive sensing (CS) framework. This has motivated a great interest in developing and applying CS methodologies to several conventional and innovative electromagnetic scenarios. This work is aimed at presenting, to the best of the authors’ knowledge, a review of the state-of-the-art and most recent advances of CS formulations and related methods as applied to electromagnetics. Toward this end, a wide set of applicative scenarios comprising the diagnosis and synthesis of antenna arrays, the estimation of directions of arrival, and the solution of inverse scattering and radar imaging problems are reviewed. Current challenges and trends in the application of CS to the solution of traditional and new electromagnetic problems are also discussed.

Please let us know if you need any further information on this contribution.

Many thanks in advance for your kindness,
Best regards,
Giacomo Oliveri

Thanks Jong, Giacomo and Gabriel !

Image Credit: NASA/JPL-Caltech/Space Science Institute 
N00236618.jpg was taken on March 27, 2015 and received on Earth March 29, 2015. The camera was pointing toward IAPETUS, and the image was taken using the CL1 and IR3 filters.
Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

No comments: