Readme.txt

This file describes the implementation of our universal compressed sensing
paper,

D. Baron and M. Duarte, Universal MAP Estimation in Compressed Sensing,
Proceedings of the 49th Allerton Conference on Communication, Control, and 
Computing, Monticello, IL, September 20011.

This implementation is based in part on an earlier implementation by 
Dror Baron for universal lossy compression in joint work with Tsachy Weissman:

http://people.engr.ncsu.edu/dzbaron/software/RD_BaronWeissman/

The current implementation uses the Markov chain Monte Carlo framework pioneered
by Jalali and Weissman in a compressed sensing framework where instead of approximating
an input we approximate an unknown input from linear measurements.

Dror Baron and Marco Duarte, 9.2011
-----------------


MAIN MATLAB FILES
-----------------

test_production_temps.m - script that runs multiple simulations of compressed 
signal estimation problem for several types of signals, as described in Section
VI of the paper.

count_update_all.m - evaluates all possible symbols and computes
Gibbs distribution; then generates new symbol and updates data
structures accordingly. Instead of working directly on the context
counts data structure, only locations of changes are saved; this
accelerates performance when the context count matrix is big.

CS_MCMC.m - The actual signal estimation algorithm. Sets up data 
structures for contexts and optimization of ell2 error; runs d_update and 
count_update_all each iteration to update data structures.

ell2_update.m - Examines all possible characters beta to replace the current
character in the sequence. For each such beta, we compute the optimal representation 
levels qZ that minimize the ell2 error between measurements y and Phi*qZ(z'), where
qZ(z') is currently estimated x. Knowing ell2(y-Phi(z'))^2 allows us to compute the 
delta (the change) in the ell2 when swapping the character. To compute the optimal 
reproduction levels we need to compute mldivide(mu'*mu,mu'*y), these are data
structures related to computing the ell2 error. However, coputing the Gram matrix mu'*mu 
is computationally intense, and to a lesser extent computing mu'*y is also intense. 
To reduce computation, we compute the Gram matrix and mu'*y once, and update them later 
each time we evaluate a different character.
(1) Gram update: when one column of mu is changed, we need only change one row of the Gram 
and one column. Each of these is changed in the same way, because the Gram is symmetric.
(2) updating mu'*y only requires to change one location in the mu_y vector, because other 
columns of mu corresponding to other entries of mu_y are unchanged.

GRAPHICS
--------

graph_production_marco.m - Script that loads data generated by simulations and 
plots the mean estimation error.

graph_production_marco_median.m - Plots the median estimation error.

axisfortex.m - sets font sizes for figures.


OTHER MATLAB ROUTINES
---------------------
alph2int.m - converts string over finite alphabet into integer.

compute_levels.m - computes optimal (in ell2 sense) reproduction levels,
as discussed in Section V in the paper.

compute_mu.m - mu is a set of auxiliary variables used to set up
the linear system used to optimize distortion levels in compute_levels.m

count.m - creates depth-k context counts for finite alphabet.

ell2_error.m - computes squared ell2 error between measurements y and 
Phi*x for estimated signal x.

entropy.m - computes per-context entropy. Redundancy for unknown
conditional empirical statistics is not accounted for, and so this
is a slight under-estimate of actual coding length.

H_m.m - computes conditional empirical entropy for entire matrix m of 
context counts (entire sequence).


