Gram-Schmidt Orthogonalization In L2

From Independent Functions to Orthogonality

In $L^2$, functions are identified when they agree almost everywhere. A finite list can therefore be linearly independent as pointwise formulas might suggest, yet dependent as $L^2$ elements if a linear combination vanishes almost everywhere. Gram–Schmidt takes a finite linearly independent list of $L^2$ elements and produces an orthonormal list with the same successive spans. Its central step is to subtract from each new function its projections onto the directions already constructed.

Let $(X,\mathcal{M},\mu)$ be any measure space; it need not be finite, complete, or sigma-finite. We use complex-valued $L^2(\mu)$, which includes real-valued functions as a special case. Functions in $L^2(\mu)$ are equivalence classes modulo equality $\mu$-a.e. We use the inner product, linear in its first argument, and its associated norm:

\langle f,g\rangle=\int_X f\overline{g}\,d\mu, \qquad \|f\|_2=\left(\int_X |f|^2\,d\mu\right)^{1/2}.

Two elements are orthogonal if their inner product is zero. A list is orthonormal if each element has norm one and distinct elements are orthogonal. The Cauchy–Schwarz inequality ensures that the displayed inner product is finite for $f,g\in L^2(\mu)$.

Definition (Gram–Schmidt algorithm): Given a finite linearly independent list $f_1,\ldots,f_n$ in $L^2(\mu)$, define recursively $$ u_1=f_1,\qquad q_1=\frac{u_1}{\|u_1\|_2}, $$ and, for $2\le k\le n$, $$ u_k=f_k-\sum_{j=1}^{k-1}\langle f_k,q_j\rangle q_j, \qquad q_k=\frac{u_k}{\|u_k\|_2}. $$ The functions $u_k$ are the residuals before normalization; the $q_k$ are the normalized outputs. The formulas are in $L^2(\mu)$, so their conclusions hold for equivalence classes, or for representatives $\mu$-a.e.

The coefficient $\langle f_k,q_j\rangle$ is the amount of $f_k$ in the already normalized direction $q_j$. Because $\|q_j\|_2=1$, no additional denominator is needed in that formula. If instead one subtracts a projection onto a non-normalized vector $v\ne0$, the corresponding term is $\frac{\langle f_k,v\rangle}{\|v\|_2^2}v$.

Why the Algorithm Works

Theorem (Gram–Schmidt): Suppose $f_1,\ldots,f_n$ are linearly independent in $L^2(\mu)$. Then the recursive formulas are defined at every step. The resulting $q_1,\ldots,q_n$ are orthonormal, and for each $k$, the spans of $f_1,\ldots,f_k$ and $q_1,\ldots,q_k$ are equal.

Proof. We proceed by induction. For $k=1$, linear independence implies $f_1\ne0$ in $L^2(\mu)$, so $\|u_1\|_2=\|f_1\|_2>0$. Thus $q_1$ is defined, has norm one, and spans the same one-dimensional space as $f_1$.

Now suppose $q_1,\ldots,q_{k-1}$ are orthonormal and their first $k-1$ elements span the same subspace as $f_1,\ldots,f_{k-1}$. For $1\le i<k$, conjugate symmetry gives $\langle q_j,q_i\rangle=0$ when $j\ne i$, while $\langle q_i,q_i\rangle=1$. Using linearity in the first argument, we obtain

\langle u_k,q_i\rangle =\langle f_k,q_i\rangle -\sum_{j=1}^{k-1}\langle f_k,q_j\rangle\langle q_j,q_i\rangle =\langle f_k,q_i\rangle-\langle f_k,q_i\rangle =0.

So the residual is orthogonal to every earlier $q_i$. If $u_k=0$ in $L^2(\mu)$, the defining formula would express $f_k$ as a linear combination of $q_1,\ldots,q_{k-1}$. By the induction hypothesis, this would put $f_k$ in the span of $f_1,\ldots,f_{k-1}$, contradicting the assumed linear independence. Therefore $\|u_k\|_2>0$, and $q_k$ is defined. Normalizing $u_k$ preserves its orthogonality to every earlier $q_i$ and gives $\|q_k\|_2=1$.

The formula for $u_k$ writes $f_k$ as $u_k$ plus a linear combination of $q_1,\ldots,q_{k-1}$. Since $q_k$ is a nonzero scalar multiple of $u_k$, adjoining $q_k$ to the earlier $q_j$'s gives the same span as adjoining $f_k$ to the earlier $f_j$'s. This proves the span claim and completes the induction. $\square$

The theorem also explains the normalization formula: after subtracting the earlier components, divide the residual by its $L^2$ norm. Independence is essential because it guarantees this residual is nonzero; without it, a zero denominator can occur.

Worked Calculations

Worked Example: The Functions 1 and x on [0,1]

Take Lebesgue measure $m$ on $[0,1]$, and apply Gram–Schmidt to the real-valued functions $f_1(x)=1$ and $f_2(x)=x$. They are linearly independent in $L^2([0,1],m)$: if $a+bx=0$ $m$-a.e., continuity implies it vanishes everywhere on $[0,1]$, and evaluating at $0$ and $1$ gives $a=b=0$.

First, $\|f_1\|_2^2=\int_0^1 1\,dx=1$, so $q_1=1$. The projection coefficient for $f_2$ is

\langle x,q_1\rangle=\int_0^1x\,dx=\frac12.

Thus $u_2(x)=x-\frac12$. Its squared norm is

\|u_2\|_2^2 =\int_0^1\left(x-\frac12\right)^2dx =\frac13-\frac12+\frac14 =\frac1{12}.

Since $\sqrt{1/12}=1/(2\sqrt{3})$, the normalized output is $q_2(x)=2\sqrt{3}(x-\frac12)$. Check: $\langle q_2,q_1\rangle=2\sqrt{3}(\frac12-\frac12)=0$, and $\|q_2\|_2^2=(2\sqrt{3})^2(1/12)=1$.

Worked Example: The First Three Monomials on [−1,1]

Use Lebesgue measure on $[-1,1]$ and start with $1,x,x^2$. These polynomial classes are linearly independent: a polynomial that vanishes almost everywhere on an interval has infinitely many roots, so it must be the zero polynomial. First, $\|1\|_2^2=2$, hence $q_1=1/\sqrt{2}$. Since $\int_{-1}^1x\,dx=0$, the residual for $x$ is $u_2=x$. Its squared norm is $2/3$, giving $q_2=\sqrt{3/2}\,x$.

For $x^2$, the coefficient along $q_1$ is $\langle x^2,q_1\rangle=(2/3)/\sqrt{2}=\sqrt{2}/3$, so its projection term is $(\sqrt{2}/3)(1/\sqrt{2})=1/3$. Its coefficient along $q_2$ is zero because $\int_{-1}^1x^3\,dx=0$. Therefore $u_3=x^2-\frac13$, and

\|u_3\|_2^2 =\int_{-1}^1\left(x^2-\frac13\right)^2dx =\frac25-\frac49+\frac29 =\frac8{45}.

Thus $q_3=\sqrt{45/8}(x^2-\frac13)=\sqrt{5/8}(3x^2-1)$. Check: $\int_{-1}^1(3x^2-1)\,dx=2-2=0$, and $\int_{-1}^1(3x^2-1)^2dx=18/5-4+2=8/5$; multiplying by $5/8$ gives $\|q_3\|_2^2=1$. The remaining orthogonality check is $\langle q_3,q_2\rangle=0$, since its integrand is an odd polynomial.

Worked Example: Piecewise-Constant Functions on Unequal Intervals

In $[0,4]$ with Lebesgue measure, let $A=[0,1)$, $B=[1,3)$, and $C=[3,4]$. Their measures are $1,2,1$, respectively, and they partition $[0,4]$. Set $f_1=\chi_{[0,4]}$ and $f_2=\chi_A+\chi_B$. These are independent in $L^2$, since $f_1=1$ on $C$ while $f_2=0$ there, and $f_2$ is not zero on $A$. Since $\|f_1\|_2^2=4$, we have $q_1=\frac12\chi_{[0,4]}$.

The coefficient $\langle f_2,q_1\rangle$ is $3/2$, because $f_2$ is one on a set of measure $1+2=3$. The residual is therefore $u_2=f_2-\frac34\chi_{[0,4]}$. It equals $1/4$ on $A$ and $B$, and $-3/4$ on $C$. Its squared norm and normalized form are

\|u_2\|_2^2 =1\left(\frac14\right)^2+2\left(\frac14\right)^2+1\left(-\frac34\right)^2 =\frac{12}{16} =\frac34, \qquad q_2=\frac{2}{\sqrt{3}}u_2.

Check: $\langle q_2,q_1\rangle=\frac12\int_0^4q_2\,dx=0$, since the integral of $u_2$ is $1(1/4)+2(1/4)+1(-3/4)=0$. Also $\|q_2\|_2^2=(4/3)(3/4)=1$. The unequal interval lengths matter: the middle value contributes twice to both calculations.

A Common Projection Error

For a non-normalized vector, subtracting its inner product coefficient alone generally does not remove the component in that direction. On $[-1,1]$, try to remove the component of $x^2$ along $f_1=1$. A mistaken calculation subtracts $\langle x^2,1\rangle\,1=(2/3)1$. The resulting function $x^2-2/3$ is not orthogonal to $1$, because

\langle x^2-\tfrac23,1\rangle =\frac23-\frac23\int_{-1}^1 1\,dx =\frac23-\frac43 =-\frac23\ne0.

The correction is to divide by the squared norm of the direction being projected onto. Here $\|1\|_2^2=2$, so the projection is $\frac{\langle x^2,1\rangle}{\|1\|_2^2}1=\frac13\,1$, and $x^2-\frac13$ is orthogonal to $1$. In Gram–Schmidt, the $q_j$'s are already normalized, which is exactly why the shorter coefficient $\langle f_k,q_j\rangle$ works.

Gram–Schmidt is useful whenever a finite collection of functions is easier to analyze through orthogonal directions than through overlapping ones. The procedure is algebraic, but its norms and inner products depend on the chosen measure: changing the interval, the measure, or the functions changes the resulting orthonormal list. For example, the polynomial outputs above are specific to Lebesgue measure on $[-1,1]$. The method gives an orthonormal basis for the finite-dimensional span of the input list; it does not assert that this span is all of $L^2(\mu)$.

Check Your Understanding

In each question, treat functions as $L^2$ equivalence classes and use the measure specified.

On $[0,1]$ with Lebesgue measure, apply Gram–Schmidt to $1$ and $x^2$. Compute the residual and its norm.
Why does linear independence guarantee that the residual $u_k$ in the algorithm has positive norm?
For a nonzero, not necessarily normalized $v\in L^2(\mu)$, write the formula for subtracting the projection of $f$ onto the span of $v$.
For the piecewise-constant example, recompute $\int_0^4u_2\,dx$ using the values on $A,B,C$, including each interval's measure.
What fails if $f_2=2f_1$ is supplied as the second function after $f_1\ne0$? Identify the residual and the step of the algorithm that is then undefined.