Compressed Sensing Work by My Friends and Colleagues

Recently some of my friends and colleagues sent me their recent work on compressed sensing/sparse signal recovery. Thanks them for keeping me informed! Here are their nice work: I welcome everybody send me his/her work and I would like to introduce his/her work in my blog :)

Hakan informed me of his work:
Karahanoglu, N.B., and Erdogan, H., “Compressed sensing signal recovery via A* Orthogonal Matching Pursuit,” ICASSP’11, Prag, May 2011.
 The journal version is:
Karahanoglu, N.B., and Erdogan, H., “A* orthogonal matching pursuit: best-first search for compressed sensing signal recovery,” submitted, available as: arxiv 1009.0396,  last update in Sep. 2011.
 Matlab code can be downloaded here. 

The abstract reads:

Compressed sensing aims at reconstruction of sparse signals following acquisition in reduced dimensions, which makes the recovery process under-determined. Due to sparsity, required solution becomes the one with minimum ℓ0 norm, which is untractable to solve for. Commonly used reconstruction techniques include ℓ1 norm minimization and greedy algorithms. This manuscript proposes a novel semi-greedy approach, namely A* Orthogonal Matching Pursuit (A*OMP), which performs A* search for the sparsest solution on a tree whose paths grow similar to the Orthogonal Matching Pursuit (OMP) algorithm. Paths on the tree are evaluated according to an auxiliary cost function, which should compensate for different path lengths. For this purpose, we suggest three different structures. We show that novel dynamic cost functions provide improved results as compared to a conventional choice. Finally, we provide reconstruction results on both synthetically generated data and images showing that A*OMP outperforms well-known CS reconstruction methods, Basis Pursuit (BP), OMP and Subspace Pursuit (SP).

Kiryung informed me of his latest updated work:

Kiryung Lee, Yoram Bresler, Marius Junge, Subspace Methods for Joint Sparse Recovery, arXiv:1004.3071v4

The abstract reads:
We propose robust and efficient algorithms for the joint sparse recovery problem in compressed sensing, which simultaneously recover the supports of jointly sparse signals from their multiple measurement vectors obtained through a common sensing matrix. In a favorable situation, the unknown matrix, which consists of the jointly sparse signals, has linearly independent nonzero rows. In this case, the MUSIC (MUltiple SIgnal Classification) algorithm, originally proposed by Schmidt for the direction of arrival problem in sensor array processing and later proposed and analyzed for joint sparse recovery by Feng and Bresler, provides a guarantee with the minimum number of measurements. We focus instead on the unfavorable but practically significant case of rank-defect or ill-conditioning. This situation arises with limited number of measurement vectors, or with highly correlated signal components. In this case MUSIC fails, and in practice none of the existing methods can consistently approach the fundamental limit. We propose subspace-augmented MUSIC (SA-MUSIC), which improves on MUSIC so that the support is reliably recovered under such unfavorable conditions. Combined with subspace-based greedy algorithms also proposed and analyzed in this paper, SA-MUSIC provides a computationally efficient algorithm with a performance guarantee. The performance guarantees are given in terms of a version of restricted isometry property. In particular, we also present a non-asymptotic perturbation analysis of the signal subspace estimation that has been missing in the previous study of MUSIC.

This is the fourth version. I read its third version, which has about 30 pages. However, the fourth version doubles the page number. So I asked Kiryung what are the main changes compared to the previous version. Kiryung replied:

"We added another subspace greedy algorithm for partial recovery step. This ends up with better empirical performance.  All algorithms presented in this paper have guarantees.  We updated the analysis by using a version of RIP,  which is different from the original uniform RIP and is satisfied by a weaker condition.  "



Justin sent me his journal paper on MMV model using AMP. It's a very cool algorithm. However, the journal paper has not been opened to the public. But I think you can read his conference paper soon:

J. Ziniel and P. Schniter, ``Efficient Message Passing-Based Inference in the Multiple Measurement Vector Problem,'' to appear in Proc. Asilomar Conf. on Signals, Systems, and Computers (Pacific Grove, CA), Nov. 2011.

-------------------------------------
Image: Nepenthes. hamata grown in my patio.