# Projection Onto Convex Sets
$$
x\_{LS}=\underset{x\in\R^n}{\min}\frac{1}{2}\lVert Ax-b\rVert^2
$$
where $$A$$ is $$m\times n$$.
Ax_{LS} projection of b onto range(A)
$$
\min \frac{1}{2} \lVert Ax-b\rVert^2 \Leftrightarrow \min \frac{1}{2} \lVert z-b\rVert^2 \text{ subject to } z\in range(A)
$$
Then (“orthogonal” or “Euclidean”) projection of a vector $$b\in \R^n$$ onto $$C\subseteq \R^n$$ convex is the solution of the convex optimization problem
$$
proj\_C(b)=\underset{z\in\R^n}{\min}\frac{1}{2}\lVert z-b\rVert^2 \text{ subject to } z\in C
$$
* Convex optimization problem
* Objective is strictly convex ⇒ solution is unique
### Properties of $$\text{proj}\_C(b)$$
* if $$b\in C$$ ⇒ $$proj\_C(b)=b$$
* $$proj\_C(b)$$ is unique
* $$z=proj\_C(b)$$ ↔ $$(b-z)^T(y-z)\le 0, \forall y\in C$$
$$-\nabla f(z)\in N\_C(z)$$
$$b-z \in N\_C(z)$$ $$\overset{\text{use definition of Normal Cone}}{\Leftrightarrow}(b-z)^T(y-z)\le 0, \forall y\in C$$
