Least squares (1 Viewer)

InteGrand · May 4, 2016

leehuan said:
$\\$Prove that $|A\textbf{x}-\textbf{y}|$ is least when $\textbf{y}-A\textbf{x}$ is orthogonal to $\sigma=$span(columns of $A).$

$\noindent I'm assuming $\vec{y}$ is a fixed vector in $\mathbb{R}^{n}$ and that $A$ is a real matrix. (The given result can also be generalised to a complex setting, or any inner product space.) Let $\vec{x}_0$ be a vector in $\sigma$ such that $\vec{y}-A\vec{x}_{0}$ is orthogonal to $\sigma$. Let $\vec{x}$ be any vector in $\sigma$. Then from what is essentially Pythagoras' theorem for vector spaces (proved in next post), we have$

$\begin{align*}\left \|A\vec{x}-\vec{y} \right \|^{2} &= \left \|A\vec{x}_{0}-\vec{y} \right \|^{2} + \left \|A\left(\vec{x}-\vec{x}_{0}\right) \right \|^{2} \quad (\text{Pythagoras' theorem}) \\ &\geq \left \|A\vec{x}_{0}-\vec{y} \right \|^{2}, \end{align*}$

$\noindent with equality iff $\left \|A\left(\vec{x}-\vec{x}_{0}\right) \right \|^{2}=0$, iff $A\left(\vec{x}-\vec{x}_{0}\right) =\vec{0}$, iff $A\vec{x}=A\vec{x}_{0}$, iff $\vec{y}-A\vec{x}=\vec{y}-A\vec{x}_{0}$, i.e. iff $\vec{x}$ is a vector in $\sigma$ such that $\vec{y}-A\vec{x}$ is orthogonal to $\sigma$, proving the claim.$

(We made use of the fact that to minimise a norm of a vector, we can just minimise its square.)

Squar3root · May 4, 2016

hi i am square

InteGrand · May 4, 2016

$\noindent This is essentially Pythagoras' theorem for $\mathbb{R}^{n}$. The result also holds in general inner product spaces with a given inner product. I'll just give the proof for $\mathbb{R}^{n}$ here though as I'm not sure if you've learnt inner products. I'll provide a link to a proof with general inner products for completeness.$

$\noindent \textit{Pythagoras' Theorem in $\mathbb{R}^{n}$.} Let $\vec{a},\vec{b}$ be orthogonal vectors in $\mathbb{R}^{n}$. Then $\left \|\vec{a}+\vec{b} \right \|^{2} = \left \|\vec{a}\right \|^{2} +\left \|\vec{b}\right \|^{2} $.$

$\noindent \textit{Proof.} Since $\vec{a}$ and $\vec{b}$ are orthogonal, we have $\vec{a}\cdot \vec{b} = 0=\vec{b}\cdot \vec{a}$. Then$

$\begin{align*}\left \| \vec{a}+\vec{b} \right \|^{2} &= \left( \vec{a}+\vec{b} \right) \cdot \left( \vec{a}+\vec{b} \right) \\ &= \vec{a}\cdot \vec{a} + \vec{a}\cdot \vec{b} +\vec{b}\cdot \vec{a} + \vec{b}\cdot \vec{b} \\ &= \left \|\vec{a}\right \|^{2} +\left \|\vec{b}\right \|^{2} \quad (\text{as }\vec{a}\cdot \vec{b} = 0=\vec{b}\cdot \vec{a}). \quad \blacksquare\end{align*}$

$\noindent In my above post, the $\vec{a}$ was $A\vec{x}_0-\vec{y}$ and the $\vec{b}$ was $A\left(\vec{x}-\vec{x}_{0}\right) = A\vec{x} -A\vec{x}_{0}$, with $\vec{a}+\vec{b} = A\vec{x}-\vec{y}$. Note that $\vec{a}$ and $\vec{b}$ are indeed orthogonal in the above post. This is because $\vec{a}=A\vec{x}-\vec{y}$ is orthogonal to $\sigma$, so by definition it is orthogonal to every vector in $\sigma$, and $\vec{b}=A\left(\vec{x}-\vec{x}_0\right) $ is such a vector (because the column space (span of columns) of $A$ is precisely the set of all $A\vec{v}$ for $\vec{v}\in \mathbb{R}^{n}$).$

The general inner product space proof is very similar: http://planetmath.org/pythagoreantheoremininnerproductspaces .

leehuan · May 4, 2016

Thanks, but I have to admit, I get almost nothing about least squares at all. I need a walkthrough for just this elementary question...

$Given the points $\left(t_i,y_i\right), i=1,\dots,\5; \\ (-1,-14),(0,-5),(1,-4),(2,1),(3,22).\\$a) Find the straight line $y=\alpha+\beta t$ of best fit to this data.$

(Completely minimal) Progress so far:

$$We require a best fit solution to $\\ \begin{align*}\alpha - \beta &= -14 \\ \alpha \quad &= -5 \\ \alpha + \beta &= -4 \\ \alpha + 2 \beta &= 1 \\ \alpha + 3\beta &= 22\end{align*}$

$$i.e. $A\textbf{x}=\textbf{y}$ where $\textbf{x}=(\alpha,\beta)^T, \textbf{y}=(-14,-5,-4,1,22)^T, \\ A=\left(\begin{matrix}1 & -1 \\ 1 & 0 \\ 1 & 1 \\ 1 & 2 \\ 1 & 3\end{matrix}\right)$

$So we want to find a vector $\textbf{x}=\textbf{x}_0$ such that $\\ \left| A\textbf{x}-\textbf{y}\right|$ is minimised.$

And then I immediately fall clueless. I still don't even know what "normal equations" are or what they mean, and I don't fully understand how A^TAx=A^Tb works either. Basically I have no clue at all when and how to use what

InteGrand · May 4, 2016

leehuan said:
Thanks, but I have to admit, I get almost nothing about least squares at all. I need a walkthrough for just this elementary question...

$Given the points $\left(t_i,y_i\right), i=1,\dots,\5; \\ (-1,-14),(0,-5),(1,-4),(2,1),(3,22).\\$a) Find the straight line $y=\alpha+\beta t$ of best fit to this data.$

(Completely minimal) Progress so far:

$$We require a best fit solution to $\\ \begin{align*}\alpha - \beta &= -14 \\ \alpha \quad &= -5 \\ \alpha + \beta &= -4 \\ \alpha + 2 \beta &= 1 \\ \alpha + 3\beta &= 22\end{align*}$

$$i.e. $A\textbf{x}=\textbf{y}$ where $\textbf{x}=(\alpha,\beta)^T, \textbf{y}=(-14,-5,-4,1,22)^T, \\ A=\left(\begin{matrix}1 & -1 \\ 1 & 0 \\ 1 & 1 \\ 1 & 2 \\ 1 & 3\end{matrix}\right)$

$So we want to find a vector $\textbf{x}=\textbf{x}_0$ such that $\\ \left| A\textbf{x}-\textbf{y}\right|$ is minimised.$

And then I immediately fall clueless. I still don't even know what "normal equations" are or what they mean, and I don't fully understand how A^TAx=A^Tb works either. Basically I have no clue at all when and how to use what

$\noindent The vector $\bold{x} = \left(\alpha,\beta\right)$ will be the vector $\bold{x}$ satisfying the \emph{normal equations} $A^T A \bold{x} = A^T \bold{y}$. So calculate $A^T A$ and $ A^T \bold{y}$, and then this just turns into solving a regular matrix equation of the form $M\bold{x} =\bold{b}$, which I assume you are very familiar with.$

$\noindent Note that $A^T A$ is always square (and in fact always symmetric). It can be proved that if $A$ has linearly independent columns, then $A^T A$ is invertible and the normal equations will have one and only one solution (the least squares solution). The result about the normal equations' solution being the least squares solution is very well-known and you can probably find lots of proofs of it online.$

InteGrand · May 4, 2016

leehuan said:
Thanks, but I have to admit, I get almost nothing about least squares at all. I need a walkthrough for just this elementary question...

$Given the points $\left(t_i,y_i\right), i=1,\dots,\5; \\ (-1,-14),(0,-5),(1,-4),(2,1),(3,22).\\$a) Find the straight line $y=\alpha+\beta t$ of best fit to this data.$

(Completely minimal) Progress so far:

$$We require a best fit solution to $\\ \begin{align*}\alpha - \beta &= -14 \\ \alpha \quad &= -5 \\ \alpha + \beta &= -4 \\ \alpha + 2 \beta &= 1 \\ \alpha + 3\beta &= 22\end{align*}$

$$i.e. $A\textbf{x}=\textbf{y}$ where $\textbf{x}=(\alpha,\beta)^T, \textbf{y}=(-14,-5,-4,1,22)^T, \\ A=\left(\begin{matrix}1 & -1 \\ 1 & 0 \\ 1 & 1 \\ 1 & 2 \\ 1 & 3\end{matrix}\right)$

$So we want to find a vector $\textbf{x}=\textbf{x}_0$ such that $\\ \left| A\textbf{x}-\textbf{y}\right|$ is minimised.$

And then I immediately fall clueless. I still don't even know what "normal equations" are or what they mean, and I don't fully understand how A^TAx=A^Tb works either. Basically I have no clue at all when and how to use what

$\noindent So calculating $A^TA$ (note that it will be a symmetric 2 by 2 matrix), we have $A^T A = \begin{pmatrix}5 & 5 \\ 5 & 15\end{pmatrix}$ (this calculation is sped up by realising that $A^T A$ is symmetric, so we don't need to calculate each entry separately, and also that the $ij$ entry of $A^T A$ is row $i$ of $A^T$ dotted with column $j$ of $A$, i.e. column $i$ of A dotted with column $j$ of $A$).$

$\noindent Also, $A^T \bold{y} = \begin{pmatrix}0 \\ 78 \end{pmatrix}$. So the least squares solution is the solution to $\begin{pmatrix}5 & 5 \\ 5 & 15\end{pmatrix} \bold{x} = \begin{pmatrix}0 \\ 78 \end{pmatrix}$ (which is $A^T A \bold{x} = A^{T} \bold{y}$). Now we just need to solve this, which is routine.$

InteGrand · May 4, 2016

leehuan · Oct 8, 2016

I was briefly flipping through content involving general maths and I found that they seem to have a formula for least squares.

https://www.boardofstudies.nsw.edu.au/syllabus_hsc/pdf_doc/maths-general-2-formulae-14.pdf

Is there any relationship between the use of these normal equations and what's on the formula sheet?

InteGrand · Oct 8, 2016

leehuan said:
I was briefly flipping through content involving general maths and I found that they seem to have a formula for least squares.

https://www.boardofstudies.nsw.edu.au/syllabus_hsc/pdf_doc/maths-general-2-formulae-14.pdf

Is there any relationship between the use of these normal equations and what's on the formula sheet?

Yes

InteGrand · Oct 8, 2016

(Those relationships hold true for the solutions to the normal equations for fitting to a line of the form y = mx + b.)

Paradoxica · Oct 9, 2016

Squar3root said:
hi i am square

but are you the least?

Least squares (1 Viewer)

leehuan

Well-Known Member

InteGrand

Well-Known Member

Squar3root

realest nigga

InteGrand

Well-Known Member

leehuan

Well-Known Member

InteGrand

Well-Known Member

InteGrand

Well-Known Member

InteGrand

Well-Known Member

leehuan

Well-Known Member

InteGrand

Well-Known Member

InteGrand

Well-Known Member

Paradoxica

-insert title here-

Users Who Are Viewing This Thread (Users: 0, Guests: 1)