Euclidean projection on a set

L. El Ghaoui

Euclidean projection on a set

An Euclidean projection of a point $x_0 \in \mathbb{R}^n$ on a set ${\bf S} \subseteq \mathbb{R}^n$ is a point that achieves the smallest Euclidean distance from $x_0$ to the set. That is, it is any solution to the optimization problem

$\min\limits_x ||x-x_0||_2: x \in {\bf S}.$

When the set ${\bf S}$ is convex, there is a unique solution to the above problem. In particular, the projection on an affine subspace is unique.

Example: assume that ${\bf S}$ is the hyperplane

${\bf S} = \{x\in \mathbb{R}^3: 2x_1+x_2-x_3 = 1\}.$

The projection problem reads as a linearly constrained least-squares problem, of particularly simple form:

$\min\limits_x ||x||_2 : 2x_1+x_2-x_3 = 1.$

The projection of $x_0 = 0$ on ${\bf S}$ turns out to be aligned with the coefficient vector $a=(2,1,-1)$ . Indeed, components of $x$ orthogonal to $a$ don’t appear in the constraint, and only increase the objective value. Setting $x=ta$ in the equation defining the hyperplane and solving for the scalar $t$ we obtain $t=1/(a^Ta) = 1/6$ , so that the projection is $x^* = a/(a^Ta) = (1/3, 1/6, -1/6)$ .

Euclidean projection on a set

License

Share This Book