Rate of convergence

Perhaps we should consider the rate of convergence of the optimization method. Glass will turn to crystal if you wait long enough. But we never can wait long enough. Inversion methods are notorious for slow convergence. Consider that matrix inversion costs are proportional to the cube of the number of unknowns; our most powerful computers balk when the number of unknowns goes above the mid hundreds; and our images generally have millions. Perhaps the crystal quartz analogy is not far fetched.

The question is whether explicitly including the missing data slows things down by adding more unknowns and complexity, or whether it can speed things up. Matrix inversion by iterative methods amounts to iterative application of an operator and its conjugate. Given $\bold d\approx\bold A\bold x$,the solution $\bold x$ is implicitly developed in a power series

$$\bold x {=}\left[ \sum_n \alpha_n (\bold A' \bold A)^n \right] \bold A'\bold d$$ (6)

where the $\alpha_n$ are implicitly determined by the numerical method (such as steepest descent or conjugate gradients). The operator $\bold A$ has the rows $\bold a_k$ on top and under those rows are optional rows of $\bold a_m$and under that are the optional stabizing rows of $\sqrt{\lambda}\,\bold I$.Why should convergence be faster when the matrix $\bold A$ includes missing data rows? I'll suggest that when the data space is completed (made large enough to fully determine the solution) then the conjugate operator $\bold A'$ has a better chance of being close to the inverse operator. Many of our data processing procedures are so huge that we do little more than apply the conjugate operator, and the conjugate to the missing-data-extended operator is better than the conjugate to the data-truncated operator.