CS: Hype or Hope, Herschel news ?, Sparsity Pattern Recovery in the Noisy Setting, Cognitive Radio, CS on Least Squares Residual, Dictionary learning

Enjoy this sighting as the shuttle program will shut down in 2010.

STS-129 Ascent Video Highlights from mike interbartolo on Vimeo.

Unrelated, did you know there were 20 probes flying around the solar system ?

There is a new online talk entitled Compressive Sensing for Computer Vision: Hype vs Hope by Rama Chellappa.

If you check the right hand side of this blog, you'll see that you can directly access the arxiv with a complex query having most of the words used for compressive sensing. The result of the query is here : http://tinyurl.com/y9v8t4a

Unbeknownst to me Jean-Luc Starck made a presentation last week in Australia:

Compressed Sensing in Astronomy - Jean-Luc Starck Special Colloquium
Friday 27 November 2009
15:30 to 16:30

ATNF Marsfield Lecture Theatre

Abstract: The spatial infrared astronomical satellite Herschel, launched on May 14 2009, is the first satellite which has a compressed sensing (CS) coder included in its on board software. We will present our motivations for using Compressed Sensing in this project. Then we will describe the practical implementation of our CS coder/decoder. We will show from simulations that CS enables to recover data with a spatial resolution enhanced up to 30% with similar sensitivity compared to the averaging technique proposed by ESA. Finally we will show how other problems in astronomy such interferometric image deconvolution or gamma ray image reconstruction can be also handled differently using CS.

Is the compressive sensing encoding scheme going to be used in production for PACS ? This suspense is killing me!

I also found the following on arxiv:

An Estimation Theoretic Approach for Sparsity Pattern Recovery in the Noisy Setting by Ali Hormati, Amin Karbasi, Soheil Mohajer, Martin Vetterli. The abstract reads:

Compressed sensing deals with the reconstruction of sparse signals using a small number of linear measurements. One of the main challenges in compressed sensing is to find the support of a sparse signal. In the literature, several bounds on the scaling law of the number of measurements for successful support recovery have been derived where the main focus is on random Gaussian measurement matrices. In this paper, we investigate the noisy support recovery problem from an estimation theoretic point of view, where no specific assumption is made on the underlying measurement matrix. The linear measurements are perturbed by additive white Gaussian noise. We define the output of a support estimator to be a set of position values in increasing order. We set the error between the true and estimated supports as the $\ell_2$-norm of their difference. On the one hand, this choice allows us to use the machinery behind the $\ell_2$-norm error metric and on the other hand, converts the support recovery into a more intuitive and geometrical problem. First, by using the Hammersley-Chapman-Robbins (HCR) bound, we derive a fundamental lower bound on the performance of any \emph{unbiased} estimator of the support set. This lower bound provides us with necessary conditions on the number of measurements for reliable $\ell_2$-norm support recovery, which we specifically evaluate for uniform Gaussian measurement matrices. Then, we analyze the maximum likelihood estimator and derive conditions under which the HCR bound is achievable. This leads us to the number of measurements for the optimum decoder which is sufficient for reliable $\ell_2$-norm support recovery. Using this framework, we specifically evaluate sufficient conditions for uniform Gaussian measurement matrices.

LS-CS: Compressive Sensing on Least Squares Residual by Namrata Vaswani. The abstract reads:

We consider the problem of recursively reconstructing time sequences of sparse signals (with unknown and time-varying sparsity patterns) from a limited number of linear incoherent measurements with additive noise. The signals are sparse in some transform domain referred to as the sparsity basis and the sparsity pattern is assumed to change slowly with time. The idea of our proposed solution, LS-CS-residual (LS-CS), is to replace compressed sensing (CS) on the observation by CS on the least squares (LS) observation residual computed using the previous estimate of the support. We bound the CS-residual error and show that when the number of available measurements is small, the bound is much smaller than that on CS error if the sparsity pattern changes slowly enough. We also obtain conditions for "stability" of LS-CS over time for a simple deterministic signal model of coefficient addition/removal and coefficient magnitude increase/decrease which has bounded signal power. By "stability", we mean that the number of misses and extras in the support estimate is bounded by a small value compared to the support size, at all times. Extensive simulation results backing our claims are shown

Mixed-Signal Parallel Compressed Sensing and Reception for Cognitive Radio by Zhuizhuan Yu, Sebastian Hoyos, Brian M. Sadler. The abstract reads:

A parallel structure to do spectrum sensing in Cognitive Radio (CR) at sub-Nyquist rate is proposed. The structure is based on Compressed Sensing (CS) that exploits the sparsity of frequency utilization. Specifically, the received analog signal is segmented or time-windowed and CS is applied to each segment independently using an analog implementation of the inner product, then all the samples are processed together to reconstruct the signal. Applying the CS framework to the analog signal directly relaxes the requirements in wideband RF receiver front-ends. Moreover, the parallel structure provides a design flexibility and scalability on the sensing rate and system complexity. This paper also provides a joint reconstruction algorithm that optimally detects the information symbols from the sub-Nyquist analog projection coefficients. Simulations showing the efficiency of the proposed approach are also presented.

In a different direction, we have:
Reference Free Structure Determination through Eigenvectors of Center of Mass Operators by Ronald R. Coifman, Yoel Shkolnisky, Fred J. Sigworth, Amit Singer. The abstract reads:

Recovering the three-dimensional structure of molecules is important for understanding their functionality. We describe a spectral graph algorithm for reconstructing the three-dimensional structure of molecules from their cryo-electron microscopy images taken at random unknown orientations. We first identify a one-to-one correspondence between radial lines in three-dimensional Fourier space of the molecule and points on the unit sphere. The problem is then reduced to determining the coordinates of points on the sphere given a subset of their pairwise geodesic distances. To recover those coordinates, we exploit the special geometry of the problem, as rendered by the Fourier projection-slice theorem, to construct a weighted graph whose vertices are the radial Fourier lines and whose edges are linked using the common line property. The graph organizes the radial lines on the sphere in a global manner that reveals the acquisition direction of each image. This organization is derived from a global computation of a few eigenvectors of the graph’s sparse adjacency matrix. Once the directions are obtained, the molecule can be reconstructed using classical tomography methods. The presented algorithm is direct (as opposed to iterative refinement schemes), does not require any prior model for the reconstructed object, and is shown to have favorable computational and numerical properties. Moreover, the algorithm does not impose any assumption on the distribution of the projection orientations. Physically, this means that the algorithm is applicable to molecules that have unknown spatial preference.

Olivier Grisel also pointed out to me another dictionary learning technique: Fast Inference in Sparse Coding Algorithms with Applications to Object Recognition by Koray Kavukcuoglu Marc’Aurelio Ranzato, Yann LeCun. The abstract reads:

Adaptive sparse coding methods learn a possibly overcomplete set of basis functions, such that natural image patches can be reconstructed by linearly combining a small subset of these bases. The applicability of these methods to visual object recognition tasks has been limited because of the prohibitive cost of the optimization algorithms required to compute the sparse representation. In this work we propose a simple and efficient algorithm to learn basis functions. After training, this model also provides a fast and smooth approximator to the optimal representation, achieving even better accuracy than exact sparse coding algorithms on visual object recognition tasks.

I could not find the following papers freely available on the web: Compressive Imaging: An Application by Robert Muise. The abstract reads:

We consider the application of compressive imaging theory to the problem of wide-area persistent surveillance. While the compressive sensing theory enjoys significant research attention, mainly because of the possibilities for orders-of-magnitude increases in signal/image processing applications, the application areas for compressive imaging have not kept pace due to the lack of an optical architecture which could directly improve current sensing capabilities. There are now cases in the literature and under study where optical architectures have been developed which require the incorporation of compressive imaging in order to perform the indicated exploitation application. This paper utilizes one such architecture to show a dramatic (two orders of magnitude) increase in performance for the application of wide-area persistent surveillance. This application together with its architecture is described as a field-of-view (FOV) multiplexing imager, and its relation to compressive imaging is discussed and exploited for increased field-of-regard (FOR) imaging. A simulated example is given in the last section with qualitatively impressive results. The optical architecture of FOV multiplexing, while showing a significant performance increase over current capabilities, also opens some interesting research questions.

Compressive Sensing of Light Fields by S.D. Babacan; R. Ansorge; M. Luessi; R. Molina; A.K. Katsaggelos. The abstract reads:

We propose a novel camera design for light field image acquisition using compressive sensing. By utilizing a randomly coded non-refractive mask in front of the aperture, incoherent measurements of the light passing through different regions are encoded in the captured images. A novel reconstruction algorithm is proposed to recover the original light field image from these acquisitions. Using the principles of compressive sensing, we demonstrate that light field images with high angular dimension can be captured with only a few acquisitions. Moreover, the proposed design provides images with high spatial resolution and signal-to-noise-ratio (SNR), and therefore does not suffer from limitations common to existing light-field camera designs. Experimental results demonstrate the efficiency of the proposed system.

Finally, here is a handy thesaurus translating terms between Numpy/python-R-Matlab here.

Credit: NASA