# Root Convergence rate of Iterative Scheme

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?

• 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 – hearse 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. – hearse Aug 22 '12 at 6:36
• in the title – David Ketcheson Aug 22 '12 at 12:19

$$X_t = M X_{t-1}$$
$$\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.
• $\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