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?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ This might be of some interest: arxiv.org/abs/1403.5969 $\endgroup$
    – Dustin G. Mixon
    Commented 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$
    – ofer zeitouni
    Commented Nov 21, 2014 at 16:47

1 Answer 1

Reset to default
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$.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .