CS: The readers' corner, GPU/Multicore for SPIRiT, Lower Bounds in Sparse Recovery, Spectral microscopy and compressive millimeter-wave holography.

The bad news is Phoenix won't revive itself after the Martian winter. It looks like the solar panels did not make it. The good news is we have many readers who wanted to share their contribution with the rest of the community, here we go:

Miki Lustig, now at Berkeley sent me the following:

Hi Igor,

FYI, my student Mark Murphy has just released a GPGPU + multicore implementation of our compressed sensing parallel MRI code.

It is linked http://www.eecs.berkeley.edu/~mlustig/Software.html

-- Miki
..

For more information on SPIRiT refer to this paper M. Lustig and J. Pauly “SPIRiT: Iterative Self-Consistent Parallel Imaging Reconstruction from Arbitrary k-Space Sampling”, Magnetic Resonance in Medicine, 2010, In Press. The L1SPIRiT page is here. From the introduction of the page:

Michael Lustig's l1-SPIRiT is a robust, iterative algorithm for artifact-free reconstruction of MR images acquired with Parallel Imaging and Compressed Sensing acceleration. In the MRI community, there is some reluctance to adopt iterative approaches to image reconstruction due to the computationally intense nature of the algorithms. This software package demonstrates that the recent "manycore" processors, in particular General-Purpose GPUs and multi-core CPUs, provide more than enough computational throughput to make iterative reconstruction algorithms feasible.

Thanks Miki. I'll add that to the compressive sensing hardware page (in the category where GPUs are used for reconstruction).

Mergen Nachin a fourth year undergraduate student at MIT double majoring in Computer Science and Mathematics just released his Undergraduate Advanced Project (undergraduate "thesis") supervised by Piotr Indyk, entitled: Lower Bounds on the Column Sparsity of Sparse Recovery Matrices. Beyond, this interesting news, I believe this is the first time we have somebody from Ulan Bator as a contributor to the field of compressive sensing. This is awesome. Here is the thesis: Lower Bounds on the Column Sparsity of Sparse Recovery Matrices by Mergen Nachin. The abstract reads:

It was recently shown that the following algorithms [BGI+08], [BI09] can approximately recover n-dimensional signal x from its sketch Ax, where the sketch length is O(k log(n/k)) and the column sparsity of A is O(log(n/k)). Our main goal in this report is to show that this column sparsity bound is tight when A is an m x n matrix with m = O(k log(n/k)).

Thanks Mergen for the heads-up and congratulations on your degree.

Christy Fernandez-Cull at Duke, sent me the following:

Hey Igor,

... I noticed on your blog that you mention work from a CS workshop at Duke related to "Image segmentation with a compressive snapshot spectral imager." Just wanted to let you know that this work was also conducted in the Duke Imaging and Spectroscopy Program and that other people were also indicated on the poster (Kerkil Choi and David Brady). Also, in case you're interested a paper related to that work was recently released - "Identification of fluorescent beads using a coded aperture snapshot spectral imager"
http://www.opticsinfobase.org/abstract.cfm?uri=ao-49-10-B59
On a tangential note, a millimeter-wave application to compressive holography has also been recently published - "Millimeter-wave compressive holography"
http://www.opticsinfobase.org/abstract.cfm?uri=ao-49-19-E67

I enjoy your blog.

Have a great week.

The paper being refered to is: Identification of fluorescent beads using a coded aperture snapshot spectral imager by Christy Fernandez-Cull, Kerkil Choi, David J. Brady, and Tim Oliver. The abstract reads:

We apply a coded aperture snapshot spectral imager (CASSI) to fluorescence microscopy. CASSI records a two-dimensional (2D) spectrally filtered projection of a three-dimensional (3D) spectral data cube. We minimize a convex quadratic function with total variation (TV) constraints for data cube estimation from the 2D snapshot. We adapt the TV minimization algorithm for direct fluorescent bead identification from CASSI measurements by combining a priori knowledge of the spectra associated with each bead type. Our proposed method creates a 2D bead identity image. Simulated fluorescence CASSI measurements are used to evaluate the behavior of the algorithm. We also record real CASSI measurements of a ten bead type fluorescence scene and create a 2D bead identity map. A baseline image from filtered-array imaging system verifies CASSI's 2D bead identity map.

the other one is behind a paywall: Millimeter-wave compressive holography by Christy Fernandez-Cull, David Wikner, Joseph Mait, Michael Mattheiss, and David Brady. The abstract reads:

We describe an active millimeter-wave holographic imaging system that uses compressive measurements for three-dimensional (3D) tomographic object estimation. Our system records a two-dimensional (2D) digitized Gabor hologram by translating a single pixel incoherent receiver. Two approaches for compressive measurement are undertaken: nonlinear inversion of a 2D Gabor hologram for 3D object estimation and nonlinear inversion of a randomly subsampled Gabor hologram for 3D object estimation. The object estimation algorithm minimizes a convex quadratic problem using total variation (TV) regularization for 3D object estimation. We compare object reconstructions using linear backpropagation and TV minimization, and we present simulated and experimental reconstructions from both compressive measurement strategies. In contrast with backpropagation, which estimates the 3D electromagnetic field, TV minimization estimates the 3D object that produces the field. Despite undersampling, range resolution is consistent with the extent of the 3D object band volume.

I also found: Sparse Fourier Sampling in Millimeter-Wave Compressive Holography by Christy Fernandez, David Brady, Joseph N. Mait, and David A. Wikner. The abstract reads:

We analyze the impact of sparse sampling on millimeter-wave (MMW) two-dimensional (2-D) holographic measurements for three-dimensional (3-D) object reconstruction. Simulations address 3-D object estimation efficacy. We present 3-D object reconstructions from experimental data.

While looking around, Google also found Christy's recently released PhD thesis :


Computational spectral microscopy and compressive millimeter-wave holography. The abstract reads:

This dissertation describes three computational sensors. The first sensor is a scanning multi-spectral aperture-coded microscope containing a coded aperture spectrometer that is vertically scanned through a microscope intermediate image plane. The spectrometer aperture-code spatially encodes the object spectral data and nonnegative least squares inversion combined with a series of reconfigured two-dimensional (2D spatial-spectral) scanned measurements enables three-dimensional (3D) (x, y, λ) object estimation. The second sensor is a coded aperture snapshot spectral imager that employs a compressive optical architecture to record a spectrally filtered projection of a 3D object data cube onto a 2D detector array. Two nonlinear and adapted TV-minimization schemes are presented for 3D (x,y,λ) object estimation from a 2D compressed snapshot. Both sensors are interfaced to laboratory-grade microscopes and applied to fluorescence microscopy. The third sensor is a millimeter-wave holographic imaging system that is used to study the impact of 2D compressive measurement on 3D (x,y,z) data estimation. Holography is a natural compressive encoder since a 3D parabolic slice of the object band volume is recorded onto a 2D planar surface. An adapted nonlinear TV-minimization algorithm is used for 3D tomographic estimation from a 2D and a sparse 2D hologram composite. This strategy aims to reduce scan time costs associated with millimeter-wave image acquisition using a single pixel receiver.

Thanks Christy, and congratulations on your Ph.D.

Finally, a reader of the blog sent me the following:

Hello Igor,
Thank you for sharing your codes with the world people.
I wish to build a measurement matrix by scrambled block hadamard ensemble. I use the code sbhe.m . It always shows :
Error using ==> cat CAT arguments dimensions are not consistent Error in ==> sbhe at 37 v2 = cat(2,vv,round(1+rand(mt,1)*(ntotal-1)));
I don't know what's wrong.
Attached is the code I downloaded from your homepage.
Can you help me to solve this problem? Thank you.

I don't know what is wrong either, last time I used it, it worked, so I really need to have the parameters used to get this error otherwise I am spending too much time on something that is not really what I want to do for the day. In any case, if somebody has a better implementation or can find the "bug" please come forward and I'll advertize it on the blog.

Image credit: NASA/JPL-Caltech/University of Arizona. Two images of the Phoenix Mars lander taken from Martian orbit in 2008 and 2010. The 2008 lander image shows two relatively blue spots on either side corresponding to the spacecraft's clean circular solar panels. In the 2010 image scientists see a dark shadow that could be the lander body and eastern solar panel, but no shadow from the western solar panel.