Tell me more ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.
up vote 2 down vote favorite

I have an iterative sequence for optimizing an EM (Expectation Maximization) algorithm based loss function $L(X)$ with $t$ being the iteration number as: $X_t=ABX_{t-1}+CX_{t-1}+X_{t-1}$ where $A$ is a diagonal matrix, $B$ and $C$ are positive semi-definite matrices. Also the diagonal entries in $A$ are the inverse of the diagonal elements of $C$. i.e, $A=Diag^{-1}(C)$.

I would like to compute the convergence rate (root-convergence rate) of this algorithm as $t\to \infty$. Am assuming it has got to do with taylor expansions, spectral radii and fixed point theorems. How is this approached or done for iterative schemes?

share|improve this question
You may get more answers if you state what EM and MM stand for and what problem they're used to solve, in the question title. – David Ketcheson Aug 22 '12 at 3:58
EM stands for Expectation Maximization – Praneeth Aug 22 '12 at 4:09
What is this scheme supposed to converge to as $t \rightarrow \infty$? Some sort of equilibrium/steady state? – Geoff Oxberry♦ Aug 22 '12 at 5:31
Yes a steady state where $||X_t-X_{t-1}||$ tends to a small value $\epsilon$ or even to zero as $t \to \infty$ where in a local/global minimum is reached. – Praneeth Aug 22 '12 at 6:36
in the title – David Ketcheson Aug 22 '12 at 12:19

1 Answer

up vote 2 down vote accepted

This is just a linear fixed-point iteration

$$ X_t = M X_{t-1}$$

where

$$\DeclareMathOperator{\diag}{diag} M = AB + C + I = (\diag C)^{-1} B + C + I .$$

The convergence rate of this iteration is linear with worst-case convergence factor equal to the spectral radius of $M$ (therefore, if $\rho(M) > 1$, the method does not converge). Furthermore, if $\rho(M) = 1$ and has any eigenvalues of magnitude 1 that are not exactly 1, the iteration also does not converge. Clearly, if $B$ and $C$ can vary independently, the iteration is not generally convergent. Note that if $\rho(M) < 1$, it always converges to 0.

share|improve this answer
What do you mean by 'eigenvalues of magnitude 1 that are not exactly 1'? Also, if 4(B+C) is the gradient of the loss, would it change the inferences on the convergence? Thanks. – Praneeth Aug 22 '12 at 12:34
$\lambda = -1$ or $\lambda = i$ are examples with magnitude $1$ that are not equal to $1$. The physical interpretation of the matrices does not change the math. Is the iteration supposed to converge to $0$? If not, perhaps you wrote down the method incorrectly. – Jed Brown Aug 22 '12 at 14:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.