More hints on compressed sensing at ICASSP 2011
"THE VALUE OF REDUNDANT MEASUREMENT IN COMPRESSED SENSING"; Victoria Kostina, Princeton University, US; Marco Duarte, Duke University, United States; Sina Jafarpour, Princeton University, US; Robert Calderbank, Duke University, US
The conference room was completely full during the presentation of this paper, in my opinion because of its evocative title. However the scenario studied in this work is much more particular as one could think from the title. The authors study the performance of a particular family of measurement matrices (weakly democratic) under the assumption that the CS quantizer has the choice to reject some measurements from the ones initially acquired. An overall bit budget for quantization is divided between (i) a set of bits to encode the set of indices for the rejected measurements, and (ii) the remaining bits that encode the values of the preserved measurements. Under these assumptions the paper concludes that throwing away certain measurements improves recovery SNR, i.e. it is better to have certain measurements quantized over a finer grid than a lot of coarse measurements.
"COMPRESSIVE SENSING MEETS GAME THEORY"; Sina Jafarpour, Princeton University, US; Volkan Cevher, Ecole Polytechnique Fédérale de Lausanne, Switzerland; Robert Schapire, Princeton University, US
Another paper with an evocative title. This work proposes a new reconstruction algorithm (MUSE) from compressed measurements corrupted with noise. This algorithm, which presents guarantees on the infinity-norm of the reconstruction error, can be formulated as a two-player game (and hence the title), which is equivalent to an alternating optimization scheme.
An interesting work on the fundamentals of estimation of parameters with underlying sparsity:
"PERFORMANCE BOUNDS FOR SPARSE PARAMETRIC COVARIANCE ESTIMATION IN GAUSSIAN MODELS"; Alexander Jung, Vienna University of Technology, Austria; Sebastian Schmutzhard, University of Vienna, Austria; Franz Hlawatsch, Vienna University of Technology, Austria; Alfred O. Hero III, University of Michigan, US
This paper studies the performance bounds on the problem of estimating the covariance matrix of a Gaussian random vector under the assumption that this covariance matrix can be modeled as a sparse expansion of known "basis matrices". The authors have derived lower bounds on the variance of both biased and unbiased estimators for a certain family of covariance matrices of interest. The analysis shows that in the low SNR regime the sparsity does not help, while in the high SNR regime the performance of an oracle estimator can be achieved. Between these two extreme cases the bound presents a transition phase polynomical in the SNR. This work studies a more involved scenario than the one by Ben-Haim et al. in their last year paper.
ICASSP will soon have to create a special session just for Yonina C. Eldar. This year she figures as coauthor of six papers. I won't go over all of them, just a couple of hints:
"SHANNON MEETS NYQUIST: CAPACITY LIMITS OF SAMPLED ANALOG CHANNELS"; Yuxin Chen, Stanford University, United States; Yonina C. Eldar, Technion / Israel Institute of Technology, Israel; Andrea Goldsmith, Stanford University, US
This preliminary work explores how capacity is affected by a sampling mechanisms below the channel's Nyquist rate. Under the Gaussianity assumption, the problem is formulated as a joint optimization over the input distribution and the receiver filter for a given set of uniform samplers. In the case of having a single receiver chain it is shown that the optimal transmission strategy avoids aliasing at the output, i.e. receiver filter not always corresponding to the classical matched filter. On the other hand, for multiple receiver chains sufficient conditions to obtain Nyquist capacity at a total rate equal to Landau rate are derived. My opinion is that the journal version of this work ("Shannon meets Nyquist: capacity limits of sampled analog channels", Y. Chen, Y. C. Eldar, and A. J. Goldsmith, in preparation) will give the first steps towards a rigorous analysis of the capacity achievable by compressed sampling schemes.
"SUB-NYQUIST SAMPLING OF SHORT PULSES"; Ewa Matusiak, University of Vienna, Austria; Yonina C. Eldar, Technion, Israel
This work applies the ideas of the modulated wideband converter to the time domain. Here it is assumed that the transmitted signal is composed by a series of narrow pulses with unknown shapes and unknown delays. In order to reduce the required sampling rate the proposed approach exploits the sparsity of the signal in the "Gabor frames" domain yielding to a similar result as in the case of the modulated wideband converter.