Let $W$ be a subspace of $\mathbb{R}^n$. For $x \in \mathbb{R}^n$, define

$$\rho (x) = \inf_{y \in W} \Vert x - y \Vert _2$$

Let $\{ u_1, \ldots, u_m \}$ be an orthonormal basis of $W$, where $m$ is the dimension of $W$. Extend this to an orthonormal basis $\{ u_1, \ldots, u_m, \ldots, u_n \}$ of all of $\mathbb{R}^n$.

How I can show that

$$\rho (x) = \left[ \mathop {\sum} \limits_{j=m+1}^n \vert \langle x, u_j \rangle \vert^2 \right]^\frac{1}{2}$$

and that it is uniquely attained at

$$y=Px, \qquad P = \mathop {\sum} \limits_{j=1}^m u_j u_j^T$$

As you know, $P$ is called the orthogonal projection of $x$ onto $W$.

  • 1
    $\begingroup$ \inf is already a defined operator ;) $\endgroup$ – AlexR Mar 27 '15 at 13:21

Note that $x = \sum_{i=1}^n \langle u_i, x\rangle u_i$ and by assumption $y = \sum_{i=1}^m \langle u_i, y\rangle u_i$ Thus $$\|x-y\|_2^2 = \sum_{i=1}^n \langle x- y, u_i\rangle^2 = \sum_{i=1}^m \langle x-y, u_i \rangle^2 + \sum_{i=m+1}^n \langle x, u_i\rangle^2 \ge \sum_{i=m+1}^n \langle x, u_i\rangle^2$$ This bound is attained when $\langle x-y, u_i\rangle = 0$ for $1\le i\le m$, i.e. for $y = \sum_{i=1}^m \langle x, u_i\rangle u_i = \sum_{i=1}^m u_iu_i^T x = Px$. This proves $$\rho(x) = \sqrt{\inf_{y\in W} \|y-x\|_2^2} = \sqrt{\|Px-x\|_2^2} = \left(\sum_{i=m+1}^n \langle x, u_i\rangle^2\right)^{\frac12}$$ as claimed. As a side note, this shows that the $\inf$ is actually a $\min$, wich only happens in a finite-dimensional setting.

The uniqueness follows from the definiteness of the inner product. $$\|y-x\|_2^2 = \|Px-x\|_2^2 \Leftrightarrow \langle y-x, u_i\rangle = 0 \quad\forall\ 1\le i\le m\\ \Leftrightarrow \langle y - Px, u_i\rangle = 0\quad\forall\ 1\le i\le m\\ \Leftrightarrow \langle y - Px, y- Px\rangle = 0\\ \Leftrightarrow y = Px$$


(1) For any $x$, $$ x= \sum_{i=1}^n a_i u_i,\ |x|^2=\sum_{i=1}^n a_i^2 $$

If $ P(x):=\sum_{i=1}^m a_i u_i$ then $$ P(x)\in W$$

If $y\in W$ then $$ y=\sum_{i=1}^m b_i u_i \in W$$ So if $$ |P(x)-x| \geq |y-x| $$ then $$ \sum_{i=m+1}^n a_i^2 \geq \sum_{i=1}^m ( a_i - b_i)^2 + \sum_{i=m+1}^n a_i^2 $$ Note that inequality does not hold, and equality holds when $y=P(x)$. Hence $P(x)$ attains minimum.

(2) Now we will write $P$ as a matrix form : $$ (\sum_{i=1}^m u_i u_i^T - P)(x)=0$$ for all $x$ Hence $P=\sum_{i=1}^m u_i u_i^T$.

  • 2
    $\begingroup$ You forgot the uniqueness. $\endgroup$ – AlexR Mar 27 '15 at 13:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.