0
$\begingroup$

I have the following Octave/Matlab code to compute an SVD-like matrix-decomposition:

function [P, Q] = matrix_factorization(R, K)

steps = 5000;
alpha = 0.0002;
reg = 0.02;

N = size(R)(1);
M = size(R)(2);

P = rand(N,K);
Q = rand(M,K);

    Q = Q';

for step=1:steps

    #iterate over training set
    for i=1:size(R)(1)
        for j=1:size(R)(2)
            if R(i,j) > 0
                eij = R(i,j) - P(i,:)*Q(:,j);
                for k=1:K
                    Pik = P(i,k);
                    P(i,k) = P(i,k) + alpha * (2 * eij * Q(k,j) - reg * P(i,k));
                    Q(k,j) = Q(k,j) + alpha * (2 * eij * Pik - reg * Q(k,j));
                endfor
            endif
        endfor
    endfor

endfor 

Q = Q';         

endfunction

The problem is even for a 3x3 matrix with 2 features it takes about 15 seconds to complete. So about 15/(5000*9*2) seconds per loop. This thing explodes really fast, so no way to compute this for matrices larger than say 100x100.

Notice I don't have a break condition in here, but it does converge so slowly, that a break condition won't really reduce the number of steps.

How could I improve this code substantially? If I have a training set of millions of entries. Should I load them from a database one after another (sounds horrible performance wise) or from a text file. Then I would need to hold all the data in my computer memory.

(If there are mathematical mistakes in my code, it would be nice if you could point it out.)

$\endgroup$
  • $\begingroup$ "How could I improve this code substantially?": use the inbuilt functions eig and/or eigs? Why are you writing your own code for this? At which point in-built functions constrain your current work-flow? You say "million of entries", I am thinking "sparsity", have you looked into sparse methods? $\endgroup$ – usεr11852 Nov 2 '14 at 11:38
  • $\begingroup$ I cannot use inbuilt functions because they require 'real' matrices. I want to ignore the 0 values in my calculation not include them. $\endgroup$ – Nimrare Nov 3 '14 at 14:10
  • 1
    $\begingroup$ Vectorize... you can't get this to perform without that in Octave/Matlab. I realize that the matrices will become large, but there might be sparse matrices available in these languages. If so, use them. If you insist of going the for loop way, use a language that does that better - like C++ or python. $\endgroup$ – ignorant Nov 24 '14 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.