NLA MT25, Gaussian random matrices
Flashcards
@Define a Gaussian random matrix.
A matrix $G \in \mathbb R^{m \times n}$ whose entries $G _ {ij}$ are i.i.d. $\sim N(0, 1)$.
@State what is meant by the orthogonal invariance of Gaussian random matrices $G$.
The distribution of a Gaussian random matrix is invariant under orthogonal multiplication, i.e. if:
- $G$ is a Gaussian matrix
- $Q$ is an orthogonal matrix independent of $G$
Then:
- $QG$ and $GQ$ are both Gaussian random matrices
@State a result about the conditioning of a square Gaussian matrix, and contrast this with the rectangular case.
Suppose $G \in \mathbb R^{n \times n}$ has i.i.d. $N(0, 1)$ entries. Then $G$ is almost surely nonsingular, but $\sigma _ \min(G)$ has density bounded away from zero at the origin, so for small $t$,
\[\mathbb P(\sigma _ \min(G) < t) \sim t,\]and hence consequently
\[\mathbb E[\sigma _ \min(G)^{-2}] = \infty.\]For rectangular random matrices with $m \ge n$ has $\sigma _ \min \approx \sqrt{m} - \sqrt{n}$ bounded away from zero by ∆marchenko-pastur, and hence $\mathbb E[\sigma _ \min^{-2}]$ is finite.
Bite-sized
The two key facts about Gaussian random matrices used throughout randomised NLA are: orthogonal invariance (the distribution is unchanged by left/right multiplication by an independent orthogonal matrix), and Marchenko-Pastur (rectangular Gaussians are well-conditioned with high probability).
Why is the orthogonal invariance of Gaussian random matrices so useful in randomised NLA analysis?
It lets us replace $GQ$ or $QG$ with another Gaussian matrix wherever $Q$ is an orthogonal matrix independent of $G$. Combined with Marchenko-Pastur conditioning of the resulting rectangular Gaussian, this is the workhorse tool behind error bounds for sketch-and-solve, Blendenpik, HMT randomised SVD, and generalised Nyström.
Two equivalent proofs of orthogonal invariance for a Gaussian column $g \sim N(0, I_n)$ under independent orthogonal $Q$: (a) compute mean $\mathbb E[Q g] = $ $0$ and covariance $\mathbb E[(Qg)(Qg)^\top] = $ $Q I_n Q^\top = I_n$, so $Qg$ has the same multivariate Gaussian distribution; (b) the joint pdf $\tfrac{1}{(2\pi)^{n/2}} e^{- \Vert g \Vert ^2/2}$ depends only on $ \Vert g \Vert $, and $ \vert \det Q \vert = 1$, so a change of variables leaves the pdf invariant.
When is a dense Gaussian sketch not the right choice in practice, despite being analytically convenient?
When forming $GA$ is too expensive: a dense Gaussian sketch costs $O(smn)$ flops, the same order as direct QR-based least-squares. Structured fast sketches like SRFT ($G = SFD$ with $F$ an FFT, $D$ random $\pm 1$ diagonal, $S$ subsampling) reduce this to $O(mn \log s + sn^2)$. CountSketch is even faster on sparse $A$. The trade-off is that the theoretical analysis becomes much more delicate.