Given a finite set of matrices $A_i$, sample $n$ matrices uniformly with replacement and compute $f_n=\|A_1 A_2\cdots A_n\|^2$. When is the following limit finite?
$$\lim_{n\to \infty} E[f_n]$$
I'm especially interested in the case when $A_i=I-a x_i x_i^\intercal$ for some vector $x_i$ and positive scalar $a$.
A paper by Deffosez formulated a sufficient condition for this to be finite, and conjectured it to also be a necessary condition, Lemma 1 of "Averaged Least-Mean-Squares: Bias-Variance Trade-offs and Optimal Sampling Distributions."
For scalar $x$, their formula recovers a standard stability result:
$$a\le \frac{2 E[x^2]}{E[x^4]}$$
For vector $x$ in $d$ dimensions, second moment tensor $X^2$, fourth moment tensor $X^4$ and Einstein summation notation:
$$a\le \text{sup}_{A\in \mathcal{S}(\mathbb{R}^d)}\frac{2 A_{ij}X^2_{jk} A_{ki}}{A_{ij}X^4_{ijkl}A_{kl}}$$
However, this formulation is difficult to apply in practice -- optimization over the space of symmetric matrices where each step of optimization takes $O(d^4)$ operations. It's also hard to interpret -- which properties of the set of $A_i$'s are most responsible for divergent behavior?
- Is the conjecture true?
- Any suggestions for how to approximate this quantity, or obtain a "nicer" pair of necessary/sufficient conditions?
