Skip to main content
1 of 14

Decay of orthogonal contributions in a random set of vectors

Suppose we sample $k$ vectors $v$ from normal distribution centered at zero and diagonal covariance with diagonal entries $1,\frac{1}{2},\ldots,\frac{1}{d}$ and normalize $v$:

$$\frac{v_1}{\|v_1\|},\frac{v_2}{\|v_2\|}, \ldots ,\frac{v_k}{\|v_k\|}$$

We apply Gram-Schmidt orthogonalization to this list to get a new set of vectors

$$u_1,u_2,u_3,\ldots,u_k$$

Can we say how the expected value of $\|u_i\|^2$ decays with $i$? For isotropic Gaussian, it decays linearly, while simulation suggests there is a simple correspondence for the case at hand, can we say what it is?

enter image description here

Motivation some optimization tasks in ML exhibit $1/k$ decay of eigenvalues, knowing this rate would let us bound the regret from using batch size $<d$ in each optimization step