MATH 417 Lecture 24

« previous | Thursday, April 17, 2014 | next »

Suppose we want to find a linear approximation Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) = a_0 + a_1 \, x} for the points Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left( 1,1 \right), \left( 2,2 \right), \left( 3, \frac{3}{2} \right), \left( 4, \frac{3}{2} \right)} :

Hence the coefficients to our control points Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_0} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_1} are

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A = \begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \\ 1 & 4 \end{bmatrix}}

and our values are

${\vec {b}}={\begin{bmatrix}1\\2\\{\frac {3}{2}}\\{\frac {3}{2}}\end{bmatrix}}$

We compute Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A^T \, A = \begin{bmatrix} 4 & 10 \\ 10 & 30 \end{bmatrix}} and solve the following for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{x} = \begin{bmatrix} a_0 \\ a_1 \end{bmatrix}} :

$A^{T}\,A\,{\vec {x}}=A^{T}\,{\vec {b}}$

${\vec {x}}={\begin{bmatrix}{\frac {5}{4}}\\{\frac {1}{10}}\end{bmatrix}}$

Hence our equation is: $f(x)={\frac {5}{4}}+{\frac {1}{10}}\,x$

General Case

for $f\in \mathbb {R} ^{n}$, $\Pi$ is a subspace spanned by $\phi _{1},\phi _{2},\ldots ,\phi _{n}$, where $\phi$'s are linearly independent.

We wish to approximate $f\in \mathbb {R} ^{n}$ by $p\in \Pi$. We do so by minimizing the value of Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \left\|f-p\right\|_{2}^{2}} for all $p\in \Pi$. This is called the best least squares fit

$p$ is just the projection of $f$ onto $\Pi$.

Normal equations are:

$A^{T}\,A={\begin{bmatrix}\left\langle \phi _{1},\phi _{1}\right\rangle &\left\langle \phi _{1},\phi _{2}\right\rangle &\dots &\left\langle \phi _{1},\phi _{n}\right\rangle \\\left\langle \phi _{2},\phi _{1}\right\rangle &\left\langle \phi _{2},\phi _{2}\right\rangle &\dots &\left\langle \phi _{2},\phi _{n}\right\rangle \\\vdots &\vdots &\ddots &\vdots \\\left\langle \phi _{n},\phi _{1}\right\rangle &\left\langle \phi _{n},\phi _{2}\right\rangle &\dots &\left\langle \phi _{n},\phi _{n}\right\rangle \end{bmatrix}}$

Residual (or rejection) belongs to the subspace perpendicular to $\Pi$, or Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Pi^\perp} .

Theorem. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\langle f-p,q \right\rangle = 0} for all $q\in \Pi$, then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} is the minimizer for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\| f - p \right\|_2^2} .

Proof. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} is the projection of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} onto a subspace, then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f-p} is the shortest vector from $\Pi$ to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} . The shortest vector from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Pi} to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} is orthogonal to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Pi} (otherwise Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\| f-p \right\|} would not be minimized). Hence $p-q$ is orthogonal to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f-p} .

Take Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q \ne p} and compute

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \left\| f-q \right\|^2 &= \left\langle f-q, f-q \right\rangle = \left\langle f-p + p-q, f-p + p-q \right\rangle \\ &= \left\| f-p \right\|^2 + \left\langle f-p, p-q \right\rangle + \left\langle p-q, f-p \right\rangle + \left\| p-q \right\|^2 \\ &= \left\| f-p \right\|^2 + \left\| p-q \right\|^2 + \underbrace{2 \left\langle f-p, p-q \right\rangle}_0 \\ &= \left\| f-p \right\|^2 + \left\| p-q \right\|^2 \end{align}}

Theus Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p = q} minimizes the value of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\| p-q \right\|^2} , and thus Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\| f - q \right\|^2 = \left\| f - p \right\|^2}

quod erat demonstrandum

Special Case

Let $\Pi$ be spanned by an orthonormal basis Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \psi_1, \ldots, \psi_k} , and let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Pi^\perp} be spanned by an orthonormal basis Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \psi_{k+1}, \ldots, \psi_n} . Thus Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{R}^n = \Pi \oplus \Pi^\perp} .

Now $f\in \mathbb {R} ^{n}$ is given by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f = \sum_{i=1}^n \left\langle f,\psi_i \right\rangle \, \psi_i} .

To find the projection, we just take the components that are members of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Pi} :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{proj}_\Pi(f) = \sum_{i=1}^k \left\langle f, \psi_i \right\rangle \, \psi_i}