CS: CS-BP new code, Compressive-Projection Principal Component Analysis, Matrix Completion, SDP Rank Reduction

Over the past three days since it was mentioned in this blog, the statistics counter on the YALL1 page of Yin Zhang has increased by more than 90 visits. It may look small, but it generally takes a long time to do this type of direct advertizing to connaisseurs like yourselves. If there is one figure of merit that I am proud of from running this blog, this is one of them: I am really happy that the blog provides rapid access to new idea or implementation that will over time have an impact. If you are releasing a code and do not see it either on this blog or on the big picture page, then please by all means let me know about it. I'll be glad to send the Nuit Blanche Effect your way.

While we are talking about reconstruction code, I noted that the CS-BP (Compressive Sensing - Belief Propagation) code/page had a new implementation by Danny Bickson (check the NBP Non-parametric belief propagation (NBP) implementation).

Simon Foucart has an interesting syllabus out for his Graduate Seminar on Compressed Sensing

I just found the following piece entitled Rethinking Signal Processing as published in the Communication of the ACM and Laurent Duval just tried Wolfram|Alpha and blogged on his experience: CS or underdetermined systems do not yield much response from that system.

James Fowler who commented on the fact that "all y'all" is the plural of "y'all", is also behind a concept called Compressive-Projection Principal Component Analysis. The connection to Compressive Sensing is explained in this excerpt:

We note that, in its reliance on encoder-side random projections, CPPCA bares some similarity to the emerging mathematical paradigm of compressed sensing1 (CS) (e.g., [7–11]). Although both CS and CPPCA consist of lightweight projection-based encoding, their decoder-side reconstructions differ significantly—CS assumes a fixed basis ensuring sparsity while CPPCA determines a data-specific PCA basis directly from the random projections. Experimental results presented below reveal that CPPCA achieves reconstruction performance substantially superior to that of a multiple-vector CS variant when applied to hyperspectral data.

The three papers on this concept are: Compressive-Projection Principal Component Analysis and the First Eigenvector by James E. Fowler. The abstract reads:

An analysis is presented that extends existing Rayleigh-Ritz theory to the special case of highly eccentric distributions. Specifically, a bound on the angle between the first Ritz vector and the orthonormal projection of the first eigenvector is developed for the case of a random projection onto a lower-dimensional subspace. It is shown that this bound is expected to be small if the eigenvalues are widely separated, i.e., if the data distribution is highly eccentric. This analysis verifies the validity of a fundamental approximation behind compressive projection principal component analysis, a technique proposed previously to recover from random projections not only the coefficients associated with principal component analysis but also an approximation to the principal-component transform basis itself.

Compressive-Projection Principal Component Analysis by James Fowler. The abstract reads:

Principal component analysis (PCA) is often central to dimensionality reduction and compression in many applications, yet its data-dependent nature as a transform computed via expensive eigendecomposition often hinders its use in severely resource-constrained settings such as satellite-borne sensors. A process is presented that effectively shifts the computational burden of PCA from the resource-constrained encoder to a presumably more capable base-station decoder. The proposed approach, compressive-projection PCA (CPPCA), is driven by projections at the sensor onto lower-dimensional subspaces chosen at random, while the CPPCA decoder, given only these random projections, recovers not only the coefficients associated with the PCA transform, but also an approximation to the PCA transform basis itself. An analysis is presented that extends existing Rayleigh-Ritz theory to the special case of highly eccentric distributions; this analysis in turn motivates a reconstruction process at the CPPCA decoder that consists of a novel eigenvector reconstruction based on a convex-set optimization driven by Ritz vectors within the projected subspaces. As such, CPPCA constitutes a fundamental departure from traditional PCA in that it permits its excellent dimensionality-reduction and compression performance to be realized in an light-encoder/heavy-decoder system architecture. In experimental results, CPPCA outperforms a multiple-vector variant of compressed sensing for the reconstruction of hyperspectral data.

Compressive-Projection Principal Component Analysis for the Compression of Hyperspectral Signatures by James E. Fowler. The abstract reads:

A method is proposed for the compression of hyperspectral signature vectors on severely resource-constrained encoding platforms. The proposed technique, compressive-projection principal component analysis, recovers from random projections not only transform coefficients but also an approximation to the principal-component basis, effectively shifting the computational burden of principal component analysis from the encoder to the decoder. In its use of random projections, the proposed method resembles compressed sensing but differs in that simple linear reconstruction suffices for coefficient recovery. Existing results from perturbation theory are invoked to argue for the robustness under quantization of the eigenvector-recovery process central to the proposed technique, and experimental results demonstrate a significant rate-distortion performance advantage over compressed sensing using a variety of popular bases.

and Fast and Near--Optimal Matrix Completion via Randomized Basis Pursuit by Zhisu Zhu, Anthony Man-Cho So, Yinyu Ye. The abstract reads:

Motivated by the philosophy and phenomenal success of compressed sensing, the problem of reconstructing a matrix from a sampling of its entries has attracted much attention recently. Such a problem can be viewed as an information{theoretic variant of the well{studied matrix completion problem, and the main objective is to design an efficient algorithm that can reconstruct a matrix by inspecting only a small number of its entries. Although this is an impossible task in general, Candes and co-authors have recently shown that under a so{called incoherence assumption, a rank r n£n matrix can be reconstructed using semidefinite programming (SDP) after one inspects O(nr log6 n) of its entries. In this paper we propose an alternative approach that is much more e±cient and can reconstruct a larger class of matrices by inspecting a signi¯cantly smaller number of the entries. Specifically, we ¯rst introduce a class of so{called stable matrices and show that it includes all those that satisfy the incoherence assumption. Then, we propose a randomized basis pursuit (RBP) algorithm and show that it can reconstruct a stable rank r n£n matrix after inspecting O(nr log n) of its entries. Our sampling bound is only a logarithmic factor away from the information{theoretic limit and is essentially optimal. Moreover, the runtime of the RBP algorithm is bounded by O(nr2 log n+n2r), which compares very favorably with the ­(n4r2 log12 n) runtime of the SDP{based algorithm. Perhaps more importantly, our algorithm will provide an exact reconstruction of the input matrix in polynomial time. By contrast, the SDP based algorithm can only provide an approximate one in polynomial time.

In the following paper by some of the same authors, there is a mention of the Johnson–Lindenstrauss lemma: A Unified Theorem on SDP Rank Reduction by Anthony Man-Cho So, Yinyu Ye, Jiawei Zhang. The abstract reads:

We consider the problem of finding a low–rank approximate solution to a system of linear equations in symmetric, positive semidefinite matrices, where the approximation quality of a solution is measured by its maximum relative deviation, both above and below, from the prescribed quantities. We show that a simple randomized polynomial–time procedure produces a low–rank solution that has provably good approximation qualities. Our result provides a unified treatment of and generalizes several well–known results in the literature. In particular, it contains as special cases the Johnson–Lindenstrauss lemma on dimensionality reduction, results on low–distortion embeddings into low–dimensional Euclidean space, and approximation results on certain quadratic optimization problems.

In [1], the connection between the Johnson-Lindenstrauss Lemma (an older result) and Compressive Sensing is made clear:

....Also, it is known that any matrix satisfying the Johnson-Lindenstrauss lemma also satisfies the near isometry property required for compressed learning [19]. However, the reverse is not true: there are some matrices, such as random Fourier matrices, that satisfy the near isometry property of compressed sensing, known as the restricted isometry property, but they do not satisfy the Johnson-Lindenstrauss lemma; ....

Reference:

[1] Compressed learning: Universal sparse dimensionality reduction and learning in the measurement domain by Robert Calderbank, Sina Jafarpour, and Robert Schapire.

Credit photo: NASA/JPL/Space Science Institute, Image taken on May 13, 2009.