CS: Random Matrix Theory and Compressive Sensing

Following up on the recent entry on Random Matrix Theory and a new blog entry entitled Bad News for PCA by Sarah, I initially used some of the following references to get a sense on how RMT is used. An interesting one is given in:

Financial Applications of Random Matrix Theory: a short review by Jean-Philippe Bouchaud, Marc Potters. The abstract reads:

We discuss the applications of Random Matrix Theory in the context of financial markets and econometric models, a topic about which a considerable number of papers have been devoted to in the last decade. This mini-review is intended to guide the reader through various theoretical results (the Marcenko-Pastur spectrum and its various generalisations, random SVD, free matrices, largest eigenvalue statistics, etc.) as well as some concrete applications to portfolio optimisation and out-of-sample risk estimation.

On March 1, Marc made a presentation explaining in some basic fashion the reason why RMT is of interest in the finance business:




One of the thing that struck me was that it was actually relevant to some of the normalization we do in machine learning which may or may not be useful. In essence, when you perform a normalization in diffusion geometries, you are removing some information about what some of the modes mean. But coming back to compressive sensing and its connection to RMT, in light of the use of RMT in array signal processing ( Fundamental limit of sample generalized eigenvalue based detection of signals in noise using relatively few signal-bearing and noise-only samples by Raj Rao Nadakuditi, Jack Silverstein) let me wonder aloud how this type of study could be connected by to compressive sensing array signal processing as featured this past week:

• Multiple Measurement Vector problems with Subspace based algorithm, Compressive MUSIC A missing link between compressive sensing and array signal processing by Jong Min Kim, Ok Kyun Lee, Jong Chul Ye
• iMUSIC: Iterative MUSIC Algorithm for Joint Sparse Recovery with Any Rank by Kiryung Lee, Yoram Bresler.

Roman Vershynin has some slides on the interrelationship between Random Matrix Theory and Compressive Sensing:

• Random matrix theory from the functional analytic perspective
• On the role of sparsity in compressed sensing and random matrix theory,
• Sparse representations and invertibility of random matrices,
• Analysis of Random Measurements: An introduction to the non-asymptotic theory of random matrices

and has just released an article entitled: How close is the sample covariance matrix to the actual covariance matrix? by Roman Vershynin. The abstract reads:

Given a distribution in Rn, a classical estimator of its covariance matrix is the sample covariance matrix obtained from a sample of N independent points. What is the optimal sample size N = N(n) that guarantees estimation with a xed accuracy in the operator norm? Suppose the distribution is supported in a centered Euclidean ball of radius O(pn). We conjecture that the optimal sample size is N = O(n) for all distributions with nite fourth moment, and we prove this up to an iterated logarithmic factor. This problem is motivated by the optimal theorem of M. Rudelson [21] which states that N = O(n log n) for distributions with nite second moment, and a recent result of R. Adamczak et al. [1] which guarantees that N = O(n) for sub-exponential distributions.

Other References:
M. Rudelson, R. Vershynin, Non-asymptotic theory of random matrices: extreme singular values,
R. Vershynin, Approximating the moments of marginals of high dimensional distributions.
R. Vershynin, On the role of sparsity in Compressed Sensing and Random Matrix Theory, Commentary.