= Gram-Schmidt process
{c}
{title2=$u_j=v_j-\sum_{i<j}\langle v_j,q_i\rangle q_i,\quad q_j=u_j/\|u_j\|$}
{wiki=Gram–Schmidt_process}
= Gram-Schmidt orthogonalization
{c}
{synonym}
The <Gram-Schmidt process> turns a finite ordered family of <linearly independent> <vectors> $v_1,\ldots,v_k$ in an <inner product space> over the <real numbers> into an <orthonormal basis> $q_1,\ldots,q_k$ of their <linear span>. It keeps every successive <linear span>, so the first $j$ new <vectors> describe exactly the same directions as the first $j$ inputs. Its idea is geometric: remove the <orthogonal projection> onto directions already found, then divide the remaining <vector> by its <norm>. This makes a complicated <basis> easier to use without changing the <vector subspace> it describes.https://ocw.mit.edu/courses/18-06sc-linear-algebra-fall-2011/7ac32be444c25e48590f47573833ccc6_MIT18_06SCF11_Ses2.4sum.pdf[MIT 18.06SC, Orthogonal matrices and Gram-Schmidt, pp. 1–3]{ref}
Start with $u_1=v_1$ and $q_1=v_1/\|v_1\|$. At step $j$, use the previously obtained <orthonormal set> to define
$$
u_j=v_j-\sum_{i=1}^{j-1}\langle v_j,q_i\rangle q_i,
\qquad q_j=\frac{u_j}{\|u_j\|},
\qquad \|u_j\|=\sqrt{\langle u_j,u_j\rangle}.
$$
The sum is the <orthogonal projection onto a finite-dimensional subspace> $W_{j-1}=\operatorname{span}(q_1,\ldots,q_{j-1})$, and $u_j$ is the <orthogonal projection residual>. <Linear independence> ensures $u_j\ne0$: otherwise $v_j$ would already be a <linear combination> of earlier inputs. If the input family is <linearly dependent>, use only the retained <orthonormal> <vectors> in the sum and omit an input whenever its remainder is the <zero vector>; do not divide by zero. The retained outputs still form an <orthonormal basis> of the original <linear span>, but their number can be smaller than $k$.
For a short verification, <orthonormality> makes every earlier <inner product> vanish:
$$
\langle u_j,q_\ell\rangle
=\langle v_j,q_\ell\rangle-\sum_{i<j}\langle v_j,q_i\rangle\langle q_i,q_\ell\rangle=0
\quad(\ell<j).
$$
Also $u_j$ is $v_j$ minus a <linear combination> of earlier <vectors>, while $v_j$ is $u_j$ plus that same <linear combination>. These two inclusions, followed by division by a nonzero <norm>, give
$$
\operatorname{span}(q_1,\ldots,q_j)=\operatorname{span}(v_1,\ldots,v_j).
$$
The argument also works in an <inner product space> over the <complex numbers> with the existing <inner product> convention, linear in the first argument: the <coefficients> remain $\langle v_j,q_i\rangle$. With the convention linear in the second argument, write $\langle q_i,v_j\rangle$ instead.
For a first picture, take $v_1=(1,1)^T$ and $v_2=(1,0)^T$ in $\mathbb R^2$ with the ordinary <dot product>. Then
$$
q_1=\frac{(1,1)^T}{\sqrt2},\qquad
\langle v_2,q_1\rangle q_1=\frac12(1,1)^T,\qquad
u_2=\frac12(1,-1)^T,\qquad
q_2=\frac{(1,-1)^T}{\sqrt2}.
$$
Subtracting the diagonal component leaves an <orthogonal> direction; dividing by its <norm> $1/\sqrt2$ makes its length one. If the second input were $(2,2)^T$ instead, its <orthogonal projection> would be the entire input and $u_2=0$, revealing <linear dependence>.
\Image[/gram-schmidt-vector-steps.png]
{title=<Gram-Schmidt orthogonalization> in $\mathbb R^2$: input <vectors>, subtraction of an <orthogonal projection>, and an <orthonormal basis>}
For a full three-dimensional calculation, use the ordinary <dot product> and the input <vectors>
$$
v_1=(1,1,0)^T,\qquad v_2=(1,0,1)^T,\qquad v_3=(0,1,1)^T.
$$
The first two steps give
$$
q_1=\frac{(1,1,0)^T}{\sqrt2},\qquad
\langle v_2,q_1\rangle=\frac1{\sqrt2},\qquad
u_2=(1/2,-1/2,1)^T,
$$
$$
\|u_2\|^2=\frac32,\qquad
q_2=\frac{(1,-1,2)^T}{\sqrt6}.
$$
At the third step, the <inner products> are $\langle v_3,q_1\rangle=1/\sqrt2$ and $\langle v_3,q_2\rangle=1/\sqrt6$. Consequently
$$
u_3=(0,1,1)^T-\frac12(1,1,0)^T-\frac16(1,-1,2)^T
=\left(-\frac23,\frac23,\frac23\right)^T,
$$
$$
\|u_3\|^2=\frac43,\qquad
q_3=\frac{(-1,1,1)^T}{\sqrt3}.
$$
The three numerator <vectors> have pairwise <dot products> $0$ and squared <Euclidean norms> $2,6,3$. Thus the displayed outputs are indeed an <orthonormal basis>, and the three nonzero remainders also confirm <linear independence> of the inputs. Keeping the removed <coefficients> produces the <QR decomposition> below.
An immediate reward is a reusable <orthogonal projection>: once an <orthonormal basis> of a <vector subspace> $W$ is known, any <vector> $b$ has
$$
P_Wb=\sum_i\langle b,q_i\rangle q_i.
$$
For the <linear span> of just the first two inputs in the three-dimensional example, $b=(0,0,1)^T$ gives $P_Wb=(1/3,-1/3,2/3)^T$. Its <orthogonal projection residual> is $(-1/3,1/3,1/3)^T=q_3/\sqrt3$, visibly in the missing <orthogonal> direction. This is the geometry behind the <linear least-squares problem>.
The formulas above describe exact arithmetic. With <floating-point arithmetic>, subtracting an <orthogonal projection> nearly equal to the input can leave a small remainder; dividing by its small <norm> can magnify existing <roundoff error>. The <Classical Gram-Schmidt> and <Modified Gram-Schmidt> arrangements agree in exact arithmetic but can give different rounded results. Exact <linear dependence> and a small computed remainder therefore require different judgments in a numerical implementation.https://nhigham.com/wp-content/uploads/2023/10/high95m.pdf[Higham, The Test Matrix Toolbox for Matlab, §8, p. 22]{ref}
Back to article page
