# Can you give me a least squares example?

1. May 6, 2010

### hkBattousai

Can you give me a "least squares" example?

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

f(x) = a3x3 + a2x2 + a1x1 + a0x0

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

How can I estimate a0, a1, a2 and a3?

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.

2. May 6, 2010

### Staff: Mentor

Re: Can you give me a "least squares" example?

Minimize sum

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

3. May 6, 2010

### hkBattousai

Re: Can you give me a "least squares" example?

Can you please give me a matrix representation?

Experimental input vector:
X = [x1 x2 x3 x4 x5 x6]T

Output vecotr of the experiment:
Y = [y1 y2 y3 y4 y5 y6]T

Coefficients of the polynomial in f(x):
A = [a0 a1 a2 a3]T
(Or, A = [a3 a2 a1 a0]T, please specify which A matrix you choose.)

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

4. May 6, 2010

### Staff: Mentor

Re: Can you give me a "least squares" example?

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 (xi, yi). 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.

5. May 6, 2010

### hkBattousai

Re: Can you give me a "least squares" example?

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.

6. May 6, 2010

### HallsofIvy

Re: Can you give me a "least squares" example?

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.

7. May 7, 2010

### hkBattousai

Re: Can you give me a "least squares" example?

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.

8. May 7, 2010

### HallsofIvy

Re: Can you give me a "least squares" example?

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
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.

9. May 7, 2010

### hotvette

Re: Can you give me a "least squares" example?

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 ATAx = ATb (called normal equations) that can be solved by Gauss Elimination or via matrix factoring techniques (e.g. LU, Cholesky, QR, SVD).

10. May 7, 2010

### Lord Crc

Re: Can you give me a "least squares" example?

I actually found the description on Mathworld rather good.

11. May 15, 2010

### hkBattousai

Re: Can you give me a "least squares" example?

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 [Broken]
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=(XTX)-1XTY 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 [Broken]

Last edited by a moderator: May 4, 2017
12. May 15, 2010

### HallsofIvy

Re: Can you give me a "least squares" example?

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.

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.

Last edited by a moderator: May 4, 2017
13. May 21, 2010

### hkBattousai

Re: Can you give me a "least squares" example?

I'm sorry for the late reply.

Anyway,
Thank you so much for your help.

14. Jul 7, 2010

### joecampbell

Re: Can you give me a "least squares" example?

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?

15. Jul 8, 2010

### hkBattousai

Re: Can you give me a "least squares" example?

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 x0 and x1 terms.