CS: The Junta problem, NESTA, Non-Iterative Superresolution Phase Retrieval of Sparse Images , NAS postdoc

Dick Lipton has a blog entry on the potential connection between the Junta Problem and Compressive Sensing.

Ever since this entry, we have been waiting for it, here it is: the NESTA code is out. Get it here. From the site:

Introduction

NESTA is a fast and robust first-order method than solves basis-pursuit problems and a large number of extensions (including tv-denoising). It is described in the paper NESTA: A Fast and Accurate First-order Method for Sparse Recovery (technical report, April 2009, California Institute of Technology) by Jérôme Bobin, Stephen Becker, and Emmanuel Candès,

The algorithm uses two ideas due to Yurii Nesterov. The first idea is an accelerated convergence scheme for first-order methods, giving the optimal convergence rate for this class of problems. The second idea is a smoothing technique that replaces the non-smooth l1 norm with a smooth version.

The basic algorithm solves the following equation, often known as basis pursuit denoising, or simply as l1-minimization:

The parameter epsilon is typically small and proportional to an estimate of the standard deviation of any noise in the measurements. If epsilon is 0, the problem is known as just basis pursuit. Basis pursuit and basis pursuit denoising are often used in statistics, image-processing, and compressed sensing.

NESTA is capable of solving many other problems; some popular extensions are discussed on this website.

The current version of code for NESTA requires that the measurement matrix A is an orthogonal projection. It is possible to extend NESTA to allow general matrices A, though this is not implemented in the code.

Analysis

For real-world signals, the signal is not sparse, but it may be sparse (or be approximately-sparse, i.e. most energy is concentrated in only a few coefficients) in a dictionary W. For example, W may be a discrete cosine basis, a Gabor frame, a curvelet frame, a wavelet basis, etc. In this case, it may be desirable to solve the analysis-based problem:

An alternative is the synthesis-based problem:

Unless the dictionary is a basis, the two problems are not equivalent. Traditionally, the synthesis-based approach has been used because it requires no modification to basis pursuit solvers: simply treat (AW) as a single operator.

NESTA is one of few algorithms that can solve the analysis problem (in addition to the synthesis problem). The code accepts W as in input.

Note that this allows NESTA to solve the reweighted l1 problem; for this case, W is a diagonal matrix. Demos showing the use of analysis and reweighting are included in the code.

You may recall a reconstruction scheme that was not iterative ? Andy Yagle goes further on that path with the following three papers (matlab codes are included in the papers):

Location of Non-Zeros in Sparse Solutions of Underdetermined Linear Systems of Equations by Andrew Yagle. The abstract reads:

The problem of computing sparse (mostly zero) or sparsifiable (by linear transformation) solutions to greatly underdetermined linear systems of equations has applications in compressed sensing. The locations of the nonzero elements in the solution is a much smaller set of variables than the solution itself. We present explicit equations for the relatively few variables that determine these nonzero locations and also propose an iterative algorithm for their solution.

Non-Iterative Superresolution Phase Retrieval of Sparse Images without Support Constraints by Andrew Yagle. The abstract reads:

We propose a new non-iterative algorithm for phase retrieval of a sparse image from low wavenumber values of its Fourier transform magnitude. No image support constraint is needed. The algorithm uses the sparsity of the image autocorrelation to reconstruct it exactly from low-wavenumber Fourier magnitude data (superresolution) using a variation of MUSIC. The sparsity of the image is then used to reconstruct it recursively from its autocorrelation. Applications include X-ray crystallography and astronomy. Two numerical examples illustrate the algorithm.

Coordinate Descent for Sparse Solutions of Underdetermined Linear Systems of Equations by Andrew Yagle. The abstract reads:

The problem of computing sparse (mostly zero) or sparsifiable (by linear transformation) solutions to greatly underdetermined linear systems of equations has applications in compressed sensing and reduced-exposure imaging. We show that coordinate descent, in which a single variable is varied while all others are held constant, is applicable to a wide variety of such problems. The method is useful for very large problems having dense system matrices.

There is a NAS associateship offered at Kirtland Air Force Base entitled: "Concurrent, Agility, and Distributed Decision Architecture for Compressive Sensing and Complexity Management". Please note the restriction on citizenship. I'll add it to the Compressive Sensing job site.


Image Credit: NASA/JPL/Space Science Institute , view of Rhea from Cassini taken on June 3,