CS: A note, "Compressed" CS, Statistical Mechanical Analysis of CS

Found on Math Overflow a question and answer on an inequality related to compressed sensing. In the comment section of yesterday's entry, Laurent Jacques made the following statement:

...In connection with the last paper mentioned in your post [On the Systematic Measurement Matrix for Compressed Sensing in the Presence of Gross Errors by Zhi Li, Feng Wu and John Wright], if I'm not wrong, an RIP analysis of matrix [Phi I] (and even [Phi Omega] for any MxM orthonormal matrix Omega) has been realized before in:

Mark Davenport, Jason Laska, Petros Boufounos, and Richard Baraniuk, A simple proof that random matrices are democratic. (Rice University ECE Department Technical Report TREE-0906, November 2009)

and used here:

Jason Laska, Mark Davenport, and Richard Baraniuk, Exact signal recovery from sparsely corrupted measurements through the pursuit of justice. (Asilomar Conf. on Signals, Systems, and Computers, Pacific Grove, California, November 2009) (see Theorem 2 inside)

It seems that Zhi Li, Feng Wu and John Wright. do not know these (previous/simultaneous?) works, and they reproved RIP for [Phi I] in their Section V. It seems however that their proof is slightly different from that of Davenport et al., and the bound on the minimal number of measurement not exactly the same. Notice also that Davenport et al. proved this result for any RIP matrix enlarged with the identity, and not only enlarged Gaussian matrices....

Thanks Laurent ! I hope this has nothing to do with the fact some of our readers in China cannot read this blog directly ?

Dick Gordon, one of the discoverer of the ART algorithm, also added something to the Radiative Transfer papers in the comment section:

re: Inverse radiative transfer and melanoma

Here’s some more prior literature on the inverse radiative transfer problem:

Chandrasekhar, S. (1960). Radiative Transfer. New York, Dover Publications.

Nevoscopy, the 3D imaging of nevi (beauty marks), which are all potential skin melanomas, has been addressed from the point of view of forward and inverse radiative transfer:

Patwardhan, S.V., A.P. Dhawan & P.A. Relue (2003). Monte Carlo simulation of light-tissue interaction: three-dimensional simulation for trans-illumination-based imaging of skin lesions. IEEE Transactions on Biomedical Engineering 52(7), 1227-1236.

Kini, P. & A.P. Dhawan (1992). Reconstruction of embedded absorbers in random media with applications in non-invasive 3D imaging of skin lesions. Proc. SPIE 1767, 360-371.

The initial approach was standard 3D computed tomography, albeit from only 3 views:

Dhawan, A.P., R. Gordon & R.M. Rangayyan (1984). Nevoscopy: three-dimensional computed tomography for nevi and melanomas in situ by transillumination. IEEE Trans. Med. Imaging MI-3(2), 54-61.

The intent is to obtain the nevus thickness, which is the most prognostic factor for metastasis: once the melanoma penetrates the dermis, cure rate on excision drops from 95% to 5%. Differences in thickness of 0.1mm matter, so this is not something your partner can detect. Actual shape doesn’t matter much, making this an ideal CS application. I’d like to see nevoscopy developed into a whole body robotic skin scanner for detecting premetastasis melanoma. Contact me at gordonr@cc.umanitoba.ca if interested. Thanks.
Yours, -Dick Gordon

Thanks Dick for the insight! The 2003 paper still seem to be looking at the forward problem which really says to me that the 1992 paper did not do well in other cases than the ones looked in the paper. Thanks to yesterday's series of papers we can hope to have better reconstruction capabilities in the future.

Found on arxiv, the following three preprints: "Compressed" Compressed Sensing by Galen Reeves and Michael Gastpar. The abstract reads:

The field of compressed sensing has shown that a sparse but otherwise arbitrary vector can be recovered exactly from a small number of randomly constructed linear projections (or samples). The question addressed in this paper is whether an even smaller number of samples is sufficient when there exists prior knowledge about the distribution of the unknown vector, or when only partial recovery is needed. An information-theoretic lower bound with connections to free probability theory and an upper bound corresponding to a computationally simple thresholding estimator are derived. It is shown that in certain cases (e.g. discrete valued vectors or large distortions) the number of samples can be decreased. Interestingly though, it is also shown that in many cases no reduction is possible.

Statistical Mechanical Analysis of a Typical Reconstruction Limit of Compressed Sensing by Yoshiyuki Kabashima, Tadashi Wadayama, Toshiyuki Tanaka. The abstract reads:

We use the replica method of statistical mechanics to examine a typical performance of correctly reconstructing $N$-dimensional sparse vector $\bx=(x_i)$ from its linear transformation $\by=\bF \bx$ of dimension $P$ on the basis of minimization of the $L_p$-norm $||\bx||_p=\lim_{\epsilon \to +0} \sum_{i=1}^N |x_i|^{p+\epsilon}$. We characterize the reconstruction performance by the critical relation of the successful reconstruction between the ratio $\alpha=P/N$ and the density $\rho$ of non-zero elements in $\bx$ in the limit $P, N \to \infty$ while keeping $\alpha \sim O(1)$ and allowing asymptotically negligible reconstruction errors. When $\bF$ is composed of independently and identically distributed random variables of zero mean and a fixed variance, the critical relation $\alpha_c(\rho)$ for $p=1$ accords with that obtained by Donoho ({\em Discrete and Computational Geometry}, vol. 35, pp. 617--652, 2006) who utilized a technique of combinatorial geometry and allowed no reconstruction errors. We also show that the critical relation does not change as long as $\bF^{\rm T}\bF$ can be characterized by a rotationally invariant random matrix ensemble and $\bF \bF^{\rm T}$ is typically of full rank.

Statistical Mechanical Analysis of Compressed Sensing Utilizing Correlated Compression Matrix by Koujin Takeda, Yoshiyuki Kabashima. The abstract reads:

We investigate a reconstruction limit of compressed sensing for a reconstruction scheme based on the L1-norm minimization utilizing a correlated compression matrix with a statistical mechanics method. We focus on the compression matrix modeled as the Kronecker-type random matrix studied in research on multi-input multi-output wireless communication systems. We found that strong one-dimensional correlations between expansion bases of original information slightly degrade reconstruction performance.

Image Credit: NASA/JPL/Space Science Institute. Saturn as seen by Cassini on Jan 25th, 2010.