凸集上投影
the following content is from https://cstheory.wordpress.com/2010/08/23/projections-onto-a-convex-body/#more-203.
Projections onto a Convex Body
Given a point and an affine subspace , the projection of onto is the point such that,
One can obviously define other notions of projection but the above is probably the most commonly used in geometry. If then the projected point is the unique point in such that the vector is orthogonal to . Also is well known that projecting any segment to an affine subspace can only shrink its length. The proofs of these facts are easy to see. But in fact these facts are just corollaries of the following two results.
Given any nonempty closed convex set and a point , there is a unique point such that,
|
and,
Let be a nonempty closed convex set. The mapping is a contraction i.e. for any we have,
|
Applying these results to affine spaces (which are nonempty closed convex sets) yields the results mentioned earlier. This projection that maps to is known as the metric projection. The proofs of these facts are in order.
Proof: First we show that the minimum distance to is indeed obtained. This is easy and the details are as follows. Since is nonempty there is some point . Let denote . Clearly a closest point to can only lie in where denotes a closed ball of radius with center . But is a closed and bounded set and is therefore compact. It is also nonempty. The function defined for as is a continuous function on a compact set and attains its minimum at some point .
Next we prove the point where attains minimum, is unique. If is another point at which then in the triangle , which has two equal sides, the perpendicular from onto segment is clearly shorter than the length . However the base of this perpendicular lies on the segment itself. By convexity of the entire segment is in and thus we have found a point in closer to than which is a contradiction.
Next we prove that the metric projection is a contraction.
Proof: Let the points be projected to and respectively and assume . Consider the hyperplanes through that are orthogonal to the vector . See figure below.
The main observation is that must lie on the other side of as . If lies on the same side of as then one can always find a point on the segment closer to than which would contradict that is the closest point to in . Similarly cannot lie on same side of as . Thus is at least the distance between and which is .