Is Banach fixed point theorem a necessary and sufficient condition for the existence of a fixed point
up vote
1
down vote
favorite
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?
functional-analysis banach-spaces machine-learning fixed-point-theorems
asked Nov 17 at 7:21
Nancy Zhang
255
add a comment |
up vote
1
down vote
favorite
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?
functional-analysis banach-spaces machine-learning fixed-point-theorems
asked Nov 17 at 7:21
Nancy Zhang
255
If you're asking if contraction in each step is necessary for convergence, then yes you're right - it is not necessary
– OnceUponACrinoid
Nov 17 at 7:24
$mathbb R$ is a Banach space and $f(x)=2x$ is map with a unique fixed point. It is not a contraction.
– Kavi Rama Murthy
Nov 17 at 12:09
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
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?
functional-analysis banach-spaces machine-learning fixed-point-theorems
asked Nov 17 at 7:21
Nancy Zhang
255
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?
functional-analysis banach-spaces machine-learning fixed-point-theorems
functional-analysis banach-spaces machine-learning fixed-point-theorems
asked Nov 17 at 7:21
Nancy Zhang
255
asked Nov 17 at 7:21
Nancy Zhang
255
asked Nov 17 at 7:21
Nancy Zhang
255
asked Nov 17 at 7:21
Nancy Zhang
255
asked Nov 17 at 7:21
Nancy Zhang
255
255
If you're asking if contraction in each step is necessary for convergence, then yes you're right - it is not necessary
– OnceUponACrinoid
Nov 17 at 7:24
$mathbb R$ is a Banach space and $f(x)=2x$ is map with a unique fixed point. It is not a contraction.
– Kavi Rama Murthy
Nov 17 at 12:09
add a comment |
If you're asking if contraction in each step is necessary for convergence, then yes you're right - it is not necessary
– OnceUponACrinoid
Nov 17 at 7:24
$mathbb R$ is a Banach space and $f(x)=2x$ is map with a unique fixed point. It is not a contraction.
– Kavi Rama Murthy
Nov 17 at 12:09
If you're asking if contraction in each step is necessary for convergence, then yes you're right - it is not necessary
– OnceUponACrinoid
Nov 17 at 7:24
If you're asking if contraction in each step is necessary for convergence, then yes you're right - it is not necessary
– OnceUponACrinoid
Nov 17 at 7:24
$mathbb R$ is a Banach space and $f(x)=2x$ is map with a unique fixed point. It is not a contraction.
– Kavi Rama Murthy
Nov 17 at 12:09
$mathbb R$ is a Banach space and $f(x)=2x$ is map with a unique fixed point. It is not a contraction.
– Kavi Rama Murthy
Nov 17 at 12:09
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3002058%2fis-banach-fixed-point-theorem-a-necessary-and-sufficient-condition-for-the-exist%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
If you're asking if contraction in each step is necessary for convergence, then yes you're right - it is not necessary
– OnceUponACrinoid
Nov 17 at 7:24
$mathbb R$ is a Banach space and $f(x)=2x$ is map with a unique fixed point. It is not a contraction.
– Kavi Rama Murthy
Nov 17 at 12:09