4
$\begingroup$

Suppose $x_i\in \mathbb{R}^d$ is sampled IID from $\mathcal{N}(0,H)$. Let $A_i=(I-x_i x_i^T)$ and assume $d$ is large. What are necessary conditions for the following to converge with probability 1?

$$\prod_{i=0}^\infty A_i \overset{p}{\to} 0$$

Convergence in probability is hard, so optimization literature almost always replaces it with "convergence in the mean". I want to bound the size of the "gap" caused by this simplification.

Background:

  • Iosif Pinelis found necessary and sufficient conditions here for isotropic $x_i$, no gap

  • Jair Taylor suggested $\det A_i>1 \text{ a.s.}$, vacuous for Gaussian $x_i$

  • "$d$ is large" fails to capture the notion of high-dimensionality if we allow some dimensions to have zero variance. Alternative is to say that "$R$ is large" where $R$ is "effective rank" of Bartlett Section 3.1 $$R=\frac{\operatorname{Tr}(H)^2}{\operatorname{Tr}(H^2)}$$

  • Spectral radius $\rho$ provides necessary and sufficient conditions for $\prod_i A_i$ to converge in the mean $$\rho(2H+hh^TH^{-1})<2$$

    . where $H$ is diagonal and $h$ is a vector of diagonal entries

Update Apr 12 2023 I see numerical evidence that "convergence in the mean" and "convergence in probability" become equivalent when $H$ is diagonal with entries proportional to $1,\frac{1}{2},\frac{1}{3},\ldots,\frac{1}{d}$ and $d$ is large.

For $d=1$ I can take an instance where distribution converges in the mean and scale it some amount. The result is divergence in the mean, but convergence in probability. Here's distribution of $\|a_{\text{step}}\|^2$ where $a_{\text{step}+1}=A_\text{step} a_\text{step}$

enter image description here

On other hand with $d=100$, it appears hard to find such scenario. Either both "in the mean" and "in probability" converge, or they both diverge. enter image description here

$\endgroup$
3
  • $\begingroup$ I would like to know what set (lowercase) h belongs to and how it is quantified, since these things are left unmentioned. $\endgroup$ Commented Apr 4, 2023 at 3:14
  • $\begingroup$ Some background on this problem $\endgroup$ Commented Apr 21, 2023 at 6:36
  • $\begingroup$ @DanielAsimov looks like $h$ was not really needed, I replaced it with $H$ which is an arbitrary covariance matrix $\endgroup$ Commented Oct 13, 2023 at 15:42

0

You must log in to answer this question.

Browse other questions tagged .