CS: Some thoughts, Distributed Basis Pursuit, LASSO, Replica Analysis, Combining Nonconvex Compressed Sensing and GRAPPA, Multi-Sensor CS

As I am enjoying re-reading Glenn Knoll's Radiation Detection and Measurement that is a source of much detailed information on radiation sensors, I am very inspired at how some of the compressed sensing techniques could be involved in these detection processes. When performing ionizing radiation detection, several stages of conversion from the initial radiation down to the electrical current are needed. While each of these stages introduces inefficiencies (admittedly a bad thing) one should look at them as an opportunity whereby the physical detector can be changed to include an instance of compressed sensing. Some of these ideas have already been featured before and I expect to add some more to the list as a result of reading this book. The other take away lesson from this is:: every time the sensing process has conversion stages, it is ripe for an application of compressed sensing/group testing techniques.

Piotr Indyk added to yesterday's post::

Hi Igor,

A quick correction: the paper

New and improved Johnson-Lindenstrauss embeddings via the Restricted Isometry Property by Felix Krahmer and Rachel Ward. 

shows that * RIP implies JL* (after randomizing the matrices). The opposite direction is also true, but it has been known for a while now.

Thanks Piotr !

Here is the list of preprints and paper I just caught:

The first is of interest in the context of the recent development of all kinds of activities related to distributed computing: Distributed Basis Pursuit by João F. C. Mota, João M. F. Xavier, Pedro M. Q. Aguiar, and Markus Püschel. The abstract reads:

Nowadays we are witnessing major changes both in the acquisition and representation of signals and in the computing platforms for their processing. One new acquisition technique is provided by the new theory of compressed sensing, which places a greater burden on the reconstruction of signals, usually a largescale optimization problem called Basis Pursuit (BP). BP consists of finding the least ℓ1 norm solution of the underdetermined linear systemMz = b. Computing platforms, on the other hand, show a trend to distributed processing, for example in the form of sensor networks. In this paper we present distributed algorithms for solving BP. This means the algorithms have no notion of “central” or any special node during their computations. We consider two scenarios in which either the columns or the rows of M are distributed among the compute nodes. We analyze the convergence of the algorithms and validate them through numerical simulations in a computer cluster.

other papers/preprints include:
A local stochastic Lipschitz condition with application to Lasso for high dimensional generalized linear models by Zhiyi Chi. The abstract reads:

For regularized estimation, the upper tail behavior of the random Lipschitz coefficient associated with empirical loss functions is known to play an important role in the error bound of Lasso for high dimensional generalized linear models. The upper tail behavior is known for linear models but much less so for nonlinear models. We establish exponential type inequalities for the upper tail of the coefficient and illustrate an application of the results to Lasso likelihood estimation for high dimensional generalized linear models.

Extension of Replica Analysis to MAP Estimation with Applications to Compressed Sensing by Sundeep Rangan, Alyson K. Fletcher, and Vivek K Goyal. The abstract reads:

The replica method is a non-rigorous but widely accepted technique from statistical physics used in the asymptotic analysis of large, random, nonlinear problems. This paper applies the replica method to analyze non-Gaussian maximum a posteriori (MAP) estimation. The main result is a counterpart to Guo and Verd´u’s replica analysis of minimum mean-squared error estimation. The replica MAP analysis can be readily applied to many estimators used in compressed sensing, including basis pursuit, lasso, linear estimation with thresholding, and zero norm-regularized estimation. Among other benefits, the replica method provides a computationally-tractable method for exactly computing various performance metrics including mean-squared error and sparsity pattern recovery probability

Combining Nonconvex Compressed Sensing and GRAPPA Using the Nullspace Method by D. S. Weller, J. R. Polimeni, L. J. Grady, L. L. Wald, E. Adalsteinsson, and Vivek K Goyal. The abstract reads:

There has been substantial interest in combining parallel image reconstruction methods like GRAPPA [1] with compressed sensing (CS) [2-4] to improve image quality at higher accelerations. Recent efforts have approached combining these methods either by cascading or iterating GRAPPA type and CS-type reconstructions [5-6] or by performing joint optimization with multiple objective functions [7]. The proposed method extends CS reconstruction in the nullspace of the acquired data [8] to jointly minimize the ℓ0-norm sparsity penalty and the ℓ2-norm deviation from GRAPPA reconstruction. This method approximates the ℓ0-norm using continuation with a differentiable nonconvex regularizer [9-10]. While this method generalizes to any sparsifying transform, we choose the discrete contourlet sparsifying transform [11] to illustrate its effectiveness in representing brain images. We demonstrate the proposed method reconstructs images at higher accelerations than GRAPPA or CS alone would allow.

A Multi-Sensor Compressed Sensing Receiver: Performance Bounds and Simulated Results by Benjamin Miller, Joel Goodman, and Keith Forsythe, John Z. Sun and Vivek K Goyal. The abstract reads:

Multi-sensor receivers are commonly tasked with detecting, demodulating and geolocating target emitters over very wide frequency bands. Compressed sensing can be applied to persistently monitor a wide bandwidth, given that the received signal can be represented using a small number of coefficients in some basis. In this paper we present a multi-sensor compressive sensing receiver that is capable of reconstructing frequency-sparse signals using block reconstruction techniques in a sensor-frequency basis. We derive performance bounds for time-difference and angle of arrival (AoA) estimation of such a receiver, and present simulated results in which we compare AoA reconstruction performance to the bounds derived.

Estimating Higher-Order Distances Using Random Projections by Ping Li, Michael Mahoney, and Yiyuan She. The abstract reads:

We provide a simple method and relevant theoretical analysis for efficiently estimating higherorder lp distances. While the analysis mainly focuses on l4, our methodology extends naturally to p = 6; 8; 10:::, (i.e., when p is even). Distance-based methods are popular in machine learning. In large-scale applications, storing, computing, and retrieving the distances can be both space and time prohibitive. Efficient algorithms exist for estimating lp distances if 0 \lt p · 2. The task for p \gt 2 is known to be difficult. Our work partially fills this gap.

Credit: NASA / GSFC / ASU, Natural Bridge on the Moon.