Wednesday, February 26, 2014

Small ball probabilities for linear images of high dimensional distributions / Circular law for random matrices with exchangeable entries

Today, we are more on the more theoretical sides of things:

We study concentration properties of random vectors of the form AX, where X = (X_1,..., X_n) has independent coordinates and A is a given matrix. We show that the distribution of AX is well spread in space whenever the distributions of X_i are well spread on the line. Specifically, assume that the probability that X_i falls in any given interval of length T is at most p. Then the probability that AX falls in any given ball of radius T \|A\|_{HS} is at most (Cp)^{0.9 r(A)}, where r(A) denotes the stable rank of A.

An exchangeable random matrix is a random matrix with distribution invariant under any permutation of the entries. For such random matrices, we show, as the dimension tends to infinity, that the empirical spectral distribution tends to the uniform law on the unit disc. This is an instance of the universality phenomenon known as the circular law, for a model of random matrices with dependent entries, rows, and columns. It is also a non-Hermitian counterpart of a result of Chatterjee on the semi-circular law for random Hermitian matrices with exchangeable entries. The proof relies in particular on a reduction to a simpler model given by a random shuffle of a rigid deterministic matrix, on Hermitization, and also on combinatorial concentration of measure and combinatorial Central Limit Theorem. A crucial step is a polynomial bound on the smallest singular value of exchangeable random matrices, which may be of independent interest.

Image Credit: NASA/JPL/Space Science Institute
Full-Res: N00220668.jpg

N00220668.jpg was taken on February 22, 2014 and received on Earth February 24, 2014. The camera was pointing toward TITAN at approximately 2,340,288 miles (3,766,329 kilometers) away, and the image was taken using the CL1 and UV3 filters.

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

No comments: