Universal compressed sensing estimation - software
A new and greatly improved implementation by
size- and level- adaptive MCMC
approach. We greatly recommend using the new implementation,
instead of the one featured below.
Junan Zhu, Dror Baron, and Marco Duarte, December 2014
This webpage describes the
used in our work on universal compressed sensing signal estimation,
described in the following paper,
The software was implemented by
based in part on an earlier implementation by
Dror Baron for universal lossy compression in joint work with
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
Feel free to also browse through other
software packages developed by our group.
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.
Other Matlab routines
- 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).
Back to my homepage.