NLA MT25, Marchenko-Pastur theorem


Flashcards

@State the Marchenko-Pastur theorem.


Suppose:

  • $X \in \mathbb R^{m \times n}$ is a random matrix
  • $X _ {ij}$ are i.i.d. with mean 0 and variance 1

Then the singular values of $X$ follow the Marchenko-Pastur distribution with density

\[\sigma \sim \frac 1 x \sqrt{((\sqrt m + \sqrt n) - x)(x - (\sqrt m - \sqrt n))}\]

and support $[\sqrt m - \sqrt n, \sqrt m + \sqrt n]$.

The Marchenko-Pastur theorem status that if:

  • $X \in \mathbb R^{m \times n}$ is a random matrix
  • $X _ {ij}$ are i.i.d. with mean 0 and variance 1

Then the singular values of $X$ follow the Marchenko-Pastur distribution with density

\[\sigma \sim \frac 1 x \sqrt{((\sqrt m + \sqrt n) - x)(x - (\sqrt m - \sqrt n))}\]

and support $[\sqrt m - \sqrt n, \sqrt m + \sqrt n]$.

Use this to @state an estimate for the minimum and maximum singular value, and hence the condition number of a rectangular matrix.

\[\begin{aligned} &\sigma _ \min(X) \approx \sqrt m + \sqrt n \\ &\sigma _ \max(X) \approx \sqrt m - \sqrt n \\ &\kappa _ 2(X) \approx \frac{1 + \sqrt{n / m}}{1 - \sqrt{n / m}} = O(1) \end{aligned}\]

and hence rectangular matrices are well-conditioned with enormous probability.





Related posts