Suppose that we are given a vector $w \in \mathbb{R}^n$ and a subspace $V \subseteq \mathbb{R}^n$ spanned by some set $\left\{ v_1, v_2, \dots, v_n \right\}$. Suppose further that $v_1, v_2, \dots, v_n$ are not orthogonal. How would we go about efficiently computing the projection of $w$ onto $V$?

It is well-known that we can first convert $\left\{ v_1, v_2, \dots, v_n \right\}$ into an orthogonal set $\left\{ \tilde{v}_1, \tilde{v}_2, \dots, \tilde{v}_n \right\}$ using using the Gram-Schmidt procedure, and then compute the projection using the standard orthogonal projection method using inner products. However, converting the non-orthogonal basis to an orthogonal basis is computationally inefficient.

Is there a faster, more direct way to do this?


Recall that the orthogonal projection $Pw$ of $w$ is determined by the properties

  1. $Pw \in V$, i. e. $Pw = \sum_i a_i v_i$ for some $a_i \in \mathbf R$.
  2. $w - Pw \in V^\bot$, i. e. $\left<w - Pw, v_j\right> = 0$ for all $j$.

So we must have \begin{align*} \left<w - Pw, v_j\right> &= 0\\ \iff \left<w,v_j\right> - \left<\sum_i a_i v_i, v_j\right> &= 0\\ \iff \sum_i \left<v_i, v_j\right> a_i &= \left<w, v_j\right> \end{align*} Now let $A := (\langle v_i,v_j\rangle)_{i,j}$, $b := (\langle w, v_j\rangle)_j$ and $x := (a_i)_i$. Then solve $Ax = b$ for $x$ to determine coefficients for $Pw$.


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.