Command Palette

Search for a command to run...

Linear Methods of AI

Orthogonal Projection

Existence and Uniqueness Theorem

An important question that arises is whether the best approximation really exists and whether its solution is unique? The answer is yes. Let VV be a Euclidean vector space and S⊂VS \subset V be a finite-dimensional vector subspace. Then for every f∈Vf \in V there exists a unique best approximation g∈Sg \in S with

∥f−g∥=min⁡φ∈S∥f−φ∥\|f - g\| = \min_{\varphi \in S} \|f - \varphi\|

This theorem guarantees that the best approximation always exists and is unique. Like finding the closest point from a location to a highway, there is always one point that gives the shortest distance.

Let nn be the dimension of SS and ψ1,…,ψn\psi_1, \ldots, \psi_n be a basis of SS. Using the Gram-Schmidt process, we can compute an orthonormal basis φ1,…,φn\varphi_1, \ldots, \varphi_n of SS with ⟨φi,φk⟩=δik\langle \varphi_i, \varphi_k \rangle = \delta_{ik}.

Every g∈Sg \in S has a unique representation as g=∑i=1nαiφig = \sum_{i=1}^n \alpha_i \varphi_i. Then it follows that

∥f−g∥2=⟨f−g,f−g⟩=⟨f−∑i=1nαiφi,f−∑k=1nαkφk⟩\|f - g\|^2 = \langle f - g, f - g \rangle = \left\langle f - \sum_{i=1}^n \alpha_i \varphi_i, f - \sum_{k=1}^n \alpha_k \varphi_k \right\rangle
=⟨f,f⟩−2∑i=1nαi⟨f,φi⟩+∑i,k=1nαiαk⟨φi,φk⟩= \langle f, f \rangle - 2 \sum_{i=1}^n \alpha_i \langle f, \varphi_i \rangle + \sum_{i,k=1}^n \alpha_i \alpha_k \langle \varphi_i, \varphi_k \rangle
=∥f∥2−2∑i=1nαi⟨f,φi⟩+∑i=1nαi2= \|f\|^2 - 2 \sum_{i=1}^n \alpha_i \langle f, \varphi_i \rangle + \sum_{i=1}^n \alpha_i^2

Using the identity (αi−⟨f,φi⟩)2=αi2−2αi⟨f,φi⟩+⟨f,φi⟩2(\alpha_i - \langle f, \varphi_i \rangle)^2 = \alpha_i^2 - 2\alpha_i \langle f, \varphi_i \rangle + \langle f, \varphi_i \rangle^2, we obtain

∥f−g∥2=∥f∥2−∑i=1n⟨f,φi⟩2+∑i=1n(αi−⟨f,φi⟩)2\|f - g\|^2 = \|f\|^2 - \sum_{i=1}^n \langle f, \varphi_i \rangle^2 + \sum_{i=1}^n (\alpha_i - \langle f, \varphi_i \rangle)^2

Function g∈Sg \in S is the best approximation of ff if and only if αi=⟨f,φi⟩\alpha_i = \langle f, \varphi_i \rangle for i=1,…,ni = 1, \ldots, n.

Orthonormal Basis Formula

For an orthonormal basis φ1,…,φn\varphi_1, \ldots, \varphi_n of SS, the best approximation is given by

g=∑i=1n⟨f,φi⟩φig = \sum_{i=1}^n \langle f, \varphi_i \rangle \varphi_i

The best approximation satisfies the distance formula

∥f−g∥=(∥f∥2−∑i=1n⟨f,φi⟩2)12\|f - g\| = \left( \|f\|^2 - \sum_{i=1}^n \langle f, \varphi_i \rangle^2 \right)^{\frac{1}{2}}

The best approximation gg of ff in SS is the orthogonal projection of ff onto SS. This means

⟨f−g,φ⟩=0 for all φ∈S\langle f - g, \varphi \rangle = 0 \text{ for all } \varphi \in S

Geometrically, the vector from gg to ff is perpendicular to the subspace SS. Imagine dropping a ball from the air to the floor, the point where it lands is the orthogonal projection of the ball onto the floor.

Construction with Arbitrary Basis

When an orthonormal basis of SS is not known, we can use an arbitrary basis ψ1,…,ψn\psi_1, \ldots, \psi_n of SS. Let g=∑i=1nαiψig = \sum_{i=1}^n \alpha_i \psi_i be the unique representation of gg with respect to this basis.

Since ψk∈S\psi_k \in S, the orthogonality condition gives

⟨f−∑i=1nαiψi,ψk⟩=0,k=1,…,n\left\langle f - \sum_{i=1}^n \alpha_i \psi_i, \psi_k \right\rangle = 0, \quad k = 1, \ldots, n

This yields the linear system

∑i=1nαi⟨ψi,ψk⟩=⟨f,ψk⟩,k=1,…,n\sum_{i=1}^n \alpha_i \langle \psi_i, \psi_k \rangle = \langle f, \psi_k \rangle, \quad k = 1, \ldots, n

The coefficient matrix A=(⟨ψi,ψk⟩)i=1,…,n,k=1,…,nA = (\langle \psi_i, \psi_k \rangle)_{i=1,\ldots,n,k=1,\ldots,n} is called the Gram matrix of the basis ψ1,…,ψn\psi_1, \ldots, \psi_n. This matrix is symmetric and positive definite. For α≠0\alpha \neq 0 it holds

αTAα=∑i,k=1n⟨ψi,ψk⟩αiαk=∥∑i=1nαiψi∥2>0\alpha^T A \alpha = \sum_{i,k=1}^n \langle \psi_i, \psi_k \rangle \alpha_i \alpha_k = \left\| \sum_{i=1}^n \alpha_i \psi_i \right\|^2 > 0

However, matrix AA can become very ill-conditioned in practice. For example, for the monomial basis 1,x,…,xn1, x, \ldots, x^n, the matrix becomes very unstable so that computing gg becomes difficult for large nn.

The Gauss approximation with an orthonormal basis of SS has the advantage of easy computation of the best approximation

g(x)=∑k=1n⟨f,φk⟩φk(x)g(x) = \sum_{k=1}^n \langle f, \varphi_k \rangle \varphi_k(x)
=∑k=1n∫abf(t)φk(t) dt φk(x)= \sum_{k=1}^n \int_a^b f(t) \varphi_k(t) \, dt \, \varphi_k(x)

without needing to solve a linear system. With an orthonormal basis, we can directly compute the projection coefficients like using a coordinate system that is already neatly arranged and mutually perpendicular.

Previous

Best Approximation in Function and Polynomial Spaces

Next

Orthogonal Polynomials