Least-squares approximations

$\newenvironment {prompt}{}{} \newcommand {\ungraded }[0]{} \newcommand {\definedTerm }[1]{\textbf {#1}} \newcommand {\dfn }[1]{\textbf {#1}} \newcommand {\wt }[0]{\widetilde } \newcommand {\ov }[0]{\overline } \newcommand {\inj }[0]{\rightarrowtail } \newcommand {\surj }[0]{\twoheadrightarrow } \newcommand {\harpoon }[0]{\overset {\rightharpoonup }} \newcommand {\orderof }[1]{\sim #1} \newcommand {\Z }[0]{\mathbb {Z}} \newcommand {\reals }[0]{\mathbb {R}} \newcommand {\real }[1]{\mathbb {R}^{#1}} \newcommand {\complexes }[0]{\mathbb {C}} \newcommand {\complex }[1]{\mathbb {C}^{#1}} \newcommand {\CC }[0]{\mathbb {C}} \newcommand {\conjugate }[1]{\overline {#1}} \newcommand {\modulus }[1]{\left \lvert #1\right \rvert } \newcommand {\zerovector }[0]{\vect {0}} \newcommand {\zeromatrix }[0]{\mathcal {O}} \newcommand {\innerproduct }[2]{\left \langle #1,\,#2\right \rangle } \newcommand {\norm }[1]{\left \lVert #1\right \rVert } \newcommand {\dimension }[1]{\dim \left (#1\right )} \newcommand {\nullity }[1]{n\left (#1\right )} \newcommand {\rank }[1]{r\left (#1\right )} \newcommand {\ds }[0]{\oplus } \newcommand {\detname }[1]{\det \left (#1\right )} \newcommand {\detbars }[1]{\left \lvert #1\right \rvert } \newcommand {\trace }[1]{t\left (#1\right )} \newcommand {\sr }[1]{#1^{1/2}} \newcommand {\spn }[1]{\left \langle #1\right \rangle } \newcommand {\nsp }[1]{\mathcal {N}\!\left (#1\right )} \newcommand {\csp }[1]{\mathcal {C}\!\left (#1\right )} \newcommand {\rsp }[1]{\mathcal {R}\!\left (#1\right )} \newcommand {\lns }[1]{\mathcal {L}\!\left (#1\right )} \newcommand {\per }[1]{#1^\perp } \newcommand {\augmented }[2]{\left \lbrack \left .#1\,\right \rvert \,#2\right \rbrack } \newcommand {\linearsystem }[2]{\mathcal {LS}\!\left (#1,\,#2\right )} \newcommand {\homosystem }[1]{\linearsystem {#1}{\zerovector }} \newcommand {\rowopswap }[2]{R_{#1}\leftrightarrow R_{#2}} \newcommand {\rowopmult }[2]{#1R_{#2}} \newcommand {\rowopadd }[3]{#1R_{#2}+R_{#3}} \newcommand {\leading }[1]{\fbox {#1}} \newcommand {\rref }[0]{\xrightarrow {\text {RREF}}} \newcommand {\elemswap }[2]{E_{#1,#2}} \newcommand {\elemmult }[2]{E_{#2}\left (#1\right )} \newcommand {\elemadd }[3]{E_{#2,#3}\left (#1\right )} \newcommand {\scalarlist }[2]{{#1}_{1},\,{#1}_{2},\,{#1}_{3},\,\ldots ,\,{#1}_{#2}} \newcommand {\vect }[1]{\mathbf {#1}} \newcommand {\colvector }[1]{\begin {bmatrix}#1\end {bmatrix}} \newcommand {\vectorcomponents }[2]{\colvector {#1_{1}\\#1_{2}\\#1_{3}\\\vdots \\#1_{#2}}} \newcommand {\vectorlist }[2]{\vect {#1}_{1},\,\vect {#1}_{2},\,\vect {#1}_{3},\,\ldots ,\,\vect {#1}_{#2}} \newcommand {\vectorentry }[2]{\left \lbrack #1\right \rbrack _{#2}} \newcommand {\matrixentry }[2]{\left \lbrack #1\right \rbrack _{#2}} \newcommand {\lincombo }[3]{#1_{1}\vect {#2}_{1}+#1_{2}\vect {#2}_{2}+#1_{3}\vect {#2}_{3}+\cdots +#1_{#3}\vect {#2}_{#3}} \newcommand {\matrixcolumns }[2]{\left \lbrack \vect {#1}_{1}|\vect {#1}_{2}|\vect {#1}_{3}|\ldots |\vect {#1}_{#2}\right \rbrack } \newcommand {\transpose }[1]{#1^{t}} \newcommand {\inverse }[1]{#1^{-1}} \newcommand {\submatrix }[3]{#1\left (#2|#3\right )} \newcommand {\adj }[1]{\transpose {\left (\conjugate {#1}\right )}} \newcommand {\adjoint }[1]{#1^\ast } \newcommand {\set }[1]{\left \{#1\right \}} \newcommand {\setparts }[2]{\left \lbrace #1\,\middle |\,#2\right \rbrace } \newcommand {\card }[1]{\left \lvert #1\right \rvert } \newcommand {\setcomplement }[1]{\overline {#1}} \newcommand {\charpoly }[2]{p_{#1}\left (#2\right )} \newcommand {\eigenspace }[2]{\mathcal {E}_{#1}\left (#2\right )} \newcommand {\eigensystem }[3]{\lambda &amp;=#2&amp;\eigenspace {#1}{#2}&amp;=\spn {\set {#3}}} \newcommand {\geneigenspace }[2]{\mathcal {G}_{#1}\left (#2\right )} \newcommand {\algmult }[2]{\alpha _{#1}\left (#2\right )} \newcommand {\geomult }[2]{\gamma _{#1}\left (#2\right )} \newcommand {\indx }[2]{\iota _{#1}\left (#2\right )} \newcommand {\ltdefn }[3]{#1\colon #2\rightarrow #3} \newcommand {\lteval }[2]{#1\left (#2\right )} \newcommand {\ltinverse }[1]{#1^{-1}} \newcommand {\restrict }[2]{{#1}|_{#2}} \newcommand {\preimage }[2]{#1^{-1}\left (#2\right )} \newcommand {\rng }[1]{\mathcal {R}\!\left (#1\right )} \newcommand {\krn }[1]{\mathcal {K}\!\left (#1\right )} \newcommand {\compose }[2]{{#1}\circ {#2}} \newcommand {\vslt }[2]{\mathcal {LT}\left (#1,\,#2\right )} \newcommand {\isomorphic }[0]{\cong } \newcommand {\similar }[2]{\inverse {#2}#1#2} \newcommand {\vectrepname }[1]{\rho _{#1}} \newcommand {\vectrep }[2]{\lteval {\vectrepname {#1}}{#2}} \newcommand {\vectrepinvname }[1]{\ltinverse {\vectrepname {#1}}} \newcommand {\vectrepinv }[2]{\lteval {\ltinverse {\vectrepname {#1}}}{#2}} \newcommand {\matrixrep }[3]{M^{#1}_{#2,#3}} \newcommand {\matrixrepcolumns }[4]{\left \lbrack \left .\vectrep {#2}{\lteval {#1}{\vect {#3}_{1}}}\right |\left .\vectrep {#2}{\lteval {#1}{\vect {#3}_{2}}}\right |\left .\vectrep {#2}{\lteval {#1}{\vect {#3}_{3}}}\right |\ldots \left |\vectrep {#2}{\lteval {#1}{\vect {#3}_{#4}}}\right .\right \rbrack } \newcommand {\cbm }[2]{C_{#1,#2}} \newcommand {\jordan }[2]{J_{#1}\left (#2\right )} \newcommand {\hadamard }[2]{#1\circ #2} \newcommand {\hadamardidentity }[1]{J_{#1}} \newcommand {\hadamardinverse }[1]{\widehat {#1}} \newcommand {\id }[0]{\mathrm {id}} \newcommand {\C }[0]{\mathbb {C}} \newcommand {\R }[0]{\mathbb {R}} \newcommand {\Q }[0]{\mathbb {Q}} \newcommand {\N }[0]{\mathbb {N}} \newcommand {\F }[0]{\mathbb {F}} \newcommand {\bbH }[0]{\mathbb {H}} \newcommand {\SO }[0]{\operatorname {SO}} \newcommand {\Dten }[0]{D_{10}} \newcommand {\calC }[0]{\mathcal {C}} \newcommand {\calD }[0]{\mathcal {D}} \newcommand {\calF }[0]{\mathcal {F}} \newcommand {\calO }[0]{\mathcal {O}} \newcommand {\calP }[0]{\mathcal {P}} \newcommand {\calN }[0]{\mathcal {N}} \newcommand {\calR }[0]{\mathcal {R}} \newcommand {\calS }[0]{\mathcal {S}} \newcommand {\calX }[0]{\mathcal {X}} \newcommand {\rmZ }[0]{\mathrm {Z}} \newcommand {\rmC }[0]{\mathrm {C}} \newcommand {\rmH }[0]{\mathrm {H}} \newcommand {\trans }[0]{\mathrm {T}} \newcommand {\Span }[0]{\operatorname {Span}} \newcommand {\Rep }[0]{\operatorname {Rep}} \newcommand {\Vect }[0]{\operatorname {Vec}} \newcommand {\Obj }[0]{\operatorname {Obj}} \newcommand {\Adj }[0]{\operatorname {Adj}} \newcommand {\Aut }[0]{\operatorname {Aut}} \newcommand {\Hom }[0]{\operatorname {Hom}} \newcommand {\End }[0]{\operatorname {End}} \newcommand {\tr }[0]{\operatorname {tr}} \newcommand {\Stab }[0]{\operatorname {Stab}} \newcommand {\FPdim }[0]{\operatorname {FPdim}} \newcommand {\lcm }[0]{\mathrm {l.c.m}} \newcommand {\proj }[0]{\operatorname {proj}} \newcommand {\Repart }[0]{\operatorname {Re}} \newcommand {\Impart }[0]{\operatorname {Im}} \newcommand {\im }[0]{\operatorname {im}} \newcommand {\rk }[0]{\operatorname {rank}} \newcommand {\diag }[0]{\operatorname {diag}} \newcommand {\Zmod }[1]{\Z /#1 \Z } \newcommand {\Reptwo }[0]{\Rep (\Z /2\Z )} \newcommand {\qaH }[0]{\mathrm {H}_{\mathrm {qa}}} \newcommand {\abH }[0]{\mathrm {H}_{\mathrm {ab}}} \newcommand {\qaZ }[0]{\mathrm {Z}_{\mathrm {qa}}} \newcommand {\qaB }[0]{\mathrm {B}_{\mathrm {qa}}} \newcommand {\1}[0]{\mathbf {1}} \newcommand {\Ctimes }[0]{\mathbb {C}^{\times }} \newcommand {\HyperFirstAtBeginDocument }[0]{\AtBeginDocument }$

The setup is as before: we are given a subspace $W\subset \mathbb R^n$ and a vector ${\bf v}\in \mathbb R^n$ . The questions are then:

Is there a vector ${\bf w}_{\bf v}\in W$ satisfying the property that $\|{\bf w}_{\bf v} - {\bf v}\|\le \|{\bf w} - {\bf v}\|$ for all ${\bf w}\in W$ ?
If such a vector exists, is it unique?

As one might imagine from the previous section, the answer is “yes.” More precisely, the vector in $W$ we are looking for is exactly the projection of $\bf v$ onto $W$ :

${\bf w}_{\bf v} = pr_W({\bf v})$ .

Proof: Write ${\bf v} - pr_W({\bf v})$ as ${\bf w}_m$ . Let ${\bf w}\in W$ be an arbitrary vector, and let ${\bf w}_p := pr_W({\bf v}) - {\bf w}$ . Then ${\bf w}_m\cdot {\bf w}_p = 0$ , so one has $\|{\bf v} - {\bf w}\|^2 = \|{\bf w}_m + {\bf w}_p\|^2 = ({\bf w}_m + {\bf w}_p)\cdot ({\bf w}_m + {\bf w}_p) = {\bf w}_m\cdot {\bf w}_m + {\bf w}_p\cdot {\bf w}_p = \|{\bf w}_m\|^2 + \|{\bf w}_p\|^2\ge \|{\bf w}_m\|^2$ This shows that the projection satisfies (LS1). However we have already shown that the projection of $\bf v$ onto $W$ is unique, so (LS2) follows as well. $\blacksquare$

The vector ${\bf v}_m = pr_W({\bf v})$ is referred to as the least-squares approximation of $\bf v$ by a vector in $W$ , because $pr_W({\bf v})$ satisfies the property that $\|{\bf v}-pr_W({\bf v})\|^2$ , which is computed as a sum of squares of differences in coordinates, is minimized. This turns out to have an important application to finding the best approximation to a system of equations in the event no actual solution exists. We discuss this next.