Post-doctoral / Internship position in Multiscale/Multirate Image Processing with Applications in the Geosciences

Laurent Duval a reader of this blog has a postdoc position (which does not require an understanding of compressive sensing):

Subject: Job: Post-doctoral / Internship position in Multiscale/Multirate Image Processing with Applications in the Geosciences

Organization: IFP
Location: Rueil-Malmaison, France
Deadline: Open until filled (beginning 2nd semester 2009)
Duration: 12 months
Gross salary: from ~2400 euros

Context:
IFP has an opening for a post-doctoral position in its Technology, Computer Science and Applied Mathematics Department. IFP is located in Rueil-Malmaison, France, near Paris. The position offers the possibility of collaboration with the Signal and Communications group at University Paris-Est.

IFP is a world-class public-sector research and training center, aimed at developing the technologies and materials of the future in fields of energy, transport and the environment. It provides public and industry stakeholders with innovative solutions for a smooth transition to the more efficient, more economical, cleaner and sustainable energies and materials of the future.

IFP fosters knowledge transfer between long-term fundamental research, applied research and industrial development in keeping with the recommendations of the Barcelona European Council held in March 2002. IFP is funded both by a State budget and by resources provided by private French and foreign international partners.

More information on the Web :
http://www.ifp.fr/
http://www.ifp.com/
http://www-igm.univ-mlv.fr/LabInfo/equipe/signal
http://www-syscom.univ-mlv.fr/~pesquet/

Topic:
The topic proposed for this post-doctoral position is focused on the analysis of geophysical data and their filtering with the help of multiscale/multirate image processing algorithms. Historically, the complexity of seismic data and its interpretation have contributed to the development of several efficient signal processing tools such as the wavelet transform.

In certain seismic data however, different wave types mixed together cannot be separated easily by standard random noise filtering schemes. In order to remedy this issue, efforts have been underway to use models that can be partially matched with data in order to allow for adaptive identification or subtraction.

The aim of the proposed work is to develop innovative techniques for multiscale/ multirate data/model matching. The eventual goal is to exploit simultaneously model and sparse features in the transformed domain with the recently developed directional wavelets and filter banks, based on local multiscale attributes.

While the proposed subject is focused on seismic applications, it is strongly related to more general issues in model based signal processing and detection theory, found in many areas of engineering and science.

Related references:
-C. Chaux et al., 2006, IEEE Trans. Image Processing 15(8) 2397-2412, doi: 10.1109/TIP.2006.875178
Image Analysis Using a Dual-Tree M-Band Wavelet Transform

-A. Droujinine, 2006, J. Geophys. Eng. 3 59-81, doi: 10.1088/1742-2132/3/1/008
Multi-scale geophysical data analysis using the eigenimage discrete wavelet transform

-J. Gauthier et al., 2009, IEEE Trans. Signal Processing, doi: 10.1109/TSP.2009.2023947
Optimization of Synthesis Oversampled Complex Filter Banks


Qualifications:
(1) A PhD degree in Electrical Engineering (signal or image processing,
computer vision, Computer Science, Applied Mathematics), or other related
experience;
(2) Programming skills with MATLAB and C/C++;
(3) Excellent skills in signal/image analysis;
(4) Knowledge in Geophysics is desirable but not required;
(5) Knowledge in wavelets and filter banks is highly desirable.

Application procedure:
Candidates should send an application letter with a PDF detailed CV, together with a list of publications, a PDF copy of their PhD Thesis and at least two reference letters.

Documents should be sent at: laurent(dot)duval(at)ifp.fr

For further information, please contact:
Laurent Duval
IFP, R1130R
1 et 4 avenue de Bois-Preau
F-92852 Rueil-Malmaison Cedex
Tel: +33 1 47 52 61 02
Tel: +33 1 47 52 70 12

CS: Sparse Recovery with Pre-Gaussian Random Matrices

Sparse Recovery with Pre-Gaussian Random Matrices by Simon Foucart, Ming-Jun Lai.The abstract reads:

We show that a matrix whose entries are independent copies of a symmetric pre-Gaussian random variable possesses, with overwhelming probability, a Modified Restricted Isometry Property in q-quasinorms for 0 \lt q \le 1/3. We then prove that, if the matrix of an underdetermined linear system of equations satisfies this property, then the sparsest solution of the system can be found using l_q-minimization.

Credit: 808caver, Moonbow over Venus, when light reflected from the Moon shines on rain at night.

CS: Update on "A Simple Compressive Sensing Algorithm for Parallel Many-Core Architectures", Saturn Equinox

Jerome Darbon just let me know the following

We have just updated our report "A Simple Compressive Sensing Algorithm for Parallel Many-Core Architectures", Alexandre Borghi, Jerome Darbon, Sylvain Peyronnet, Tony Chan and Stanley Osher. We have added more experiments including time results for the newest Nvidia GPUs and multi-cores of Intel. You might be interested by these new results.

The new version is available here:

ftp://ftp.math.ucla.edu/pub/camreport/cam08-64.pdf

or as a webpage here:

http://jerome.berbiqui.org/parallel-many-core-CS/

This is very interesting as we now have information about what happens beyond some toy models. The first version of this paper was covered earlier when it came out. Let us note that other authors and teams have since used GPUs to perform the compressive sensing reconstruction (see the second part of the Compressive Sensing Hardware page). From that list, there are four:

2.1 UCLA GPU/Multicore solver.

2.2 University of Calgary GPU solver.

2.3 Graz University of Technology GPU solver

2.4 University of Wisconsin Implementation of SpaRSA on a GPU

Let us note that the SpaRSA paper is specifically designed around implementing non greedy solver on the GPU. One should also keep in mind, as I mentioned earlier this year, that there is always the Jacket product allowing Matlab to GPU programming. The paper of Jerome and co-workers covers multicore CPUs, an area of investigation left untouched by the other investigations, even though it looks like this type of approach is bound for a bright future. Thanks Jerome for the heads-up!

By the way, today is Saturn Equinox, an event that takes place every fifteen years, which means two things:

• If you are trying to watch Saturn tonight on a nice summer night, there will be no rings for you.
• Low incidence light from the Sun translates into very large shadows, check out More Saturn ring awesomeness

Image Credit: NASA/JPL/Space Science Institute.

CS: A Short Note on Compressed Sensing, Non-Iterative Reweighted-Norm Least-Squares Local l_0 Minimization, CVPR09 and a talk

Today, we have two papers, some conference papers and a presentation, here we go:

A Short Note on Compressed Sensing with Partially Known Signal Support by Laurent Jacques. The abstract reads:

In this short note, we propose another demonstration of the recovery of sparse signals in Compressed Sensing when their support is partially known. In particular, without very surprising conclusion, this paper extends the results presented recently in [VL09] to the cases of compressible signals and noisy measurements by slightly adapting the proof developed in [Can08].

Laurent also mentions on his page that if somebody finds an error he would be happy to get your feedback.

Non-Iterative Reweighted-Norm Least-Squares Local l_0 Minimization for Sparse Solutions to Underdetermined Linear System of Equations by Andrew Yagle. The abstract reads:

We present a non-iterative algorithm for computing sparse solutions to underdetermined M×N linear systems of equations. The algorithm computes a solution which is a local minimum of the l_0 norm (number of nonzero values) obtained from the l_1 norm (sum of absolute values) minimum. At each step, it uses reweighted-norm least-squares minimization to compute the l_pp norm for values of p decreasing from 2 to 0. The result is similar to the l_1 solution, but uses less computation (solution of ten M×M systems of equations), and there are no convergence issues.

Andy makes the difference between iteration and recursion. I think his approach is different compared to the current reweighted l_p strategies. I look forward to someone implementing this algorithm.

The CVPR '09 paper that are on the web are listed here.

Frank Curtis will make a presentation at Lehigh University, Bethlehem, PA on 19-21 August 2009 with the title: A Sequential Quadratic Programming Method for Nonsmooth Optimization
The desscription of the talk:

Algorithms for the solution of smooth, constrained optimization problems have enjoyed great successes in recent years. In particular, the framework known as sequential quadratic programming (SQP) has been studied and applied to a variety of interesting applications. Similarly, there has been a great deal of recent work on the solution of nonsmooth, unconstrained optimization applications. One approach that has been successful in this context is gradient sampling (GS) — a method that, unlike the many variations of bundle methods, only requires the computation of gradients during the solution process. In this talk, we combine elements of SQP and GS to create an algorithm for nonsmooth, constrained optimization and illustrate the potential for such an approach on illustrative test problems in eigenvalue optimization and compressed sensing.

Credit: NASA/JPL/Space Science Institute, Punching through the F Ring, Released: August 7, 2009 (PIA 11662). Something is going through Saturn's F ring as it turns out Saturn's Equinox comes up every fifteen years and this inclination allows one to see in greater details things that are going through the rings. Via Bad Astronomy Blog. This is interesting, as we recently saw comets hitting Jupiter in a fifteen year interval. I know this sound stupid but has anyone evalute if the angle of inclination of this "thing" is the same as that of the other "thing" that Jupiter two weeks ago ?

Ensemble Averaging Love

Well now that the Netflix competition is over, the folks at Netflix thinks they can up the ante of the suspense that occured in the first contest by having a second contest. Woohoo! It's all fine and dandy but I keep on having mixed feelings about putting all these nerdy brains to work on a problem where one matches one's taste to others through proxies such as movies. There is a tougher challenge at hand and one you can directly impact: People matching. As it so happens, Markus Frind, the guy who started Plenty of Fish is looking for a person with a Ph.D to help out in the referral engine for his hugely successful free dating site. Think of it as the Craig's list of love. Can you really handle finding Luuuuvvvv ? As the Chinese say, may you live in interesting times....


PS: for those of you not accustomed to the word, Luuuuvvv is sometimes pronounced the same as love in certain part of the U.S. where country music is typically a hallmark.

Video: LeeAnn Rimes, Blue. LeeAnn first sang this song when she was 13. Many people remember the first time they heard that song.

CS: An announcement and a plea. Videos of CS particle Filter results

I am going to be offline starting next Tuesday till the end of the month. The automatic submission system of Blogger allows me to post some entries in advance. If you want to submit a job description, a paper or a code at a certain date in the second part of August, I can write the entry now and it will show up at the appropriate time on the blog. You just need to give me the address where the job description/paper or code will be located and the date at which you want an announcement to be made on the blog. Thank you.

David a commenter on the previous entry rightly pointed out that the video of Rich Baraniuk's presentation on Compressive Sensing presenting the MIT Random Lens Imager by Rob Fergus, Antonio Torralba, and William T. Freeman has pulled by the author of the video. If you are that person please, pretty please put it back on youtube for the enlightment of the community.

In case it doesn't show up again, I think I am going to have to make a video myself. and that my friends, it would surely be an abomination.

While checking Youtube, I found the following two videos using Compressive Sensing and Particle Filter. If somebody knows the owner or the paper used to get these results, I'll be glad to make a larger mention of it on the blog. Here they are:

Description: Compressive tracking of two targets using the Compressive Particle Filter. We used a CS matrix with each element drawn iid from N(0,1). The total number of measurements is 1000. The circles denote the approximate target size.

Description: Video results of the Compressive Particle Filter. The frames are 144x176. We used 1000 measurements and a CS matrix with each element drawn iid from N(0,1). The circle denotes the estimated size of the target.

CS: Blind Deconvolution and a postdoc.

In the past, I have mentioned that one of the big issue when one was trying to arrange a Compressive Sensing system (or any system for that matter) was the issue of calibration. But in compressive sensing, it takes a particular importance as the mixing or multiplexing is supposedly random. Let's take the example of the MIT Random Lens Imager (by Rob Fergus, Antonio Torralba, and William T. Freeman) featured in one of Rich Baraniuk's presentation on Compressive Sensing:

(this video and others can be found on the Compressive Sensing Hardware page [Update: It looks like the video was removed])

After having constructed such a system, one is bound to go through a lengthy calibration process of taking pictures of known elements and their response on the sensor with the eventual expectation that with enough such calibration photos one would be able to build the Point Spread Function or the Camera Response Function. The MIT paper takes the right point of view that the PSF should also be sparse and tries to devise this PSF for a small part of the sensor (they use only a 32x32 section of the CMOS/CDD, see figure 7) and one wonders how one can speed up this process now that we have faster reconstruction algorithms as the MIT report came out in 2006. This issue of finding the (here random) mixing system is known in the literature as blind deconvolution. I did a search on this keyword in my e-mail box that contains the daily dump of my webcrawler and found the following papers that I may or may not have covered:

Non-Iterative Valid Blind Deconvolution of Sparsifiable Images using an Inverse Filter by Andrew Yagle. The abstract reads:

We propose a new non-iterative algorithm for the blind deconvolution problem of reconstructing both a sparsifiable image and a point-spread function (PSF) from their valid 2D convolution. No support constraint is needed for either the image or the PSF, nor is non-negativity of the image. The only requirements are that the PSF be modelled as having a finite support inverse or equalizing filter (IF), and that the product of the (known) numbers of nonzero pixels in this inverse filter and the sparsified image be less than the total number of image pixels. The algorithm requires only the solution of a large linear system of equations and a small rank-one matrix decomposition.

and also:

• L. Zhang, A. Cichocki and S. Amari, Geometrical structures of FIR manifold and their application to multichannel blind deconvolution
• Bo Zhang, Ph.D. dissertation: Contributions to fluorescence microscopy in biological imaging: PSF modeling, image restoration, and super-resolution detection
• Anat Levin, Yair Weiss, Fredo Durand, William T. Freeman, Understanding and Evaluating Blind Deconvolution Algorithms
• Kyle Herrity, Raviv Raich and Alfred O. Hero, "Blind deconvolution for sparse molecular imaging
• Kyle Herrity, Raviv Raich and A.O. Hero, "Blind reconstruction of sparse images with unknown point spread function

Let us note that this is not the same case studied by Yaron Rachlin and Dror Baron in The Secrecy of Compressive Sensing Measurements. In that case, the inputs AND the mixing matrix are unknowns.


I also found this job on the interwebs: a postdoc at University of Edinburgh, Scotland, I am adding it to the Compressive Sensing Jobs page:

University of Edinburgh School of Engineering: Research Associate in "Compressed Sensing SAR"

Vacancy details

* Vacancy Reference: 3011316
* Department: School of Engineering
* Job Title: Research Associate in "Compressed Sensing SAR"
* Job Function: Academic
* Job Type: Full Time
* Live Date: 29-Jul-2009
* Expiry Date: 20-Aug-2009
* Salary Scale: £20,226 - £23,449
* Internal job: No. Anybody can apply for this position.
* Further Information: Further Information
* Conditions Of Employment: View Conditions of Employment

School of Engineering: Research Associate in "Compressed Sensing SAR"

This post is to investigate a compressed sensing coding techniques for use in Synthetic Aperture Radar (SAR) remote sensing applications.

The purpose of "Compressed sensing SAR" is to provide SAR imaging with a superior compression system that has the capability of practically transmitting large quantities of SAR data to the receiving station over restricted bandwidth with minimal on board computation. The communication or data storage bottleneck is a key factor currently limiting coverage and/or resolution in SAR instruments. Our unique approach to addressing this problem is to utilize the new concept of "compressed sensing" to remove this bottleneck. Compressed sensing has the potential to provide a compression scheme that is bandwidth efficient while requiring minimal on-board processing. The project will explore the feasibility of such a technique and design and evaluate a proof of concept compression system. In addition, you will have the opportunity to work closely with other members of the sparse representations research group within the Institute for Digital Communications.

You will have a PhD (or have recently submitted) or equivalent in engineering, computer science or related discipline, and have a strong background in signal processing. The appointment will be for two years starting on 1st October 2009 or as soon as possible thereafter.

Fixed Term: 2 years

CS: Sparsity in Random Matrix Theory, Approximation of functions of few variables in high dimensions, YALL1, KSVD-Box v11

Going back from "applied" math to "pure" mathematics: On the role of sparsity in Compressed Sensing and Random Matrix Theory by Roman Vershynin. The abstract reads:

We discuss applications of some concepts of Compressed Sensing in the recent work on invertibility of random matrices due to Rudelson and the author. We sketch an argument leading to the optimal bound \Omega^(N−1/2) on the median of the smallest singular value of an N × N matrix with random independent entries. We highlight the parts of the argument where sparsity ideas played a key role.

Following up on some elements shown in the third Paris Lecture of Ron DeVore, here is the more substantive paper: Approximation of functions of few variables in high dimensions by Ron DeVore, Guergana Petrova, Przemyslaw Wojtaszczyk. The abstract reads:

Let f be a continuous function defined on \Omega:= [0, 1]^N which depends on only l coordinate variables, f(x1, . . . , xN) = g(xi1 , . . . , xi` ). We assume that we are given m and are allowed to ask for the values of f at m points in \Omega. If g is in Lip1 and the coordinates i_1, . . . , i_l are known to us, then by asking for the values of f at m = L^l uniformly spaced points, we could recover f to the accuracy |g|Lip1L−1 in the norm of C(). This paper studies whether we can obtain similar results when the coordinates i_1, . . . , i_l are not known to us. A prototypical result of this paper is that by asking for C(l)L^l(log2 N) adaptively chosen point values of f, we can recover f in the uniform norm to accuracy |g|Lip1L−1 when g 2 Lip1. Similar results are proven for more general smoothness conditions on g. Results are also proven under the assumption that f can be approximated to some tolerance \epsilon (which is not known) by functions of l variables.

I note that the authors make a connection to the Junta's problem as discussed by Dick Lipton recently and mentioned here.

Also, following up on yesterday's release of a dictionary learning technique (without the code yet), today we have two new upgrades of a dictionary learning tool and a reconstruction solver:

Ron Rubinstein has released a new version of the K-SVD dictionary learning technique. From the page:

KSVD-Box v11 Implementation of the K-SVD and Approximate K-SVD dictionary training algorithms, and the K-SVD Denoising algorithm. Requires OMP-Box
v9.

Update (August 3 2009): KSVD-Box v11 has been released, and adds 1-D signal handling!

Yin Zhang just released YALL1 version beta-6 that can solve 2 more models for A*A' = I (with bug fixing). From the page:

This Matlab code can currently be applied to the following eight (8) L1-minimization
problems:

• (BP) min ||Wx||w,1 s.t. Ax = b
• (L1/L1) min ||Wx||w,1 + (1/ν)||Ax - b||1
• (L1/L2) min ||Wx||w,1 + (1/2ρ)||Ax - b||22
• (L1/L2con) min ||Wx||w,1, s.t. ||Ax - b||2 \le δ
• (BP+) min ||x||w,1 s.t. Ax = b and x \ge 0
• (L1/L1+) min ||x||w,1 + (1/ν)||Ax - b||1 s.t. x \ge 0
• (L1/L2+) min ||x||w,1 + (1/2ρ)||Ax - b||22 s.t. x \ge 0
• (L1/L2con+) min ||x||w,1, s.t. ||Ax - b||2 <= δ, x \ge 0

where A is m by n with m less than n, and the solution x (or its representation Wx) is supposed to be (approximately) sparse. The data (A,b) can be real or complex, and the signal x can also be complex in the cases of no nonnegativity constraint. A unitary sparsifying basis W is allowed and the 1-norm for x (or Wx) can be weighted by a vector w \ge 0. The capacity for solving models (L1/L2con) and (L1/L2con+) has been added to version beta-6 for A*A' = I.

Image credit: NASA, ESA, and H. Hammel (Space Science Institute, Boulder, Colo.), and the Jupiter Impact Team. If you recall the Another Space Odyssey entry, well, this picture is that of this impact as viewed by Hubble. Via the Bad Astronomy blog.

CS: Online Sparse Coding and Matrix Factorization, GraDes, TSW-CS

Today, we have a potential game changer in dictionary learning which as we all know is part of compressive sensing since it allows one to reconstruct sparse signals after being incoherently acquired. The article is Online Learning for Matrix Factorization and Sparse Coding by Julien Mairal, Francis Bach, Jean Ponce, Guillermo Sapiro and features a somewhat simple algorithm that seems to scale to very large datasets. The abstract of the paper reads:

Sparse coding—that is, modelling data vectors as sparse linear combinations of basis elements—is widely used in machine learning, neuroscience, signal processing, and statistics. This paper focuses on the large-scale matrix factorization problem that consists of learning the basis set, adapting it to specific data. Variations of this problem include dictionary learning in signal processing, non-negative matrix factorization and sparse principal component analysis. In this paper, we propose to address these tasks with a new online optimization algorithm, based on stochastic approximations, which scales up gracefully to large datasets with millions of training samples, and extends naturally to various matrix factorization formulations, making it suitable for a wide range of learning problems. A proof of convergence is presented, along with experiments with natural images and genomic data demonstrating that it leads to state-of-the-art performance in terms of speed and optimization for both small and large datasets.

One of the author, Julien Mairal, mentioned to me that the algorithm should be shortly available. I have added the paper (and soon to follow code) to the dictionary section of the Big Picture in Compressive Sensing.

Rahul Garg let me know that the GraDes algorithm is now available here. It was featured in Gradient Descent with Sparsification: An iterative algorithm for sparse recovery with restricted isometry property by Rahul Garg and Rohit Khandekar and mentioned here. As Laurent Jacques and the authors mentioned later, GraDes is pretty much an IHT algorithm. I have added it to the reconstruction section of the Big Picture in Compressive Sensing page.

Finally, we have Exploiting Structure in Wavelet-Based Bayesian Compressive Sensing by Lihan He and Lawrence Carin. The abstract reads:

Bayesian compressive sensing (CS) is considered for signals and images that are sparse in a wavelet basis. The statistical structure of the wavelet coefficients is exploited explicitly in the proposed model, and therefore this framework goes beyond simply assuming that the data are compressible in a wavelet basis. The structure exploited within the wavelet coefficients is consistent with that used in waveletbased compression algorithms. A hierarchical Bayesian model is constituted, with efficient inference via Markov chain Monte Carlo (MCMC) sampling. The algorithm is fully developed and demonstrated using several natural images, with performance comparisons to many state-of-the-art compressive-sensing inversion algorithms.

The TSW-CS code is part of the Bayesian Compressive Sensing Code of Larry Carin's group at Duke.

Credit: World Science Festival 2009: Bobby McFerrin Demonstrates the Power of the Pentatonic Scale from World Science Festival on Vimeo.

CS: Short Stats

So far there has been 511 entries on Compressive Sensing in this blog. If you are coming to the blog, the statistics on the right hand side show that the blog has about 467 subscribers reading this blog through an RSS feed, while another 182 people receive every entry by e-mail. About 300 to 500 people come to the site on a daily basis thanks to search engines and other sources. In short, a little more than a 1000 people are interested in learning what is up on the subject of Compressive Sensing.

After an initial spike of interest, about 50 people now come to the Compressive Sensing hardware page weekly. Every week, we also have on average:

• 120 people come to the Compressive Sensing jobs page
• 190 people come to the Compressive Sensing videos / online talks page
• and 800 people come to the Big Picture in Compressive Sensing page.
  

I am even surprised that some people e-mailing me know about the Big Picture in Compressive Sensing page but not the blog!