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.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:
- 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.
- Correct evaluation of support set for strictly sparse signals (Wainwright's metric; RFG and Akcakaya-Tarokh also like this metric).
- Mean ell_1 error.
- 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:
And another one: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.
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
No comments:
Post a Comment