An optimization is tractable if there exists an algorithm which can solve it in polynomial time.
The zero norm $||\mathbf{x}||_0$ is the number of non-zero entries in $\mathbf{x} \in \R^{n}$ and is derived from the following expression (note also that, since it fails homogeneity, this is not a norm):
$$ ||\mathbf{x} || _0 \triangleq \lim _{p\rightarrow 0} (\sum _{i=1}^n |x_i|^p)^{\frac{1}{p}} $$
An affine set is a subset $X \sube U$ (of a subspace $\mathbf{U} \leq \mathbf{V}$ of an ambient vector space $\mathbf{V}$) associated with a vector $x^{(0)} \in V$ such that every element is an element of $U$ offset by $x^{(0)}$.
$$ X = \{ x^{(0)} + u \space | \space u\in U\} = x^{(0)} + U $$
A projection $P_{\mathbf{U}} : V\rightarrow U$ is a linear map from a vector space $\mathbf{V}$ to a subspace $\mathbf{U} \leq \mathbf{V}$ that satisfies the following criterion:
$$ P_\mathbf{U}(v) := \argmin _{ P \in U^V} || P(v) - v|| $$
<aside> <img src="/icons/castle_yellow.svg" alt="/icons/castle_yellow.svg" width="40px" />
Orthogonality of Projection. The difference between a vector and its projection is always orthogonal to the subspace projected onto.
$$ v - P_{\mathbf{U}}(v) \in U^{\perp} $$
The proof is mechanical. A corollary of this is that the optimal solution is uniquely determined by the point $u \in U$ such that $v - u \in U^\perp$.
</aside>
<aside> <img src="/icons/castle_yellow.svg" alt="/icons/castle_yellow.svg" width="40px" />
Euclidean Projection. The projection $P_{\mathbf{U}}$ onto a subspace $\mathbf{U} \leq \R^n$ with respect to the standard Euclidean norm is defined as follows,
$$ P_{\mathbf{U}}(v) = \sum _{i=1}^d \langle v \space| \space e_i\rang e_i $$
where $e_{1:d}$ is an orthonormal basis of $\mathbf{U}$.
An affine projection is a projection onto an affine set.
<aside> <img src="/icons/castle_yellow.svg" alt="/icons/castle_yellow.svg" width="40px" />
Amendment to Orthogonality of Projection. The orthogonality of the projection no longer holds, since $\mathbf{U}$ need not contain the origin. We can rectify this by asserting that the difference between a vector and its projection is orthogonal to the difference of its projection and any point in $\mathbf{U}$.
$$ v-P_{\mathbf{U}}(v) \perp P_{\mathbf{U}}(v) - u \hspace{15pt} \forall u \in U $$
The proof is also mechanical.
</aside>