CS: Around the blogs in 80 hours, Sparse Recovery Algorithms: Sufficient Conditions in terms of Restricted Isometry Constants and a PhD Position.

Yesterday's entry triggered two comments. One of them reads as follows:

Dear Igor,

You have to be careful: the paper of Candes et al. use an *analysis* prior, which means they consider the L1 norm of the inner product with the atoms, not the L1 norm of the coefficients in the dictionary.

For ortho systems, these are equivalent, but for redundant dictionaries, the more your dictionary is coherent, the more different these two reconstructions differ.

This is why this (wonderful) result tells another story. I think it is important to make the distinction between these "two kinds of L1", analysis vs. synthesis.

For some redundant systems (but not all !), which are tight frames (or approximately tight), like curvelet, etc. this analysis prior makes lots of sense, because for some image classes (eg. cartoon) one knows that the analysis is sparse.

Another fascinating question is for non tight frame analysis prior like TV : what can you tell.

Bob Sturm wrote about the recent Probabilistic Matching Pursuit algorithm featured here recently in :

• Some Experiments with Probabilistic Orthogonal Matching Pursuit
• Paper of the Day (Po'D): The Other Probabilistic Matching Pursuits Edition

Laurent Jacques wonders about a New class of RIP matrices ? What's a submodular function you ask, I am glad you did, I had the same question. Here is an answer.

I mentioned Random Matrix Theory a while back, Terry Tao has some news results that he explains in Random matrices: Localization of the eigenvalues and the necessity of four moments. He makes a reference to the book An Introduction to Random Matrices by Greg Anderson, Alice Guionnet and Ofer Zeitouni. Of related interest:

• Statistical Mechanics and Random Matrices by Alice Guionnet and
• Mean Field Models for Spin Glasses by Michel Talagrand.

Finally, Simon Foucart let me know of one of his proceedings paper entitled: Sparse Recovery Algorithms: Sufficient Conditions in terms of Restricted Isometry Constants. The abstract reads:

We review three recovery algorithms used in Compressive Sensing for the reconstruction s-sparse vectors x 2 CN from the mere knowledge of linear measurements y = Ax 2 Cm, m 'ess than N. For each of the algorithms, we derive improved conditions on the restricted isometry constants of the measurement matrix A that guarantee the success of the reconstruction. These conditions are d2s less than 0.4652 for basis pursuit, d3s less than 0.5 and d2s less than 0.25 for iterative hard thresholding, and d4s less than 0.3843 for compressive sampling matching pursuit. The arguments also applies to almost sparse vectors and corrupted measurements. The analysis of iterative hard thresholding is surprisingly simple. The analysis of basis pursuit features a new inequality that encompasses several inequalities encountered in Compressive Sensing.

Finally, Laurent Jacques is advertizing a PhD position related to compressed sensing:

PhD position on "Solving Optical Inverse Problems by Promoting Sparsity”

Université catholique de Louvain (UCL)
Louvain-la-Neuve, Belgique.

DESCRIPTION:

Nowadays, assuming that a signal (e.g., a 1-D signal, an image or a volume of data) has a sparse representation, i.e., that this signal is linearly described with few elements taken in a suitable basis, is an ubiquitous hypothesis validated in many different scientific domains. Interestingly, this sparsity assumption is the heart of methods solving inverse problems, i.e., estimating a signal from some linear distorting observations. Sparsity stabilizes (or regularizes) these signal estimation techniques often based on L1-norm (or Total Variation norm) minimization and greedy methods.

The PhD project concerns the application of the sparsity principle to solve particular inverse problems occurring in optics. Often with optical sensors, the observation of objects of interest is mainly corrupted by two elements: the noise, either due to the sensor (e.g., electronic/thermic noise) or to the light physics (e.g., Poisson noise), and the Point Spread Function (PSF) of the sensor which blurs (or convolves) the pure image.

The student will develop mathematical methods and algorithms for image denoising and image deconvolution common for confocal microscopy, deflectometry or interferometry, where the sparsity assumption provides significant gains compared to former methods like back-projections, least square methods, or Tikhonov regularization. Connections will be also established with the recent field of compressed sensing, where the sparsity principle really drives the design of innovative optical sensors.

ADVISORS:
* Prof. Philippe Antoine (IMCN, UCL)
* Dr Laurent Jacques (ICTEAM, UCL)
* Prof. C. De Vleeschouwer (ICTEAM, UCL)

COLLABORATORS:
* Prof. François Chaumont (ISV, UCL)
* Prof. Batoko Henri (ISV, UCL)
* Abdelmounaim Errachid (ISV, UCL)

INDUSTRIAL PARTNERSHIP:
* Lambda-X S.A., Nivelles, Belgium.

PROFILE:
* M.Sc. in Applied Mathematics, Physics, Electrical Engineering, or Computer Science;
* Knowledge (even partial) in the following topics constitutes assets:
o Convex Optimization methods,
o Signal/Image Processing,
o Classical Optics,
o Compressed Sensing and inverse problems.
* Experience with Matlab, C and/or C++.
* Good communications skills, both written and oral;
* Speaking fluently in English or French is required. Writing in English is mandatory.

WE OFFER:

* A research position in a dynamic and advanced high-tech environment, working on leading-edge technologies and having many international contacts.
* Funding for the beginning of the thesis with the possibility to extend it by a couple of years or to apply for a Belgian NSF grant.

APPLICATION:

Applications should include a detailed resume, copy of grade sheets for B.Sc. and M.Sc. Names and complete addresses of referees are welcome.

Please send applications by email to

laurent.jacques@uclouvain.be
ph.antoine@uclouvain.be
christophe.devleeschouwer@uclouvain.be

Questions about the subject or the position should be addressed to the same email addresses.

Credit: NASA / JPL / SSI / processed by Astro0/unmannedspaceflight.com, Peering through the fountains of Enceladus, Here, unmannedspaceflight.com forum member Astro0 has combined two frames captured by Cassini during its May 18 encounter with Enceladus to include both the backlit plumes and the background imagery: Titan and the rings.