For a matrix with N rows, M columns, and d nonzero entries per row, and you want the top K singular vector / value pairs, then the scaling looks like this:
It will take K map-reduce passes over your input data, each one costing you O(N*d^2) operations distributed on your cluster, followed by O(M*K) operations currently done sequentially to form your final singular vectors. Typically M << N and this is not considered. -jake 2011/12/12 Fernando Fernández <[email protected]> > Hi all, > > This is a question for everybody, though it may be better answered by Jake > Mannix. Do you guys know what is the complexity of the algorithm > implemented in mahout for Lancos SVD? Linear, quadratic, etc.. > > > Thanks in advance!! > Fernando. >
