1
$\begingroup$

Banach fixed point theorem requires a contraction mapping from a metric space into itself, but when I was learning some machine learning algorithms, some questions rise above: k-means is an algorithm for clustering, it can be proved that this method will converge, but the proof of convergence of the algorithm doesn't involve fixed point theorem. I feel the iteration of the centering point for each cluster in this method is very similar the iteration of the fixed point iteration steps so I tried to prove this convergence using Banach fixed point theorem. However I couldn't construct a contraction mapping in this problem. So I guess if the iteration steps in k-means is not a contraction at all. In order to test this assumption, I generate some random number on my computer and use the k-means steps to cluster and calculate the norm distance between each iteration point.To my surprise, it is NOT a contraction!but it does converge in finite steps. I think the convergence shows the existence of the fixed point under this iteration. So with these facts, can I say the Bananch Fixed point theorem gives a sufficient condition on the existence of a fixed point, but it might not be necessary?

$\endgroup$
  • $\begingroup$ If you're asking if contraction in each step is necessary for convergence, then yes you're right - it is not necessary $\endgroup$ – OnceUponACrinoid Nov 17 '18 at 7:24
  • $\begingroup$ $\mathbb R$ is a Banach space and $f(x)=2x$ is map with a unique fixed point. It is not a contraction. $\endgroup$ – Kavi Rama Murthy Nov 17 '18 at 12:09

Your Answer

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

Browse other questions tagged or ask your own question.