10
$\begingroup$

Introduction and notations:

Here is a new and simple version of my algorithm which seems to terminates (according to my experiments), and now I would like to prove that.

Let the notation $x_i \in \mathbb{R}^p$ refer to a $p$ dimensional data point (a vector). I have three sets A, B and C, such that $|A| = n$, $|B| = m$, $|C| = l$: $$A = \{x_i | i = 1, .., n\}$$ $$B = \{x_j | j = n+1, .., n+m\}$$ $$C = \{x_u | u = n+m+1, .., n+m+l\}$$

Given $k \in \mathbb{N^*}$, let $d_{x_i}^A$ denote the mean Euclidean distance from $x_i$ to its $k$ nearest points in $A$; and $d_{x_i}^C$ denote the mean Euclidean distance from $x_i$ to its $k$ nearest points in $C$.

Algorithm:

I have the following algorithm which iteratively modifies the sets A and B by moving some selected elements from A to B and vis versa, and C remains always the same (do not change). To make it simple: the purpose of the algorithm is to better separate the sets $A$ and $B$ such that "the points of $B$ are more similar to those of a known fixed set $C$" and "the points of $A$ are finally self-similar and farther from those of $C$ and the final set $B$":

  • $A' = \{ x_i \in A \mid d_{x_i}^A > d_{x_i}^C \}$ ... (1)
  • $A = A \setminus A'$; $B = B \cup A'$ ... (2)
  • $B' = \{ x_i \in B \mid d_{x_i}^A < d_{x_i}^C$ } ... (3)
  • $B = B \setminus B'$; $A = A \cup B'$ ... (4)
  • Repeat (1), (2), (3), and (4) until: (no element moves from $A$ to $B$ or from $B$ to $A$, that is A' and B' become empty) or ($|A| \leq k$ or $|B| \leq k$)

The algorithm terminates in two cases:

  • when $|A|$ or $|B|$ becomes less than or equals to $k$
  • or the most standard case, when $A' = B' = \emptyset$, which means that no more elements moves between A and B.

Question:

How to prove that this algorithm eventually terminates ? I didn't found a convenient potential function which can be strictly minimized or maximized by the algorithm. I have unsuccessfully tried some functions: the function $\sum_{x \in A} d_x^C + \sum_{x \in B} d_x^A$ but it is not increasing at each iteration. The function $\sum_{x \in A} d_x^A + \sum_{x \in B} d_x^C$ but it is not decreasing at each iteration. The function $\sum_{x \in A} d_x^A + \sum_{x \in B} d_x^B$ seems not to be decreasing at each iteration. The function $\sum_{x \in A} d_x^B + \sum_{x \in B} d_x^A$ seems not to be increasing at each iteration. So what is the convenient potential function which can be show to either increase or decrease at each iteration ? Or should we show that the function decreases but not at each iteration (after some iterations rather) ? How ?

Notes:

  • The $k$ nearest points to $x$ in a set $S$, means: the $k$ points (others than $x$) in $S$, having the smallest Euclidean distance to $x$. You can just take $k = 1$ to simplify the analysis.
  • I don't know if this may help or not, but I have the following property for my initial sets $A, B, C$: initially $\forall x_i \in B, x_j \in A$, if $x_b \in C$ is the nearest point to $x_i$ and $x_a \in C$ is the nearest point to $x_j$ then always $distance(x_i, x_b) < distance(x_j, x_a)$. This intuitively means that points in $B$ are closer to $C$ than points in $A$.
  • If that makes the analysis easier: it is totally possible to consider a slightly different version of the Algorithm where as soon as a point from $A$ should be moved to $B$, it is moved from $A$ to $B$ (without passing by $A'$), and vis versa for $B$.
$\endgroup$

migrated from mathoverflow.net Nov 26 '13 at 18:53

This question came from our site for professional mathematicians.

  • 3
    $\begingroup$ Why are you interested in this particular algorithm? $\endgroup$ – Stefan Kohl Nov 22 '13 at 11:27
  • 1
    $\begingroup$ shna : What is it that you want to do with a collection of points arbitrarily divided into three sets? $\endgroup$ – ARi Nov 22 '13 at 15:33
  • 4
    $\begingroup$ @shna Knowing the purpose and goal of the algorithm may lead to improved intuition, and therefore help the problem. $\endgroup$ – Richard Rast Nov 22 '13 at 18:17
  • $\begingroup$ @RichardRast To make the explanation simple: the purpose is to better separate the sets $A$ and $B$ such that "the points of $B$ are more similar to those of a known fixed set $C$" and "the points of $A$ are finally self-similar and farther from those of $C$ and the final set $B$". $\endgroup$ – shn Nov 22 '13 at 19:18
  • $\begingroup$ Migration to cstheory was declined. $\endgroup$ – François G. Dorais Nov 25 '13 at 20:38
2
$\begingroup$

Here's the solution for the case $k = 1$:

Assume the algorithm does not terminate. Since there are a finite number of states of the algorithm (assignments of points to $A$ and $B$), the algorithm state must repeat in a cycle. Since the cycle goes through different states, there must be a point that switches between $A$ and $B$ infinitely often.

Let $x$ be a point that switches infinitely often in this cycle. Pick the first iteration of the algorithm within the cycle during which $x$ switches from $B$ to $A$. For $x$ to switch to $A$, there must have been at least one point $x'$ in $A$, with $d_x^C > dist(x, x')$. Arbitrarily pick the smallest-labeled such point; define a function $f$ so that $f(x) = x'$. Note that $x'$ also must switch between $A$ and $B$ infinitely often (because if $x'$ stayed in $A$ permanently, so would $x$), so we can take $f(f(x)), f(f(f(x))),$ etc.

Since we have a finite number of points, the iterates of f must eventually repeat: $f^n(x) = f^m(x)$ for some $m > n$. Now look at the corresponding sequences of distances from C: $d_{f(x)}^C, d_{f^2(x)}^C, ... d_{f^n(x)}^C, ... $. Since it repeats, this sequence cannot be uniformly decreasing. There must be an iterate $o$ such that $d_{f^{o-1}(x)}^C \leq d_{f^o(x)}^C$

Now, $f^{o-1}(x)$ and $f^o(x)$ are close enough to each other to cause each other to be in $A$, if one of them is. That is, they're closer to each other than either of them is to $C$: $d_{f^o(x)}^C \geq d_{f^{o-1}(x)}^C > dist(f^{o-1}(x), f^o(x))$ (from definition of $f$)

So as soon as $f^{o-1}(x)$ and $f^o(x)$ are both in $A$, they will keep each other in $A$ forever (see lines 1-2 of the algorithm). This contradicts the fact that all the iterates of $f$ must switch sets infinitely often. Thus, for the case when $k = 1$, the algorithm terminates.

$\endgroup$
  • $\begingroup$ This is somehow complicated and may be shown only for $k = 1$. Rather, it is much better if we can derive a potential function which can be shown to be increasing or decreasing at each iteration. Or a that can be shown to be increasing or decreasing after "some" iterations rather than 1. $\endgroup$ – shn Nov 25 '13 at 16:18
  • 1
    $\begingroup$ @shn I'm not sure why you're criticizing the choice of proof technique of somebody who's been more successful at solving your problem than you have. Especially when your own question lists four failed attempts at using your preferred technique. $\endgroup$ – David Richerby Nov 26 '13 at 20:21
  • 1
    $\begingroup$ @DavidRicherby I'm not criticizing ;) I actually discussed about that solution with "causative" (who gave this answer) on IRC and we found that it will not be possible to prove it this way for $k > 1$; so we deduced that it is much better if we can derive a potential function which can be shown to be decrease at each iteration. My comment was just informative. $\endgroup$ – shn Nov 26 '13 at 20:27

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.