12
$\begingroup$

Suppose $f:M \to N$ is a smooth map between complete Riemannian manifolds of the same dimension. Suppose $Df(m_0)$ is invertible, and $n$ is a point close to $f(m_0)$. Can we perform Newton iteration to find a point $m^*$ mapping to $n$ as we do in the proof of the Inverse Function Theorem, by taking $m_{i+1} = \exp_{m_i} \circ (Df_{m_i})^{-1} \circ \log_{f(m_i)}(n)$? Hopefully we would expect this to converge to a point mapping to $n$ if $n$ is chosen close enough to $f(m_0)$.

My apologies if this is nonsense; I'm still learning about Riemannian manifolds, $\log$, $\exp$, etc.

$\endgroup$
9
  • 1
    $\begingroup$ Interesting! This seems like a reasonable idea. $\endgroup$
    – user98602
    Commented Aug 12, 2015 at 21:00
  • 1
    $\begingroup$ Why are you using $Df_{m_0}$ instead of $Df_{m_i}$, which would be standard Newton iteration and guarantee convergence close enough to $f(m_0)$? $\endgroup$ Commented Aug 20, 2015 at 11:44
  • $\begingroup$ @GeorgeLowther Maybe I need to be better informed on the basic method of Newton iteration. For instance, in the proof of the inverse function theorem, I understood that we essentially use $Df_{m_0}$ (because a priori the derivative is only assumed to be invertible at a single point $m_0$, and it might be tricky to show that $m_i$ remain close enough to that point so that $Df_{m_{i}}$ remain invertible). I was thinking something similar here, but there's no reason why we couldn't assume invertibility of $Df$ where we like and get a weaker result. $\endgroup$
    – Eric Auld
    Commented Aug 20, 2015 at 11:50
  • 1
    $\begingroup$ I think they both work, but you get faster convergence using $Df_{m_i}$. $\endgroup$ Commented Aug 20, 2015 at 12:37
  • 2
    $\begingroup$ I thought you might find Chapter 6 of eeci-institute.eu/GSC2011/Photos-EECI/EECI-GSC-2011-M5/… interesting esp. the convergence analysis $\endgroup$
    – shall.i.am
    Commented Sep 2, 2015 at 13:27

1 Answer 1

1
+100
$\begingroup$

Not a full answer, but an extended comment following up on my comment above:

Pick charts $\phi:M \to \mathbb{R}^n$ and $\psi:N\to\mathbb{R}^n$; then you can "pull back" the function $f$ to a function $$g: \mathbb{R}^n\to\mathbb{R}^n,\quad x\mapsto (\psi \circ f \circ \phi^{-1})(x).$$

Now you can run Newton's method on the function $g(x) - \psi(n)$, with update rule $$x_{i+1} = x_i - (Dg)^{-1}[g(x_i)-\psi(n)].$$

Now clearly this form of Newton's method requires only differential structure on $M$ and $N$, and not a metric: no matter what charts $\phi$ and $\psi$ you pick, provided that the initial guess is sufficiently close to the root, $f$ is sufficiently regular, etc. and that the iterates $x_i$ do not leave the charts, you will converge to a solution $x_\infty$. Of course, the intermediate iterates will vary depending on your choice of charts, but "being a root" is clearly a coordinate-independent property of points of $M$.

What you've done is chosen $\phi$ and $\psi$ to be natural coordinates on $M$ and $N$. An extra wrinkle is that you are changing charts each iteration; how this affects convergence of Newton's method is not obvious to me offhand. Your formulation is nice in that it is coordinate-free: I'm not convinced it's necessarily more efficient from a computational perspective, though, since the best choice of charts (in the sense of maximizing the radius of convergence) has as much to do with the form of $f$ as $M$ and $N$. Even for $f:\mathbb{R}^2\to\mathbb{R}^2$, for instance, switching from Cartesian to polar coordinates can dramatically affect if and how quickly Newton's method converges for a given function and initial guess.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .