# Restricted singular values of random matrix

Let $X \in \mathbb{R}^{p\times p}$ be a large square matrix, consisting of i.i.d. Gaussian entries. Then it is known that the singular values of $X$ follow the Marchenko-Pastur law.

Now let's introduce an adversary, who arbitrarily selects $p/2$ rows of X and form a submatrix. Can the adversary succeed to make the singular values of this matrix look very different from the Marchenko-Pastur law of a $\frac{p}{2} \times p$ Gaussian matrix?

• This might be of some interest: arxiv.org/abs/1403.5969 – Dustin G. Mixon Nov 21 '14 at 14:53
• It is not the spectrum of X that follows the MP law, but rather the singular values. – ofer zeitouni Nov 21 '14 at 16:47

## 1 Answer

It depends what do you mean by "look very different". I assume that you mean that the empirical measure is close to that of the MP law. The answer below assumes this is what you meant.

Short answer: no.

Longer answer: there is an exponential (in $p$) number of ways to choose the rows. But the concentration of the empirical measure is exponential in $p^2$.

• Could you please name some references? Thanks! – John Wong Dec 21 '14 at 8:31
• For the concentration a handy reference is my paper with A. Guionnet ECP 2000. – ofer zeitouni Dec 22 '14 at 5:54