Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
3  
Can you fix your notation? For instance, what does "c_i = 1/0" mean? Generally, expressions like "1/0" strike fear in the hearts of mathematicians. If this means that c_i is either 1 or 0, then C' is just the unit n-cube. –  NKS Dec 29 '11 at 17:26
1  
And if $C$ is indeed a hypercube, then you can get the closest point in $C$ to an arbitrary point $b$ simply by clamping each coordinate of $b$ to the range $[0,1]$. –  Rahul Dec 29 '11 at 17:59
    
Yes, i just mean that $c_i$ is either 1 or 0, and so $C'$ is the unit n-cube. –  mike Dec 29 '11 at 17:59
    
I'm sorry but I don't know what 'clamping' means here. Thanks. –  mike Dec 29 '11 at 18:20
1  
I believe by 'clamping', @RahulNarain simply means that if the coordinate is greater than 1 make it 1, if it is less than 0 make it 0, and otherwise leave it as is. This makes intuitive sense if you can visualize it in two or three dimensions. –  smackcrane Dec 29 '11 at 19:01
show 3 more comments

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:

  1. $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$
  2. $b_i\in[0,1]\implies b_i-b^\ast_i=0\implies (b_i-b^\ast_i)(c_i-b^\ast_i) =0$
  3. $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$.

share|improve this answer
    
Thanks. Very helpful. –  mike Dec 29 '11 at 19:49
add comment

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$.

share|improve this answer
    
Thanks. Very helpful. –  mike Dec 29 '11 at 19:50
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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