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.

Call for Paper: Special Issue on Dependent Component Analysis

There will be a special issue on Dependent Component Analysis in EURASIP Journal on Advances in Signal Processing.  Dependent component analysis (DCA) is a big extension of ICA, and is one of the main directions of the ICA field in recent years.  I think this issue should be a good window to see current progress on DCA.

The issue includes the following topics (but not limited to):
- Multidimensional component analysis
- (Independent) subspace analysis
- Vector component analysis
- Correlated component analysis
- Topographical component analysis
- Tree-dependent component analysis
- Blind dependent component analysis
- Informed (Bayesian) dependent component analysis
- and their applications

Manuscripts Submission Date:  Feb 1, 2012.
Publication date: Oct.1, 2012.


--------------------------------------------------------
Image: Nepenthes.talangensis, grown in my partio.

How people in science see each other

Today Tobias sent us a picture titled "How people in science see each other". It is very funny.  Enjoying! (click the picture for larger view)

Noise Folding Puts Tough Requirements on Compressed Sensing Algorithms?

Tonight I read two papers on noise folding in the compressed sensing problem. They are:

[1] M.A.Davenport, J.N.Laska, J.R.Treichler, R.G.Baraniuk, The Pros and Cons of Compressive Sensing for Wideband Signal Acquisition: Noise Folding vs. Dynamic Range. Preprint, April, 2011

[2] E.Arias-Castro, Y.C.Eldar, Noise Folding in Compressed Sensing, IEEE Signal Processing Letters, vol.18, no.8, 2011

The noise folding is a silent topic in the hot compressed sensing field. The problem is described as follows:
y = A (x + n) + v                 (1)
Namely, the signal itself contains noise (called 'signal noise' or 'source noise'). v is the measurement noise. The model can be rewritten as
y = Ax + (An+v) = Ax + u.   (2)
Intuitively, the 'noise' has increased, and this will bring "troubles" to algorithms.

The above two papers rigorously analyze how the signal noise n affects the estimation quality, the RIP condition, and so on.

In [1], the authors consider the case when the matrix A is orthonormal and v is not present. They found that the noise folding has a significant impact on the amount of noise present in CS measurements; every time one doubles the subsampling factor g (i.e. the ratio of column number of A to its row number), the SNR loss increases roughly by 3dB, namely,

In [2] the authors considered a general case (i.e. A is not necessarily orthonormal and the measurement noise v is present) and showed that the model (1) is equivalent to
y_hat = Bx +z
where B is a matrix whose coherence and RIP constants are very close to those of A, and z is zero-mean white noise vector with covariance matrix (sigma^2 + g * sigma_0^2) I., where E{v} = 0, E{v v^T} = sigma^2 * I,  and E{n}=0, E{n n^T} = sigma_0^2 * I.. The result also suggests that the effect of signal noise n is to degrade the SNR by a factor of g.

Clearly, these results tell every algorithm designer (note: most algorithms essentially perform on the rewritten model (2) ):

1) To design algorithms that work well under strong noise environment, especially when the subsampling factor g is large.

2) To design algorithms that do not need any prior knowledge on the noise level. In practice we perhaps can get some knowledge on the strength of measurement noise v, but we have much less knowledge on the strength of signal noise n. Consequently, we don't know the strength of the equivalent noise u (see the rewritten model (2)). Note that many algorithms use the knowledge of the noise level (in model (2) ) to set a good value for their regularization parameter. So, this means that the regularization parameter (related to the noise level) should be automatically learned by algorithms themselves, not pre-set.

A quick example is the EEG source localization. In this application, the measurement noise level is well controlled by  EEG recording machines. However, we know little about the strength of the signal noise. As we have known,  the regularization parameter strongly affects algorithms' performance. So, an algorithm with user-defined regularization parameter may perform far from optimally.

Neuroskeptic: What Is Brain "Activation" on fMRI?

Neuroskeptic has a blog entry, reporting a 2010 paper:

Harris S, Jones M, Zheng Y, & Berwick J (2010). Does neural input or processing play a greater role in the magnitude of neuroimaging signals? Frontiers in neuroenergetics, 2 PMID: 20740075

which argues that 80% of the BOLD signal is caused by internal processing of neurons, and only 20% is due to input from other neurons.

This result again points out the big gap between fMRI activity and EEG activity, since the input from other neurons is thought to be the "source" of EEG.  This also gives us a caution on a group of EEG source localization approaches which use fMRI activity as a spatial constraint for the localization problem. 


The abstract of the paper is:

An important constraint on how hemodynamic neuroimaging signals such as fMRI can be interpreted in terms of the underlying evoked activity is an understanding of neurovascular coupling mechanisms that actually generate hemodynamic responses. The predominant view at present is that the hemodynamic response is most correlated with synaptic input and subsequent neural processing rather than spiking output. It is still not clear whether input or processing is more important in the generation of hemodynamics responses. In order to investigate this we measured the hemodynamic and neural responses to electrical whisker pad stimuli in rat whisker barrel somatosensory cortex both before and after the local cortical injections of the GABA_A agonist muscimol. Muscimol would not be expected to affect the thalamocortical input into the cortex but would inhibit subsequent intra-cortical processing. Pre-muscimol infusion whisker stimuli elicited the expected neural and accompanying hemodynamic responses to that reported previously. Following infusion of muscimol, although the temporal profile of neural responses to each pulse of the stimulus train was similar, the average response was reduced in magnitude by ∼79% compared to that elicited pre-infusion. The whisker-evoked hemodynamic responses were reduced by a commensurate magnitude suggesting that, although the neurovascular coupling relationships were similar for synaptic input as well as for cortical processing, the magnitude of the overall response is dominated by processing rather than from that produced from the thalamocortical input alone.

Recent conferences and workshops on sparsity and compressed sensing

Here are some recent conferences and workshops on sparsity and compressed sensing. From the link you can read abstract, download pdf files, and/or watch videos. Enjoy!

IMA High Dimensional Phenomena

Duke Workshop on Sensing and Analysis of High-Dimensional Data (SAHD)

SPARS 2011: Signal Processing with Adaptive Sparse Structured Representations

ICML 2011 workshop on Structured Sparsity: Learning and Inference

The Neurocritic: Neuromarketing means never having to say you're peer reviewed (but here's your NYT op-ed space)

Here is an interesting post by The Neurocritic:

The Neurocritic: Neuromarketing means never having to say you're peer reviewed (but here's your NYT op-ed space)

A simple comparison of sparse signal recovery algorithms when the dictionary matrix is highly coherent

Sparse signal recovery (or called compressed sensing in literature) has wide applications in source localization, radar detection, target tracking, and power spectrum estimation, etc. The basic model is:
y = A x + v,
where A is a know dictionary matrix, y is an available measurement vector (data vector), and v is the unknown measurement noise vector. The task is to estimate the source vector x, which has only K nonzero elements (K is a very small number). In the applications mentioned above, the dictionary matrix A is highly coherent.

In this post I'll show an experiment result, in which twelve typical algorithms were compared when the dictionary matrix A was highly correlated. The dictionary matrix was a simplified real-world lead-field matrix used in EEG source localization (see the figure below), whose size was 80 x 390. The maximum coherence of the columns of A was 0.9983.

The twelve algorithms were:
(1) T-MSBL [1] (although T-MSBL is developed for the multiple measurement vector model, it can also be used in this single measurement vector model)
(2) EM-SBL[2]
(3) ExCov [3]
(4) CoSaMP[4]
(5) Subspace Pursuit [5]
(6) Approximate Message Passing (AMP) [6] 
(7) Bayesian Compressive Sensing (BCS)[7]
(8) Magic-L1[8]
(9) Hard Thresholding Pursuit (HTP) [9]
(10) Fast Bayesian Matching Pursuit (FBMP)[10]
(11) FOCUSS[11]
(12) Smooth L0 (SL0) [12]

Some of the algorithms needed to know some a priori information, and we fed these algorithms with the required a priori information. Details are given in the following list:

T-MSBL: did not require any a priori information
EM-SBL: did not require any a priori information
ExCov: did not require any a priori information
CoSaMP: fed with the number of nonzero elements
Subspace Pursuit: fed with the number of nonzero elements
AMP: did not require any a priori information
BCS: did not require any a priori information
Magic-L1: needed to know the SNR to calculate the regularization parameter
FBMP: fed with the true SNR value, and the number of nonzero elements (used to calculate the activity probability of elements)
FOCUSS: fed with the true SNR value
HTP: noise was removed, since it can only be used in noiseless cases; in the noisy case it completely failed
Smooth L0: noise was removed, since it can only be used in noiseless cases; in the noisy case it completely failed

The experiment was repeated 1000 trials. In each trial, the number of nonzero elements in the source vector x was 3, i.e.K=3. These nonzero elements had the unit amplitude. Their indexes in x were randomly chosen. SNR was 25dB. The measurement indexes are Failure Rate and MSE.

The comparison result in terms of Failure Rate is given below:

The result in terms of MSE is given below, where I only show the MSE's of 8 algorithms, since other algorithms completely failed.

We can clearly see T-MSBL has the best performance. In many applications such as neuroelectromagnetic source localization, Direction-of-Arrival estimation, radar detection, under-water sonar processing, power spectrum estimation, the ability of algorithms to handle the cases when dictionary matrices are highly coherent is very important (especially in the presence of noise). The simple experiment shows the advantage of T-MSBL in these cases.

All the codes and the demo to reproduce the above results can be downloaded at: http://sccn.ucsd.edu/%7Ezhang/Experiment.rar

Details about the experiment can be found in the short note: http://sccn.ucsd.edu/%7Ezhang/comparison.pdf


Reference:

[1] Z. Zhang and B. D. Rao, “Sparse signal recovery with temporally
correlated source vectors using sparse Bayesian learning,” IEEE Journal
of Selected Topics in Signal Processing, vol. 5, no. 5, pp. 912–926, 2011.

[2] D. P. Wipf and B. D. Rao, “Sparse Bayesian learning for basis selection,”
IEEE Trans. on Signal Processing, vol. 52, no. 8, pp. 2153–2164, 2004.

[3] K. Qiu and A. Dogandzic, “Variance-component based sparse signal
reconstruction and model selection,” IEEE Trans. on Signal Processing,
vol. 58, no. 6, pp. 2935–2952, 2010.

[4] D. Needell and J. A. Tropp, “CoSaMP: Iterative signal recovery from
incomplete and inaccurate samples,” Applied and Computational Harmonic
Analysis, vol. 26, no. 3, pp. 301–321, 2009.

[5] W. Dai, O. Milenkovic,  “Subspace pursuit for compressive sensing signal reconstruction,”
IEEE Trans. Information Theory, vol. 55, no. 5, pp. 2230–2249, 2009.

[6] D. L. Donoho, A. Maleki, and A. Montanari, “Message-passing algorithms
for compressed sensing,” PNAS, vol. 106, no. 45, pp. 18 914–
18 919, 2009.

[7] S. Ji, Y. Xue, and L. Carin, “Bayesian compressive sensing,” IEEE Trans.
on Signal Processing, vol. 56, no. 6, pp. 2346–2356, 2008.

[8] E. Candes, J. Romberg, and T. Tao, “Stable signal recovery from
incomplete and inaccurate measurements,” Communications on Pure and
Applied Mathematics, vol. 59, no. 8, pp. 1207–1223, 2006.

[9] S. FOUCART, “Hard thresholding pursuit: an algorithm for compressive
sensing,” preprint, 2011. [Online]. Available: http://www.math.drexel.
edu/»foucart/HTP Rev.pdf

[10] P. Schniter, L. C. Potter, and J. Ziniel, “Fast bayesian matching pursuit:
Model uncertainty and parameter estimation for sparse linear models,”
preprint. [Online]. Available: http://www2.ece.ohio-state.edu/»schniter/
pdf/tsp09 fbmp.pdf

[11] I. F. Gorodnitsky and B. D. Rao, “Sparse signal reconstruction from
limited data using FOCUSS: a re-weighted minimum norm algorithm,”
IEEE Trans. on Signal Processing, vol. 45, no. 3, pp. 600–616, 1997.

[12] H. Mohimani, M. Babaie-Zadeh, and C. Jutten, “A fast approach for
overcomplete sparse decomposition based on smoothed l0 norm,” IEEE
Trans. on Signal Processing, vol. 57, no. 1, pp. 289–301, 2009.