CS: Compressed Sensing Phase Retrieval, Deterministic SFT, A generalization of Kolmogorov’s theory of n-widths for infinite dimensional spaces, a job.

From Wikimization, here is a newer version of Toward 0-norm Reconstruction, and a Nullspace Technique for Compressive Sampling as presented by Christine Law with Gary Glover at the Linear Algebra and Optimization Seminar (CME510), iCME, Stanford University, November 19, 2008.

Unlike what I said earlier, the paper entitled Compressed Sensing Phase Retrieval with Matthew Moravec, Justin Romberg and Richard Baraniuk can be found here.

Adi Akavia was speaking on Monday, December 8 2008 at MIT. The talk presentation reads:

Computing the Fourier transform is a basic building block used in numerous applications. For data intensive applications, even the O(N log N) running time of the Fast Fourier Transform (FFT) algorithm may be too slow, and sub-linear running time is necessary. Clearly, outputting the entire Fourier transform in sub-linear time is infeasible, nevertheless, in many applications it suffices to find only the \tau-significant Fourier transform coefficients, that is, the Fourier coefficients whose magnitude is at least \tau-fraction (say, 1%) of the energy (ie, the sum of squared Fourier coefficients). We call algorithms achieving the latter SFT algorithms. 

In this work we present a *deterministic* algorithm that finds the $\tau$-significant Fourier coefficients of functions f over *any finite abelian group G* in time polynomial in log|G|, 1/\tau and L_1(f) (for L_1(f) denoting the sum of absolute values of the Fourier coefficients of f). Our algorithm is robust to random noise. 

Our algorithm is the first deterministic and efficient (ie, polynomial in log|G|) SFT algorithm to handle functions over any finite abelian groups, as well as the first such algorithm to handle functions over Z_N that are neither compressible nor Fourier-sparse. Our analysis is the first to show robustness to noise in the context of deterministic SFT algorithms. Using our SFT algorithm we obtain (1) deterministic (universal and explicit) algorithms for sparse Fourier approximation, compressed sensing and sketching; (2) an algorithm solving the Hidden Number Problem with advice, with cryptographic bit security implications; and (3) an efficient decoding algorithm in the random noise model for polynomial rate variants of Homomorphism codes and any other concentrated and recoverable codes.

Hum.. (I put the emphasis in the text) here is another statement along the lines that sparsity is not being the main prerequisite condition for subsampling. I look forward to seeing more of that paper.

On December 17-19, 2008, at the Workshop on Optimization and Applications, Institute of Mathematics and Informatics, Bulgarian Academy of Sciences in Sofia, Bulgaria, Ognyan Kounchev will give a talk entitled A generalization of Kolmogorov’s theory of n-widths for infinite dimensional spaces: applications to Compressive sensing. The abstract reads:

Recently, the theory of widths has got high interest due to its importance for the so-called Compressive sensing, see the works of D. Donoho, E. Candes, T. Tao, R. Baraniuk and others. On the other hand, the theory of n-widths of Kolmogorov (a kind of Optimal recovery theory) is not appropriate for the spaces of functions depending on several variables - this is seen from the simplest examples which one would like to have treated by a theory of Optimal recovery. We generalize the theory of n-widths of Kolmogorov by considering approximation by infinite-dimensional spaces of functions which have so far ”harmonic dimension n” in some sense. A large class of such spaces having ”harmonic dimension n” is provided by the solutions of elliptic differential operators of order 2n. We indicate possible applications to Compressive sensing.

Here is a new job posting for a post-doc in the group of Jean-Luc Starck at CEA near Paris. The description reads:

JOB OPPORTUNITY

Title of the job : Post-doctoral position (3 years), Signal/Image processing at CEA Saclay, Service d’Astrophysique. The Service d'Astrophysique (SAp) at CEA Saclay invites applications for a postdoctoral appointment in the area of data analysis/image processing of astronomical data to work with Jean-Luc Starck.

The CEA Saclay is a government research center situated 40 minutes from central Paris, France. The SAp has a wide interest in astrophysics ranging from planets to cosmology, with a specialisation in space missions (eg. Euclid, XMM-Newton, Herschel, PLANCK, JWST, Integral etc) and instrumentation (eg. Megacam on the Canada-France-Hawaii Telescope). The position is to work on sparse representation of astronomical data for different applications such as non-Gaussianity detection, inverse problem and compressed sensing.

Candidates should have a PhD in Image processing, Physics or Astronomy.

Previous experience in sparse representations (wavelet, curvelets, etc) and the development of data analysis methods is preferred, but experience in related areas is also suitable.

The position, funded for at least 3 years (up to 5 years), will be renewed on a yearly basis depending on scientific progress and achievement. The gross minimum salary will be 34,000€ annually (~2,260€ net per month), and will be adjusted according to experience and family situation. A minimum of 5,000 € per year of travel money for each position will also be provided, in addition to the usual funding support of any French institution (medical insurance, etc). Applicants are requested to send a CV, a list of publications, and a brief statement of research interests. This material together with three letters of reference should be sent by the closing date to

Jean-Luc Starck

Laboratoire Astrophysique des Interactions Multi-échelles

Irfu, Service d'Astrophysique, CEA Saclay,

F-91191 GIF-Sur-YVETTE CEDEX, France.

Email: check the flyer for more information.

The closing date for receipt of applications : February 28, 2009

The job posting has been to the CSJobs page.

The ICPR 2010 conference has Compressed Sensing as a subject of interest.

Image Credit: NASA/JPL/Space Science Institute, image of Tethys taken on December 9th, 2008.