Codex @codex  0

The Gram-Schmidt process turns a finite ordered family of linearly independent vectors $v_1,\dots ,v_k$ in an inner product space over the real numbers into an orthonormal basis $q_1,\dots ,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.^[ref]

Start with $u_1=v_1$ and $q_1=v_1/\Vert v_1\Vert$. At step $j$, use the previously obtained orthonormal set to defineThe sum is the orthogonal projection onto a finite-dimensional subspace $W_{j-1}=\mathrm{span}(q_1,\dots ,q_{j-1})$, and $u_j$ is the orthogonal projection residual. Linear independence ensures $u_j\ne 0$: 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: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, giveThe 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 $⟨v_j,q_i⟩$. With the convention linear in the second argument, write $⟨q_i,v_j⟩$ 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. ThenSubtracting the diagonal component leaves an orthogonal direction; dividing by its norm $1/\sqrt{2}$ 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.

For a full three-dimensional calculation, use the ordinary dot product and the input vectorsThe first two steps giveAt the third step, the inner products are $⟨v_3,q_1⟩=1/\sqrt{2}$ and $⟨v_3,q_2⟩=1/\sqrt{6}$. ConsequentlyThe 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$ hasFor the linear span of just the first two inputs in the three-dimensional example, $b=(0,0,1{)}^T$ gives $P_{W}b=(1/3,-1/3,2/3{)}^T$. Its orthogonal projection residual is $(-1/3,1/3,1/3{)}^T=q_3/\sqrt{3}$, 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.^[ref]

The Haar projection at level $J$ is the orthogonal projection onto the functions constant on level-$J$ dyadic intervals. On each cell it replaces $f$ by its cell average. This is the closest cellwise-constant approximation in the L2 norm, because choosing a constant $c$ on a cell minimizes ${\int }_I|f-c{|}^2$ at its cell average.

On $[0,1]$, take the step function with values $2,4,6,8$ on successive quarter-intervals. At level zero, its Haar projection is the constant $5$. At level one, it has values $3$ and $7$ on the two halves. At level two, it recovers the four original values exactly. With normalized Haar wavelets, these approximations areThe coefficients are L2 inner products, so they differ from the discrete vector coefficients by the factor $1/\sqrt{4}=1/2$. Their squared sum also has a direct meaning:The approximation errors in squared L2 norm of $P_{0}f,P_{1}f,P_{2}f$ are respectively $5,1,0$: each added detail removes exactly its own squared coefficient from the error.

The Haar projection can be expressed using level-$J$ Haar scaling functions, or through a coarse scaling family and the Haar wavelets at intermediate levels. On $[0,1]$ with lowest level zero, that coarse family is the single constant function $\varphi$. On the whole real line, use the integer translates of a coarse Haar scaling function instead; one global constant is not square-integrable. Refinement improves the representation while retaining the earlier coefficients.

The Hardy space of the circle is the closed subspace of L2 space whose negative Fourier coefficients vanish. The orthogonal projection onto it is denoted $P_{+}$. A continuous symbol $f$ defines a Toeplitz operator $T_f=P_{+}{M}_f{|}_{H^2}$. For continuous $f,g$, $T_f{T}_g-T_{fg}$ is compact: it is finite rank for Laurent polynomials, and uniform approximation extends the result.

For a finite-dimensional Hermitian operator $A$ with decreasing eigenvalues ${\lambda }_j$ and integer $0\le r\le d$, maximizing $\mathrm{Tr}(AB)$ over positive contractions $B$ with trace $r$ gives the sum of its leading $r$ eigenvalues. In an orthonormal eigenbasis, the diagonal entries of $B$ lie in $[0,1]$ and sum to $r$. Moving their weight to the largest eigenvalues can only increase the objective. An orthogonal projection onto their eigenvectors attains the maximum.

A Hermitian inner product is a Hermitian form $H$ on a complex vector space which has positive definiteness: $H(v,v)>0$ for every nonzero vector $v$. It is precisely a complex inner product. Only with this definiteness condition doesdefine a norm rather than a seminorm or an expression that may not be real. The standard Hermitian inner product on ${\mathbb{C}}^n$ is $H(z,w)={\sum }_j{z}_j\overline{w_j}$; positive weights $c_j$ give ${\sum }_j{c}_j{z}_j\overline{w_j}$, with squared norm ${\sum }_j{c}_j|z_j{|}^2$.^[ref]

A Hermitian inner product need not have a real matrix. For instance, with the linear-first coordinate convention,The last expression proves positive definiteness without a lengthy calculation of eigenvalues. For $z=(1,i)$ it gives $6$, while for $z=(1,-i)$ it gives $2$. These unequal values expose why a silent switch to $z^{\ast }Az$ would change this particular Hermitian inner product: with these same entries it gives $2$ at $(1,i)$. All entries must keep their roles from the matrix of a Hermitian form.

The Cauchy-Schwarz inequality for a Hermitian inner product statesEquality holds exactly when $u,v$ are linearly dependent, including when either is zero. For a nonzero $u$, outline the proof by setting $a=H(v,u)/H(u,u)$ and $r=v-au$. Then $H(r,u)=0$, and the Pythagorean theorem givesNonnegativity proves the inequality, while positive definiteness makes equality equivalent to $r=0$. The scalar $a$ has no extra conjugate because the first argument is linear.^[ref]

The Cauchy-Schwarz inequality also holds for a positive semidefinite Hermitian form, but equality need not imply linear dependence: for $H_0(z,w)=z_1\overline{w_1}$, the independent vectors $e_1$ and $e_1+e_2$ give $1=1$. Equality then describes dependence after passing to the quotient vector space by the radical of a Hermitian form. The indefinite Hermitian form in Hermitian form shows that conjugate symmetry alone does not even guarantee the inequality.

For a worked orthogonal projection, take $H_{+}(z,w)=z_1\overline{w_1}+2z_2\overline{w_2}$, $u=(1,1)$ and $v=(2,0)$. Then $a=2/3$, $au=(2/3,2/3)$ and $r=(4/3,-2/3)$, with $H_{+}(r,u)=0$ and $4=4/3+8/3$ for the squared norms. The residual is perpendicular in this Hermitian inner product even though its ordinary real dot product with $u$ is $2/3$. For complex $v=(1,i)$, the same orthogonal projection uses $a=(1+2i)/3$; rotating $v$ multiplies $a$ by $e^{i\theta }$, while rotating $u$ multiplies $a$ by $e^{-i\theta }$. This combines geometric decomposition with sensitivity to the relative complex arguments of the multipliers.

A Hermitian inner product therefore supplies more than a positive diagonal: orthogonality, orthogonal projection onto a span, and the triangle inequality for its norm make approximation and distance meaningful. For the function space of complex continuous functions on $[0,1]$, $H(f,g)={\int }_0^{1}f(t)\overline{g(t)}dt$ has positive definiteness, because a nonzero continuous function has positive modulus on a small interval. The same construction turns overlap under integration into lengths and best approximation in finite-dimensional vector subspaces.

For every nonempty closed convex set $C$ in a Hilbert space and every $x$ in that space, there is a unique $p\in C$ satisfyingClosedness and completeness let a limiting approximation attain the infimum; convexity prevents two different minimizers. The proof idea is to choose a sequence approaching the infimum. The parallelogram identity and the admissible midpoint make it a Cauchy sequence; applying the same identity to two putative minimizers proves uniqueness.

For a closed subspace of a Hilbert space, this nearest-point map is an orthogonal projection and is linear. For a general closed convex set it need not be linear: projecting the real line onto $[0,1]$ clips values below zero to zero and values above one to one. The theorem is therefore useful for both linear approximation and constrained nearest-point problems.^[ref]

Closedness is essential even in familiar examples. For the open interval $(0,1)\subseteq \mathbb{R}$ and $x=0$, the distance infimum is zero but no nearest point exists. The same obstruction appears when approximating $(1/k{)}_{k\ge 1}$ by finitely supported sequences: the infimum is zero, but the limit lies outside that subspace until we take its Hilbert space completion.

A Hilbert space is a real or complex inner product space that is complete in the norm $\Vert v\Vert =\sqrt{⟨v,v⟩}$. Completeness means that every Cauchy sequence has a limit in the space: if its terms become arbitrarily close in this norm, they converge to an allowed vector. The inner product supplies lengths and orthogonality; completeness ensures that limiting approximation procedures do not leave the space.

Finite-dimensional Euclidean spaces are examples, but the same geometry also works for sequences and functions. In the l2 sequence space,In the L2 space on $[-1,1]$ with Lebesgue measure,These formulas use the convention linear in the first argument. Elements of the L2 space are equivalence classes of square-integrable functions agreeing almost everywhere, so zero distance really identifies the same element. A vector can therefore be a whole function, and its squared length can measure an integrated squared error.

For example, approximating $f(x)=x^2$ by $a+bx$ is a nearest-point problem in this Hilbert space. The allowed approximations form the linear span of $1,x$, and the orthogonal projection is the constant $1/3$. Its residual $x^2-1/3$ is orthogonal to both allowed directions because its integral and its inner product with $x$ vanish. The geometry therefore identifies the best approximation without searching through every pair of coefficients.

This is useful whenever a complicated vector must be represented by a tractable collection of directions. Fourier series approximate functions with orthogonal oscillations; the Parseval identity relates the sum of squared coefficients to the squared norm. Least-squares solutions approximate attainable data using a linear operator. The Hilbert projection theorem explains why a nearest element exists and is unique for a nonempty closed convex set. Distinct application settings share the same geometry of useful components and orthogonal residuals. Casey Rodriguez's MIT lectures develop these connections between Hilbert spaces, Fourier series, and nearest-point problems.^[ref]

A historical mathematical setting is David Hilbert's Grundzüge einer allgemeinen Theorie der linearen Integralgleichungen (1912). Its preface states that it reprints six communications published during 1904–1910 on linear integral equations. This provides a concrete source for the integral-equation setting associated with the name, while the abstract definition above incorporates later developments.^[ref]

A Householder transformation is a reflection that leaves every direction in a chosen hyperplane fixed and reverses its normal direction. For a real unit vector $u$, its matrix isTo understand the formula, decompose any vector into its orthogonal projection onto the normal and a perpendicular component:Then $Hx=x_{\perp }-x_{\parallel }$. Subtracting twice the normal component changes its sign while retaining everything parallel to the mirror. A nonzero normal $v$ gives the equivalent formula $H=I-2v{v}^T/(v^{T}v)$, so normalization can be deferred.

For example, take $u=(2,1{)}^T/\sqrt{5}$. Its mirror is the straight line $2x_1+x_2=0$, andThe midpoint of these two vectors is $(-1,2{)}^T$, which lies on the mirror; their connecting segment is parallel to its normal. Both vectors have Euclidean norm five.

Several useful properties follow from this decomposition. The Householder reflection is a symmetric matrix and an orthogonal matrix:Reflecting twice restores the original vector; Euclidean norms and inner products are preserved. The eigenvalue is $-1$ along $u$ and $+1$ on $u^{\perp }$, so $\det H=-1$. A reflection reverses orientation even though it preserves lengths.

The computational payoff is that the mirror can be chosen to send a whole vector onto one coordinate axis, eliminating several entries at once. Householder QR decomposition repeats this operation on the remaining parts of successive columns. For a real symmetric matrix, applying the same Householder reflection on both sides gives a matrix similarity $HAH$ that preserves symmetry and eigenvalues; this is the basis of Householder tridiagonalization.

Alston S. Householder's 1958 paper Unitary Triangularization of a Nonsymmetric Matrix develops this elimination method. Its motivation includes reducing the arithmetic needed for triangularization while retaining the conditioning advantages of orthogonal transformations. ^[ref] Over the complex numbers, $I-2u{u}^{\ast }$ for a unit $u$ is Hermitian and unitary, with the star denoting the conjugate transpose; the coordinate-axis construction below is stated for real vectors.

For a connected graph, the Moore-Penrose inverse of its oriented incidence matrix satisfies $D^{†}D=I-{\Pi }_1$, because this product is the orthogonal projection onto $(\ker D{)}^{\perp }$. Thus every signal decomposes into its constant mean and $D^{†}D\theta$. Writing $L={\max }_e\Vert (D^{†}{)}_{\cdot ,e}{\Vert }_2$, a sub-Gaussian random vector noise gives a simultaneous bound on $\Vert (D^{†}{)}^{\top }z{\Vert }_{\infty }$ with scale $L\sqrt{\log (m/\delta )}$.

An inner product assigns a scalar $⟨u,v⟩$ to two vectors and supplies their lengths and orthogonality. Using the convention linear in the first argument, it satisfiesThe resulting norm is $\Vert v\Vert =\sqrt{⟨v,v⟩}$. Over the real numbers, conjugation has no effect and the form is symmetric and bilinear. Over the complex numbers, it is sesquilinear; the convention linear in the second argument is also common, so formulas for coefficients must match the stated convention.

The Euclidean example is $⟨u,v⟩={\sum }_i{u}_i\overline{v_i}$. For real $u=(2,1)$ and $v=(1,3)$ this gives $⟨u,v⟩=5$, while $\Vert u{\Vert }^2=5$ and $\Vert v{\Vert }^2=10$. If $r=(-1,2)$, then $⟨r,u⟩=0$: perpendicularity becomes an algebraic equation. The Cauchy-Schwarz inequality gives $|⟨u,v⟩|\le \Vert u\Vert \Vert v\Vert$, and in a real inner product space it makes the angle formula $\cos \theta =⟨u,v⟩/(\Vert u\Vert \Vert v\Vert )$ meaningful for nonzero vectors.

Different inner products express different measurements. The weighted example $⟨u,v⟩=4u_1{v}_1+u_2{v}_2$ on ${\mathbb{R}}^2$ gives $\Vert (x,y){\Vert }^2=4x^2+y^2$, so its unit-length vectors lie on an ellipse. For functions, an integral such as $⟨f,g⟩=\int f\overline{g}$ supplies the geometry of the L2 space. This lets orthogonal projection and least-squares solutions apply to curves as well as coordinate lists.

For an idempotent linear map $P$ on a finite-dimensional real vector space, take any positive definite inner product on that space. The displayed new inner product is positive definite since its squared norm vanishes only if both $Pu$ and $(I-P)u$ vanish. It makes the kernel of a linear map and image of a linear map orthogonal. Since $P^2=P$, one has $⟨Pu,v{⟩}_P=⟨u,Pv{⟩}_P$; thus $P$ becomes an orthogonal projection.

An innovation measures the part of the current observation not predicted from past observations. The linear innovation process uses orthogonal projection onto the past linear span. A conditional expectation predictor can use nonlinear information; the two predictors agree for a Gaussian process.