CS: Twitter, Several news and findings, A Non-Iterative Procedure for Undetermined Systems, Molecular imaging, Super-resolution X-ray

For those of who know what this is, I am on Twitter.

Thomas Blumensath sent me a kind e-mail :

As an avid reader of your blog, I thought I clarify the following points raised in one of your previous entries regarding the OLS algorithm.

Firstly, we did not propose the method in our paper. This method has been around with many names and in many guises. Our paper actually gives a good historical overview (which was its main purpose). A better reference for the OLS algorithm would be:

S. Chen, S. A. Billings, and W. Luo, “Orthogonal least squares methods and their application to non-linear system identification.,” International Journal of Control, vol. 50, no. 5, pp. 1873–1896, 1989.

Secondly, I would like to point out that ols is also available in my Sparsify toolbox (greed_ols).

Thanks Thomas for the clarification.


Svetlana Avramov-Zamurovic presented a tutorial on Compressive Sensing in a course at the USNA. She also made a video of it. It is here. The slides and attendant paper by Richard Baraniuk on which the presentation is based. I'll add it to the Compressive Sensing Videos page.

Jort Gemmeke let me know that the schedule and list of presentation of the Compressive Sensing Workshop is now available here. Lots of goodies.

Andryian Suksmono has just released a draft e-book on Compressive Sensing. The mild caveat is that it is in Indonesian. No worry, Google Translate now has Indonesian to English translation services.

Felix J. Herrmann, Yogi Erlangga, Tim Lin have released a new version of Compressive simultaneous full-waveform simulation.

A passing thought: when you hear about an imaging system that is diffraction-limited, you are really hearing that the analog way of combining light rays together to form an image has limits. If you have read the previous entry on compressive phase retrieval featuring Ab Initio Compressive Sensing Phase retrieval by Stefano Marchesini and Compressed Sensing Phase Retrieval by Matthew Moravec, Justin Romberg and Richard Baraniuk, you know by now that every time you hear about an indirect measurement system or have the ability to engineer the PSF (Point Spread Function), it is likely you should be able to use the strength of compressive sensing to perform measurements.

Here are three papers that I think are interesting in different respect:

Sparse image reconstruction for molecular imaging by Michael Ting, Raviv Raichand, Alfred O. Hero III. The abstract reads:

The application that motivates this paper is molecular imaging at the atomic level. When discretized at subatomic distances, the volume is inherently sparse. Noiseless measurements from an imaging technology can be modeled by convolution of the image with the system point spread function (psf). Such is the case with magnetic resonance force microscopy (MRFM), an emerging technology where imaging of an individual tobacco mosaic virus was recently demonstrated with nanometer resolution. We also consider additive white Gaussian noise (AWGN) in the measurements. Many prior works of sparse estimators have focused on the case when H has low coherence; however, the system matrix H in our application is the convolution matrix for the system psf. A typical convolution matrix has high coherence. The paper therefore does not assume a low coherence H. A discrete-continuous form of the Laplacian and atom at zero (LAZE) p.d.f. used by Johnstone and Silverman is formulated, and two sparse estimators derived by maximizing the joint p.d.f. of the observation and image conditioned on the hyperparameters. A thresholding rule that generalizes the hard and soft thresholding rule appears in the course of the derivation. This so-called hybrid thresholding rule, when used in the iterative thresholding framework, gives rise to the hybrid estimator, a generalization of the lasso. Unbiased estimates of the hyperparameters for the lasso and hybrid estimator are obtained via Stein’s unbiased risk estimate (SURE). A numerical study with a Gaussian psf and two sparse images shows that the hybrid estimator outperforms the lasso.

a related (older) presentation can be found in A. O. Hero, R. Raich, and M. Ting, Finding dust in space: localizing atoms from noisy projections.

Here is another interesting and somewhat surprising paper: A Non-Iterative Procedure for Computing Sparse and Sparsifiable Solutions to Slightly Underdetermined Linear Systems of Equations by Andrew Yagle. The abstract reads:

We consider the problem of reconstructing a sparse image from a few of its 2-D DFT frequency values. A sparse image has pixel values that are mostly zero, with a few non-zero values at unknown locations. The number of known 2-D DFT values must exceed four times the number of non-zero pixel values. We unwrap the 2-D problem to a 1-D problem using the Good-Thomas FFT, and apply Prony's method to compute the non-zero pixel value locations. Thus we reformulate the problem as a dual 2-D harmonic retrieval problem. Our solution has three advantages over direct application of 2-D ESPRIT: (1) Instead of solving a huge generalized eigenvalue problem, we compute the roots on the unit circle of a huge polynomial; (2) the locations of the known 2-D DFT values need not form a centrosymmetric region; and (3) there are no matching issues. Our algorithm is also applicable to 2-D beamforming.

and New Atomicity-Exploiting Algorithms for Super-Resolution X-Ray Crystallography by Andrew Yagle. The abstract reads:

The X-ray crystallography problem is to reconstruct a crystalline structure from the Fourier magnitude of its diffracted scattering data. This has three major difficulties: (1) Only Fourier magnitude (not phase) data are known; (2) There is no support constraint (since the crystal is periodic); and (3) only low-wavenumber scattering data are available. But it also has two major advantages: (1) the crystal is sparse (atomicity) since it consists of isolated atoms; and (2) the crystal structure often has even symmetry. We exploit atomicity to show that the crystal can be reconstructed easily from only low wavenumber Fourier data. We also propose new algorithms for reconstruction of crystals with even or no symmetry from low-wavenumber Fourier magnitude data using two or one isomorphic replacements (4 algorithms). Small numerical examples illustrate the algorithms.

Sparse Imputation for Noise Robust Speech Recognition Using Soft Masks by Jort Gemmeke, Bert Cranen. The abstract reads:

In previous work we introduced a new missing data imputation method for ASR, dubbed sparse imputation. We showed that the method is capable of maintaining good recognition accuracies even at very low SNRs provided the number of mask estimation errors is sufficiently low. Especially at low SNRs, however, mask estimation is difficult and errors are unavoidable. In this paper, we try to reduce the impact of mask estimation errors by making soft decisions, i.e., estimating the probability that a feature is reliable. Using an isolated digit recognition task (using the AURORA-2 database), we demonstrate that using soft masks in our sparse imputation approach yields a substantial increase in recognition accuracy, most notably at low SNRs.

Credit: NASA/JPL/Space Science Institute, Photo of Saturn's rings taken by Cassini the day before yesterday.