CS: Feedback on analog compression, Complex Sparse Projections for CS, Hybrid CS, Statistical Mechanical Assessment, Sparse Channel Estimation

Yihong Wu whom I featured the day before yesterday sent me the following:

Dear Igor,

.... The journal version of the analog compression paper is published last month and available here:

Yihong and Sergio Verdú, "Rényi Information Dimension: Fundamental Limits of Almost Lossless Analog Compression", IEEE Transactions on Information Theory, Vol. 56, No. 8, pp. 3721 -- 3748, August 2010.

Essentially what we did is a Shannon theory for compressed sensing. As an approach to lossless encoding of analog sources by real numbers rather than bits, compressed sensing  deals with efficient recovery of sparse real vectors from the information provided by linear measurements. Instead of a worst-case (Hamming) approach, we develop a Shannon-theoretical framework for compressed sensing, where we model sources as random processes and adopt a source-coding (resp. joint source-channel coding) approach to noiseless (resp. noisy) compressed sensing problems. The information dimension and MMSE dimension of the source prove to be the fundamental limits of compression rate. The research about the noisy case is still in progress, with some partial results summarized in that poster.

Let me know if you have any question or comment.

Best regards,
Yihong

Thanks Yihong !


I also found the following thanks to the Google:

Complex Sparse Projections for Compressed Sensing by Abdolreza Abdolhosseini Moghadam and Hayder Radha. The abstract reads:

Sparse projections for compressed sensing have been receiving some attention recently. In this paper, we consider the problem of recovering a k-sparse signal (x) in an n-dimensional space from a limited number (m) of linear, noiseless compressive samples (y) using complex sparse projections. Our approach is based on constructing complex sparse projections using strategies rooted in combinatorial design and expander graphs. We are able to recover the non-zero coefficients of the k-sparse signal (x) iteratively using a low-complexity algorithm that is reminiscent of well-known iterative channel decoding methods. We show  that the proposed framework is optimal in terms of sample requirements for signal recovery (m = O (k log(n=k))) and has a decoding complexity of O (mlog(n=m)), which represents a tangible improvement over recent solvers. Moreover we prove that using the proposed complex-sparse framework, on average 2k \lt m · 4k real measurements (where each complex sample is counted as two real measurements) suffice to recover a k-sparse signal perfectly.

Hybrid Compressed Sensing by Abdolreza Abdolhosseini Moghadam and Hayder Radha. The abstract reads:

We consider the problem of recovering a k-sparse signal (x) from hybrid (complex and real), noiseless compressive samples (y) using a mixture of complex-valued sparse and realvalued dense projections within a single matrix. The proposed Hybrid Compressed Sensing (HCS) employs the complex-sparse part of the projection matrix to divide the n-dimensional signal (x) into subsets. In turn, each subset of the signal (coefficients) is mapped onto a complex sample of the measurement vector (y). Under a worst-case scenario of such sparsity-induced mapping, when the number of complex sparse measurements is sufficiently large then this mapping leads to the isolation of a significant fraction of the k non-zero coefficients into different complex measurement samples from y. Using a simple property of complex numbers (namely complex phases) one can identify the isolated non-zeros of x. After reducing the effect of the identified non-zero coefficients from the compressive samples, we utilize the realvalued dense submatrix to form a full rank system of equations to recover the signal values in the remaining indices (that are not recovered by the sparse complex projection part). We show that the proposed hybrid approach can recover a k-sparse signal (with high probability) while requiring only m ¼ 3k 3 p n=2k real measurements (where each complex sample is counted as two real measurements). We also derive expressions for the optimal mix of complex-sparse and real-dense rows within an HCS projection matrix. Further, in a practical range of sparsity ratio (k=n), the hybrid approach outperforms even the most complex compressed sensing frameworks (namely basis pursuit with dense Gaussian matrices). The theoretical complexity of HCS is less than the complexity of solving a full-rank system of m linear equations. In practice, the complexity can be lower than this bound.

Also on arxiv:

Statistical Mechanical Assessment of a Reconstruction Limit of Compressed Sensing: Toward Theoretical Analysis of Correlated Signals by Koujin Takeda, Yoshiyuki Kabashima. The abstract reads:

We provide a scheme for exploring the reconstruction limit of compressed sensing by minimizing the general cost function under the random measurement constraints for generic correlated signal sources. Our scheme is based on the statistical mechanical replica method for dealing with random systems. As a simple but non-trivial example, we apply the scheme to a sparse autoregressive model, where the first differences in the input signals of the correlated time series are sparse, and evaluate the critical compression rate for a perfect reconstruction. The results are in good agreement with a numerical experiment for a signal reconstruction.

Sparse Channel Estimation for Amplify-and-Forward Two-way Relay Network with Compressed Sensing by Guan Gui, Qun Wan, Wei Peng, Fumiyuki Adachi. The abstract reads:

Amplify-and-forward two-way relay network (AFTWRN) was introduced to realize high-data rate transmission over the wireless frequency-selective channel. However, AFTWRC requires the knowledge of channel state information (CSI) not only for coherent data detection but also for the selfdata removal. This is partial accomplished by training sequence-based linear channel estimation. However, conventional linear estimation techniques neglect anticipated sparsity of multipath channel and thus lead to low spectral efficiency which is scarce in the field of wireless communication. Unlike the previous methods, we propose a sparse channel estimation method which can exploit the sparse structure and hence provide significant improvements in MSE performance when compared with traditional LS-based linear channel probing strategies in AF-TWRN. Simulation results confirm the proposed methods.

Image Credit: NASA/JPL/Space Science Institute 

N00161950.jpg was taken on August 27, 2010 and received on Earth August 30, 2010. The camera was pointing toward GREIP, and the image was taken using the CL1 and CL2 filters.