PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (230)
Orphanage
Unclass'd
Unproven (519)
Corrections (17)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: No information on entry rating
[parent] best approximation in inner product spaces (Feature)

The study of best approximations in inner product spaces has a very elegant treatment with profound consequences. Most of the theory of Hilbert spaces depends on this study and several approximation problems are better understood using this techniques and results.

For example: least square fitting, linear regression, approximation of functions by polynomials, among many other problems, can be seen as particular cases of the general study of best approximation in inner product spaces.

Some of the above problems are going to be discussed later in this entry.

Existence and Uniqueness

Our fundamental result on the existence and uniqueness of best approximations is the following (we postpone its proof to this attached entry):

Theorem - Let $ X$ be an inner product space and $ A \subseteq X$ a complete, convex and non-empty subset. Then for every $ x \in X$ there exists a unique best approximation of $ x$ in $ A$, i.e. there exists a unique element $ a_0 \in A$ such that

$\displaystyle \Vert x-a_0\Vert = d(x,A) = \inf_{a \in A} \Vert x - a\Vert. $

Geometric Interpretation

The following result gives a very geometric interpretation of the best approximation when $ A$ is a subspace of $ X$. We also postpone its proof to an attached entry.

Theorem - Let $ X$ be an inner product space, $ A \subseteq X$ a subspace and $ x \in X$. The following statements are equivalent:

  • $ a_0 \in A$ is the best approximation of $ x$ in $ A$.
  • $ a_0 \in A$ and $ x-a_0 \perp A$.

Thus, the best approximation of $ x$ in a subspace $ A$ is just the orthogonal projection of $ x$ in $ A$.

Calculation of Best Approximations

When the $ A$ is a complete subspace of $ X$, the best approximation can be "calculated" explicitly. Recall that, in this case, $ A$ becomes an Hilbert space (since it is complete) and therefore it has an orthonormal basis.

Again, we postpone the proof of the next result to an attached entry.

Theorem - Let $ X$ be an inner product space and $ A \subseteq X$ a complete subspace. Let $ (e_i)_{i \in J}$ be an orthonormal basis for $ A$. Then for every $ x \in X$ the best approximation $ a_0 \in A$ of $ x$ in $ A$ is given by

$\displaystyle a_0= \sum_{i \in J} \langle x, e_i \rangle e_i \;. $

One can also write the best approximation in terms of any other basis (not necessarily an orthonormal one). For simplicity we present here how that can be done when $ A$ is a finite dimensional subspace of $ X$.

Theorem - Let $ X$ be an inner product space and $ A \subseteq X$ a finite dimensional subspace. Let $ v_1, \dots, v_n$ be a basis for $ A$. Then for every $ x \in X$ the best approximation $ a_0 \in A$ of $ x$ in $ A$ is given by

$\displaystyle a_0 = \sum_{i=1}^{n} a_0^i v_i $
where the coefficients $ a_0^i$ are the solutions of the system of equations
$\displaystyle \begin{pmatrix} \langle v_1, v_1 \rangle & \cdots & \langle v_1, ... ...\langle x, v_1 \rangle\ \vdots \ \langle x, v_n \rangle \end{pmatrix} \; . $

$ Remark - $ The above matrix is a symmetric positive definite matrix, which implies that the system has a unique solution as expected.

Applications

There are several applications of the above results. We explore two of them in the following.

- Approximation of functions by polynomials :

Suppose we want to find a polynomial of degree $ \leq n$ that approximates in the best possible way a given function $ f$. We are in fact trying to find a point in the subspace of polynomials of degree $ \leq n$ that is closest to $ f$, i.e. we are trying to find the best approximation of $ f$ in that subspace.

For example, let $ f \in L^2([0,1])$. Consider the basis $ v_k(t)= t^k ,\quad 0\leq k \leq n, \;$ of the subspace of polynomials of degree $ \leq n$.

The best approximation of $ f$ by these polynomials is the function $ a_0(t) = a_0^1 +a_0^1 t + \dots + a_0^n t^n$, where the coefficients $ a_0^1, \dots, a_0^n$ are the solutions of the system

$\displaystyle \begin{pmatrix} 1 & \cdots & \frac{1}{n+1} \ \vdots & \ddots & ... ...pmatrix} \int_0^1 f(t)dt\ \vdots \ \int_0^1 t^n f(t) dt \end{pmatrix} \; . $

$ Remark -$ Instead of polynomials we could approximate $ f$ by any other type of functions using the same procedure.

- Best Fitting Lines :

Suppose we want to find the line that best fits some given points $ (t_1, y_1), \dots, (t_n, y_n)$, i.e. the affine function $ a_0(t) = \alpha t + \beta$ that minimizes $ \displaystyle \sum_{k = 1}^n \vert a_0(t_k) - y_k\vert^2$.

We are then led to consider the inner product

$\displaystyle \langle f, g \rangle = \sum_{k=1}^n f(t_k)g(t_k) $
in the space of functions $ h:\{t_1, \dots, t_k\} \longrightarrow \mathbb{R}$.

With this setting we are then looking for the best approximation of the function $ f(t_k)=y_k$ on the subspace of affine functions.

A base for the subspace of affine functions is given by the functions $ v_1(t) = 1$ and $ v_2(t) = t$.

The best approximation of $ f$ on this space is the function $ a_0(t) = \beta + \alpha t$, where the coefficients $ \beta, \alpha$ are the solutions of the system

$\displaystyle \begin{pmatrix} n & \sum_{k=1}^n t_k \ \sum_{k=1}^n t_k & \sum_... ... = \begin{pmatrix} \sum_{k=1}^n y_k\ \sum_{k=1}^n y_k t_k \end{pmatrix} \; . $

Thus, the function $ a_0(t) = \beta + \alpha t$ obtained by the above procedure provides the line that best fits the data $ (t_1, y_1), \dots, (t_n, y_n)$.



Anyone with an account can edit this entry. Please help improve it!

"best approximation in inner product spaces" is owned by asteroid.
(view preamble)

View style:

Also defines:  approximation by polynomials, best fitting lines

This object's parent.

Attachments:
proof of existence and uniqueness of best approximations (Proof) by asteroid
Log in to rate this entry.
(view current ratings)

Cross-references: space of functions, inner product, line, point, degree, applications, implies, symmetric, matrix, equations, solutions, coefficients, finite dimensional, orthonormal, basis, orthonormal basis, orthogonal projection, equivalent, subspace, interpretation, subset, convex, proof, polynomials, functions, least square, approximation, Hilbert spaces, theory, consequences, inner product spaces, best approximations
There are 3 references to this entry.

This is version 9 of best approximation in inner product spaces, born on 2007-09-13, modified 2007-09-15.
Object id is 9935, canonical name is BestApproximationInInnerProductSpaces.
Accessed 1755 times total.

Classification:
AMS MSC: 41A50 (Approximations and expansions :: Best approximation, Chebyshev systems)
 41A52 (Approximations and expansions :: Uniqueness of best approximation)
 41A65 (Approximations and expansions :: Abstract approximation theory )
 46C05 (Functional analysis :: Inner product spaces and their generalizations, Hilbert spaces :: Hilbert and pre-Hilbert spaces: geometry and topology )
 46N10 (Functional analysis :: Miscellaneous applications of functional analysis :: Applications in optimization, convex analysis, mathematical programming, economics)
 49J27 (Calculus of variations and optimal control; optimization :: Existence theories :: Problems in abstract spaces)
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)