Let $C \subset R^n$ be the convex hull of the set of points C' \subset R^n such that for every c \in C', $c_i \in \{0,1\}$. Let $b \not \in C$. Is there an algorithm that will generate the closest (by euclidean distance) $c^\ast \in C$ to $b$?
Closest Points in Euclidean Space
-
0The closest point may not be a vertex of the cube. – 2011-12-29
3 Answers
Claim: The $i$-th coordinate of nearest point to $b$ in $C$, denoted $b^\ast$, is given by:
$b^\ast_i = \left\{\begin{array}{rl} 0 & \text{if }b_i<0 \\\\ b_i & \text{if } b\in[0,1] \\\\ 1 & \text{else (i.e. }b_i>1\text{)} \\\\ \end{array}\right. $
(Note: $b^\ast$ is the orthongal projection of $b$ onto $C$ normally denoted $P_{C}(b)$)
Proof: For $b\in\mathbb R^n$, each $i\in\{1,\dots,n\}$ and for all $c\in C$ we have one of the following cases:
- $b_i<0 \implies b_i-b^\ast_i<0$ and $c_i-b^\ast_i > 0 \implies (b_i-b^\ast_i)(c_i-b^\ast_i) <0$
- $b_i\in[0,1]\implies b_i-b^\ast_i=0\implies (b_i-b^\ast_i)(c_i-b^\ast_i) =0$
- $b_i>0 \implies b_i-b^\ast_i>0$ and $c_i-b^\ast_i < 0 \implies (b_i-b^\ast_i)(c_i-b^\ast_i) <0$
In each case we have $(b_i-b^\ast_i)(c_i-b^\ast_i)\leq 0$. From this it follows that: $ \langle b-b^\ast,c-b^\ast\rangle = \sum_i(b_i-b^\ast_i)(c_i-b^\ast_i) \leq 0$
By the charaterisation of best approximation this implies that $b^\ast$ is the nearest point to $b$ in $C$.
Since you say the set of points C' whose coordinates are $0$ or $1$, I'm assuming that C' contains all such points, i.e., C' is the set of vertices of the unit $n$-cube. Then $C$ is the unit $n$-cube, which consists of all points $(x_1,x_2,...,x_n)$ such that each $x_i$ is in $[0,1]$, and the boundary $\partial{C}$ is the subset where at least one $x_i$ is exactly $0$ or $1$. It is not entirely clear if you want the nearest point on the boundary or in the entire set, so I will give both answers.
Let $b\in\mathbb{R}^n$. To find the nearest point to $b$ in the interior plus boundary of the cube, we can do the following: for each $i$, take the coordinate $c^{*}_i = 0$ if $b_i<0$, or $c^{*}_i=1$ if $b_i>1$, or $c^{*}_i=b_i$ otherwise. This minimizes the distance $|c^{*}_i - b_i|$ for each coordinate independently, and so it minimizes the overall Euclidean distance as well. If this point is already in $\partial{C}$, which will happen if any $b_i$ is $\le 0$ or $\ge 1$ (i.e., if $b$ is not in the interior of the unit cube), or if we wanted the nearest point in the entire set $C$, then we are done. Otherwise, we need to project $c^{*}=b$ out onto the nearest face, which we do by selecting the (possibly not unique) coordinate $i$ that minimizes $\min(|b_i|, |1-b_i|)$ and setting $c^{*}_i=0$ if $b_i\le1/2$ or $c^{*}_i=1$ if $b_i>1/2$.
The crucial point is that the maximizer will always lie on the boundary of the unit cube. Let's illustrate an algorithm for the cube in $\mathbb{R}^3$, which is easily visualized. The algorithm should generalize. The cube has 6 sides and the affine span of each side is a 2-dimensional affine subspace. For each such subspace, you can find the closest point in the affine subspace by orthogonal projection. If one of these points lies actually in the cube, you are done. If not, you look at the 1-dimensional dimensional affine subspaces spanned by each edge. Apply orthogonal projection again, if the point is in the cube you are done. If not, you check for all edges which one is closest. One has to be.
Note: I have no proof for this, but geometrically it makes sense. That the point must be on the boundary, I can prove.
-
0Awesome. I'll get to Vienna next Sunday (August 6th), and the first three weeks of September I have to be back in Israel. But I'll be back for some months, at least, after that. – 2017-07-27