CS: SparSA, Q/A, CS and Random Arrays, KF for reconstruction, Inferring Rankings Under Constrained Sensing, Post-silicon timing, a course and SSP09

And you thought, you'd go home for the week-end with nothing to stuff your brain with. Tough luck!

First, after a request, Mario Figueiredo kindly released the SparSA code featured in “Sparse reconstruction by separable approximation” (new version) by Stephen Wright, Robert Nowak, Mario Figueiredo. The MATLAB code available here:

http://www.lx.it.pt/~mtf/SpaRSA

It has been added to the reconstruction section of the Big Picture. By the way, I have tried to clean up both the reconstruction and the measurement/encoding matrix section, if you find I missed an item or I am wrong, please let me know. Thanks. In particular, the measurement/encoding matrix section also includes a blurb on the different properties (RIP, JN,....) that a matrix should have to allow for recovery of sparse solutions.

After the CS in radio interferometry entry of last week . I went ahead and asked dumb questions to the authors:

...What I am gathering out of it is that CS-spgl1 and Clean are kind of close to each other except for an advantage for CS for the lower number of measurements....

Laurent Jacques responded with :

This is not exactly what we shown. Let me summarize our approach here and Yves will possibly complement my explanation.

First, CLEAN is a Matching Pursuit with an additional degree of freedom : a parameter gamma that weight the removal of the selected atom from the current residual. (for usual MP, gamma=1 since the whole atom is removed from the residual at each iteration). Since astronmers took this parameter very small (typically gamma=1/10), they got a greedy method very efficient for deconvolving the true sky from the frequency coverage seen as a convolutive kernel. Or, using CS terminology, CLEAN is good to minimize the number of measurements while still having a good reconstruction. Therefore, in its results, CLEAN is closer to OMP than MP. My interpretation is that CLEAN is a "kind of" Taylor development of OMP making CLEAN very close to OMP when gamma is small.

Second, what we observed is that CLEAN and Basis Pursuit BP (solved by any methods like spgl1 or proximal methods) are working (in average) equally well, i.e. they are similar in the number of measurements they required to reach a certain quality of reconstruction. Remember that there is no exact recovery since the signal is compressible and since the measurements can be noisy. In my mind, we tried also with OMP and the quality reached was also very similar for the same number of measurements. This could be reconfirmed.

So, for us, BP does not beat CLEAN for the quality (SNR) of the reconstruction for this particular application where the sensing is performed randomly in the Fourier plane and where the sparsity basis is the canonical basis. BP has however the advantage to see clearly the global minimization to reach. Therefore, the number of iterations in a BP solver is well controlled compared to CLEAN where the stopping criterion is not always clearly set (and a small gamma provides perhaps a better quality but also a huge number of iterations).

I also asked :

... Except that I am under the weird impression that you are not comparing similar techniques since you put an additional constraint of positivity on the CS scheme....

Laurent Jacques answered :

BP+, i.e. BP plus the positivity constraint, is outside of the CS theory in our presentation of CS. (I know that they are some recent progress on that point in the CS theory, e.g working with the null space property.) So here, we have observed that BP+ provides better quality than CLEAN/BP for the same frequency coverage (number of measurements). We do not prove why. We just assume that the addition of this new a priori information(that correspond to a convex constraint in the problem) makes the problem more stable in its resolution.

One could mention that Clean or MEM are not using specifically the sparsity of the signal and on could say that indeed you are not comparing similar techniques. CLEAN assumes the sparsity as MP does. So, we can compare it to BP and BP+.

However, MEM assumes the smoothness/constancy of the signal (the converse of the sparsity) since by definition it maximizes the entropy. So, we didn't compare MEM to CLEAN/BP/BP+ because of this.

Yves Wiaux further added:

...Astronomers use both CLEAN and MEM. In that regard we might want to compare our methods to both. But indeed we only compare BP and our prior-enhanced-BP to CLEAN (which somehow already assumes sparsity, while MEM does not). And for both kinds of signals analyzed (a positive signal without noise, and a general signal with noise and whose statistics were preliminarily studied) simulations show that BP and CLEAN provide more or less the same performance. On the contrary prior-enhanced-BP does significantly better (here the accuracy is proven from simulations only, as CS gives no theoretical result for these enhanced problems, for the moment)...

while Pierre Vandergheynst finally added:

...another advantage of BP or global minimization algos with respect to greedy (or local minimization) is this possibility of adding external constrains (like positivity). You can't do that too easily with MP for example. Same thing for plugging in deeper statistical models : you can more easily weight BP with a priori than MP (though we've done that in a paper 2 years ago and compared both, see: On the Use of A Priori Information for Sparse Signal Approximations...

This is all great, thank you Laurent, Yves, Pierre for being kind enough to answer. As one can see older algorithms will eventually be included in the CS framework and we can expect that information to lead into improved algorithms. Lawrence Carin is making that sentiment crystal clear with On the Relationship Between Compressive Sensing and Random Sensor Arrays. The abstract reads:

Random sensor arrays are examined from a compressive sensing (CS) perspective. It is demonstrated that the natural random-array projections manifested by the media Green’s function are consistent with the projection-type measurements associated with CS. This linkage allows the use of existing CS theory to quantify the performance of random arrays, of interest for array design. The analysis demonstrates that the CS theory is applicable to arrays in vacuum as well as in the presence of a surrounding media; further, the presence of a surrounding media with known properties may be used to improve array performance.

A very nice paper. Echoing the previous Q/A, we can read:

We demonstrate that these algorithms, as well as RELAX from array processing [15], while developed independently, are highly related to one another (in fact, OMP and CLEAN are essentially the same algorithm).

or

This paper makes the explicit connection between decades-old random sensor arrays and the much newer CS, demonstrating that the former is a special case of the latter. It is therefore not surprising that the aforementioned independently developed algorithms are highly inter-related.

and finally,

A challenge for CS inversion involves a requirement for knowledge of psi, which is sensitive to the exact placement of the antennas and of the surrounding scattering media (if a design like that in Figure 3 is employed). However, a given structure may be “calibrated” to infer psi, by simply performing far-field measurements of e, with a source antenna placed at large R within the aforementioned plane; the array response e is then measured as a function of the source angle . By performing this one-time calibration for a sufficient set of angles  element of [0, 2pi (or desired subset of angles), one may directly measure psi. Once this one-time measurement of psi is performed, “standard” CS inversion algorithms may be used to recover x for an arbitrary source J().

This aspect of CS will clearly become tremendously important in the future. Be it the Random Lens Imager at MIT or the Hyperspectral Imager at Duke, whenever we are designing or spreading the Point Spread Functions or PSF of these systems, we are going to need a simple and not so hard way to implement efficient calibration procedures. In some way this is a simpler problem than the question being asked by Yaron Rachlin and Dror Baron on The Secrecy of Compressive Sensing Measurements ( featured earlier) since here, we have some x's and corresponding y's and are trying to figure out the measurement matrix. This is clearly a simple problem if one has enough samples, but the question is, how can the physics help in determining a low bound for the number of measurements necessary to know all the measurement matrix with a certain accuracy.

In other news three papers showed up on my radar screen: A Simple Method for Sparse Signal Recovery from Noisy Observation Using Kalman Filtering by Avishy Carmi, Pini Gurfil, Dimitri Kanevsky. The abstract reads:

We present a simple method for recovering sparse signals from a series of noisy observations. Our algorithm is a Kalman filter (KF) that utilize a so-called pseudo-measurement technqiue for optimizing the convex minimization problem following from the theory of compressed sensing (CS). Compared to the recently introduced CS-KF in [1] which involves the implementation of an additional CS optimization algorithm (e.g., the Dantzig selector), our method is remarkebly easy to implement as it is exclusively based on the KF formulation. The results of an extensive numerical study are provided demonstrating the performance and viability of the new method.

A Simple Method for Sparse Signal Recovery form Noisy Observations Using Kalman Filtering. Embedding Approximate Quasi-Norms for Improved Accuracy also by Avishy Carmi, Pini Gurfil, Dimitri Kanevsky. The abstract reads:

In a primary research report we have introduced a simple method for recovering sparse signals for a series of noisy observations using a Kalman filter (KF). The new method utilizes a so-called pseudo-measuremnet technique for optimizing the convex minimization problem following from the theory of compressed sensing (CS). The CS-embedded KF approach has shown promising results when applied for reconstruction of linear Gaussian sparse processes.

This report presents an imporved version fo the KF algorithm for the recovery of sparse signals. In this work we substitute the l_1 norm by an appropriate quasi-norm l_p, 0 p 1. This modification which better suits the original combinatorial problem, greatly improves the accuracy of the resulting KF algorithm. This however involves the implementation of an extended KF (EKF) stage for properly computing the state statistics.

If we are talking EKF, I wonder how better performing an algorithms based on the Unscented Kalman Filter (an a-ah moment for me) would do.

Finally, Post-silicon Timing Characterization by Compressed Sensing by Davood Shamsi, Petros Boufounos, Farinaz Koushanfar. The abstract reads

We address post-silicon timing characterization of the unique gate delays and their distributions on each manufactured IC. Our proposed approach is based upon the new theory of compressed sensing that enables efficient sampling and reconstruction of sparse signals using significantly fewer measurements than previously thought possible. The first step in performing timing measurements is to find the sensitizable paths via traditional testing methods. Next, we show that variations are sparse in wavelet domain. Then, using the compressed sensing theory, our method estimates the delay distributions by a small number of timing measurements. We discuss how the post-silicon characterization method can enable a range of new and emerging applications including improved simulation models, post-silicon optimization, and IC fingerprinting. Experimental results on benchmark circuits show that using compressed sensing theory can characterize the post-silicon variations with a mean accurately of 95% in the pertinent sparse basis.

Mike Wakin has written a course on Connexions on Compressive Sensing. Check it out.

A student conference at MIT will feature Srikanth Jagabathula who will talk about Inferring Rankings Under Constrained Sensing. The abstract of his talk reads:

Motivated by applications like elections, web-page ranking, revenue maximization etc., we consider the question of inferring popular rankings using constrained data. More specifically, we consider the problem of inferring a probability distribution over the group of permutations using its first order marginals. We first prove that it is not possible to recover more than O(n) permutations over n elements with the given information. We then provide a simple and novel algorithm that can recover up to O(n) permutations under a natural stochastic model; in this sense, the algorithm is optimal. In certain applications, the interest is in recovering only the most popular (or mode) ranking. As a second result, we provide an algorithm based on the Fourier Transform over the symmetric group to recover the mode under a natural majority condition; the algorithm turns out to be a maximum weight matching on an appropriately defined weighted bipartite graph. The questions considered are also thematically related to Fourier Transforms over the symmetric group and the currently popular topic of compressed sensing.

There is a IEEE Workshop on Statistical Signal Processing in Cardiff, Wales, UK on Aug.31-Sept. 3, 2009. In the submission section, there is a track for compressive sensing and sparse approximation.

• Submission of Proposals for Special Sessions February 9, 2009
  
• Paper submissions April 14, 2009
  
• Notification of acceptance June 15, 2009
  
• Camera ready paper submission June 29, 2009
  
• Advanced Registration June 29, 2009

Credit: Grego!'s flicker photostream, Janis Krum. Images first appeared on Twitter. Plane Crash on Hudson river. I'll definitely consider flying US Airways from now on. Who would have known that Airbus planes floated ?!