8 December 2007 - 15:19The Inverse Function Theorem

I was working on methods for determining the inverse of a specific function. Namely, a two dimensional bijective vector function of the following kind:

In the particular problem the function is sampled on a regular grid so only a discrete map is available. It is therefore tempting to find the inverse by simply exchanging the arguments:

The problem with this naive approach is that the inverse function will properly not be represented on a regular grid and even if the function is bijective in its continuous representation the discrete sampling does not have to be so. Finally, neighbors in the discrete representation of the function does not have to be neighbors in the inverse representation, because the function is not necessarily conformal (does not preserve angles). This essentially means that if you want the inverse function represented on a regular grid you will have to do some linear interpolation between the non-regular grid points, which you do not know the neighbors of. It is therefore difficult and computational expensive to reach good results on a regular grid! (I have tried this by using a BFS algorithm to locate the neighbors and then a bresenhams rasterization algorithm in order to compute the linear interpolation at the regular grid points.)

Instead I turned to another method which would completely neglect these problems! Namely, exploiting the inverse function theorem. You might have encountered this theorem in its one dimensional version.

Let f: I->R be a monotonic function, which is differentiable in the interval I with f’(X) ≠ 0 for all x in I. The inverse function f^-1: J -> R is then differentiable and for all y in J the following holds:

In my application I need the generalized version to include the nature of higher dimensions

The Inverse Function Theorem
Let f: R^n -> R^n be continuously differentiable on some open set containing a, and suppose det(Jf(a))≠0 (J being the Jacobian). Then there is some open set V containing a and an open W containing f(a) such that f: V -> W has a continuous inverse f^-1: W -> V which is differentiable for all y in W.

In matrix representation this can be expressed as:

where J denotes the Jacobian.

Using this magnificent theorem it is possible to find the inverse function by simply solving the differential equation. In practice this can be done numerically using various methods (for example using Runge-Kutta methods).

For the specific case of two dimensions one will obtain two pairs of equations for which one will need to solve only one of the pair’s equations simultaneously. This means that it is possible to solve independently in either the x direction or the y direction. The two pairs of equations takes the form:

or

where

The inverse function can then be obtained on a regular grid and the only worry is whether the determinant of the Jacobian of the function is zero, because then the approach breaks down!

Useful Links
http://en.wikipedia.org/wiki/Inverse_function
http://en.wikipedia.org/wiki/Runge_kutta
http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm