Euclidean projection on a set

Alicia Y. Tsai; Authors: Laurent EI Ghaoui; Contributors: Phan Hoang, Tony Tin, Ha To Tam, Nguyen Van Kep, Le Dinh Nam, Juliette Decugis, Nguyen Quoc Cuong.; Giuseppe C. Calafiore

Euclidean projection on a set

An Euclidean projection of a point $x_0$ in $\mathbb{R}^n$ on a set $\mathbf{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_x \, \left\| x - x_0 \right\|_2 \, : \, x \in \mathbf{S}.$

When the set $\mathbf{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 $\mathbf{S}$ is the hyperplane

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

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

$\min_x \, \left\| x \right\|_2 \, : \, 2x_1 + x_2 -x_3 = 1.$

The projection of $x_0 = 0$ on $\mathbf{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 = t a$ in the equation defining the hyperplane and solving for the scalar $t$ we obtain