6
$\begingroup$

Suppose we solve an $m\times n$ full-rank system of equations $Ax=b$ by iterating the following for a small enough $\mu>0$

$$x=x+\mu B(b-Ax)$$

Is there a nice description of kinds of $B$ which make this iteration convergent? For instance, for $n=1$, $A,B$ can be viewed as vectors, and this iteration converges iff their dot product is positive. What about $n>1$?

  1. $B=A^\dagger$ is (trust-region) Newton's method
  2. $B=A^T$ is gradient descent on least-squares objective
  3. $B=I$ is modified Richardson iteration, only works for positive-definite $A$

Curious if there's a family of methods between 2. and 3. -- converges for any full-rank $A$, but without relying too much on $A^Ty$ (much more expensive than $Ax$ in my application)

Edit

  • It seems sufficient that $(BA)^T+BA\succ 0$. This means $\mu$ can be made small enough to ensure each step is contractive. However, it is not necessary since for not normal $BA$, convergence may happen after initial transient "hump".

  • it is necessary (but not sufficient) that all eigenvalues of $BA$ have a positive real part. Negative eigenvalue means you'll be pushed away from solution in those direction.

  • which means it is necessary that $B=-SA^\dagger$ for some stable matrix $S$ when $n=m$

  • It is sufficient that $B=A^T P$ for some positive definite $P$. This ensures update has form to $I-\mu C$ with positive definite $C$

  • Last condition seems too restrictive, since we could use $B=\text{sign}(A^T)$

$\endgroup$

1 Answer 1

1
$\begingroup$

Found the answer in Francesca Rapetti course notes here, preconditioned Richardson can be made convergent iff $BA$ is positive stable, which is true iff $B=SA^\dagger+Z^T$ for some positive stable $S$ and $Z^TA=0$.

enter image description here

So for instance for the following matrix $$PA=\left( \begin{array}{cc} 2 & 100 \\ -300 & 100 \\ \end{array} \right)$$

Would set $$\alpha=\frac{51}{15100}$$

Which gives $\rho(I-\alpha PA)=1$ (notebook)

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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