Gram–Schmidt Process · aiwiki.page

The Gram–Schmidt process is an algorithm in linear algebra that constructs an orthonormal basis from an ordered, linearly independent collection of vectors. It successively subtracts the components of each vector along previously constructed directions, then normalizes the remaining vector. The resulting vectors span the same subspace as the original collection. Applied to matrix columns, the process produces a QR decomposition, connecting its geometric interpretation with computational methods. (github.com)

Mathematical setting

Let $v_1,\ldots,v_n$ be vectors in a vector space over the real numbers or complex numbers, equipped with an inner product. Orthogonality means that the inner product of two vectors is zero; orthonormality additionally requires each vector to have unit length. Gram–Schmidt uses the associated norm,

\|v\|=\sqrt{\langle v,v\rangle}.

The construction applies to abstract inner-product spaces, not only coordinate vectors: polynomials and suitable spaces of functions also admit it. (people.tamu.edu)

The standard assumption is linear independence. If the input is a basis of a finite-dimensional space, the output is an orthonormal basis of that space. More generally, it is a basis of the inputs’ linear span, which may be a proper subspace of the ambient space. (github.com)

Classical construction

Use the convention that $\langle x,y\rangle$ is conjugate-linear in its first argument and linear in its second. Set

u_1=v_1,\qquad q_1=\frac{u_1}{\|u_1\|}.

For $k=2,\ldots,n$ , define

u_k=v_k-\sum_{j=1}^{k-1}q_j\langle q_j,v_k\rangle, \qquad q_k=\frac{u_k}{\|u_k\|}.

Each summand is the orthogonal projection of $v_k$ onto the direction $q_j$ . Subtracting their sum leaves the component perpendicular to all previously constructed directions. Omitting normalization gives mutually orthogonal vectors $u_k$ , rather than unit vectors $q_k$ . (archive.nptel.ac.in)

The justification follows directly from the inner-product identities. Assuming the earlier $q_j$ are orthonormal, for every $i<k$ ,

\langle q_i,u_k\rangle =\langle q_i,v_k\rangle -\sum_{j<k}\langle q_i,q_j\rangle \langle q_j,v_k\rangle =0.

Moreover, each new vector is a linear combination of the first $k$ inputs, and the defining equation expresses $v_k$ in terms of the new vectors. Consequently,

\operatorname{span}(q_1,\ldots,q_k) =\operatorname{span}(v_1,\ldots,v_k).

Independence ensures $u_k\ne0$ , so normalization is possible. (archive.nptel.ac.in)

For dependent inputs, a zero residual identifies a vector already in the span of earlier accepted vectors; it can be discarded. The output generally depends on input order, although the final spanned subspace does not. (people.tamu.edu)

Worked example

Consider, in Euclidean space $\mathbb R^3$ ,

v_1=(1,1,0),\qquad v_2=(1,0,1).

With the standard dot product, the first normalized vector is

q_1=\frac{(1,1,0)}{\sqrt2}.

The second residual is

u_2=v_2-q_1\langle q_1,v_2\rangle =(1,0,1)-\tfrac12(1,1,0) =(\tfrac12,-\tfrac12,1).

Thus

q_2=\frac{(1,-1,2)}{\sqrt6}.

Direct calculation gives $\langle q_1,q_2\rangle=0$ and unit norm for both vectors. This illustrates the general construction: $q_1,q_2$ form an orthonormal basis of the plane spanned by the two inputs. (archive.nptel.ac.in)

Matrix formulation and least squares

Place $n$ independent vectors in the columns of an $m\times n$ matrix $A$ , with $m\ge n$ . Gram–Schmidt yields

A=QR,

where $Q=[q_1\ \cdots\ q_n]$ and $R$ is upper triangular. Its entries are

r_{jk}=\langle q_j,v_k\rangle\quad(j<k), \qquad r_{kk}=\|u_k\|>0.

The relation $Q^*Q=I_n$ uses the conjugate transpose $Q^*$ and the identity matrix. For real matrices, $Q^*=Q^T$ . When $m=n$ , $Q$ is an orthogonal matrix in the real case and a unitary matrix in the complex case. (github.com)

For ordinary least squares, minimizing $\|Ax-b\|_2$ reduces, in exact arithmetic, to solving

Rx=Q^*b.

The fitted vector is $QQ^*b$ . This avoids explicitly forming the normal equations $A^*Ax=A^*b$ , an important distinction in numerical computation. (ocw.mit.edu)

Modified Gram–Schmidt and numerical behavior

In floating-point arithmetic, classical Gram–Schmidt can lose orthogonality, particularly when input vectors are nearly dependent. Modified Gram–Schmidt changes the order of operations: initialize $w=v_k$ , then successively compute

r_{jk}=\langle q_j,w\rangle,\qquad w\leftarrow w-q_jr_{jk},

before normalizing $w$ . Each projection therefore uses the updated residual rather than the original vector. The two versions are equivalent in exact arithmetic but differ in numerical stability. (ocw.mit.edu)

Modified Gram–Schmidt generally preserves orthogonality better, but substantial loss can still occur. Reorthogonalization repeats the projection-removal step to reduce remaining components along earlier vectors. Both basic versions require $O(mn^2)$ arithmetic operations. Householder transformations provide another QR construction with stronger orthogonality properties in floating-point computation. (netlib.org)

Function spaces and iterative methods

Applying Gram–Schmidt to $1,x,x^2,\ldots$ , using

\langle f,g\rangle=\int_{-1}^{1}\overline{f(x)}g(x)\,dx,

produces orthogonal polynomials. With conventional scaling, these are the Legendre polynomials, beginning with $1$ , $x$ , and $(3x^2-1)/2$ . Conventional Legendre normalization differs from unit-norm normalization. In a separable Hilbert space, orthogonalizing a countable collection with dense span produces an orthonormal basis in the sense of closed linear span. (people.tamu.edu)

In numerical linear algebra, Gram–Schmidt also builds bases of Krylov subspaces. Orthogonalizing successive matrix-generated vectors underlies the Arnoldi iteration, which supplies the orthonormal basis used by the generalized minimal residual method for solving linear systems. (netlib.org)