2
$\begingroup$

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?

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

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

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.