CS: RIP vs NSP, Clarifications by Jared Tanner and Remi Gribonval

Yesterday's post got some nice feedback. Two things:

• Thank you to Jared Tanner and Remi Gribonval for being kind enough to take some time off to answer yesterday's question.
• I suck as I have covered some of these issues/papers before but cannot seem to have a good grasp on this issue.
  

Here are these answers:

Jared Tanner was the first one to respond to yesterday's post:

Dear Igor,

I just read your Oct. 14th posting on Nuit Blanche where the following question was raised by Giuseppe Paleologo:

"do you know how much weaker is the nullspace property vs. restricted isometry? Are there studies on this?"

and your comment that "I am sure a specialist could clear that up for all of us by sending me a short E-mail." Here are a few take away "bullets", followed by a longer discussion.

a) The RIP is a generic tool that can be used for many algorithms, whenever sparsity is the simplicity being exploited.

b) The NSP is only applicable to sparse approximation questions where there is an "objective", such as l1 minimization.

c) For l1 minimization, the NSP is a weaker assumption than the RIP, see "Compressed Sensing: How sharp is the RIP?" by Blanchard, Cartis, and Tanner.

d) l1 minimization is the only setting where NSP and the RIP have been used to try to answer the same question, and is the only setting where it is fair to compare them. NSP is equivalent to l1 minimization recovery, and for this reason RIP implies the NSP, but not the other way around.

e) Both methods can be used to imply stability.

f) Many matrix ensembles are proven to have bounded RIP (Gaussian, Fourier, etc...). Many matrix ensembles are proven to have the NSP, see " Counting the faces of randomly-projected hypercubes and orthants, with applications" by Donoho and Tanner, to appear in Discrete and Computational Geometry.

Now for the longer discussion:

First of all, what is the NSP? Lets focus on the case of \min \|x\|_1 subject to Ax=b where there is an x_0 that is k-sparse with Ax_0=b and A is of size n by N. (Note the ordering k\lt n \lt N.) min l1 recovers x_0 if and only if thereis no vector \nu in the null space of A such that x_0+\nu is interior to (or intersects the boundary of) the l1 ball defined by \|x_0\|_1. (See image above depicting this, with the blue object being the l1 ball, the yellow circle being x_0 and the red line being the null space of A.) The NSP asks if this occurs for any x_0 that is k sparse, effectively moving x_0 to each of the 2^N (N \choose k) k-faces of the l1 ball. That the null space of A shifted to k-faces of the l1 ball never goes interior probably seems a very strict requirement, but it often holds. In fact, this notion isn't new, it is referred to as "neighborliness" in the convex polytope community. David L. Donoho analyzed this question in detail in 2005, precisely characterizing the values of (k,n,N) when this does and does not hold, see "Neighborly Polytopes and Sparse Solutions of Underdetermined Linear Equations."

How does this compare with RIP? First of all, RIP has nothing to do with l1 minimization, but is clearly a natural property to desire in sparse approximation. This is both the strength and weakness of the RIP. It has been used to prove convergence results for many algorithms, including many for which the null space property would give no information. However, because it is a general tool, the RIP based conditions are generally very restrictive. There is only one venue where it is appropriate to directly compare the null space property and the RIP, this is the recovery results for l1 minimization where both can be used. Not surprisingly, the null space results derived by Donoho are much weaker than associated RIP based results.

This raises a very related point, how does one read RIP based results? When is it true that RIP constants of order 2k are less then 0.45? (See Foucart and Lai, ACHA 2009, pages 395-407 for this l1 recovery condition.) How much more restrictive is it to require RIP constants of order 3k to be less than say 0.2? (See Subspace Pursuit by Dai and Milenkovic.) Some answer this question by saying that matrix class zzz has bounded RIP constants so this is satisfied when n \gt O(k\log(N/k)). Unfortunately, this type of answer does not allow one to distinguish between the above two conditions, and essentially says that all state of the art CS algorithms behave at the optimal order. Although true, this might not be helpful to a practitioner who wants to know what is the best algorithm for them, and how large n must be. To shed some light on this, Jeffrey B. Blanchard, Coralia Cartis, and myself derived improved bounds on the RIP constants for the Gaussian ensemble, and showed how these bounds can be used to make more transparent when the above mentioned conditions are satisfied; allowing one to take the values k,n,N and easily verify if the bound would be satisfied. (Note these bounds require large problem sizes to be effective.) Andrew Thompson joined us to repeat this process for many of the greedy algorithms, see "Phase transitions for greedy sparse approximation algorithms" at: http://www.maths.ed.ac.uk/~tanner/publist.html

Lastly, the NSP and RIP prove a "strong equivalence", that the matrix can be used for compressed sensing of any k sparse vector. There is a less restrictive version of the NSP, which proves what Donoho termed "weak equivalence". Weak equivalence ensures that the matrix can be used for compressed sensing for all but a vanishingly small fraction of k sparse vectors. Note, this is what one observes in practice when
selecting a k sparse vector at random and tests the an algorithms performance. (For a discussion of weak equivalence see "Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing" by Donoho and Tanner.) Efforts are underway to derive weak versions of the RIP, see "Construction of a Large Class of Deterministic Sensing Matrices".

Hope that answers a few questions....

Then, Remi Gribonval sent the following:

Dear Igor,

Regarding the RIP vs NSP discussion, I think our recent IEEE Trans. Inf. Theory paper with Mike Davies pretty much shows how sharper the NSP is wrt the RIP. The paper can be found here and our preprint was discussed on a previous post on Nuit Blanche. We also have a conference paper at SAMPTA09 which considers stable versions of the NSP, seemingly identical to the "truncated NSP" of Wotao Yin and Yilun Wang mentioned in a recent post. This paper is available here.

One way to summarize the results is the following

• Any matrix satisfying the RIP with delta_2m \lt 0.414 (slightly better constants are known) must satisfy the NSP of order m, and L1 minimization therefore recovers all m-sparse vectors.
• There exists matrices with RIP delta_2m arbitrarily close to 1/sqrt(2) which fail to satisfy the NSP of order m, and for which L1 will therefore fail to recover some m-sparse vectors
• Yet, there are matrices with RIP arbitrarily close to 1 which satisfy the NSP of order m, and where L1 is therefore successful.

With this respect,

• The RIP is a sufficient condition to guarantee that the NSP (or, even better, its stable version) is satisfied. The RIP (implicitly, with a small RIP constant) is not necessary to guarantee the recovery of sparse vectors (and the stable approximate recovery of compressible vectors).
• however the RIP seems necessary to guarantee robustness to noise

I guess that similar results would hold for the RIP-1 property and other sufficient conditions which differ from the NSP which is a necessary and sufficient condition. Another line of thought is that of Jared Tanner and David Donoho, where they consider "weak recovery thresholds" for specific families of random matrices, that is to say they allow an exponentially small fraction of m-sparse vectors that may not be recovered. Then, the NSP no longer characterizes the threshold, but the RIP is even less accurate.

I hope that this contributes to clarifying these questions....

@article{Davies:2008ab,
Author = {Davies, M. E. and Gribonval, R{\'e}mi},
Journal = {IEEE Trans. Inform. Theory},
Month = may,
Number = {5},
Pages = {2203--2214},
Title = {Restricted Isometry Constants where $\ell^p$ sparse recovery can fail for $0 <>
Volume = {55},
Year = {2009}}

@inproceedings{Davies:2009aa,
Address = {Marseille, France},
Author = {Davies, M. E. and Gribonval, R{\'e}mi},
Booktitle = {Proc. SAMPTA'09 (Sampling Theory and Applications)},
Month = {may},
Title = {On Lp minimisation, instance optimality, and restricted isometry constants for sparse approximation},
Year = {2009}}

Thank you Jared and Remi !

CS: RIP vs NSP, Deterministic Sensing Matrices with Statistical Isometry Property , Modified Basis Pursuit Denoising,

When listening to the beginning of this video entitled Gutenberg and the Monks, Seth Godin introduces the subject with this amusing little story:

So it's a few hundred year ago and one the most famous German of all time says

"I have this really cool thing, I have invented it, it's called the printing press and what we can do is print a lots of copies and ship them all around the country they can put them on display and when they don't sell them they can ship them back and we'll shred them and then we can print more copies."

And I would imagine a conversation when he announced this and the monks said:

"Well, that's all well and good but will this impact our ability to sit in a dark quiet abbey and do calligraphy all day ?"

To which he responded

"Well it doesn't really help your ability to do calligraphy all day, and in fact it's a totally different way of going about doing what you do."

and in response most of the monks, my guess, said:

"Well we are really busy let us know how it goes."

I cannot but help thinking that you could replace some of these words with compressive sensing if instead of looking at increment of current technologies, CS were to be judiciously applied to new hardware. The new hardware must absolutely bring a new dimension to the data gathering process and its eventual use. So much so that the current technology players would have to look at it and say in unison: Well we are really busy let us know how it goes.

Giuseppe Paleologo on Twitter, asks the following burning question:

@igorcarron do you know how much weaker is the nullspace property vs. restricted isometry? Are there studies on this? #compressedsensing

My recollection is that there isn't, however, there seems to be that there is an issue about whether one property is stronger than the other (especially considering that there seems to be different definition for the Null Space Property). See this recent entry for a view on this. In all, I think somebody ought to write a paper on this as it clearly is an issue some people (including me) would like to have a closure on. Then again, I am sure a specialist could clear that up for all of us by sending me a short E-mail. I'll make sure it gets wide publicity.

Checking for RIP is hard, this is why some are looking at building deterministic sensing matrices with some similar property as shown in Construction of a Large Class of Deterministic Sensing Matrices that Satisfy a Statistical Isometry Property by Robert Calderbank, Stephen Howard, Sina Jafarpour. The abstract reads:

Compressed Sensing aims to capture attributes of $k$-sparse signals using very few measurements. In the standard Compressed Sensing paradigm, the $\m\times \n$ measurement matrix $\A$ is required to act as a near isometry on the set of all $k$-sparse signals (Restricted Isometry Property or RIP). Although it is known that certain probabilistic processes generate $\m \times \n$ matrices that satisfy RIP with high probability, there is no practical algorithm for verifying whether a given sensing matrix $\A$ has this property, crucial for the feasibility of the standard recovery algorithms. In contrast this paper provides simple criteria that guarantee that a deterministic sensing matrix satisfying these criteria acts as a near isometry on an overwhelming majority of $k$-sparse signals; in particular, most such signals have a unique representation in the measurement domain. Probability still plays a critical role, but it enters the signal model rather than the construction of the sensing matrix. We require the columns of the sensing matrix to form a group under pointwise multiplication. The construction allows recovery methods for which the expected performance is sub-linear in $\n$, and only quadratic in $\m$; the focus on expected performance is more typical of mainstream signal processing than the worst-case analysis that prevails in standard Compressed Sensing. Our framework encompasses many families of deterministic sensing matrices, including those formed from discrete chirps, Delsarte-Goethals codes, and extended BCH codes.

Also found on Arxiv: Modified Basis Pursuit Denoising (MODIFIED-BPDN) for Noisy Compressive Sensing with Partially Known Support by Wei Lu, Namrata Vaswani. The abstract reads:

In this work, we study the problem of reconstructing a sparse signal from a limited number of linear 'incoherent' noisy measurements, when a part of its support is known. The known part of the support may be available from prior knowledge or from the previous time instant (in applications requiring recursive reconstruction of a time sequence of sparse signals, e.g. dynamic MRI). We study a modification of Basis Pursuit Denoising (BPDN) and bound its reconstruction error. A key feature of our work is that the bounds that we obtain are computable. Hence, we are able to use Monte Carlo to study their average behavior as the size of the unknown support increases. We also demonstrate that when the unknown support size is small, modified-BPDN bounds are much tighter than those for BPDN, and hold under much weaker sufficient conditions (require fewer measurements).

CS: Model-Based Compressive Sensing

Woohoo. If you recall, Model-based compressive sensing is a way of acquiring less compressive sensing signals than usual by using the tree-like structure of images in wavelet bases. The authors at Rice Richard Baraniuk, Volkan Cevher, Marco Duarte, Chinmay Hegde, Michael Wakin have written the following papers on it (Preprint, SPARS 2009, CISS 2009, NIPS 2008, ICASSP 2008, SPARS 2005). They have released the attendant toolbox. From the website:

The standard compressive sensing (CS) theory dictates that robust signal recovery is possible from $M=O(K\log(N/K))$ measurements. We demonstrate that it is possible to substantially decrease $M$ without sacrificing robustness by leveraging more realistic signal models that go beyond simple sparsity and compressibility by including dependencies between values and locations of the signal coefficients.

We have designed algorithms that enable fast recovery of piecewise smooth signals - sparse signals that have a distinct "connected tree" structure in the wavelet domain. Our Tree Matching Pursuit (TMP) algorithm significantly reduces the search space of the traditional Matching Pursuit greedy algorithm, resulting in a substantial decrease in computational complexity for recovering piecewise smooth signals. Our Hidden Markov Tree-based Reweighted $\ell_1$-norm minimization algorithm leverages the probabilistic model for wavelet-sparse signals to enable a reduction on the number of measurements necessary for recovery. An additional advantage of these algorithms is that they perform an implicit regularization to combat noise in the reconstruction.

We also propose a union-of-subspaces model-based CS theory that parallels the conventional theory and provides concrete guidelines on how to create model-based recovery algorithms with provable performance guarantees. For some well-suited signal models, we can provably offer robust recovery from just $M=O(K)$ measurements.

CS: Wavefront Coding for Random Lens Imagers ?

Do you recall that question I asked a while back to Rich Baraniuk annd Justin Romberg about the reason why the soccer ball image from the single pixel camera was Ok but still kind of blurry (this was a question initially asked by an anonymous commenter on the blog) ?

Do you recall the so-so quality of the reconstruction of the random lens imager ?

Maybe part of the issue is that, in either cases, the light wavefront phase was not considered in the calibration process. Indeed, if you recall the calibration process of the random lens imager, it does not into account for this parameter:

In a totally different area, Allard Mosk and Ivo Vellekoop [1] [2] are concerned, among other things, with light delivery in human tissues. One of the problems with human tissue is its extraordinary diffusivity. Some folks spent much time trying to compute light dispersion through these tissues in order to detect specific cancers or known markers and so forth. In effect, they either are solving an inverse problem with the diffusion equation and some are even heroic to the point of doing it with the full transport (or radiative transfer) equation. In the problem of delivering light to a specific area inside the body, one has to control the forward problem. In their recent publication [1][2] Allard Mosk and Ivo Vellekoop show that by modulating the phase of an incoming light beam through the use of an SLM they can rectify the direction of the light after it has gone through a random medium (also called 'opaque lens') as shown in the diagram below:




In their more recent paper, Ivo Vellekoop, A. Lagendijk and Allard Mosk have essentially achieved a higher focusing capability than what would be offered by a simple lens thanks to the use of a random medium.


This is explained in their recent Exploiting disorder for perfect focusing. The abstract reads:

We demonstrate experimentally that disordered scattering can be used to improve, rather than deteriorate, the focusing resolution of a lens. By using wavefront shaping to compensate for scattering, light was focused to a spot as small as one tenth of the diraction limit of the lens. We show both experimentally and theoretically that it is the scattering medium, rather than the lens, that determines the width of the focus. Despite the disordered propagation of the light, the prole of the focus was always exactly equal to the theoretical best focus that we derived.

One cannot escape the similarities between these figures and the ones above for the random lens imager. Figure 2.a is the same beam of light through a simple lens, Figure 2.b, is the random projection of the same single beam of light after it has gone through the random/opaque material. Figure 2.d is the configuration of the SLM that allows the initial beam of light to be focused. Figure 2.c is the resulting beam of light modulated with the SLM configuration in 2.d after it has gone through the random/opaque material. In other words, Figure 2.b is the random projection of a dirac like input in about the same way as in the Random Lens imager case.

What is very interesting from this paper is that they have an analog algorithm that allows them to go through a series of SLM configurations that eventually provides a single focused beam. For any random medium, they can find a certain SLM configuration so that a focused beam comes out on the outside. In effect, they are solving a calibration issue. In the random lens imager case, calibration is performed by sending several coded signals (not phase coded) and by gathering their responses. This collection of responses is then used to produce a dictionary. The dictionary is then used to build future images obtained from the random lens imager. What this paper shows is that the random medium provides phase modulation and that any random lens imager should need a calibration step that includes some phase information.

Other cameras designs that are either affected by this issue or are solving the phase coding problem include:

• Heterodyning Light Photography of Ashok Veeraraghavan, Ramesh Raskar, Amit Agrawal, Ankit Mohan and Jack Tumblin
• The Reference Structure work of David Brady and his team.
• Random Convolution Imager of Justin Romberg,

At my low level, my question is how can we build a dirt cheap random lens imager that integrates an SLM and can be calibrated in a simple (albeit slow) fashion ?

Thank you to Laurent Jacques for pointing me to this very nice work. We have to thank the Arxiv blog for raising, once again, our awareness on this issue.

References:

[1] I.M. Vellekoop and A.P. Mosk, Universal optimal transmission of light through disordered materials
[2] I. M. Vellekoop, and A. P. Mosk, Phase control algorithms for focusing light through turbid media
[3] Rice Compressive Sensing Single Pixel Camera using 40% samples.

CS: Video of Dror Baron at Google on CS-BP

As an add-on to the last entry, Dror Baron just gave a talk at Google.



The belief propagation algorithm is explained starting here.


At 1 hour into the talk, Dror and Muthu briefly try to evaluate how a new algorithm (different from BP) fares with regards to the group testing based reconstruction solvers. Dror then goes on to explain some of the differences between the generic Compressed Sensing setting and that found in Finance where Hedge funds or high frequency traders are trying to devise the future of a stock price. The video will be added to the compressive sensing video page.

CS: LP Decoding meets LP Decoding: A Connection between Channel Coding and Compressed Sensing, A Q&A with Dror Baron and Dongning Guo/ Two jobs

Baam!...Today we have some deep impact stuff. First, recall that LCROSS will smash on the Moon in exactly six hours and thirty minutes (at 6:31 CST or 12:31 GMT) and you can watch it live. Let us note that it was re-targeted thanks to the recent observations of the Japanese Kaguya probe. Second, we have a new paper, a Q&A with authors of another and two job offers.

Before all that, there is an interview by Kareem Carr of Terry Tao and how he does it all (including the blogging thing). Israel Gelfand passed away, I am sure he is the one who gave his name to the Gelfand's width, a subject related to CS. Terry Tao has an entry on him. Lei Yu, Laurent Jacques, Dirk Lorenz agree that this paper answers Angshul Majumdar's question of yesterday. Dirk also mentions another paper. Thanks guys! The second question of yesterday's entry might find an answer in the first job offer at the end of this entry. Let's explore the deep impact stuff now. By the way the first article might answer a recent commenter's question on Terry's blog. Here it is:

LP Decoding meets LP Decoding: A Connection between Channel Coding and Compressed Sensing by Alexandros Dimakis and Pascal Vontobel. The abstract reads:

This is a tale of two linear programming decoders, namely channel coding linear programming decoding (CCLPD) and compressed sensing linear programming decoding (CS-LPD). So far, they have evolved quite independently. The aim of the present paper is to show that there is a tight connection between, on the one hand, CS-LPD based on a zero-one measurement matrix over the reals and, on the other hand, CC-LPD of the binary linear code that is obtained by viewing this measurement matrix as a binary parity-check matrix. This connection allows one to translate performance guarantees from one setup to the other.

The slides of the presentation can be found here. Alex summed it nicely for me in a short email conversation:

...The paper connects the channel coding problem to compressed sensing. The result is if a binary code corrects k errors under Feldman's LP decoding (that is a LP relaxation of the channel coding problem ) then the same (0,1) matrix, (taken over the reals) recovers all k-sparse signals. Further if it corrects a given set of errors, you can recover the same sparsity in a signal, and there are channel coding conditions that correspond to l1/l1 robust recovery and l2/l1 robust recovery. This means that you can use error correcting code parity check matrices as measurement matrices and you can transfer theoretical results from coding theory into compressed sensing

Thanks Alex !

I was struck by Dongning Guo, Dror Baron, and Shlomo Shamai's paper (mentionned here) entitled A Single-letter Characterization of Optimal Noisy Compressed Sensing. and specifically these excerpts:

"...What can one infer about an individual element of the sparse signal based on the measurements?...Taking another perspective, we can say that whatever one can infer about an input element of the sparse signal based on the measurements is asymptotically identical to what one can infer about the same element if all other input elements were zero, but the measurements were noisier...The single-letter characterization of the marginal posterior distribution leads to a simple characterization of all other elemental metrics of the CS problem, such as the minimum mean-square error (MMSE), the error probability, the entropy, etc. This result is convenient for many practical purposes, for example, to determine the number of measurements and the SNR required for achieving a certain quality of reconstruction. We note that the results in this paper also advance the understanding of the fundamental nature of noisy CS by describing a boundary between what is physically possible and what is not. Another sharp characterization of phase transition deals only with noiseless measurements [3], [4]. The result in this paper is thus sharper than many other results on noisy CS obtained using the restricted isometry property developed in [5]....It is found that sparse measurement matrices perform just as well; and BP is asymptotically optimal in case of sparse mesurement matrix....This suggests that for relatively large systems, one should prefer to use sparse measurement matrices so that low-complexity algorithms such as belief propagation can exploit the sparsity of the measurement matrix without sacrificing the estimation performance..."

So I went ahead and asked Dror Baron and Dongning Guo several questions:

Igor: I think I get most of the paper which eventually points to using sparse matrices for large problems because the Belief Propagation algorithm would do well there. Is that correct?

Dror: Absolutely 100% correct. Not only "do well," CS-BP is asymptotically optimal under many circumstances. In particular, in case the fixed-point equation has a unique solution, nothing can do non-negligibly better in the Bayesian setting. We now know that the "nice graphs" in the CS-BP journal paper were not "good luck" this is a great algorithm. Shriram Sarvotham (and later Danny Bickson) did great work. The quality of implementation of CS-BP is a factor. Danny Bickson's implementation is good but we're still working on it, and we're making progress.

Dongning Guo also joined the discussion and highlighted the following:

One crucial point that is not elaborated in the Allerton paper is that BP is known to be optimal only when the fixed-point equation has a unique solution. The single-letter characterization of BP is rigorous, but the iterative formula for eta^t may not converge to the optimal performance. This does not mean the BP performs poorly in these cases. It is widely believed that in those cases where BP is not optimal, it is pretty much as good as any other algorithms that perform local computations instead of seeking global optimality. It is not immediately clear whether L1 optimization performs better than BP. This is a delicate issue, and we hope to elaborate on this in the future.

Igor: I was wondering the following, how hard would it be to have similar figures of phase transitions as the one shown by Tanner but for noisy signals ? In the end, I believe this is the figure of merit that people like me would react to.

Dror: With noisy signals there is no sharp transition a la Donoho-Tanner, instead there is a graceful degradation. You add a bit more noise or remove a few measurements, and estimation quality will degrade just a bit. You probably saw the "degradation" term eta in our paper. Eta should usually be continuous in the parameters (measurement ratio mu and signal to noise ratio gamma). Depending on the parameters, there could be phase transition in eta and hence in the performance. We are currently studying this phenomenon.

Igor: Do you have the code that allowed to produce figure 2 ?

Dror: Yes, definitely, I did that code. We are trying to put together a software platform that computes the CS characterization for a range of cases.

Igor: Finally, I am not sure if this is a usual way of expressing oneself in your part of the literature, but I was a little uneasy about this "single letter" term, why didn't you choose the term "single parameter" instead, is there too much possibility for people to get confused with that parameter term and the lingo used in the bayesian framework ?

Dror: The "single-letter" terminology is well-accepted in information theory. Basically it means that the performance of a large system (e.g., long block length or many measurements) is characterized by formulas based on the distribution of one or a few random variables independent of the size of the system. In the compressed sensing context, as you scale up the size of the problem (M and N) with a fixed ratio M/N, the asymptotic posterior distribution of any component of the signal is characterized as the posterior of a scalar channel, which does not depend on the size (M,N). Note that the posterior is a sufficient statistic, it will give you any performance metric you like:

1. Mean square error (MSE) such as the very recent nice paper by Rangan-Fletcher-Goyal, which relies on Dongning's work with Sergio Verdu in 2005.
2. Correct evaluation of support set for strictly sparse signals (Wainwright's metric; RFG and Akcakaya-Tarokh also like this metric).
3. Mean ell_1 error.
4. etc.

Igor: One more thing, do the sparse measurement matrices have to have certain characteristics ? do they need to fullfill some type of condition ?

Dror: Minor technical conditions.

Igor: I realize it is somehow unfair to compare a bayesian reconstruction solver with other reconstruction solvers, as the bayesian solver gives more information in the end, but in terms of rapidity what are the order of magnitude difference in time needed to reconstruct a signal between the CS-BP and say GPSR, SPGL1,...

Dror: I have not compared with SPGL1. However, in our paper on CS-BP we have shown that for inputs of length N=10,000 GPSR is twice faster than CS-BP and scales worse; we expect CS-BP to be faster for problems of length N=20,000. Additionally, I believe that Danny Bickson is trying to improve the implementation, and I greatly respect his expertise in this arena.

Igor: Finally, a real dumb and open question, Yilun Wang and Wotao Yin (featured here: http://nuit-blanche.blogspot.com/2009/09/cs-isd-new-compressed-sensing-algorithm.html) devised an algorithm to reconstruct a signal based on keeping the same number of measurements, do you think CS-BP could help in that type of problematic (you are given only a certain number of measurements and you are looking through the appropriate measurements within the initial set to reconstruct the signal as best as possible) ?

Dror: For sparse matrices, and given the input statistics, CS-BP is asymptotically optimal (or near-optimal), and will extract as much information from the measurements as any other algorithm.

Thanks Dror and Dongning !

Finally, Laurent Daudet just sent me a Postoc job offer in Paris which has been added to the Compressive Sensing Jobs page:

One-year post-doctoral position : Compressed Sensing for acoustic imaging

Deadline: 25/10/2009


CONTEXT

New sampling methods, known as « compressed sensing », allow the acquisition of signals at a potentially much lower data rate than in the classical (Shannon-type) framework, by taking into account the sparse structure of the signals in well-chosen bases. The analysis of acoustical fields is one of the natural applications of this theory. This is the topic of the ECHANGE (new generation of acoustic sampling) project, funded by the French National Research Agency (ANR), that provides funding for this 1-year post-doctoral position.


The hired post-doctoral researcher will be at the junction between experimentalists (MPIA team of the D’Alembert Institute of mechanical engineering, University Paris 06), and specialists of acoustical signal processing (Langevin Institute « Waves and Images »). The goal will be to propose new theoretical and/or algorithmic frameworks, for the application of compressed sensing to various scenario of acoustical imaging. One such scenario could be the adaptation of beamforming techniques for the localization and characterization of acoustical sources (in terms of elementary sources).



In particular, this job involves
• Taking an active part in the scientific / technical aspects of the project :
• Developing new algorithms, in constant interaction with experimentalists ; testing these ideas with strict evaluation protocols, comparison with state-of-the-art.
• Work planning and supervision ;
• Writing scientific articles. Presenting the work at national / international conferences and meetings of the ECHANGE consortium ;
• Taking part in the writing of deliverables ;
• Taking part in some administrative tasks related to the project (meetings organization, writing minutes, etc.).


REQUIRED QUALIFICATION
A PhD (/doctorate), or equivalent, in applied mathematics, signal processing, or acoustics.


REQUIRED EXPERTISE
Perfect knowledge of digital signal processing
Confirmed expertise in at least one of these fields : compressed sensing OR sparse representations OR inverse problems OR acoustic imaging.
Proficiency with Matlab
Excellent written and spoken English


Would be a plus :

Knowledge of C/C++, open-source and cross-platform projects (Unix / MacOS / Windows)
Experience with ANR-funded research


The candidate must show good communication skills, and be an excellent team player. He/she must like research at the junction of theory and experiments. He/she must be well organized and be able to work autonomously.



CONTRACT DURATION AND SALARY
12 month contract
Gross monthly salary of about 2200 euro.

START DATE
01.01.2010, or soon thereafter

PLACE OF WORK
Institut Langevin « Ondes et Images » (LOA)
ESPCI 10 rue Vauquelin 75231 Paris Cedex 05 – FRANCE
http://www.institut-langevin.espci.fr/Langevin-Institute
ideally located in the middle of Paris “Montagne Sainte-Geneviève” hub of scientific research, and quintessential parisian “Mouffetard” neighborhood.

Regular visits to Institut Jean Le Rond d’Alembert, Saint-Cyr-L’Ecole (suburbs of Paris).


SCIENTIFIC SUPERVISION
Laurent Daudet : laurent.daudet@espci.fr
Professor at Université Paris Diderot – Paris 7
Contact person for informal enquiries.


HOW TO APPLY
e-mail only application (cover letter, detailed resume, list of publications and list of max 5 references with contact email) to laurent.daudet@espci.fr
with cc to François Ollivier francois.ollivier@upmc.fr

The deadline for application is 25/10/2009.

And another one:

October 6, 2009, Postdoctoral Positions in Wireless Communications

Employer: University of Vigo (Doctoral University)
Location: Vigo, Spain
Category: Postdoc/Graduate Assistant position of:
Others (Communication)
Posted: Oct. 06, 2009
Description & Requirement

DESCRIPTION

The Signal Processing in Communications Group (GPSC, www.gts.tsc.uvigo.es/gpsc ), affiliated with the Department of Signal Theory and Communications at University of Vigo, Spain, invites applications for one postdoctoral position in the field of wireless communications. The selected candidates will join GPSC to investigate fundamentals and algorithm design/evaluation for communication and sensor networks.
Areas of particular interest include:
- Sensor networks
- Cognitive Radio
- Compressed Sensing

GPSC is formed by 6 faculty members from the University of Vigo as well as several MSc and PhD students, and participates in several research projects funded by the European Commission and the Spanish Government. Among these, the recently launched COMONSENS project (www.comonsens.org) integrates investigators from 10 different top research institutions in Spain. GPSC members also actively collaborate with the Galician R&D Center in Advanced Telecommunications (GRADIANT, www.gradiant.org ) in diverse contracts with ICT companies. Thus, the selected candidates will enjoy unique opportunities to participate in exciting research projects with both industry and academia.

DESIRABLE BACKGROUND

• A Ph.D. degree in Electrical Engineering is required; PhD obtained before January 1, 2007
• Knowledge and experience in sensor networks, cognitive radio and/or compressed sensing
• Good verbal and written skills in English are required
• Strong publications in international conferences and journals in the area of communications
• Postdoctoral experience in a recognized group with expertise in the field is a plus
• Experience in the organization, management and training of technical staff/students is a plus
• Communication, computing and interpersonal skills are important
• Capacity to work both independently and within a team

Application

Applications should include electronic copies of the following:
• A detailed Curriculum Vitae. (*Please include your e-mail address and a recent picture.)
• A cover letter addressing the specified job qualifications.
• A letter of recommendation by a senior Professor/Researcher.
• A copy of the publication deemed as best representative of the candidate’s creative research.
Priority consideration will be given to applications received by November 1, 2009. Applications will be accepted until position is filled.

Contact: Nuria González Prelcic
Departamento de Teoría de la Señal y Comunicaciones
ETSET. University of Vigo
36310 Vigo. Spain
Phone: +34 986 818656, e-mail: nuria@gts.tsc.uvigo.es

CS: Questions on IST, Audio CS and anoter GPR

I get often different questions from different types of readers and sometimes I cannot think of an answer right away and I find somebody who can or I blog about it. Today I have two questions, if you have an answer, please feel free to answer in the comment or send me a blurb. In the latter case, please also let me know if you want me to use your name:

Angshul Majumdar asked me the following question:

Can you please refer a paper, where it is being derived that the Iterative Soft Thresholding is actually solving the l1 regularized least squares problem?

Any specialists out there can help ?

Another reader who shall remain nameless asked the following question:

I have a problem about compressed sensing. My major project is "compressed sensing of audio signal using multiple sensor". Can you help me about method of compressed sensing audio using multiple sensor ?

It looks like an assignment of some sort but I very glad this person asked the question as this was a subject of a conversation I had with some of you including Bob Sturm. The issue at hand is really interesting in that recording is a well known business and plenty of actors in that field have very different offerings in terms of low and high end equipment. So the idea is really, how does a Compressed Sensing method of acquiring an audio signal become disruptive compared to the well established industry ? My take and it is a crazy one, is to see if we can let Nature help. Instead of Imaging with Nature (TM), what about performing Audio with Nature. Any thoughts from any of you on this would be very much welcome. By the way, I am half kidding when I say that we ought to be thinking on how we could perform audio recording on a pottery which we all know is a myth.

In a different area, yesterday, I mentioned a Step-Frequency Radar with Compressive Sampling (SFR-CS) concept out of the Drexel. As an anonymous reader pointed out, the claim of being the first might not be entirely accurate. From the comment:

The authors say "The application of compressive sampling to narrow-band radar systems was recently investigated in [2], [3] and [4], [5], and [6]. The application of CS on SFR has not been investigated before."

Hadn't Gurbuz, McLellan and Scott done GPR using stepped frequency radar in "A Compressive Sensing Data Acquisition and Imaging Method for Stepped Frequency GPRs," IEEE Transactions in Signal Processing, vol. 57, issue 7, pp. 2640-2650 (2009)

That paper is here behind a paywall. I had heard about it only through a talk given at Rice. Thank you anonymous reader !

CS: Step-Frequency Radar with Compressive Sampling (SFR-CS)

Here is an application of compressive sensing to a specific type of radar. The description of the approach is given in Step-Frequency Radar with Compressive Sampling (SFR-CS) by Sagar Shah, Yao Yu, Athina Petropulu. The abstract reads:

Step-frequency radar (SFR) is a high resolution radar approach, where multiple pulses are transmitted at different frequencies, covering a wide spectrum. The obtained resolution directly depends on the total bandwidth used, or equivalently, the number of transmitted pulses. This paper proposes a novel SFR system, namely SFR with compressive sampling (SFRCS), that achieves the same resolution as a conventional SFR, while using significantly reduced bandwidth, or equivalently, transmitting significantly fewer pulses. This bandwidth reduction is accomplished by employing compressive sampling ideas and exploiting the sparseness of targets in the range velocity space.

I'll add it to the Compressive Sensing Hardware page shortly.