CS: Lower Bounds for Sparse Recovery, Super-resolution, Sparse Multipath Channels, RIP for Structurally-Subsampled Unitary Matrices

The photo on the side shows the resulting plume as seen from the LCROSS cameras.

In a different direction, here is a thing I did not know about SSDs. As opposed to Hard Disk Drives, SSDs can allow parallel access to different jobs running on the CPU. SSDs also allow faster access to the data in memory (that part I knew). I wonder how this could help some of the reconstruction processes in Compressive Sensing ?

Jean-Luc Stark will give a talk at Saclay today, let us hope that the audience will get to hear if the initial tests of Compressive Sensing encoding of the PACS camera on Herschel are good.

Now let's go back to papers. I mentioned the abstract earlier, but now the paper is now available: Lower Bounds for Sparse Recovery by Khanh Do Ba, Piotr Indyk, Eric Price and David Woodruff. The abstract reads:

We consider the following k-sparse recovery problem: design an m * n matrix A, such that for any signal x, given Ax we can efficiently recover x^ satisfying ||x - x^||_1 \le C min_k-sparse x0 ||x - x'||_1. It is known that there exist matrices A with this property that have only O(k log(n/k)) rows. In this paper we show that this bound is tight. Our bound holds even for the more general randomized version of the problem, where A is a random variable, and the recovery algorithm is required to work for any fixed x with constant probability (over A).

I mentioned this approach before as it was featured in a video online, here is the associated paper: Super-Resolution with Sparse Mixing Estimators by Stephane Mallat and Guoshen Yu. The abstract reads:

We introduce a class of inverse problem estimators computed by mixing adaptively a family of linear estimators corresponding to different priors. Sparse mixing weights are calculated over blocks of coefficients in a frame providing a sparse signal representation. They minimize an l1 norm taking into account the signal regularity in each block. Adaptive directional image interpolations are computed over a wavelet frame with an O(N logN) algorithm.

According to the paper, the SME algorithm is at http://www.cmap.polytechnique.fr/~mallat/SME.html, but it is not there for the moment.

Also found on the interwebs:

Signal Detection in Sparse Multipath Channels by Matt Malloy and Akbar Sayeed. The abstract reads:

In this paper, we revisit the problem of signal detection in multipath environments. Existing results implicitly assume a rich multipath environment. Our work is motivated by physical arguments and recent experimental results that suggest physical channels encountered in practice exhibit a sparse structure, especially at high signal space dimension (i.e., large time-bandwidth product). We first present a model for sparse channels that quantifies the independent degrees of freedom (DoF) in the channel as a function of the physical propagation environment and signal space dimension. The number of DoF represents the delay-Doppler diversity afforded by the channel and, thus, critically impacts detection performance. Our focus is on two types of non-coherent detectors: the energy detector (ED) and the optimal non-coherent detector (ONCD) that assumes full knowledge of channel statistics. Results show, for a uniform distribution of paths in delay and Doppler, the channel exhibits a rich structure at low signal space dimension and then gets progressively sparser as this dimension is increased. Consequently, the performance of the detectors is identical in the rich regime. As the signal space dimension is increased and the channel becomes sparser, the ED suffers significant degradation in performance relative to the ONCD. Finally, our results show the existence of an optimal signal space dimension - one that yields the best detection performance - as a function of the physical channel characteristics and the operating signal to noise ratio (SNR).

After the result on Toeplitz matrices, which eventually could be used for coded aperture here is a new paper for measurement matrices having other properties: A Restricted Isometry Property for Structurally-Subsampled Unitary Matrices by Waheed Bajwa, Akbar Sayeed and Robert Nowak, The abstract reads:

Subsampled (or partial) Fourier matrices were originally introduced in the compressive sensing literature by Candes et al. Later, in papers by Candes and Tao and Rudelson and Vershynin, it was shown that (random) subsampling of the rows of many other classes of unitary matrices also yield effective sensing matrices. The key requirement is that the rows of U, the unitary matrix, must be highly incoherent with the basis in which the signal is sparse. In this paper, we consider acquisition systems that—despite sensing sparse signals in an incoherent domain—cannot randomly subsample rows from U. We consider a general class of systems in which the sensing matrix corresponds to subsampling of the rows of matrices of the form  = RU (instead of U), where R is typically a low-rank matrix whose structure reflects the physical/technological constraints of the acquisition system. We use the term “structurally-subsampled unitary matrices” to describe such sensing matrices. We investigate the restricted isometry property of a particular class of structurally-subsampled unitary matrices that arise naturally in application areas such as multiple-antenna channel estimation and sub-nyquist sampling. In addition, we discuss an immediate application of this work in the area of wireless channel estimation, where the main results of this paper can be applied to the estimation of multiple-antenna orthogonal frequency division multiplexing channels that have sparse impulse responses.

Finally, here is a recent presentation by Toh Kim Chuan on An accelerated proximal gradient method for nuclear norm minimization.

LCROSS Zoomed in image of the impact plume. The extent of the plume at 15 sec is approximately 6-8 km in diameter. Credit: NASA Click for full resolution.