Sequential sampling of Gaussian and von Mises-Fisher Random Variable

2010-12-06T19:15:11Z

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$?

Answer by Tim van Beek for Sequential sampling of Gaussian and von Mises-Fisher Random Variable

2010-12-06T19:47:26Z

Edit: The following statement is an "answer" to the first part of the question and should be ignored, since the "real meat" is in the addendum :-)

This is a rather general question, let me point out two directions in which one could proceed:

What you describe is an example of a discrete approximation to a stochastic differential equation via an Euler schema, for more details have a look at this page on the wiki Azimuth: stochastic differential equation. It is possible to define stochastic differential equations in higher dimensions, of course, and on smooth real manifolds, for example. The discrete Euler schema for an equation with additive white noise adds a Gaussian random variable on every timestep, but it is possible to define equations with different noise/random processes, see for example stochastic integral on wikipedia.
You stick to discrete time equations and processes, in this case a good buzz word to look for are "random iterative models", see for example the book of the same name by Marie Duflo, (review in ZMATH here). I'm sure there are a lot more buzz words connected to your question :-)

About calculating the distribution: There are examples in continuous and in discrete time where it is possible to calculate the distribution exactly, or to prove certain concentration theorems. In continuous time, there are for example SDE where exact solutions are known, resp. associated Fokker-Planck equations where the solution is known exactly. An example is the Ornstein-Uhlenbeck process. There it is possible to explicitly state the distribution of $x(t)$ given $x_{t=0} := x_0$.

As for discrete times, there are several theorems about the rate of convergence to the stationary distribution for certain Markov chains in Duflo's book.

Sequential sampling of Gaussian and von Mises-Fisher Random Variable - MathOverflow

Sequential sampling of Gaussian and von Mises-Fisher Random Variable

Answer by Tim van Beek for Sequential sampling of Gaussian and von Mises-Fisher Random Variable