----------------------------------------------------------------------------
README file for lsNTF
----------------------------------------------------------------------------

Michael P. Friedlander
Kathrin Hatz
Version 1.0.1
16 October 2006

This software package is documented in this technical report:

  M. P. Friedlander and Kathrin Hatz, "Computing a nonnegative tensor
  factorization", UBC Computer Science Technical Report TR-2006-21,
  October 2006.

The license information is contained in the file LICENSE.
   
----------------------------------------------------------------------------
Overview
----------------------------------------------------------------------------

lsNTF implements the following four algorithms:

NTF            - Nonnegative tensor factorization (NTF) using
                 alternating least squares.
NMF            - Nonnegative matrix factorization (NMF) using
                 alternating least squares.
projGradNMF    - Projected gradient method for NMF (Chih-Jen Lin, 2005).
multUpdateNMF  - Multiplicative update for NMF (Lee and Seung, 1999).


1. Nonnegative matrix factorization (NMF)
-----------------------------------------

   Given a nonnegative n-by-m matrix V, NMF approximately factorizes V
   into the two nonnegative factors W (n-by-r) and H (r-by-m), thereby
   giving V ~ W*H'.
   lsNMF solves the following problem:

   minimize     1/2 ||V-W*H'||^2 + gamma (||W(:)||_1 + ||H(:)||_1) 
     W,H                                                           (*)
   subject to   W, H nonnegative.                       

   V can be any shape.  The inner dimension r is given by the user.
   The regularization parameter gamma helps to keep the solution
   bounded and encourages sparseness of the computed factors W,H.
   gamma can be zero.

   lsNMF solves (*) via a sequence of nonnegative linear least-squares
   subproblems.  The software package BCLS is used to solve each of these
   subproblems.

   Two other algorithms for NMF are included as a comparison:
   - projGradNMF: implements the projected gradient method described by
                  Chih-Jen Lin, 2005.
   - multUpdateNMF: implements the multiplicative-update method described
                  by Lee and Seung, 1999.

2. Nonnegative tensor factorization (NTF)
-----------------------------------------

   Given a nonnegative 3-mode tensor V, NTF computes the approximate
   factorization

   (*)          V ~  G  x_1  A^(1)  x_2  A^(2)  x_3  A^(3)

   where A^(1), A^(2), A^(3) are nonnegative matrices and G is a nonnegative
   3-mode core tensor.  (Note that  "x_1", "x_2", and "x_3" denote the 
   "1-mode", "2-mode", and "3-mode" tensor-matrix products.  They don't sub-
   script x!)  lsNTF computes (*) via the problem

   (**)

   minimize     phi(A) + gamma (||A^(1)(:)||_1+||A^(2)(:)||_1+||A^(3)(:)||_1) 
    A^(i)       
   subject to   A^(i) nonnegative for i = 1,2,3,

   where        phi(A) = 1/2 || V - G  x_1  A^(1)  x_2  A^(2)  x_3  A^(3) ||^2.   
                   
   V can be any shape, the dimension of the core tensor G is also
   given by the user. The regularization parameter gamma keeps the
   problem bounded and also controls the sparseness of the
   factors; gamma may be zero.

   In order to use alternating least squares, lsNTF transforms (*) into 
   three linear subproblems, which are each solved by BCLS. 

----------------------------------------------------------------------------
Prerequisites
----------------------------------------------------------------------------

At minimum, you need the following to run lsNTF:

1. MATLAB (we've only tested lsNTF with Matlab 7.1-7.3)

2. TensorToolbox (http://csmr.ca.sandia.gov/~tgkolda/TensorToolbox/)

and optionally,

3. Sample data set (e.g., http://cbcl.mit.edu/cbcl/software-datasets/FaceData2.html)

----------------------------------------------------------------------------
Quick Start
----------------------------------------------------------------------------

For these instructions, we assume that lsNTF has been downloaded and
unpacked into the directory lsNTF.  We write $lsNTF to indicate the
full path of this directory.

1. Downloading the face image database:
---------------------------------------
    
   To run the face experiment, you must first download the CBCL face
   database from
   
   http://cbcl.mit.edu/cbcl/software-datasets/FaceData2.html.
 
   Put the uncompressed database into the directory dataCBCL/. The
   directory structure should look like this:

   lsNTF/
       dataCBCL/
          README  
          faces.tar.gz    
          svm.test.normgrey  
          svm.train.normgrey
   
   N.B.: The file faces.tar.gz doesn't have to be extracted; only
   svm.test.normgrey is used.


2. Downloading and installing BCLS:
-----------------------------------

   The BCLS package forms a core part of our NTF/NMF implementation.
   Precompiled MEX interfaces are already included for Mac OSX, Linux,
   and WinXP, and can be found in the bcls subdirectory:

      lsNTF/
          bcls/...
          ...

   If you wish to use lsNTF for other platforms you may download the
   source code for the BCLS library and its MEX interface from

      http://www.cs.ubc.ca/~mpf/index.php?q=bcls

   Install it anywhere you wish and make sure to add this location to
   the Matlab path. 

3. Downloading and Installing the TensorToolbox:
------------------------------------------------

   Download the TensorToolbox at:

   http://csmr.ca.sandia.gov/~tgkolda/TensorToolbox/.

   Put the uncompressed file in the directory lsNTF/. The
   directory structure should look like this:

      lsNMF/
          bcls/...
          code/...
          dataCBCL/...
          tensor_toolbox_2.0/...
          ...

4. Modify the Matlab path:
--------------------------

   From the Matlab prompt, do

   >> addpath $lsNTF
   >> addpath $lsNTF/code
   >> addpath $lsNTF/bcls
   >> addpath $lsNTF/dataCBCL
   >> addpath $lsNTF/tensor_toolbox_2.0/

  N.B. The TensorToolbox's directory name may have changed by the time you
  download it.  Change this appropriately.

----------------------------------------------------------------------------
Run the experiments
----------------------------------------------------------------------------

To run the experiments, type
  
   >> runNTF('algorithm');

   where 

   algorithm =  'lsNMF'         to run the nonnegative Matrix Factorization, 
                'lsNTF'         to run the nonnegative Tensor Factorization,
                'multUpdateNMF' to run the multiplivative Update for NMF 
                                (Lee and Seung, 1999), 
                'projGradNMF'   to run the Projected Gradient Method
                                for NMF (Chih-Jen Lin, 2005), 
                'all'           to run all algorithms.

----------------------------------------------------------------------------
Bugs
----------------------------------------------------------------------------

1. There is an error in lsNTF.m if the tensor V is of size I_1 x I_2 x
   1 (e.g. for decomposing one face).
   Matlab and the Tensor Toolbox store the size of V in a different way:
   
   V in Matlab :                   size(V) = I_1 x I_2
   V retured by the TensorToolbox: size(V) = I_1 x I_2 x 1.
  
   Matlab prints 'dimensions don't match' if for example the
   Tensor Toolbox returns G of size I_1 x I_2 x 1 and we want to
   compute V - G with V of size I_1 x I_2. 

2. There is probably a bug in gradientNMF.m, which we haven't found
   yet. The function gradientNMF.m computes the symbolic
   gradient of the objective function in lsNMF. gradientNMF.m is not
   used in the currnet settings, alternatively we use an approximate gradient
   computed by BCLS. There is a flag in lsNMF for using the
   symbloic gradient of the objective.

----------------------------------------------------------------------------
Problems
----------------------------------------------------------------------------

If there are any problems, don't hesitate to contact us. You find the
e-mail addresses below. Please provide as much information on the
nature of the problem as possible.  


----------------------------------------------------------------------------
Contact
----------------------------------------------------------------------------

Michael P. Friedlander
Department of Computer Science, University of British Columbia
mpf@cs.ubc.ca                        http://www.cs.ubc.ca/~mpf

Kathrin Hatz
Interdiscipliary Center for Scientific Computing of the
Ruprecht-Karls-University of Heidelberg
khatz@ix.urz.uni-heidelberg.de  

----------------------------------------------------------------------------
Bibliography
----------------------------------------------------------------------------

-  Bret W. Bader and Tamara G. Kolda, MATLAB Tensor Classes for Fast
   Algorithm Prototyping, ACM Trans. Math. Software, to appear
   (accepted 2006).

-  D. Lee and H.S. Seung,
   " Learning the parts of objects by nonnegative matrix factorization", 1999. 

-  Chih-Jen Lin, 
   "Projected gradient methods for nonnegative matrix factorization", 2005

