Best approximation - Ciallo Wiki

1 Problem formulation and notation

1.1 Distance to a subspace

Let \(X\) be a normed (or inner-product) space with norm \(\\|\cdot\\|\). Given a (linear) subspace \(M\subseteq X\) and a point \(x\in X\), the best approximation problem seeks an element \(m^\*\in M\) that minimizes the distance from \(x\) to \(M\):

\\|x-m^\*\\|=\inf_{m\in M}\\|x-m\\|.

\] The minimized value is often denoted \(\operatorname{dist}(x,M)\). When such an \(m^\*\) exists, it is called a best approximant of \(x\) from \(M\).

1.2 Norms, metrics, and induced approximation criteria

The distance criterion is induced by the norm: the “closest” point depends on \(\\|\cdot\\|\). In inner-product spaces, the norm comes from the inner product, but in general Banach spaces different norms can change the minimizer set. The induced metric is \(d(u,v)=\\|u-v\\|\), so the optimization is equivalent to minimizing \(d(x,m)\) over \(m\in M\).

1.3 Existence and uniqueness questions

Two foundational issues accompany the formulation:

Existence: does the infimum become a minimum, i.e., does there exist \(m^\*\in M\) attaining the distance?
Uniqueness: if a minimizer exists, is it unique?

Both are governed by structural properties of the space and the subspace, such as completeness and closedness (and, in non-Hilbert settings, convexity properties tied to the norm).

2 Geometry in inner-product spaces

2.1 Orthogonal projection viewpoint

In an inner-product space \(H\), the best approximation from a subspace is tightly linked to orthogonal projection. When \(M\) is a closed subspace, there exists an orthogonal projection operator \(P_M:H\to M\) such that \(P_M x\in M\) is the closest point in \(M\) to \(x\).

2.1.1 Characterization by orthogonality

The key geometric property is that the residual \(x-P_M x\) is orthogonal to the subspace: \[ x-P_M x \perp M. \] Equivalently, for every \(m\in M\), \[ \langle x-P_M x,\, m\rangle=0. \] This orthogonality condition serves as a practical characterization of the best approximant.

2.1.2 Best approximation theorem (orthogonality implies optimality)

If \(m^\*\in M\) satisfies \[ x-m^\*\perp M, \] then \(m^\*\) is optimal: for any \(m\in M\), \[

\\|x-m\\| \ge \\|x-m^\*\\|.

\] Thus, orthogonality of the residual not only describes the projection but also guarantees minimal distance.

2.2 Pythagorean identity and error decomposition

Inner-product geometry provides an exact quantitative decomposition of error.

2.2.1 Right-angle structure of residuals

When \(m^\*\) is the orthogonal projection of \(x\) onto \(M\), the vector \(x-m^\*\) is orthogonal to every \(m-m^\*\) with \(m\in M\). This forms a right-angle relationship in the underlying vector geometry.

2.2.2 Energy or squared-norm interpretation

Using orthogonality, one obtains the Pythagorean-type identity: \[

\\|x-m\\|^2=\\|x-m^\\\|^2+\\|m-m^\\\|^2 \quad (m\in M).

The minimized residual norm \(\\|x-m^\\\|^2\) can be read as the “energy” left outside the subspace, and the additional term \(\\|m-m^\\\|^2\) measures how far \(m\) departs from the projection.

2.3 Uniqueness for closed subspaces

If \(M\) is closed in a Hilbert space, then the orthogonal projection exists and is unique, so the best approximant is unique. Intuitively, if two points in \(M\) achieved the same minimal distance, their difference would lie in \(M\) while also being compatible with orthogonality to the residual, forcing equality.

3 Algebraic characterization (least squares)

3.1 Normal equations

In finite-dimensional least-squares problems, the best approximation to data is commonly formulated as minimizing a squared residual. Suppose \(H=\mathbb{R}^n\) with the Euclidean inner product and \(M\) is a linear subspace described as the span of the columns of a matrix \(A\in\mathbb{R}^{n\times k}\). The best approximation to \(x\in\mathbb{R}^n\) from \(M\) is obtained by solving a least-squares system \[

\min_{c\in\mathbb{R}^k}\\|x-Ac\\|^2.

\] A necessary condition for optimality leads to the normal equations \[ A^{\mathsf T}A\,c = A^{\mathsf T}x, \] whenever the minimizer exists.

3.2 Orthogonality of residual vectors

The normal equations encode the orthogonality condition. If \(r=x-Ac^\*\) is the residual at the minimizer, then \[ A^{\mathsf T}r=0, \] meaning that \(r\) is orthogonal to the column space of \(A\), which is the subspace \(M\).

3.3 Coordinate formulations using bases

The projection can be expressed in coordinates when a basis for \(M\) is chosen.

3.3.1 Projection matrix in finite-dimensional spaces

If \(M\) has an orthonormal basis \(u_1,\dots,u_k\), then the projection onto \(M\) is \[ P_M x=\sum_{i=1}^k \langle x,u_i\rangle u_i. \] In matrix form, if \(U=[u_1\,\cdots\,u_k]\) has orthonormal columns, then \[ P_M = U U^{\mathsf T}. \] For non-orthonormal bases, formulas involve Gram matrices and pseudoinverses, but the conceptual content remains the same: the projection is a linear map determined by orthogonality to \(M^\perp\).

4 Existence and approximation in general normed spaces

4.1 Conditions for existence of nearest points

In a general normed space \(X\), existence is not automatic. A common sufficient setting is a complete space (Banach space) together with a closed, convex target set; for a linear subspace this typically means closedness. While Hilbert spaces have especially strong projection properties, Banach spaces require additional assumptions tied to geometry of the norm and compactness-type arguments.

4.2 Non-uniqueness and dependence on norm choice

Even when a nearest point exists, it may fail to be unique. Non-uniqueness can occur because the unit sphere geometry associated with the norm may contain “flat” regions, allowing multiple points in \(M\) to be equally close to \(x\). Moreover, changing the norm can change the minimizing set.

4.3 Strict convexity and uniqueness of best approximants

A widely used criterion for uniqueness is strict convexity of the norm. Roughly, strict convexity means that line segments on the unit sphere are not flat: if two distinct points have the same maximal norm and lie on a line, their midpoint has strictly smaller norm. In such spaces, best approximations to closed convex sets—hence to closed subspaces—tend to be unique when a minimizer exists.

5 Computation and algorithms

5.1 Explicit projection using orthonormal bases

When an orthonormal basis of \(M\) is available, best approximation is computed directly from inner products: \[ P_M x=\sum_i \langle x,u_i\rangle u_i. \] This approach is numerically stable in many settings because orthonormality avoids conditioning issues inherent to general bases.

5.2 Gram–Schmidt and numerical stability considerations

If an orthonormal basis is not given, one may construct it from a spanning set using the Gram–Schmidt process. In floating-point arithmetic, classical Gram–Schmidt can suffer from loss of orthogonality; modified Gram–Schmidt or reorthogonalization strategies are often used to improve numerical reliability. The computational objective remains to enable the projection formula via near-orthonormal vectors.

5.3 QR factorization approach to least squares

For least-squares problems in finite dimensions, the QR factorization is a standard computational method. If \(A=QR\) with \(Q\) orthonormal and \(R\) upper triangular, then the minimizer for \(\\|x-Ac\\|\) can be found efficiently by transforming the system into an upper-triangular one. This avoids explicitly forming \(A^{\mathsf T}A\), which can worsen conditioning.

5.4 Iterative projection methods

5.4.1 Alternating projections (conceptual overview)

When the subspace (or constraint set) is expressed via intersections or unions of simpler structures, one can use alternating projections, repeatedly projecting onto each component. While the exact best approximation may be difficult to compute directly, iteration can reduce the distance to the feasible set under appropriate conditions.

5.4.2 Krylov/subspace iteration connections

In large-scale computations, one often seeks approximations in growing subspaces built from the data and operators involved (e.g., residuals and their images under linear mappings). These subspaces lead to iterative schemes where each step resembles a best-approximation update within a restricted space, linking the theory to Krylov methods and other subspace iteration techniques.

6 Applications to data fitting and regression

6.1 Linear least squares as best approximation

Linear regression and related fitting problems can be interpreted as best approximation. In the common Euclidean setting, the fitted model is the orthogonal projection of the observed response vector onto the span of the regressors. The residual vector then lies in the orthogonal complement, making the geometric interpretation precise.

6.2 Subspace models in statistical learning contexts (high level)

Beyond classical regression, many learning models involve approximating data or functions by restricting to structured sets—linear subspaces, low-rank manifolds (locally linearized), or feature spans. Even when the full model is not linear, local or surrogate optimization often reduces to variants of best approximation to a subspace or to a sequence of such subproblems.

6.3 Error bounds and interpretation of residual norms

The minimized residual norm \(\\|x-P_M x\\|\) measures the mismatch between the data and the chosen model class. In applications, residual norms are used to quantify fit quality, compare competing subspaces, and diagnose whether the modeling capacity captures the dominant components of the data.

7.1 Chebyshev and minimax comparisons (conceptual contrast)

Best approximation in normed spaces is often contrasted with minimax (uniform) approximation, where the objective is to minimize the maximum deviation rather than a least-squares-type distance. While both are approximation principles, they typically lead to different optimality conditions and computational approaches.

7.2 Approximation by spans of basis functions

A broad class of approximation schemes selects a finite-dimensional subspace generated by basis functions and computes the closest element to a target within that span. Whether the basis comes from polynomials, splines, wavelets, or learned features, the underlying mechanism is the same: projection (or its Banach-space analogue) onto a chosen span.

7.3 Duality and best approximation in Hilbert spaces

In Hilbert spaces, duality principles connect best approximation to functional analytic viewpoints. Orthogonality conditions can be reframed through linear functionals, and near-optimality estimates can be expressed using adjoint operators and energy norms. These relationships provide general tools for bounding errors and proving convergence in approximation schemes.

8 Theory of best approximation properties

8.1 Bessel’s inequality and near-best bounds

For orthonormal families \((u_i)\), Bessel’s inequality gives \[

\sum_i	\langle x,u_i\rangle	^2 \le \\|x\\|^2.

\] This inequality supports estimates of how much of \(x\) is captured by a chosen subspace generated by the \(u_i\), and it yields bounds on the residual norm. In practice, it helps quantify approximation quality when one uses a partial orthonormal expansion.

8.2 Convergence of projections onto nested subspaces

Consider a sequence of nested closed subspaces \(M_1\subseteq M_2\subseteq\cdots\) with union dense in the ambient Hilbert space. The corresponding projections \(P_{M_n}x\) converge to \(x\) in norm. This result links approximation quality to how well the subspaces capture the directions of \(x\).

In approximation theory, Jackson-type results provide quantitative rates describing how well a function can be approximated by elements from finite-dimensional subspaces in terms of smoothness measures. While the exact form depends on the setting (e.g., polynomial approximation, spline spaces, or other bases), the conceptual theme is that best-approximation errors decay at predictable speeds under regularity assumptions.

9 Common examples and worked scenarios

9.1 Best approximation by polynomials (overview)

Polynomial approximation frequently uses the idea of projecting a target function onto the subspace of polynomials of degree at most \(n\), typically in an \(L^2\) Hilbert space. The resulting best approximation minimizes an integral of squared error over the chosen domain with respect to a weight, and it connects directly to least-squares fitting.

9.2 Best approximation in finite-dimensional Euclidean spaces

In \(\mathbb{R}^n\) with the Euclidean norm, best approximation to a subspace is the geometric orthogonal projection. Given a subspace defined by linearly independent vectors, one can compute the projection using an orthonormal basis (or via QR factorization). The residual is orthogonal to the subspace, and the Pythagorean identity explains how squared distances split between captured and discarded components.

9.3 Best approximation in function spaces (Hilbert setting overview)

For function spaces such as \(L^2\) with inner product \(\langle f,g\rangle=\int f\overline{g}\), the best approximation from a subspace of functions is the \(L^2\)-orthogonal projection. This setting is central to signal processing, numerical methods, and spectral approximations, where one projects onto spans of basis functions to minimize mean-squared error.