I don't find any article discussing this problem, so I dare to ask it.
Suppose we are dealing with a data $x_0 \in \mathbb{R}$ and a function $f:\mathbb{R} \to \mathbb{R}$. Say we repeatedly apply $f$ on the initial data to generate a sequence $(x_0, x_1, \cdots)$ where $x_1 = f(x_0), x_2 = f(x_1), x_3 = f(x_2), \cdots$. It is guaranteed that the function $f$ will converges to a point $x'$, but I'm only interested in computing sequence up to $x_n$.
Now I want to see what happens if the sequence is perturbed. Let's define the perturbed sequence $(\tilde{x}_0, \tilde{x}_1, \cdots)$ as follows.
- $\tilde{x}_0 = x_0$
- For $\tilde{x}_i$ with $i > 0$, first compute $x_i = f(\tilde{x}_{i-1})$ and pick a random point from a Gaussian distribution $N(x_i, \sigma)$ with some fixed $\sigma$. This random point will be picked independently from $(\tilde{x}_0, \cdots,\tilde{x}_{i-2})$ but only depends on the previous point $\tilde{x}_{i-1}$.
I want to generalize this experiment such that the data $x$ live in higher dimension or even on a hypersphere. Or maybe using some distributions other than gaussian. But first of all, I need to know the distribution of $\tilde{x}_n$.
I'm guessing the perturbed value $\tilde{x}_n$ will have some distribution (probably gaussian) centered at $x_n$ with a variance being a function of $n$ and $\sigma$, but it's somewhat hard to find such a distribution. If it's impossible to compute the distribution, I'd like to show that the distribution of $\tilde{x}_n$ is sharply concentrated around $x_n$.
Does my guessing seem reasonable? Then how can I solve this? Any suggestion?
updated later.
Previously, I phrased my question in a general terminology since I worried that my question would be too focused and narrow. Now I'll enunciate my original question.
I'm working on tweaking power iteration to find a dominant eigenvector $v_1$ for a given symmetric and semi-definite matrix $A\in\mathbb{R}^{d\times d}$. The power iteration initially picks a random vector $q_0$ and computes $q_1 = \frac{Aq_0}{||Aq_0||}$, $q_2 = \frac{Aq_1}{||Aq_1||}$, ... , $q_n = \frac{Aq_{n-1}}{||Aq_{n-1}||}$. We can regard it as $n$ rounds of 'normalized matrix-vector multiplication.' The normalization guarantees that each $q_i$ is a unit vector. As long as the initial vector $q_0$ is not perpendicular to $v_1$, $q_n$ converges to $v_1$.
In my setting, the computation of $\frac{Aq_{i-1}}{||Aq_{i-1}||}$ is perturbed; it returns a perturbed unit vector $\tilde{q}_i$ which is modeled as a von Mises-Fisher (vMF) distribution over a hypershpere in $\mathbb{R}^d$. For the mean vector $\mu$ and the concentration parameter $\kappa$, the pdf of vMF distribution in $d$-dimensional hypersphere is $f_d(x; \mu, \kappa) = C_d(\kappa) \exp(\kappa\mu^T x)$ with some normalization factor $C_d(\kappa)$. The greater the value of $\kappa$, the higher the concentration of the distribution around the mean direction $\mu$. (I assume that $\kappa$ is fixed for the entire round.) It means each round returns $\tilde{q}_i$, a unit vector randomly picked around the original vector $q_i = \frac{A\tilde{q}_i}{||A\tilde{q}_{i-1}||}$.
I assume that the perturbed power iteration also converges to the dominant eigenvector but under a restricted condition. But finding out the asymptotic behavior of $\tilde{q}_n$ is somewhat tricky since for each round a vMF random variable undergoes normalized matrix-vector multiplication and maps to some distribution other than vMF distribution.
My question is:
- Does $\tilde{q}_n$ still converge to the dominant eigenvector?
- Is there any reference to find out the distribution of $\tilde{q}_n$? Or can I show it sharply concentrated around the dominant eigenvector?
- Is there any useful distribution on a hypersphere other than vMF that will help analyzing the distribution of $\tilde{q}_n$?