Serving the Quantitative Finance Community

 
User avatar
ppauper
Posts: 11729
Joined: November 15th, 2001, 1:29 pm

Re: Which solver to use?

January 4th, 2018, 6:31 am

cuch is correct here,
(snip)
Looking at your non-TEX formulae it looks like you are solving normal equations. Your problem is linear.
[$]Ax = b[$]

least squares solution solve

[$]A^{\rm T} Ax = A^{\rm T}b[$]

in your case K = A, P = x, Y = x, yes?
1) As I understand this, in this example the matrix to be factored or inverted isn't square.
as cuch said, with least squares, you solve [$]A^{\rm T} Ax = A^{\rm T}b[$] and [$]A^{\rm T} A[$] IS square

you can solve the linear system [$]A^{\rm T} Ax = A^{\rm T}b[$] by matrix inversion if you want to, but it's a lot quicker to use row-reduction techniques (Gauss-Jordan).
 
User avatar
MartinGale7
Topic Author
Posts: 70
Joined: April 1st, 2011, 7:42 am

Re: Which solver to use?

January 4th, 2018, 10:43 am

Thank you @ppauper.

That clarifies it on the square matrix issue. I will investigate Gauss-Jordan. I've tried Cholesky however past about 1000x1000 this gets very slow. I believe it is O(n^3) in processing time and there may be issues with numerical stability/precision.

(I'm not an expert in this field.)
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: Which solver to use?

January 4th, 2018, 12:47 pm

Cholesky can't be applied.as such, Wasn't built for this problem. See Golub and van Loan.

Based on your comment I just remembered a bunch of lectures from Gil Strang (my academic 'grandpa") on  numerical linear algebra for a great overview.

+ more..
 
User avatar
MartinGale7
Topic Author
Posts: 70
Joined: April 1st, 2011, 7:42 am

Re: Which solver to use?

January 23rd, 2018, 11:00 am

Just an update on this. I have been able to achieve what I was looking to do and the results look good. I've been able to solve a GPR problem through an iterative optimisation method rather than matrix inversion or factorisation (eg Cholesky). This means I can have say 10000 or 100000 support points.

Initially I used 'Gradient Descent'. This worked well but was slow. I then switched to 'Conjugate Gradient'. This was much faster. I'm currently in the process of implementing 'ADAM Stochastic Gradient Descent' which I suspect will be better. It definitely seems to be the fashion in the deep learning field at the moment.

Thanks for all of your help.
 
User avatar
outrun
Posts: 4573
Joined: January 1st, 1970, 12:00 am

Re: Which solver to use?

January 23rd, 2018, 12:39 pm

Very good progress!

The momentum part from ADAM might indeed help. The stochastic part of SGD might not be very relevant in the context of local minima / saddle points because the problem is convex, ..but from a memory/cache point of view you could see speedups when using mini-batches?
 
User avatar
MartinGale7
Topic Author
Posts: 70
Joined: April 1st, 2011, 7:42 am

Re: Which solver to use?

January 23rd, 2018, 4:24 pm

Yes, I hope so. In my case I think there is only one (local) minimum as long as I am using an error squared cost. If using abs error then I can try multi-start, ie using different starting points to confirm they all up at the same (local) minimum.

Happy days.