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?

  1. Is the conjecture true?
  2. Any suggestions for how to approximate this quantity, or obtain a "nicer" pair of necessary/sufficient conditions?
  • 4
    $\begingroup$ This doesn't directly answer your question, but there is a classic paper of Furstenberg and Kesten showing that the limit $\lim_{n \to \infty} \frac{1}{n} E[\log f_n]$ exists under mild hypotheses (and there is also a central limit theorem): mathscinet.ams.org/mathscinet-getitem?mr=121828 $\endgroup$
    – Terry Tao
    Aug 14, 2020 at 20:37


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.