%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%      Matlab Codes package (Version 2.1) for		   %
%	ExCoV: Expansion-Compression Variance-component    %
%   Sparse Signal Reconstruction from Noisy Measurements %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Authors: A. Dogandzic and K. Qiu
The Matlab codes are written and debugged by Kun Qiu.
Tested Configurations: Matlab 7.2.0.232(R2006a) on PC

The codes in this package are free program. You are welcome to use them for academic 
purposes. If you use this code in your research and publications, please put a reference to our paper. 
If you find any bug or have any suggestion, please contact the authors through
email: ald@iastate.edu and/or kqiu@iastate.edu.


%%%%%%%%%%%%%%% File list %%%%%%%%%%%%%%%%
--root folder
	"Spike.m":			This is the test bed file in which sparse signal and sensing matrices are generated 
					and various reconstruction algorithms are called to recover the signal.
	"ImageEx.m":		This is the test file of 2D tomographic imaging example.
--folder "Algorithms"
	"ExCoV.m":			Our core ExCoV reconstruction function.
	
	"ExCoVapp.m":		Our core approximate ExCoV reconstruction function.

	"ExCoVls":			Our large scale ExCoV reconstruction function in which the sensing matrix is implemented in function handle and 
					conjugate gradient is used to invert the linear system. 

	"CoSaMP.m":			The CoSaMP reconstruction algorithm designed by D. Needell and J. A. Tropp 
					"CoSaMP: Iterative signal recovery from incomplete and inaccurate samples";
					this file is coded by Kun Qiu.

	"hard_l0_Mterm_mod.m":	The (normalized) hard thresholding algorithms by T. Blumensath and M. E. Davies;
					the original file "hard_l0_Mterm.m" can be downloaded at:
					http://www.personal.soton.ac.uk/tb1m08/sparsify/sparsify.html
					Kun Qiu has modified the original file to incorporate a more common 
					convergence criterion.
	
	"SBL.m":			The sparse Bayesian learning method by D.P. Wipf and B.D. Rao., see
					"Comparing the effects of different weight distributions on finding sparse representations",
					and "Sparse Bayesian learning for basis selection";
					this file is coded by Kun Qiu.

	"BCS_fast_rvm.m":		The Bayesian compressive sensing method by Shihao Ji, Ya Xue, and Lawrence Carin,
					downloaded at: http://people.ee.duke.edu/~lihan/cs/

	"GPSR_BB.m":		The Gradient Projection for Sparse Reconstruction method by Mário Figueiredo, Robert D. Nowak, Stephen J. Wright,
					downloaded at: http://www.lx.it.pt/~mtf/GPSR/

	"l1qc_logbarrier.m" and
	"l1qc_newton.m":		Stable signal recovery from incomplete and inaccurate measurements by E. Candes, J. Romberg, and T. Tao,
					downloaded at l1-magic suite: http://www.acm.caltech.edu/l1magic/
--folder "subfunctions"
	The files in this folder are only useful in the tomographic imaging example "ImageEx.m". 
	Most of them are from Rice wavelet toolbox and can be downloaded from http://www-dsp.rice.edu/software/rice-wavelet-toolbox.
	Files "A_fhp.m", "At_fhp", and "LineMask" are from l1-magic suite: http://www.acm.caltech.edu/l1magic/.
	Files "H_idwt1d.m", "Ht_dwt1d.m" and "psnr.m" are created by Kun Qiu.
 


%%%%%%%%%%%%%%% Quick Start %%%%%%%%%%%%%%%%%
As a quick demo, simply type "Spike" in the Matlab command window and see. 

To see the tomographic imaging example, open "ImageEx.m" file and run.

%%%%%%%%%%%%%%% User Guide for ExCoV core function %%%%%%%%%%%%
The ExCoV algorithm can surely be plugged in other applications that you come up with. 
The ExCoV function (as well as many other sparse reconstruction methods) simply solves 
the underdetermined linear system: 
					y=Hx+e
where H is fat matrix and e is some small additive noise.

Calling ExCoV algorithm is extremely easy: you just need to input the measurement y and
the sensing matrix H, and ExCoV will output the sparse solution x_hat.
[Matlab code: x_hat=ExCoV(H,y)]

There are other useful outputs you may want to know, eg: noise variance \sigma2, 
number of iterations, support set of high signal coefficients, the following 
code example will do the job:
[Matlab code: [x_hat,sigma2_hat,Support,Count]=ExCoV(H,y)]

Our ExCoV method is automatic in that we do not have many tuning parameters as other
methods do. We do not need any convergence tolerance level or any form of threshold to make
the algorithm work. The only tunable variable is the moving average window size, which is 
employed only because we do not want to cease the "spike-digging" process prematurely. 
In fact, the choice of moving average window size is very insensitive to the performance
of the algorithm. The default value is 10 and I believe this number will work for almost all
applications. 

If you run the demo "Spike" file, you will see that our ExCoV works in a transparent fashion:
it plots every single step of the entire reconstruction process. If the figure ExCoV draws
annoys you, you have option to shut it off and make ExCoV work silently. To achieve this, all
you need to do is set the optional variable 'Visibility' to be zero. The following syntax will do:
[Matlab code: x_hat=ExCoV(H,y,'Visibility',0);]

For the details of the usage of optional inputs, open the "ExCoV.m" file and read the 
instructions therein.

The "Spike" file is operating system independent.

The tomogoraphic imaging example is only tested on PC; for those who want to run on Mac, 
you need to download and unwrap the appropriate wavelet toolbox at 
http://www-dsp.rice.edu/software/rice-wavelet-toolbox
and add the path of the obtained files in MATLAB.
We have not tested our image example on other operating system. 


%%%%%%%%%%%%%%%% To reproduce the figures %%%%%%%%%%%%%%%%
For those of you who want to recover the mean squared error curves in Fig.2 and 3 on the webpage, 
simply go into the "Spike" file, re-specify the parameters at the beginning of the file and run. 
Specifically, we computed mean squared error by averaging 2000 trails, so set TrialNum=2000; we also
vary the number of measurements N from 90 to 140; to select the signal type, simply set the 
SignalType variable to 0 (binary sparse signal) or 1 (Gaussian sparse signal). 
Collect the MSE data under different parameter sets (the "Spike" file will 
automatically save the  data with appropriate name according to the parameters) and plot them.

To recover the 2-D tomographic imaging example in Fig.4 on the webpage, open the "ImageEx.m" file and
run. To reprodice the PSNR curve in Fig.5, re-specify the parameter "RadialNum" from 26 to 43 with increment by 1, collect
the data under different number of radial lines (thereby different measurement ratio N/m) and plot them.



Version: 2.1
Date posted: Dec. 29, 2009



