Gram-Schmidt Orthogonalization

The Gram-Schmidt process is a simple algorithm for producing orthogonal basis for any nonzero subspace of $\R^n$.

Given a basis $\{ \x_1, \dots, \x_p \}$ for a nonzero subspace $W$ of $\R^n$, define

\[ \begin{aligned} \newcommand{\v}{\mathrm{v}} \v_1 &= \x_1 \\ \v_2 &= \x_2 - \frac{\x_2 \cdot \v_1}{\v_1 \cdot \v_1} \v_1 \\ \v_3 &= \x_3 - \frac{\x_3 \cdot \v_1}{\v_1 \cdot \v_1} \v_1 - \frac{\x_3 \cdot \v_2}{\v_2 \cdot \v_2} \v_2 \\ &\vdots \\ \v_p &= \x_p - \frac{\x_p \cdot \v_1}{\v_1 \cdot \v_1} \v_1 - \frac{\x_p \cdot \v_{p-1}}{\v_{p-1} \cdot \v_{p-1}} \v_{p-1} \end{aligned} \] Then $\{ \v_1, \dots, \v_p \}$ is an orthogonal basis for $W$. In addition, \[ \newcommand{\span}[1]{\mathrm{Span}\{#1\}} \span{\v_1, \dots,\v_k} = \span{\x_1, \dots, \x_k} \text{\quad for $1 \le k \le p$} \]

QR Factorization

If $A$ is an $m \times n$ matrix with linearly independent columns, then $A$ can be factored as $A = QR$, where $Q$ is an $m \times n$ matrix whose columns form an orthonormal basis for $\mathop{\mathrm{Col}}A$ and $R$ is an $n \times n$ upper triangular invertible matrix with positive entries on its diagonal.

Such factorization can be realized by Gram-Schmidt orthogonalization. The columns of $A$, say denoted as $\x_1, \dots, \x_n$, form the basis of $\Col A$. Apply the Gram-Schmidt process to construct an orthogonal basis $\{ \v_1, \dots, \v_n \}$ for $\Col A$ and let \[ Q = [\v_1, \dots, \v_n] \] For every $k = 1, \dots, n$, $\x_k$ is in $\span{\x_1, \dots, \x_k} = \span{\v_1, \dots, \v_k}$. So there are constants $r_{1k}, \dots, r_{kk}$ such that \[ \x_k = [\v_1, \dots, \v_k] \begin{bmatrix} r_{1k} \\ \vdots \\ r_{kk} \end{bmatrix} \] $r_{kk}$ is nonzero or else $\x_k$ is in $\span{\x_1, \dots, \x_{k-1}}$, which violates the linear independence condition of columns of $A$. We can assume $r_{kk} > 0$; otherwise we can multiply both $r_{kk}$ and $\v_k$ by $-1$ without compromising previous conditions. Let \[ \newcommand{\r}{\mathrm{r}} \r_k = \begin{bmatrix} r_{1k} \\ \vdots \\ r_{kk} \\ 0 \\ \vdots \\ 0 \end{bmatrix} \] We have $\x_k = Q \r_k$ for $k = 1, \dots, n$. Then \[ A = [\v_1, \dots, \v_n] [\r_1, \dots, \r_n] = Q R \] The fact that $R$ is invertible follows easily the fact that $Q$’s columns are linearly independent. Because $k$-th element of $k$-th column, i.e. $r_{kk}$, is positive, $R$’s diagonal entries are positive.

Last updated on Jan 7, 2022