// Demonstrates the iterative approach.

import edu.gwu.lintool.*;
import java.util.*;

public class MovieRatingsIterativeSVD {

    public static void main (String[] argv)
    {
	// Rows are users, columns are movies.
	// Missing ratings are marked by 0

        double[][] X = {
  // Movies: 1  2  3  4  5  6    1+2=action, 3+4=drama, 5+6=comedy
	    {5, 4, 1, 1, 4, 0},  // User 1,  users 1 & 2 are similar
	    {4, 5, 1, 2, 0, 5},  // User 2
	    {0, 0, 4, 0, 5, 4},  // User 3   users 3 and 4 are similar
	    {4, 0, 4, 0, 5, 0},  // User 4
	    {4, 4, 1, 0, 1, 1},  // User 5   5 & 6 are similar
	    {5, 5, 0, 1, 2, 1},  // User 6
	    {3, 3, 3, 3, 3, 3},  // User 7   7 & 8 are similar
	    {2, 3, 2, 3, 2, 3},  // User 8
	    {5, 0, 0, 0, 0, 0}   // User 9   9 is very dissimilar from all
	};
	
	iterativeSVD (X, 1000);
    }


    static void iterativeSVD (double[][] X, int numIterations)
    {
	// Initial matrices U (m x m) and  (m x n)
	int m = X.length, n = X[0].length;

	// The U matrix that'll store the r_i vectors: one r_i in each row.
	double[][] U = new double[m][m];

	// The W matrix that'll store each w_j matrix, one w_j per column.
	double[][] W = new double[m][n];

	// Initialize both sets of vectors to 1
	for (int i=0; i<m; i++) {
	    for (int k=0; k<m; k++) {
		U[i][k] = 1;             // r_i = (1,1,...,1)
	    }
	}

	for (int i=0; i<m; i++) {
	    for (int j=0; j<n; j++) {
		W[i][j] = 1;             // w_j = (1,1,...,1)
	    }
	}
	
	// Iterate for given # of iterations.

	double alpha = 0.01;
	for (int iter=0; iter<numIterations; iter++) {

	    for (int i=0; i<m; i++) {
		for (int j=0; j<n; j++) {
		    if (X[i][j] > 0.01) {   // Non-zero

			// Let r_i = row i of U, w_j = col j of W

			// First, the dot product
			double rDotw = 0;
			for (int k=0; k<m; k++) {
			    rDotw += U[i][k] * W[k][j];
			}			
			// r_i <- r_i + alpha*w_j (X[i][j] - r_i dot w_j)
			// w_j <- w_j + alpha*u_i (X[i][j] - r_i dot w_j)
			double[] r_i_change = new double [m];
			double[] w_j_change = new double [m];
			for (int k=0; k<m; k++) {
			    r_i_change[k] = alpha*W[k][j]*(X[i][j]-rDotw);
			    w_j_change[k] = alpha*U[i][k]*(X[i][j]-rDotw);
			}
			// Now apply:
			for (int k=0; k<m; k++) {
			    U[i][k] = U[i][k] + r_i_change[k];
			    W[k][j] = W[k][j] + w_j_change[k];
			}

		    } //end-if
		} //end-inner-for
	    }// end-outer-for

	}// end-iterations

	double[][] predicted = MatrixTool.matrixMult (U,W);
	LinUtil.print ("Iterative: predicted", predicted);
    }

}