Junan Zhu, Dror Baron, and Marco Duarte, December 2014

• 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 (pdf, talk).

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.

Below is a brief description of files used in our implementation. Comments will be appreciated.

Dror Baron and Marco Duarte, September 2011

Dror, October 2011

• 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.

• 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.

• 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).