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$
2
  • 2
    $\begingroup$ This might be of some interest: arxiv.org/abs/1403.5969 $\endgroup$ Nov 21, 2014 at 14:53
  • 2
    $\begingroup$ It is not the spectrum of X that follows the MP law, but rather the singular values. $\endgroup$ Nov 21, 2014 at 16:47

1 Answer 1

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$
2
  • $\begingroup$ Could you please name some references? Thanks! $\endgroup$
    – John Wong
    Dec 21, 2014 at 8:31
  • $\begingroup$ For the concentration a handy reference is my paper with A. Guionnet ECP 2000. $\endgroup$ Dec 22, 2014 at 5:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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