least squares

we try to fit a function y(x) = sum( a[i]*f[i](x), i=1..n )
meaning the function y is a linear combination of functions f[i](x)
given a set of measurement pairs {x_i, y_i} i=1..m we try to find the most optimal parameters [a1 .. an]

given A*x=b
A is a matrix with a[i,j] = a[j]*f[j](x[i]) or row i is: a[1]*f[1](x[i]) .. a[n]*f[n](x[i]) or col j is: a[j]*f[j](x[1]) .. a[j]*f[j](x[m]) minimizing the distance from A*x to b : minimize |A*x-b| or |A*x-b|^2 = innerprod((A*x-b, A*x-b) = (A*x-b)' * (A*x-b) = (A*x)'*A*x - (A*x)'*b - b'*A*x + b'*b = x'*A'*A*x - 2*x'*A'*b + b'*b to get minimum: equate diffential of this to 0: 2*A'A*x - 2*b'*A = 0 -> solve A'*A*x = A'*b [ transpose given matrix A of n columns and m rows, the transpose A' of A is: A'[i,j] = A[j,i] (A*B)' = B'*A' ] [ innerprod given vectors x= (x[i], i=1..n) and y=(y[i], i=1..n) : innerprod(x, y) = sum ( x[i]*y[i], i=1..n ] ]