Does this algorithm terminate in all scenarios?

Let $x \in \mathbb{R}^p$ denote a $p$-dimensional data point (a vector). I have two sets $A = \{x_1, \dots, x_n\}$ and $B = \{x_{n+1}, \dots, x_{n+m}\}$, so $|A| = n$, and $|B| = m$. Given $k \in \mathbb{N^*}$, let $d_x^{(A, k)}$ denote the mean Euclidean distance from $x$ to its $k$ nearest points in $A$; and $d_x^{(B, k)}$ denote the mean Euclidean distance from $x$ to its $k$ nearest points in $B$.

I have the following algorithm:

• $A' = \{ x_i \in A \mid d_{x_i}^{A, k)} > d_{x_i}^{(B, k)} \}$ ... (1)
• $A = A \setminus A'$ ... (2)
• $B' = \{ x_i \in B \mid d_{x_i}^{A, k)} < d_{x_i}^{(B, k)}$ ... (3)
• $B = B \setminus B'$ ... (4)
• $A = A \cup B'$ ... (5)
• $B = B \cup A'$ ... (6)
• Repeat (1), (2), (3), (4), (5) and (6) 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)

Does this algorithm terminate, and if so, is it possible to easily prove it ? Is it also possible to have an upper bound for the number of iterations required to terminate ?

Note: "The $k$ nearest points to $x$ in a set $S$" means: The $k$ points (other than $x$) in $S$, having the smallest Euclidean distance to $x$.

-
Is the algorithm intended to be asymmetrical, as written? I'd have expected steps (2) and (3) to be reversed, so that the evaluation of A' and B' are acting symmetrically over the full set of n+m vectors. – Hugo van der Sanden Nov 21 '13 at 1:25
@HugovanderSanden if steps (2) and (3) are reversed the algorithm do note terminate. For instance in p = 1 dimension with k = 1, if A = {0, 3} and B = {2, 5} then elements of A and B will swap between A and B at each iteration. This is why, it is asymmetrical, as written. – shna Nov 21 '13 at 8:09
Ok, presumably it needs an extra termination check for |A| <= k after step 2 then; from your example, I also infer that d_x^(A,k) is intended to be defined over the k nearest points in A excluding x itself otherwise we have d_x^(A,1) = 0 whenever x is in A. – Hugo van der Sanden Nov 21 '13 at 8:27

Counterexample

This algorithm does not terminate. Here is a counterexample, in dimension $p=2$, with $m=n=2$ points in each set, only looking at the $k=1$ nearest neighbours.

$$A=\left\{ \begin{pmatrix}-2\\0\end{pmatrix}, \begin{pmatrix}0\\1\end{pmatrix} \right\} \qquad B=\left\{ \begin{pmatrix}3\\0\end{pmatrix}, \begin{pmatrix}0\\-1\end{pmatrix} \right\}$$

The two points with $0$ in their first coordinate will change sets in every iteration. After two iterations you are back where you started, so this cannot terminate.

Step by step

Since you doubt my counterexample in a comment below, here is a detailed step-by-step execution of your algo in this case. I'm using the same names for the points as you did:

$$x_1=\begin{pmatrix}-2\\0\end{pmatrix} \qquad x_2=\begin{pmatrix}0\\1\end{pmatrix} \qquad x_3=\begin{pmatrix}3\\0\end{pmatrix} \qquad x_4=\begin{pmatrix}0\\-1\end{pmatrix} \\ A=\{x_1,x_2\} \qquad B=\{x_3,x_4\}$$

• $A'=\{x_2\}$ since $d_{x_2}^{(A,1)}=\lVert x_1-x_2\rVert=\sqrt5>2=\lVert x_4-x_2\rVert=d_{x_2}^{(B,1)}$
• $A=A\setminus A'=\{x_1\}$
• $B'=\{x_4\}$ since $d_{x_4}^{(A,1)}=\lVert x_1-x_4\rVert=\sqrt5<\sqrt{10}=\lVert x_3-x_4\rVert=d_{x_4}^{(B,1)}$
• $B=B\setminus B'=\{x_3\}$
• $A=A\cup B'=\{x_1,x_4\}$
• $B=B\cup A'=\{x_2,x_3\}$
• $A'=\{x_4\}$ since $d_{x_4}^{(A,1)}=\lVert x_1-x_4\rVert=\sqrt5>2=\lVert x_2-x_4\rVert=d_{x_4}^{(B,1)}$
• $A=A\setminus A'=\{x_1\}$
• $B'=\{x_2\}$ since $d_{x_2}^{(A,1)}=\lVert x_1-x_2\rVert=\sqrt5<\sqrt{10}=\lVert x_3-x_2\rVert=d_{x_2}^{(B,1)}$
• $B=B\setminus B'=\{x_3\}$
• $A=A\cup B'=\{x_1,x_2\}$
• $B=B\cup A'=\{x_3,x_4\}$
-
The problem statement has starts with a vector $x$, which vector does not appear in your answer. – Gerry Myerson Nov 20 '13 at 22:01
The vector $x$ also does not appear in the algorithm, and looks to me as a placeholder to explain notation. Gerhard "Ask Me About System Design" Paseman, 2013.11.20 – Gerhard Paseman Nov 20 '13 at 22:37
@MvG for you example, the algorithm that I provide terminates. Let the points: x1=(-2, 0), x2=(0,1), x3=(3,0), x4=(0,-1). At the first step A' = {} because distance(x1, x2) is not higher than distance(x1, x4), and distance(x2, x1) is not higher than distance(x2, x4), see step (1) of my Algorithm. So in step (2) A still the same. Similarly, in step (3) the B' = {x4} because x4 is closer to x1 than to x3, and x3 is not put in B' because distance(x3, x2) is not less than distance(x3, x4). Now at steps (5) and (6) we end up with A = {x1,x2,x4} and B={x3}. Algo stops now subce|B|=1$\leq$k – shna Nov 20 '13 at 22:39
@shna: I updated my answer to include a detailed step-by-step run. $A'=\{x_1\}$ because the distance(x2,x1) is higher than the distance(x2,x4). – MvG Nov 21 '13 at 8:53
@MvG Ok, you are right for that version of the algorithm. What about the case where instead of identifying $ALL x_i \in A'$ (Step 1), I immediately move $x_i$ from A to B as soon as I detect that $d^{(A,k)}_{x_i}>d^{(B,k)}_{x_i}$ (and vice versa) ? that is we do not need A' and B', we directly move a point from A to B as soon as we detect it (and from B to A as soon as we detect it). Will we have the same problem ? I just tested that on your example and it terminates. – shna Nov 21 '13 at 9:51