Denoising, lossy compression, and signal estimation:
There are fundamental connections between denoising, lossy compression, signal estimation
(including in the linear setting of compressed sensing),
and other statistical inference problems.
For example, a denoising problem where an input x is observed with noise z,
y=x+z, can be solved by applying a lossy compressor to y. That is, we seek the portion
of y that is compressible and thus has low entropy.
Over the last several years, we have been exploring a framework based on the
minimum description length (MDL) principle to solve these sorts
of problems. This line of work started when
Tsachy Weissman
and I took his previous work on universal lossy compression of binary vectors
and extended it to lossy compression of continuous-valued signals.
An MDL approach to compressed sensing:
Recall the above optimization problem for compressed sensing (CS),
ŵ=argmin_{w}{U(w)+ λ||y-ΦQ(w)||^{2}}.
A brute force optimization over w is computationally intractable. Instead, we propose
an algorithmic approach based on Markov chain Monte Carlo (MCMC). This approach is
reminiscent of our framework for lossy data compression.
In our objective function, we first need to quantize the estimate w.
A judicious design of our quantization levels is crucial.
On the one hand, with a small number of fixed quantization levels, w will
suffer from large quantization errors.
On the other hand, a large number of levels will make it difficult for the algorithm
to converge, not to mention that the algorithm will become much slower.
Due to these limitations, we developed a four-stage framework
(size- and level-adaptive MCMC, SLA-MCMC) that adaptively matches the
complexity of w to that of the true underlying alphabet of the signal.
A flowchart for SLA-MCMC is shown in the following figure,
where L(r) denotes running r iterations of a level-adaptive MCMC
algorithm that uses a fixed number of levels while adaptively adjusting
the quantization levels; MERGE, ADD-out, and ADD-in are three
procedures that remove or add levels to the current quantizer; D1-D3
are critetia to determine when to carry out these three procedures
(details appear in our papers).
The estimation quality of SLA-MCMC is comparable and in many cases better than existing
algorithms. The following figure illustrates the estimation quality of SLA-MCMC and some
existing algorithms. The quality is quantified by the mean signal-to-distortion ratio
(defined as the signal energy divided by the mean squared error; the higher the better)
for a two-state Markov source with a zero state and a non-zero state,
where non-zeros follow a uniform distribution, U[0,1].
J. Zhu,
D. Baron, and
M. F. Duarte,
"Recovery from Linear Measurements with Complexity-Matching
Universal Signal Estimation,"
IEEE Trans. Signal Proc., vol. 63, no. 6, pp. 1512-1527, March 2015
(arxiv,
pdf,
Matlab).
J. Zhu,
D. Baron, and
M. F. Duarte,
"Complexity-Adaptive Universal Signal Estimation for Compressed Sensing,"
Proc. Stat. Signal Process. Workshop, Gold Coast, Australia, June 2014
(pdf,
poster).