# Orthogonal matrix onto subspace spanned by non-orthogonal set

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$.