 **************************************************************************************************************
 * 
 *              A matlab package to re-run the experiments reported in the following paper:
 *
 *  Xiao-Tong Yuan, Tong Zhang, Truncated Power Method for Sparse Eigenvalue Problems, Technical Report, 2011
 *               
 **************************************************************************************************************

** TABLE OF CONTENTS:

* Overview 
* Algorithms
* How to Run 
* Copyright


	              *******************************************

** OVERVIEW:

TPower is a truncated power method for sparse eigenvalue problem which aims at extracting sparse eigenvectors with at most k non-zero components. 
The algorithm along with its applications in sparse PCA and densest k-subgraph is extensively described in our online paper: "Xiao-Tong Yuan, Tong Zhang, Truncated Power Method for Sparse Eigenvalue Problems, Technical Report, 2011".  

There are three subfolders in the root of this package: algorithms, experiments and misc. The subfolder "algorithms" contains all the matlab implementations of algorithms used in the experiments. The subfolder "experiments"
contains all the matlab scripts for the experiments reported in our paper. The subfolder "misc" contains all the common files used in the algorithms and experiments. 


		      ********************************************


** ALGORITHMS:

All the algorithms are implemented and tested with the software platform Matlab v7.12, Windows XP. Their codes are in the 'TPower_1.0/algorithms/' directory which include

* TPower and its variants TPower_SPCA and TPower_DkS. Here TPower_SPCA is a special design of TPower to solve the sparse PCA problem, while TPower_DkS is a special design of TPower to solve the densest k-subgraph (DkS) problem.

* GPower: a sparse PCA code package provided by the authors of "Journee et al., Generalized Power Method for Sparse Principal Component Analysis, JMLR 2010".

* PathSPCA: a sparse PCA code package provided by the authors of "Optimal Solutions for Sparse Principal Component Analysis, JMLR 2008"

* Greedy_DkS: our re-implementations of two greedy DkS algorithms proposed by 
"Feige et al., The Dense k-Subgraph Problem, Algorithmica, 2001" and 
"Ravi, et al., Heuristic and Special Case Algorithms for Dispersion Problems, Oper. Res., 1994", respectively.


  
		       ********************************************


** HOW-TO RUN:

For successfully running the experiments provided in this package, the users are adviced
to first run the Matlab file "path_setting.m" located at the root folder of the package.  


* To re-run the experiments on sparse PCA:

  In this group of experiments, we provide the matlab scripts to reproduce the results on three benchmark data sets used in our paper: Pitprops, Genedata and 20NG. 


 (1) Pitprops data set: 
    
     (a) cd to 'TPower_1.0/experiments/SparsePCA/Pitprops/script/X' (here 'X' represents 'TPower' or 'GPower' or 'PathSPCA') and simply run matlab script file 'test_pitprops.m'.  
     
     (b) The output results can be found in the directory 'TPower_1.0/experiments/SparsePCA/Pitprops/result'.
    
 
 (2) Genedata data set: 
 
     (a) cd to 'TPower_1.0/experiments/SparsePCA/GeneData/script/X' (here 'X' represents 'TPower' or 'PathSPCA') and simply run the three matlab script files contained in this subfolder.       

     (b) The output results can be found in the directory 'TPower_1.0/experiments/SparsePCA/GeneData/result'.  

     (c) The figures in eps can be generated by running the .m files in the directory 'TPower_1.0/experiments/SparsePCA/GeneData/result/plot_draw'.


 (3) 20NG data set: 

     (a) cd to 'TPower_1.0/experiments/SparsePCA/20NG/script/X' (here 'X' represents 'TPower' or 'PathSPCA') and simply run matlab script file 'test_20ng.m'.  

     (b) The output results can be found in the directory 'TPower_1.0/experiments/SparsePCA/20NG/result'.
 

* To re-run the experiments on DkS:


   In this group of experiments, we provide the matlab scripts to reproduce the results on the airline_usca data set and four webgraph data sets: amazon2008, crn2000, hollywood2009 and ljournal2008. 
For the experiment on 'airline_usca' data set, the Mapping Toolbox is needed to be installed in Matlab so that the map figures can be plotted.
Moreover, to successfully run the expriments on 'hollywood2009' and 'ljournal' data sets, the users of Windows XP or Windows Vista are adviced to enable the 3GB switch 
(see e.g.,'http://dwf.blogs.com/beyond_the_paper/2009/04/enabling-3gb-switch-on-windows-vista.html' for a tutorial). 
 
 (1) airline_usca data set: 

     (a) cd to 'TPower_1.0/experiments/DkS/airline_usca/script/X' (here 'X' represents 'TPower' or 'Greedy_DkS_Feige' or 'Greedy_DkS_Ravi') and simply run the matlab script files contained in this subfolder.  
     
     (b) The output results can be found in the directory 'TPower_1.0/experiments/DkS/airline_usca/result'.

     (c) The figures in eps can be generated by running the matlab script files contained in the directory 'TPower_1.0/experiments/DkS/airline_usca/plot_draw/X' (here 'X' represents 'CPU' or 'Density' or 'Maps').  
         Note that to generate figures in the 'Maps' subfolder, the Mapping Toolbox is needed to be installed in Matlab. 



 (2) amazon2008 data set: 

     (a) Download the graph matrix amazon-2008.graph and its property file amazon-2008.properties from http://law.dsi.unimi.it/webdata/amazon-2008/. 

     (b) cd to 'TPower_1.0/experiments/DkS/webgraph_amazon2008/data' and copy the two downloaded files in step (a) to this folder. Run the data_generate_amazon2008.m to generate the output data file 'data.mat'.  

     (b) cd to 'TPower_1.0/experiments/DkS/webgraph_amazon2008/script/X' (here 'X' represents 'TPower' or 'Greedy_DkS_Feige' or 'Greedy_DkS_Ravi') and simply run matlab script files contained in this subfolder.  
     
     (c) The output results can be found in the directory 'TPower_1.0/experiments/DkS/webgraph_amazon2008/result'.

     (d) The figures in eps can be generated by running the matlab script files contained in the directory 'TPower_1.0/experiments/DkS/webgraph_amazon2008/plot_draw/X' (here 'X' represents 'CPU' or 'Density').


 (3) cnr2000 data set: 

     (a) Download the graph matrix cnr-2000.graph and its property file cnr-2000.properties from http://law.dsi.unimi.it/webdata/cnr-2000/. 

     (b) cd to 'TPower_1.0/experiments/DkS/webgraph_cnr2000/data' and copy the two downloaded files in step (a) to this folder. Run the data_generate_cnr2000.m to generate the output data file 'data.mat'.  

     (b) cd to 'TPower_1.0/experiments/DkS/webgraph_cnr2000/script/X' (here 'X' represents 'TPower' or 'Greedy_DkS_Feige' or 'Greedy_DkS_Ravi') and simply run matlab .m files contained in this subfolder.  
     
     (c) The output results can be found in the directory 'TPower_1.0/experiments/DkS/webgraph_cnr2000/result'.

     (d) The figures in eps can be generated by running the matlab script files contained in the directory 'TPower_1.0/experiments/DkS/webgraph_cnr2000/plot_draw/X' (here 'X' represents 'CPU' or 'Density').



 (3) hollywood2009 data set: 

     (a) Download the graph matrix hollywood-2009.graph and its property file hollywood-2009.properties from http://law.dsi.unimi.it/webdata/hollywood-2009/. 

     (b) cd to 'TPower_1.0/experiments/DkS/webgraph_hollywood2009/data' and copy the two downloaded files in step (a) to this folder. Run the data_generate_hollywood2009.m to generate the output data file 'data.mat'.  

     (b) cd to 'TPower_1.0/experiments/DkS/webgraph_hollywood2009/script/X' (here 'X' represents 'TPower' or 'Greedy_DkS_Feige' or 'Greedy_DkS_Ravi') and simply run matlab .m files contained in this subfolder.  
     
     (c) The output results can be found in the directory 'TPower_1.0/experiments/DkS/webgraph_hollywood2009/result'.

     (d) The figures in eps can be generated by running the matlab script files contained in the directory 'TPower_1.0/experiments/DkS/webgraph_hollywood2009/plot_draw/X' (here 'X' represents 'CPU' or 'Density').


 (4) ljournal2008 data set: 

     (a) Download the graph matrix ljournal-2008.graph and its property file ljournal-2008.properties from http://law.dsi.unimi.it/webdata/ljournal-2008/. 

     (b) cd to 'TPower_1.0/experiments/DkS/webgraph_ljournal2008/data' and copy the two downloaded files in step (a) to this folder. Run the data_generate_ljournal2008.m to generate the output data file 'data.mat'.  

     (b) cd to 'TPower_1.0/experiments/DkS/webgraph_ljournal2008/script/X' (here 'X' represents 'TPower' or 'Greedy_DkS_Feige' or 'Greedy_DkS_Ravi') and simply run matlab .m files contained in this subfolder.  
     
     (c) The output results can be found in the directory 'TPower_1.0/experiments/DkS/webgraph_ljournal2008/result'.

     (d) The figures in eps can be generated by running the matlab script files contained in the directory 'TPower_1.0/experiments/DkS/webgraph_ljournal2008/plot_draw/X' (here 'X' represents 'CPU' or 'Density').

	          
                        ********************************************


** COPYRIGHT:

Copyright (C) 2011/2012 - Xiao-Tong Yuan.  

This library is distributed under GNU General Public License (see COPYING
for details).

For any questions and comments, please send your email to  xtyuan1980@gmail.com