NLA MT25, Marchenko-Pastur theorem
Flashcards
@State the Marchenko-Pastur theorem for the singular values of a random rectangular matrix.
Suppose:
- $X \in \mathbb R^{m \times n}$ with $m \ge n$, entries i.i.d. with mean $0$ and variance $1$.
- As $m, n \to \infty$ with “aspect” $n/m \to y \in (0, 1]$ fixed
Then:
- The singular values of $X$ asymptotically lie in $[\sqrt m - \sqrt n, \sqrt m + \sqrt n]$
- On $[\sqrt m - \sqrt n, \sqrt m + \sqrt n]$, the empirical singular value distribution converges to the PDF
The Marchenko-Pastur theorem states that if:
- $X \in \mathbb R^{m \times n}$ with $m \ge n$, entries i.i.d. with mean $0$ and variance $1$.
- As $m, n \to \infty$ with “aspect” $n/m \to y \in (0, 1]$ fixed
then:
- The singular values of $X$ asymptotically lie in $[\sqrt m - \sqrt n, \sqrt m + \sqrt n]$
- On $[\sqrt m - \sqrt n, \sqrt m + \sqrt n]$, the empirical singular value distribution converges to the PDF
\[p(\sigma) = \frac{1}{\pi n \sigma} \sqrt{\left( (\sqrt m + \sqrt n)^2 - \sigma^2 \right)\left(\sigma^2 - (\sqrt m - \sqrt n)^2\right)}.\]
Use this to @state an estimate for the minimum and maximum singular value, and hence the condition number of a rectangular matrix.
and hence rectangular matrices are well-conditioned with enormous probability.
@Visualise the singular value spectrum of four matrices $X \in \mathbb R^{m \times n}$ with increasing aspect ratio $m / n$ by considering the ∆marchenko-pastur theorem.
Bite-sized
For random $X \in \mathbb R^{m \times n}$ ($m \ge n$) with i.i.d. mean-$0$ variance-$1$ entries, Marchenko-Pastur says the singular values asymptotically lie in $[<span class="cloze" tabindex="0">\sqrt m - \sqrt n</span>, <span class="cloze" tabindex="0">\sqrt m + \sqrt n</span>]$.
Does the Marchenko-Pastur theorem require the entries of $X$ to be Gaussian?
No. It holds for any distribution with mean $0$ and variance $1$, as long as the entries are independent. Gaussian is convenient for analysis because it additionally enjoys orthogonal invariance, but the MP statement itself is distribution-free.
Non-asymptotic Marchenko-Pastur: the probability that a singular value of an $m \times n$ i.i.d. random matrix falls outside $[\sqrt m - \sqrt n, \sqrt m + \sqrt n]$ by an amount $t$ or more is bounded by $\exp(-c t^2)$ for some constant $c > 0$.
In one phrase, what does Marchenko-Pastur tell us about rectangular random matrices?
“Rectangular random matrices are well-conditioned.” Concretely, $\kappa _ 2(X) \approx \tfrac{1 + \sqrt{n/m}}{1 - \sqrt{n/m}} = O(1)$ for $m > n$, independent of the matrix size — with enormous probability.