Return to Question

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 list of vectors:

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

$u_i$ contains component of $v_i$ orthogonal to $v_{i-1},v_{i-2},\ldots$ so we expect it to shrink with $i$. Can we say how the expected value of $\|u_i\|^2$ decays with $i$? For isotropic Gaussian, it decays linearly, while simulation below suggests there is a simple correspondence for the case at hand, can we say what it is?

For $d=1000$, the following is graph for mean and variance of $\|u_k\|^2$

Motivation some optimization tasks in ML exhibit $1/k$ decay of eigenvalues (Section 3.5 of NQM paper. $1/k$ decay is implied by log-regularity, and by alpha-capacity conditions, Appendix A.1 of Varre paper. Knowing the rate at new vectors approach linear dependence lets us bound regret from using a particular batch size.

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 list of vectors:

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

$u_i$ contains component of $v_i$ orthogonal to $v_{i-1},v_{i-2},\ldots$ so we expect it to shrink with $i$. Can we say how the expected value of $\|u_i\|^2$ decays with $i$? For isotropic Gaussian, it decays linearly, while simulation below suggests there is a simple correspondence for the case at hand, can we say what it is?

For $d=1000$, the following is graph for mean and variance of $\|u_k\|^2$

Motivation some optimization tasks in ML exhibit $1/k$ decay of eigenvalues (Section 3.5 of NQM paper. $1/k$ decay is implied by log-regularity, and by alpha-capacity conditions, Appendix A.1 of Varre paper. Knowing the rate at new vectors approach linear dependence lets us bound regret from using a subset of the full dataset for linear estimation problems

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 list of vectors:

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

$u_i$ contains component of $v_i$ orthogonal to $v_{i-1},v_{i-2},\ldots$ so we expect it to shrink with $i$. Can we say how the expected value of $\|u_i\|^2$ decays with $i$? For isotropic Gaussian, it decays linearly, while simulation below suggests there is a simple correspondence for the case at hand, can we say what it is?

For $d=1000$, the following is graph for mean and variance of $\|u_k\|^2$

Motivation some optimization tasks in ML exhibit $1/k$ decay of eigenvalues (Section 3.5 of NQM paper. $1/k$ (or faster) decay is already assumed in analysis of algorithms (implied by log-regularity, and by alpha-capacity conditions, Appendix A.1 of Varre paper). Hence knowing this rate with $1/k$ assumption would let us bound the regret from using batch size $<d$ in each optimization step.

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 list of vectors:

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

$u_i$ contains component of $v_i$ orthogonal to $v_{i-1},v_{i-2},\ldots$ so we expect it to shrink with $i$. Can we say how the expected value of $\|u_i\|^2$ decays with $i$? For isotropic Gaussian, it decays linearly, while simulation below suggests there is a simple correspondence for the case at hand, can we say what it is?

For $d=1000$, the following is graph for mean and variance of $\|u_k\|^2$

Motivation some optimization tasks in ML exhibit $1/k$ decay of eigenvalues (Section 3.5 of NQM paper. $1/k$ decay is implied by log-regularity, and by alpha-capacity conditions, Appendix A.1 of Varre paper. Knowing the rate at new vectors approach linear dependence lets us bound regret from using a particular batch size.

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 list of vectors:

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

$u_i$ contains component of $v_i$ orthogonal to $v_{i-1},v_{i-2},\ldots$ so we expect it to shrink with $i$. Can we say how the expected value of $\|u_i\|^2$ decays with $i$? For isotropic Gaussian, it decays linearly, while simulation below suggests there is a simple correspondence for the case at hand, can we say what it is?

For $d=1000$, the following is graph for mean and variance of $\|u_k\|^2$

Motivation some optimization tasks in ML exhibit $1/k$ decay of eigenvalues (Section 3.5 of NQM paper. Also Wigner's semicircle law predicts $1/k$ decay for the first few eigenvalues), knowing this rate would let us bound the regret from using batch size $<d$ in each optimization step. Ideally, one would be able to figure out how many vectors are needed to capture half the orthogonal variance present in the full set of vectors in terms of simple properties of the distribution, like $\text{Tr}(\Sigma)$,$ \|\Sigma\|$

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 list of vectors:

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

$u_i$ contains component of $v_i$ orthogonal to $v_{i-1},v_{i-2},\ldots$ so we expect it to shrink with $i$. Can we say how the expected value of $\|u_i\|^2$ decays with $i$? For isotropic Gaussian, it decays linearly, while simulation below suggests there is a simple correspondence for the case at hand, can we say what it is?

For $d=1000$, the following is graph for mean and variance of $\|u_k\|^2$

Motivation some optimization tasks in ML exhibit $1/k$ decay of eigenvalues (Section 3.5 of NQM paper. $1/k$ (or faster) decay is already assumed in analysis of algorithms (implied by log-regularity, and by alpha-capacity conditions, Appendix A.1 of Varre paper). Hence knowing this rate with $1/k$ assumption would let us bound the regret from using batch size $<d$ in each optimization step.