Can you give me a least squares example?

[hkBattousai]

Can you give me a "least squares" example?

Assume that, I have a function to estimate like below:

f(x) = a₃x³ + a₂x² + a₁x¹ + a₀x⁰

After several experiments I have obtained these (x, f(x)) pairs:
(x₁, y₁)
(x₂, y₂)
(x₃, y₃)
(x₄, y₄)
(x₅, y₅)
(x₆, y₆)

How can I estimate a₀, a₁, a₂ and a₃?

I searched in Google, there are lots of definition of the theorem, but there is no example. I will be glad if you guys spare your time to help me.

 

[Borek]

Minimize sum

$$\sum (y_i - f(x_i))^2$$

 

[hkBattousai]

Assume that, I have a function to estimate like below:

f(x) = a₃x³ + a₂x² + a₁x¹ + a₀x⁰

After several experiments I have obtained these (x, f(x)) pairs:
(x₁, y₁)
(x₂, y₂)
(x₃, y₃)
(x₄, y₄)
(x₅, y₅)
(x₆, y₆)

How can I estimate a₀, a₁, a₂ and a₃?

I searched in Google, there are lots of definition of the theorem, but there is no example. I will be glad if you guys spare your time to help me.

Can you please give me a matrix representation?

Experimental input vector:
X = [x₁ x₂ x₃ x₄ x₅ x₆]^T

Output vecotr of the experiment:
Y = [y₁ y₂ y₃ y₄ y₅ y₆]^T

Coefficients of the polynomial in f(x):
A = [a₀ a₁ a₂ a₃]^T
(Or, A = [a₃ a₂ a₁ a₀]^T, please specify which A matrix you choose.)


How can I find the vector A in terms of X and Y experiment result vectors.

 

[Borek]

To understand the idea there is no need for matrix representation.

Let's say you want to do linear regression, y=ax+b. You have set of pairs (x_i, y_i). You look for a & b such that the sum

$$\sum (y_i - ax_i - b)^2$$

has minimum value. Calculate derivatives (d/da, d/db) of the sum, compare them to zero, solve for a & b - and you are done. This is high school math.

Your example - with third degree polynomial - is not linear in x, so I don't think you can use simple vector X for your purposes. But I can be wrong.

 

[hkBattousai]

^ Thank you for your answer.

I'm a grad-student, one of my courses include this LMS topic. My textbook doesn't explain how the theorem is applied, it just gives the solution in an example. I need to learn the implementation of this theorem by means of matrices. Internet sources give the formal definition of this theorem, unfortunately there is no example.

I will be happy if you could give me a start point.

 

[HallsofIvy]

Think of $a_3x^3+ a_2x^2+ a_1x+ a_0$ as the matrix product
$$\begin{bmatrix}x^3 & x^2 & x & 1 \end{bmatrix}\begin{bmatrix}a_3 \\ a_2 \\ a_1 \ a_0 \end{bmatrix}$$

Since you have 6 data points, you have that repeated 6 times- a matrix product with 6 rows:

$$\begin{bmatrix} x_1^3 & x_1^2 & x_1 & 1 \\ x_2^3 & x_2^2 & x_3 & 1 \\ x_3^3 & x_3^2 & x_3 & 1 \\ x_4^3 & x_4^2 & x_4 & 1 \\ x_5^3 & x_5^2 & x_5 & 1 \\ x_6^3 & x_6^2 & x_6 & 1\end{bmatrix}\begin{bmatrix}a_3 \\ a_2 \\ a_1 \\ a_0\end{bmatrix}= \begin{bmatrix}y_1 \\ y_2 \\ y_3 \\ y_4 \\ y_5 \\ y_6\end{bmatrix}$$

Writing that as Ax= y where x, the vector of "a"s, is 4 dimensional, and y is in a six dimensional space, Ax is in a 4 dimensional subspace and that has an exact solution only if y happens to be in that subspace. If it is not, then the "closest" we can get to y is to the projection of y in that vector space. In particular, that means that y- Ax must be orthogonal to that space: <Au, y- Ax>= 0 for all v in $R^4$. Letting $A^*$ be the adjoint (transpose) of A, $<u, A^*(y- Ax)= 0$.

But now, since that inner product is in $R^4$ and u could be any vector in $R^4$, we must have $A^*(y- Ax)= A^*y- A^*Ax= 0$ or $A^*Ax= A^*y$. If $A^*A$ has an inverse (which it typically does in problems like this), $x= (A^*A)^{-1}A^*y$ gives the coefficients for the "least squares" cubic approximation.

 

[hkBattousai]

Sorry for the late reply.

$$\begin{bmatrix} x_1^3 & x_1^2 & x_1 & 1 \\ x_2^3 & x_2^2 & x_3 & 1 \\ x_3^3 & x_3^2 & x_3 & 1 \\ x_4^3 & x_4^2 & x_4 & 1 \\ x_5^3 & x_5^2 & x_5 & 1 \\ x_6^3 & x_6^2 & x_6 & 1\end{bmatrix}\begin{bmatrix}a_3 \\ a_2 \\ a_1 \\ a_0\end{bmatrix}= \begin{bmatrix}y_1 \\ y_2 \\ y_3 \\ y_4 \\ y_5 \\ y_6\end{bmatrix}$$

This equation is XA = Y, isn't it?
Only the Y matrix is given. How can I form the X matrix here?

Thank you so much for your help.

 

[HallsofIvy]

I'm thinking of the 4 by 6 matrix, made from the $x_i$ as "A" and the column matrix, made from the $a_i$ as "X".

You said, in your original post, that

After several experiments I have obtained these (x, f(x)) pairs:
(x1, y1)
(x2, y2)
(x3, y3)
(x4, y4)
(x5, y5)
(x6, y6)

so you have both $xi$ and $y_i$. If you were given only the y-values with no corresponding x information, there is no possible way to set up a formula.

 

[hotvette]

How can I estimate a₀, a₁, a₂ and a₃?

I searched in Google, there are lots of definition of the theorem, but there is no example. I will be glad if you guys spare your time to help me.

Here is an explanation that might be useful.

http://www.personal.psu.edu/jhm/f90/lectures/lsq2.html

The final matrix equation is equivalent to the linear system A^TAx = A^Tb (called normal equations) that can be solved by Gauss Elimination or via matrix factoring techniques (e.g. LU, Cholesky, QR, SVD).

 

[Lord Crc]

I actually found the description on Mathworld rather good.

 

[hkBattousai]

I found the explanation of the method in a textbook, and I want to share it here. But since I'm not quite familiar with Latex, I will attach photos instead:
[PLAIN]http://img704.imageshack.us/img704/6940/dscf4205.jpg
I realized that this solution is the same as HallsofIvy offered, I wish I understood what he meant earlier...

Q1) The equation is XA=Y, why don't we just solve it by means of A=X^-1Y, and use A=(X^TX)^-1X^TY instead?

Q2) Is this solution of A an "estimate" or the real A? It is obvious that the solution is just an estimate, but why? The solution of the equation in the picture (XA=Y) is straight forward, after which step we say that the "A" vector is an estimate rather than the real A?

Q3) We use this method to estimate the test results as a polynomial. But do we have to estimate it as a polynomial only? I mean, can we estimate f(x) in term of other kinds functions? The picture below illustrates what I'm trying to ask:
[PLAIN]http://img80.imageshack.us/img80/7320/dscf4204.jpg

 

[HallsofIvy]

I found the explanation of the method in a textbook, and I want to share it here. But since I'm not quite familiar with Latex, I will attach photos instead:
[PLAIN]http://img704.imageshack.us/img704/6940/dscf4205.jpg
I realized that this solution is the same as HallsofIvy offered, I wish I understood what he meant earlier...

Q1) The equation is XA=Y, why don't we just solve it by means of A=X^-1Y, and use A=(X^TX)^-1X^TY instead?

because X, in general, doesn't have an inverse. Here, you are trying to fit a cubic, with four coefficients, to six points so you have a 6 by 4 matrix. That is not a square matrix and so does not have an inverse. You can always fit a line to two points, a quadratic to three points and a cubic to four points, exactly, because that way you have the same number of coefficients as equations and so have a square matrix that you can invert.

Q2) Is this solution of A an "estimate" or the real A? It is obvious that the solution is just an estimate, but why? The solution of the equation in the picture (XA=Y) is straight forward, after which step we say that the "A" vector is an estimate rather than the real A?

What do you mean by a "real" A? In general there is NO cubic that actually passes through six given points. There is NO "real" A in that sense.

Q3) We use this method to estimate the test results as a polynomial. But do we have to estimate it as a polynomial only? I mean, can we estimate f(x) in term of other kinds functions? The picture below illustrates what I'm trying to ask:
[PLAIN]http://img80.imageshack.us/img80/7320/dscf4204.jpg[/QUOTE]
No, there are many other functions that are generally used- exponential and sine and cosine functions are often used. And, yes, exactly the same formulas apply.

 

[hkBattousai]

I'm sorry for the late reply.
I don't know why but I didn't receive email notification for your reply this time, though by default I'm receiving email notification of replies.

Anyway,
All your answers are satisfactory for me.
Thank you so much for your help.

 

[joecampbell]

To understand the idea there is no need for matrix representation.

Let's say you want to do linear regression, y=ax+b. You have set of pairs (x_i, y_i). You look for a & b such that the sum

$$\sum (y_i - ax_i - b)^2$$

has minimum value. Calculate derivatives (d/da, d/db) of the sum, compare them to zero, solve for a & b - and you are done. This is high school math.

Your example - with third degree polynomial - is not linear in x, so I don't think you can use simple vector X for your purposes. But I can be wrong.

im finding a least squares method on these points. (-10,1),(-10,-1),(10,1),(10,-1)
and I ended up with 4+4(a)squared+400(b)squared=minimum
this might sound retarted to you guys, but what do i do now?

 

[hkBattousai]

im finding a least squares method on these points. (-10,1),(-10,-1),(10,1),(10,-1)
and I ended up with 4+4(a)squared+400(b)squared=minimum
this might sound retarted to you guys, but what do i do now?

Why don't you use the general formula in the picture in the image file in post #11?
You only have to modify the X matrix by only including x⁰ and x¹ terms.