MATH 323 Lecture 23

« previous | Tuesday, November 20, 2012 | next »

Least Squares Problem

given a 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 m \times n} matrix 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} with rank $n$, the least-squares solution to the equation 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 \vec{x} = \vec{b}} 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 A^T A \vec{x} = A^T \vec{b}}

and has the unique solution

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 \hat{x} = (A^T A)^{-1} A^T \vec{b}}

the vector ${\vec {p}}\in A{\vec {x}}$ in the range of $A$ is closest to ${\vec {b}}$.

Assume the columns of $A$ constitute an orthonormal basis in $R(A)$.

Theorem 5.5.6

If the column vectors of $A$ form an orthonormal set of vectors in $\mathbb {R} ^{m}$, then $A^{T}A=I$ and the solution to the least squares problem is

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

Proof

We need to show that $A^{T}A=I$.

If $A^{T}A=(c_{ij})$, then $c_{ij}={\vec {a}}_{i}\cdot {\vec {a}}_{j}=\delta _{ij}={\begin{cases}1&i=j\\0&{\text{otherwise}}\end{cases}}$

Therefore, the diagonal entries for $i=j$ will be 1, and all other matrix cells will be 0.

Q.E.D.

Theorem 5.5.7

Let $S$ be a subspace in $(V,\langle \cdot ,\cdot \rangle )$ and let $x\in V$.

Let $\dim {S}=n$ and $\{x_{1},\ldots ,x_{n}\}$ be an orthonormal basis for $S$.

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 = \sum_{i=1}^n c_i \, x_i} where 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 c_i = \langle x, x_i} for all 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 i} , 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-x \in S^\perp} .

Proof

Show that 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-x) \perp x_i} for any $i$:

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} \langle p-x, x_i \rangle &= \left\langle \sum_{j=1}^n c_j \, x_j, x_i \right\rangle - \langle x, x_i \rangle \\ &= \sum_{j=1}^n c_j \langle x_j, x_i \rangle - \langle x, x_i \rangle \\ &= \sum_{j=1}^n c_j \delta_{ij} - \langle x, x_i \rangle \\ &= c_i \langle x_i, x_i \rangle - c_i \\ &= c_i - c_i \\ &= 0 \end{align}}

Theorem 5.5.8

Under hypothesis of #Theorem 5.5.7, 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 element 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 S} that is closest 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 x} . That is, 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 \| y-x \| > \|p-x\|} for all 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 y \ne p} in 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 S} .

Corollary 5.5.9

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 S} be a nonzero subspace in 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}^m} 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 p \in \mathbb{R}^m} .

If \{\vec{u}_1, \ldots, \vec{u}_k \} is an orthonormal basis 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 S} 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 U = (\vec{u}_1, \ldots, \vec{u}_k)} , then the projection 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{p}} 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 \vec{b}} onto $S$ is given by \vec{p} = UU^T \vec{b}</math>

Proof

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{p} = \sum_{i=1}^k c_i \, \vec{u}_i = U\vec{c} = UU^T \vec{b}}

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{c} = \begin{pmatrix} \vec{u}_1^T \vec{b} \\ \vdots \\ \vec{u}_k^T \vec{b} \end{pmatrix} = U^T \vec{b}}

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 P = UU^T} be the projection matrix 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 S} .

Going back to the formula for the least squares solution, 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 \hat{x} = (A^T A)^{-1} A^T \vec{b}} , $P=(A^{T}A)^{-1}A^{T}$

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 unique 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 S} regardless of basis used. However, 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 = UU^T} can only be used for orthonormal bases; other calculations must use 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 = (A^T A)^{-1} A^T}

Example

Find best least squares approximation 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 e^x} on [0,1] by a linear function (subspace of C[0,1])

• Space: C[0,1]
• Inner product: 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 \langle f, g \rangle = \int_0^1 f(x) \, g(x) \,\mathrm{d}x}
• Subsace: 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 S = \mathrm{Span}\{1,x\}} (linear functions)

Find 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} such that 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 (x-a) \perp 1} :

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 \langle 1, x-a \rangle = \int_0^1 (x-a)\,\mathrm{d}x = \frac{1}{2} - a = 0}

Therefore 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 = \tfrac{1}{2}} , 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 \{ 1, x-\tfrac{1}{2} \}} forms an orthogonal basis 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 S} .

Find orthonormal basis 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 S} :

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\| x - \frac{1}{2} \right\| &= \sqrt{\int_0^1 \left( x - \frac{1}{2} \right)^2 \,\mathrm{d}x} = \frac{1}{\sqrt{12}} \\ \| 1 \| &= 1 \\ u_1 &= 1 \\ u_2 &= \frac{x-\frac{1}{2}}{\left\|x-\frac{1}{2}\right\|} = \sqrt{12}\left(x-\frac{1}{2}\right) \end{align}}

Therefore 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 \{1, \sqrt{12}(x-\tfrac{1}{2}) \}} forms an orthonormal basis 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 S}

Find least squares 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 \begin{align} p &= c_1\, u_1 + c_2 \, u_2 \\ c_1 &= \langle \mathrm{e}^x, u_1 \rangle = \int_0^1 \mathrm{e}^x \,\mathrm{d}x = \mathrm{e}-1 \\ c_2 &= \langle \mathrm{e}^x, u_2 \rangle = \int_0^1 \mathrm{e}^x \, \left(x-\frac{1}{2} \right) \,\mathrm{d}x = \sqrt{3}(3-e) \\ p &= (\mathrm{e}-1) \cdot 1 + (\sqrt{3}(\mathrm{e}-3)) \cdot (\sqrt{12}(x-\tfrac{1}{2})) \\ &= (4\mathrm{e}- 10) + (6(3-\mathrm{e})) \, x \end{align}}

Fourier 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 \begin{align} r_k &= \sqrt{a_k^2 + b_k^2} \\ \theta_k &= \arctan{\left( \frac{b_k}{a_k}\right)} \\ a_k \cos{kx} + b_k \sin{kx} &= r_k \cos{kx-\theta_k} \end{align}}

The last formula is the equation for harmonic motion.

Gram-Schmidt Process

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 V, \langle \cdot, \cdot \rangle} , 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 \{ x_1, \ldots, x_n \}} basis in 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 V} ,

How do we obtain 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 \{u_1, \ldots, u_n \}} , an orthonormal basis 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 S} so that 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{Span}\{ x_1, \ldots, x_n \} = \mathrm{Span}\{ u_1, \ldots, u_n \}} ?

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} u_1 &= \frac{x_1}{\|x_1\|} \\ \mathrm{Span}\{x_1\} &= \mathrm{Span}\{u_1\} = V_1 \\ p_1 &= \mathrm{proj}_{V_1}(x_2) = \langle x_2, u_1 \rangle \cdot u_1 \\ &x_2 - p_1 \perp V_1 \\ u_2 &= \frac{x_2 - p_1}{\|x_2-p_1\|} \\ \mathrm{Span}\{x_1,x_2\} &= \mathrm{Span}\{u_1,u_2\} = V_2 \\ p_2 &= \mathrm{proj}_{V_1}(x_3) = \langle x_3, u_2 \rangle \cdot u_2 \\ &x_3 - p_2 \perp V_2 \\ &\ldots \end{align}}

Theorem 5.6.1

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 \{ x_1, \ldots, x_n \}} be a basis 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 V, \langle \cdot, \cdot \rangle} . 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 u_1 = \tfrac{x_1}{\|x_1\|}} and define 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 u_2, \ldots, u_n} recursively 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 u_{k+1} = \frac{x_{k+1} - p_k}{\|x_{k+1} - p_k \|}}

Where 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_k = \langle x_{k+1}, u_1 \rangle u_1 + \langle x_{k+1}, u_2 \rangle u_2 + \dots + \langle x_{k+1}, u_k \rangle u_k} 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 x_{k+1}} onto 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 v_k = \mathrm{Span}(u_1,\ldots,u_k) = \mathrm{Span}(x_1,\ldots,x_k)} .

The set 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 \{u_1,\ldots,u_n\}} is an orthonormal basis 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 V} .