Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Ask HN: what linear algebra do you use most often for practical problems?

news.ycombinator.com

Post reply on HN
Print view View original

11–20 of 31 posts

Re: Ask HN: what linear algebra do you use most often for practical problems?

#11

Post by kurtosis »

pskomoroch wrote: post #10
kurtosis wrote: post #5

I apologize for threadjacking but you guys might be able to help. I have a different problem - I would like to compute an approximate SVD of a very large sparse matrix, (for spectral clustering) but I can't find a good implementation which works for datasets too large to fit in core. This is a hadoop scale problem. What's the best way to do this? Of course, finding all the singular values/vectors is out of the questi…

Distributed, Large-Scale Latent Semantic Analysis by Index Interpolation. Sebastiano Vigna http://tinyurl.com/d99779 [PDF]

thanks to all, you guys are awesome

Re: Ask HN: what linear algebra do you use most often for practical problems?

#12

Post by biotech »

I probably use multi-linear regression most often, but occasionally I'll encounter a Linear Programming problem.

I'm currently looking for a good Partial Least Squares algorithm in C/C++. Any suggestions? I know R has a popular PLS algorithm, but I was hoping to avoid the learning curve.

Re: Ask HN: what linear algebra do you use most often for practical problems?

#13

Post by buss »

miloshh wrote: post #9
kurtosis wrote: post #5

I apologize for threadjacking but you guys might be able to help. I have a different problem - I would like to compute an approximate SVD of a very large sparse matrix, (for spectral clustering) but I can't find a good implementation which works for datasets too large to fit in core. This is a hadoop scale problem. What's the best way to do this? Of course, finding all the singular values/vectors is out of the questi…

As long as the 100 vectors fit in memory, it shouldn't be too bad. I think the commonly used algorithm to find the first singular vectors is Lanczos iteration, where the key operation is multiplying the 100 vectors by the large matrix. I don't know if there's an existing library for this though...

There is indeed, http://tedlab.mit.edu/~dr/svdlibc/ this is a sparse svd solver using the Lanczos approach.

I've used this, it works pretty quickly and produces exact results, unlike a gradient descent approach. Unfortunately, assuming I did everything correctly, it doesn't ignore the zeros in the data. I think this because after centering the data (subtracting the mean and dividing by the standard deviation for each row in the matrix), it just doesn't finish. I must have left it running for two days before I gave up on it. My assumption is that it was trying to approximate all the zeros which, due to centering, now were seen as the average rating for that user. I'm sure you could modify it to ignore those values, though.

edit: Please note that I could be way off in that my interpretation of the program not finishing. If someone knows I'm wrong, please tell me.

Re: Ask HN: what linear algebra do you use most often for practical problems?

#14

Post by jey »

kurtosis wrote: post #5

I apologize for threadjacking but you guys might be able to help. I have a different problem - I would like to compute an approximate SVD of a very large sparse matrix, (for spectral clustering) but I can't find a good implementation which works for datasets too large to fit in core. This is a hadoop scale problem. What's the best way to do this? Of course, finding all the singular values/vectors is out of the questi…

I've been using PROPACK lately to perform SVD on a gigantic matrix, and it kicks ass. It's a fortran and/or MATLAB package for SVD of large sparse or "structured" matrices. http://soi.stanford.edu/~rmunk/PROPACK/

You just have to provide a matrix-vector product function, specify a few parameters (how many singular values to find, should it compute the singular vectors, maximum number of iterations, etc) and it takes care of the rest. It uses the Lanczos iteration approach mentioned in sibling comments, and it seems like a far nicer implementation than SVDPACK and SVDLIBC.

Let me know if you want a copy of my C interface to PROPACK.

Re: Ask HN: what linear algebra do you use most often for practical problems?

#15

Post by kurtosis »

buss wrote: post #8
kurtosis wrote: post #5

I apologize for threadjacking but you guys might be able to help. I have a different problem - I would like to compute an approximate SVD of a very large sparse matrix, (for spectral clustering) but I can't find a good implementation which works for datasets too large to fit in core. This is a hadoop scale problem. What's the best way to do this? Of course, finding all the singular values/vectors is out of the questi…

Gradient descent is a good solution for approximate SVD, I'm using it as part of my data mining final project (working on the netflix prize). I'm using this guy's code: http://www.timelydevelopment.com/demos/NetflixPrize.aspx , modified to print out the singular vectors when it finishes. It took about 32 hours (can't quite remember) to find the first 64 singular values* on the netflix dataset (480000x18000, 1.2% non-…

Thanks for the link - these results are encouraging. I'll think about it - if I come up with anything I'll let you know. Good luck.

Re: Ask HN: what linear algebra do you use most often for practical problems?

#17

Post by jey »

omarish wrote: post #7

You can save a ton of time by formulating a linear algebra problem as a shortest path problem; you can end up using dijkstra's algorithm to enumerate the possible solutions. http://en.wikipedia.org/wiki/Knapsack_problem

I don't get it (at all). Can you elaborate?

Re: Ask HN: what linear algebra do you use most often for practical problems?

#18

Post by jey »

buss wrote: post #13
miloshh wrote: post #9

Earlier quoted context omitted.

As long as the 100 vectors fit in memory, it shouldn't be too bad. I think the commonly used algorithm to find the first singular vectors is Lanczos iteration, where the key operation is multiplying the 100 vectors by the large matrix. I don't know if there's an existing library for this though...

There is indeed, http://tedlab.mit.edu/~dr/svdlibc/ this is a sparse svd solver using the Lanczos approach. I've used this, it works pretty quickly and produces exact results, unlike a gradient descent approach. Unfortunately, assuming I did everything correctly, it doesn't ignore the zeros in the data. I think this because after centering the data (subtracting the mean and dividing by the standard deviation for each…

Maybe you encountered some numerical instability in SVDLIBC, but I would guess that there probably was a bug in the parameters you passed to SVDLIBC. Might want to try it again with a smaller matrix and compare it against MATLAB or something to flush out any bugs.

Re: Ask HN: what linear algebra do you use most often for practical problems?

#19

Post by buss »

jey wrote: post #14
kurtosis wrote: post #5

I apologize for threadjacking but you guys might be able to help. I have a different problem - I would like to compute an approximate SVD of a very large sparse matrix, (for spectral clustering) but I can't find a good implementation which works for datasets too large to fit in core. This is a hadoop scale problem. What's the best way to do this? Of course, finding all the singular values/vectors is out of the questi…

I've been using PROPACK lately to perform SVD on a gigantic matrix, and it kicks ass. It's a fortran and/or MATLAB package for SVD of large sparse or "structured" matrices. http://soi.stanford.edu/~rmunk/PROPACK/ You just have to provide a matrix-vector product function, specify a few parameters (how many singular values to find, should it compute the singular vectors, maximum number of iterations, etc) and it takes…

I'd be interested in trying it out, can you send it my way a la sbuss a cise d ufl d edu

Cheers

Post reply on HN