Range of $a$ such that $w \leftarrow w-a x \langle w, x \rangle$ converges almost surely?

Question

Suppose $x_i$ come from 2-d standard Normal centered at 0. What is the range of $a$ for which the following iteration converges almost surely?

$$w_{i+1} = w_i-a x_i \langle w_i, x_i \rangle$$

For 1-d, one can write $w_{i+1}^2$ as $w_i^2=w_0^2\prod_i (1-\alpha x_i^2)$, take log and apply central limit theorem. For 2-D, one could use a similar approach, but using matrix logarithm instead of regular logarithm. However, this side-steps some technical details (we have a product of rank-1 matrices, how can you take matrix logarithm of that?) so I'm wondering if the resulting estimate is valid.

In particular, it predicts that iteration converges iff $\alpha \in (0.12131, 0.91861)$, while in simulations, I'm seeing convergence for $\alpha=0.93$ (but divergence for $\alpha=0.94$)

The question is equivalent to finding $\alpha$ such that $C_i$ converges almost surely where

$$C_i=w_i w_i^T$$ $$C_{i+1}=(1-\alpha x_i x_i^T)C_i(1-\alpha x_i x_i^T)$$

Answer 1

As you say, the threshold is around $a=0.937087$.

The exact condition for convergence is $$ \int_{0}^{2\pi}\int_0^\infty\log(1-2ar^2\cos^2\theta+a^2r^4\cos^2\theta)re^{-r^2/2}\,dr\,d\theta<0. $$ I don't think there will be a clean formula for $a$.

The derivation of the expression is as follows: Let $r_j=\|w_j\|$. The entire problem is rotationally symmetric. Additionally, the operation is linear. Combining these two facts, we have $r_{j+1}=Z_jr_j$ where $(Z_j)$ is an i.i.d sequence of random variables. Taking logarithms, we have that $r_j\to 0$ if $\mathbb E \log Z<0$ and $r_j\to\infty$ if $\mathbb E \log Z>0$.

To compute $\mathbb E\log Z$, suppose without loss of generality that $w_j=(1,0)$. Write $x_{j+1}=(r\cos\theta,r\sin\theta)$ where $r$ is distributed as a Rayleigh random variable and $\theta$ is uniform on $[0,2\pi]$. Then $$ w_{j+1}=(1,0)-a(r\cos\theta,r\sin\theta)r\cos\theta, $$ so that $Z_{j+1}=\|w_{j+1}\|$. The expression for $\mathbb E\log Z_{j+1}$ is then as displayed in the first display equation.