Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Solving normal equation system in C++

I would like to solve the system of linear equations:

 Ax = b

A is a n x m matrix (not square), b and x are both n x 1 vectors. Where A and b are known, n is from the order of 50-100 and m is about 2 (in other words, A could be maximum [100x2]).

I know the solution of x: $x = \inv(A^T A) A^T b$

I found few ways to solve it: uBLAS (Boost), Lapack, Eigen and etc. but i dont know how fast are the CPU computation time of 'x' using those packages. I also don't know if this numerically a fast why to solve 'x'

What is for my important is that the CPU computation time would be short as possible and good documentation since i am newbie.

After solving the normal equation Ax = b i would like to improve my approximation using regressive and maybe later applying Kalman Filter.

My question is which C++ library is the robuster and faster for the needs i describe above?

like image 795
Eagle Avatar asked Jan 03 '11 13:01

Eagle


People also ask

What is normal equation?

Normal equations are equations obtained by setting equal to zero the partial derivatives of the sum of squared errors (least squares); normal equations allow one to estimate the parameters of a multiple linear regression.

Can we use normal equation in logistic regression?

Can the normal equation be used for logistic regression? Unfortunately no. There's only one conditional model in classification theory that has a closed-form solution - linear regression.


4 Answers

This is a least squares solution, because you have more unknowns than equations. If m is indeed equal to 2, that tells me that a simple linear least squares will be sufficient for you. The formulas can be written out in closed form. You don't need a library.

If m is in single digits, I'd still say that you can easily solve this using A(transpose)*A*X = A(transpose)*b. A simple LU decomposition to solve for the coefficients would be sufficient. It should be a much more straightforward problem than you're making it out to be.

like image 134
duffymo Avatar answered Oct 12 '22 14:10

duffymo


uBlas is not optimized unless you use it with optimized BLAS bindings.

The following are optimized for multi-threading and SIMD:

  1. Intel MKL. FORTRAN library with C interface. Not free but very good.
  2. Eigen. True C++ library. Free and open source. Easy to use and good.
  3. Atlas. FORTRAN and C. Free and open source. Not Windows friendly, but otherwise good.

Btw, I don't know exactly what are you doing, but as a rule normal equations are not a proper way to do linear regression. Unless your matrix is well conditioned, QR or SVD should be preferred.

like image 26
watson1180 Avatar answered Oct 12 '22 14:10

watson1180


If liscencing is not a problem, you might try the gnu scientific library

http://www.gnu.org/software/gsl/

It comes with a blas library that you can swap for an optimised library if you need to later (for example the intel, ATLAS, or ACML (AMD chip) library.

like image 40
Tom Avatar answered Oct 12 '22 13:10

Tom


If you have access to MATLAB, I would recommend using its C libraries.

like image 30
swegi Avatar answered Oct 12 '22 14:10

swegi