What You Will Gain By Rounding: Theory and Algorithms for Rounding Rank
=======================================================================

This folder contains the source code and synthetic data generators
accompanying the paper 

Stefan Neumann, Rainer Gemulla & Pauli Miettinen, 2016:
What You Will Gain By Rounding: Theory and Algorithms for Rounding Rank.
In Proceedings of the 16th IEEE International Conference on Data Mining
(ICDM). 

The extended version of this paper is published as
Stefan Neumann, Rainer Gemulla & Pauli Miettinen, 2016:
What You Will Gain By Rounding: Theory and Algorithms for Rounding Rank.
arXiv:1609.05034v2 [cs.DM].

This code is free to use for academic purposes provided that you cite
the above paper. 


Software requirements
---------------------

The algorithms are implemented in Matlab and C and are tested to work with
Matlab 2014b and 2015b. To compile the C files, you will also need a C 
compiler that is supported by Matlab's MEX system. 

The projection method and nuclear norm method need solvers. The projection
method can use Matlab's build-in linprog, but the experiments were 
conducted using Gurobi (www.gurobi.com), which is freely available for 
academic use. The nuclear norm minimizer requires the CVX package 
(www.cvxr.com), which is also freely available for academic use. 


Package contents
----------------

The files RoundingRank*.m implement the methods to estimate the rounding
rank. The files minErrRR*.m implement (some of) the methods for minimum-
error fixed rounding rank decompositions, although some comparison methods
are implemented in other files.

The files run_*.m are the drivers for the experiments (both synthetic and
real-world). They contain all the details and parameters used in the
experiments, and can also be used as examples on how to call the different
methods. For further information, "help <method>" will produce a
help text in Matlab.

The synthetic data is not included, but the scripts to generate it are
called make_*_data.m. Real-world data is not included, but can often be
downloaded from the URLs listed in the main submission. 


Preliminaries
-------------

Some algorithms require extra steps to be taken before they can be used.

o Asso
    In order to run the experiments with the Asso algorithm, you must
    first compile it by issuing
    > make_select_best_column

o CVX
    If you want to use the CVX solvers (or the Nuclear algorithm), you must
    first install the CVX package (http://cvxr.com/cvx/), and then edit the
    'setup_cvx.m' file appropriately.

o Gurobi
    If you have, and want to use, the Gurobi solver, you must copy
    the file 'linprog.m' from <gurobi dir>/examples/matlab/ to this folder and
    re-name it to 'linprog_gurobi.m'. You must also edit the 'setup_gurobi.m'
    file to have the correct directory for the Gurobi.

o LPCA
    To execute the LPCA code, you must first dowload the original LPCA code
    from Andrew I. Schein's homepage, 
    http://www.andrewschein.com/software/lpca_code.tar
    Copy the file lpca_fit.m to this folder and patch it with the file 
    lpca_fit.patch: for example, in Bash, 
    $ patch lpca_fit.m lpca_fit.patch

o MT
    To use the Mannila--Terzi (MT) algorithm, you must first compile its
    source code in Nestedness.c. 
    > mex CFLAGS="\$CFLAGS -std=c99 -Wall -O3 -march=native" Nestedness.c BinaryHeap.c
    (See also below for an example.) N.B. The exact CFLAGS are compiler-
    specific, please consult your C-compilers documentation for further help.

o Permutation
    In order to use the Permutation algorith, you must first compile its 
    sources in ShaysInC.c file:
    > mex CFLAGS="\$CFLAGS -std=c99 -Wall -O3 -march=native" ShaysInC.c

o Synthetic data
    In order to create the synthetic data, you must call the functions
    make_*_data.m, for example,
    > make_big_synth_data; make_small_synth_data; make_nested_data


Example use
-----------

To replicate the nestedness experiments (Sect. V.D), you will first need
to generate the nested matrices:
> make_nested_data
This will generate the matrices in folder ../data/synth/. If you want to
change the folder, edit the file make_nested_data.m.

Before you can run the code, you must also compile the Mannila--Terzi code:
> mex CFLAGS="\$CFLAGS -std=c99 -Wall -O3 -march=native" Nestedness.c BinaryHeap.c
To run the experiments, 
> run_synth_nested();
If you have changed the data directory (or want to change the results
directory), you have to edit the file run_synth_nested.m. If you want to
run only the NNRR1 algorithm, you can 
> run_synth_nested('allAlgos', false, 'greedy', true);
Further info on which experiments to run can be obtained by
> help run_synth_nested

If you want to plot the results, you can
> plot_synth_nested
If you have changed the results directory, you have to edit this file to 
match.
