# 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 Nov 21, 2014 at 14:53
• It is not the spectrum of X that follows the MP law, but rather the singular values. Nov 21, 2014 at 16:47

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$.