CS: A Thesis on Analog-to-Information Converter using Random Demodulation, a talk, Jacket GPU, Inverse problems in acoustic tomography

Following up on a previous entry, Valerio Cambareri, a reader of this blog, just received his Bachelor of Engineering in Italy. This corresponds to a level of end of Junior year in the U.S. and Bac + 3 in France. He produced an undergraduate thesis (at the Junior level) on Compressive Sampling. The thesis is entitled:

Conversione Analog-To-Information Tramite Architettura Random Modulation Preintegration

Additional figures can be found here. It is in Italian, but if you have been reading about CS for a while, most of it is understandable. This work is based on a previous paper: Theory and Implementation of an Analog-to-Information Converter using Random Demodulation of Jason Laska, Sami Kirolos, Marco F. Duarte, Tamer Ragheb, Richard Baraniuk and Yehia Massoud. It uses newer solvers to reconstruct the signal.

In other news:

•  Stephane Chretien will talk about Lagrangian relaxation of the compressed sensing problem, at Boston University in the Statistics Department seminar, on November 4th, 2008 from 4 to 5 pm. The abstract of the talk reads: 

  Lagrangian relaxation is a general methodology for approximating hard combinatorial problems and has been applied with success to various instances such as the Max-Cut problem. The compressed sensing problem of recovering the sparsest solution to a system of linear equations is known to be NP-hard and is often relaxed by means of l1 minimization, i.e. a simple linear program. The goal of this talk is to present an approximate Lagrangian relaxation of the compressed sensing problem leading to a better relaxation scheme than l1 minimization. The resulting iterative algorithm is called Alternating l1. One of the standard features of the Lagrangian approach for hard combinatorial problems is to provide provably efficient approximation schemes. In the case of l1 minimization, E. Cands, T. Tao and their collaborators were able to to show that with high probability, l1 minimization does in fact better in that it recovers the solution of the original sparsest recovery problem exactly. We will show that the Alternating l1 algorithm allows to recover the sparsest solution with fewer observations than l1 norm minimization. As many recent proposals for the compressed sensing problem, an additional parameter has to be tuned in order to obtain signicant improvements over the plain l1 strategy. A nice feature of our approach is that this additional parameter is nothing but a Lagrange multiplier and the best value is simply the one that optimizes the dual function. We will also show how to circumvent the dicult task of computing the dual optimizer exactly by proposing a meaningful value of this parameter allowing for signicant improvements in the first two steps of the method, hence avoiding fastidious empirical tuning as is usually done in the case of other methods such as the Reweighted l1 algorithm.

• The SLIM blog has a summary entry on Compressed sensing versus sparse recovery
  
• In light of the reconstruction hardware from UCLA, I found out about Jacket: a GPU engine for Matlab. You may want to download the beta version before it becomes a paid product, and 
• Ivana Jovanovic at EPFL just released her Ph.D thesis entitled Inverse problems in acoustic tomography, where Compressed Sensing and Finite Rate of Innovation are compared. The abstract of the thesis reads:
  

Acoustic tomography aims at recovering the unknown parameters that describe a field of interest by studying the physical characteristics of sound propagating through the considered field. The tomographic approach is appealing in that it is non-invasive and allows to obtain a significantly larger amount of data compared to the classical one-sensor one-measurement setup. It has, however, two major drawbacks which may limit its applicability in a practical setting: the methods by which the tomographic data are acquired and then converted to the field values are computationally intensive and often ill-conditioned. This thesis specifically addresses these two shortcomings by proposing novel acoustic tomography algorithms for signal acquisition and field reconstruction. The first part of our exposition deals with some theoretical aspects of the tomographic sampling problems and associated reconstruction schemes for scalar and vector tomography. We show that the classical time-of-flight measurements are not sufficient for full vector field reconstruction. As a solution, an additional set of measurements is proposed. The main advantage of the proposed set is that it can be directly computed from acoustic measurements. It thus avoids the need for extra measuring devices. We then describe three novel reconstruction methods that are conceptually quite different. The first one is based on quadratic optimization and does not require any a priori information. The second method builds upon the notion of sparsity in order to increase the reconstruction accuracy when little data is available. The third approach views tomographic reconstruction as a parametric estimation problem and solves it using recent sampling results on non-bandlimited signals. The proposed methods are compared and their respective advantages are outlined. The second part of our work is dedicated to the application of the proposed algorithms to three practical problems: breast cancer detection, thermal therapy monitoring, and temperature monitoring in the atmosphere. We address the problem of breast cancer detection by computing a map of sound speed in breast tissue. A noteworthy contribution of this thesis is the development of a signal processing technique that significantly reduces the artifacts that arise in very inhomogeneous and absorbent tissue. Temperature monitoring during thermal therapies is then considered. We show how some of our algorithms allow for an increased spatial resolution and propose ways to reduce the computational complexity. Finally, we demonstrate the feasibility of tomographic temperature monitoring in the atmosphere using a custom-built laboratory-scale experiment. In particular, we discuss various practical aspects

of time-of-flight measurement using cheap, off-the-shelf sensing devices.

Image Credit: NASA/JPL/Space Science Institute, W00050373.jpg was taken on October 21, 2008 and received on Earth October 22, 2008. The camera was pointing toward SATURN-RINGS at approximately 1,114,766 kilometers away.