Contraction Mapping¶
Consider a space \((X, d)\) where \(X\) is a set and \(d\) is a metric function (distance function). For a positive number \(\gamma \in [0, 1)\) and any elements \(x1, x2 \in X\), if we have
the special mapping function \(f\) is the contraction mapping function. The minimum value \(\gamma\) can take is called the Lipschitz constant.
If \(\gamma >=1\), Contraction mapping doesn’t exist.
Explanation¶
The key inequality is \(d(f(x1), f(x2)) \leq \gamma d(x1, x2)\). We can think this way. There are two sets, \(X\) and \(X'\). \(X'\) is generated by applying function \(f\) onto each element in \(X\). The magic of the function \(f\) is that elements in \(X'\) are more dense. Of course, “dense” is measured by \(d\).
With the previous intuition, we can translate the theorem in the following language: Consider a set \(X\) and a compressing function \(f\). We are able to compress set \(X\) to set \(X'\) using \(f\). The distance of any pair of elements in \(X\) are shrinked by a scale of \(\gamma\) after doing the mapping.
Imagine \(X\) as a data file in your computer and \(f\) as a file compression software, e.g. winrar. \(X'\) is the compressed file which is much smaller than \(X\). Since \(X\) and \(X'\) is one-to-one mapped, i.e. decompress \(X'\) always gives you \(X\) and compress \(X\) always gives you \(X'\), \(f\) is a function.