Which potential function does this algorithm minimize ?

[ShNaYkHs]

Hello,

I'm sorry for asking this question here in English since I don't know Russian. I heard that Russians are pretty good in mathematics and computer science. Any help would be greatly appreciated.

Considering two sets $A, B$ containing some $p$-dimensional points $x \in \mathbb{R}^p$. Let $d_x^S =$ min$_{x' \in S \setminus \{x\}} \lVert \mathbf{x - x'} \rVert$ denote the Euclidean distance from $x$ to its nearest point in $S$. We have a very simple algorithm:

1. $\forall x \in A$, if $d_x^A > d_x^B$ then move $x$ from $A$ to $B$.
2. $\forall x \in A$, if $d_x^A < d_x^B$ then move $x$ from $B$ to $A$.
3. Repeat (1) and (2) until convergence

Convergence is when there is no more $x \in A$ such that $d_x^A > d_x^B$, and there is no more $x \in B$ such that $d_x^A < d_x^B$.

How could I figure out which function does this algorithm minimize or maximize at each iteration ?
The function $\Phi(A)+\Phi(B) = \sum_{x \in A} d_x^A + \sum_{x \in B} d_x^B$ does not seem to decrease at each iteration.

Thanks for help

[maxal]

ShNaYkHs в сообщении #792715 писал(а):

The function $\Phi(A)+\Phi(B) = \sum_{x \in A} d_x^A + \sum_{x \in B} d_x^B$ does not seem to decrease at each iteration.

It does. For example, if $x\in A$ and $d_x^A > d_x^B$, then moving $x$ from $A$ to $B$ decreases $\Phi(A)+\Phi(B)$ by the value of $d_x^A - d_x^B$.

[ShNaYkHs]

maxal в сообщении #792722 писал(а):

ShNaYkHs в сообщении #792715 писал(а):

The function $\Phi(A)+\Phi(B) = \sum_{x \in A} d_x^A + \sum_{x \in B} d_x^B$ does not seem to decrease at each iteration.

It does. For example, if $x\in A$ and $d_x^A > d_x^B$, then moving $x$ from $A$ to $B$ decreases $\Phi(A)+\Phi(B)$ by the value of $d_x^A - d_x^B$.

I have checked both experimentally and analytically that $\Phi(A)+\Phi(B)$ is not decreased at each iteration. This is because when you move $x$ from $A$ to $B$, $\Phi(A)+\Phi(B)$ is not necessarily decreased by $d_x^A - d_x^B$, because A changes and some points in A becomes nearest to each other (while they where not before removing $x$). When you remove $x$ from $A$ and there is some $y \in A$ for which $x$ was the nearest point, then the nearest point of $y$ becomes another point in $A$. Thus $\Phi(A)+\Phi(B)$ do not necessarily decreases by $d_x^A - d_x^B$ in this case.

I can actually give you a counter example where it is not minimized. For example, let A={(0,0,0),(0,0,1),(0,0,−1)}, B={(0.99,0,0),(0.99,1,0),(0.99,−1,0)}. Then after the first iteration only (0,0,0) moves from A to B, and we can verify that the function increases.

[maxal]

You are right. Here is an appropriate potential function, which unfortunately is not easy to describe.

Let $M=A\cup B$ and for every $x\in M$ define $C_x = \{ y\in M : d(x,y) = \min_{z\ne x} d(x,z) \}$ as the set of points closest to $x$.
Define a graph $G$ whose vertices are the elements of $M$ and every vertex $x\in M$ has incident edges $(x,y)$ for every $y\in C_x$. For each edge, we assign length equal the distance between its endpoints.

Notice that graph $G$ does not depend on a particular partition of $M$ into sets $A$ and $B$.

Let $e_1, e_2, \dots, e_m$ be a fixed ordering of the edges of $G$ such that the length of edges does not increase.

Now, define the potential function associated with partition $M=A\cup B$ as

$$\sum_{k=1}^m 2^k \cdot c(e_k)$$

where the coefficient $c(e_k)=1$ if the endpoints of edge $e_k$ are in distinct parts (i.e., one in $A$ and the other in $B$); otherwise $c(e_k)=0$.

For example, suppose that $x\in A$ and $d_x^A > d_x^B$ so that we move $x$ from $A$ to $B$.
The inequality $d_x^A > d_x^B$ implies that $C_x \subset B$.
The potential here changes as follows:
(i) the coefficient of every edge $(x,y)$ for $y\in C_x$ turns from 1 to 0 (there is at least one such edge);
(ii) the coefficients of edges $(x,z)$ (if they present in $G$) for $z\in A$ turn from 0 to 1.
However, the edges of type (i) are strictly shorter than the edges of type (ii) (since $z\not\in C_x$), and thus edges of type (i) have higher indices, making the potential decrease.

[ShNaYkHs]

maxal в сообщении #792762 писал(а):

However, the edges of type (i) are strictly shorter than the edges of type (ii) (since $z\not\in C_x$), and thus edges of type (i) have higher indices, making the potential decrease.

Thanks for you answer. I have two questions:

1) Question 1) For a given $x \in A$ where $d_x^A > d_x^B$, we can imagine the case where we have only one edge $(x,y)$ of type (i) which is incident to $x$ and we have much more edges $(x,z)$ of type (ii) which are incident to $x$. In this situation, even if the edge of type (i) is strictly shorter than the edges of type (ii), it is possible that potential increases because there are too many edges $(x,z)$ whose coefficients turn from 0 to 1, and possibly making the potential increase.

2) Question 2) What if we define define $d_x^S$ as the mean distance from $x$ to its $n$ nearest points in $S$ ? Does your reasoning still the same (same graph and so on) ? Or do this reasoning works only if $n=1$ ?

[maxal]

ShNaYkHs в сообщении #793088 писал(а):

1) Question 1) For a given $x \in A$ where $d_x^A > d_x^B$, we can imagine the case where we have only one edge $(x,y)$ of type (i) which is incident to $x$ and we have much more edges $(x,z)$ of type (ii) which are incident to $x$. In this situation, even if the edge of type (i) is strictly shorter than the edges of type (ii), it is possible that potential increases because there are too many edges $(x,z)$ whose coefficients turn from 0 to 1, and possibly making the potential increase.

2) Question 2) What if we define define $d_x^S$ as the mean distance from $x$ to its $n$ nearest points in $S$ ? Does your reasoning still the same (same graph and so on) ? Or do this reasoning works only if $n=1$ ?

Answer 1: If you have a binary number and switch the $k$-th bit (counting from less significant to most significant bits) in it from 1 to 0, then it does not matter how you change bits with lower indices, the resulting number will be still smaller than the original one. Somewhat extreme example: consider number $2^k$, if you switch the $k$-th bit from 1 to 0, and all the other bits from 0 to 1, you'll get number $2^k-1$ which is smaller than $2^k$.

Answer 2: I guess the graph would need to be modified. I'll check later.

[ShNaYkHs]

maxal в сообщении #793109 писал(а):

Answer 1: If you have a binary number and switch the $k$-th bit (counting from less significant to most significant bits) in it from 1 to 0, then it does not matter how you change bits with lower indices, the resulting number will be still smaller than the original one. Somewhat extreme example: consider number $2^k$, if you switch the $k$-th bit from 1 to 0, and all the other bits from 0 to 1, you'll get number $2^k-1$ which is smaller than $2^k$.

Answer 2: I guess the graph would need to be modified. I'll check later.

Ok thank you, I understand the first answer now. I'll wait for your answer concerning the case where we define $d_x^S$ as the mean distance from $x$ to its $n$ nearest points in $S$.

[ShNaYkHs]

ShNaYkHs в сообщении #793161 писал(а):

maxal в сообщении #793109 писал(а):

Answer 1: If you have a binary number and switch the $k$-th bit (counting from less significant to most significant bits) in it from 1 to 0, then it does not matter how you change bits with lower indices, the resulting number will be still smaller than the original one. Somewhat extreme example: consider number $2^k$, if you switch the $k$-th bit from 1 to 0, and all the other bits from 0 to 1, you'll get number $2^k-1$ which is smaller than $2^k$.

Answer 2: I guess the graph would need to be modified. I'll check later.

Ok thank you, I understand the first answer now. I'll wait for your answer concerning the case where we define $d_x^S$ as the mean distance from $x$ to its $n$ nearest points in $S$.

Any idea for the case where $n > 1$ please ?