Theses: Graph-based Techniques for Compression and Reconstruction of Sparse Sources
Ramirez Javega

Abstract

The main goal of this thesis is to develop lossless compression schemes for analog and binary
sources. All the considered compression schemes have as common feature that the encoder can
be represented by a graph, so they can be studied employing tools from modern coding theory.
In particular, this thesis is focused on two compression problems: the group testing and the
noiseless compressed sensing problems. Although both problems may seem unrelated, in the
thesis they are shown to be very close. Furthermore, group testing has the same mathematical
formulation as non-linear binary source compression schemes that use the OR operator. In this
thesis, the similarities between these problems are exploited.
The group testing problem is aimed at identifying the defective subjects of a population with
as few tests as possible. Group testing schemes can be divided into two groups: adaptive and
non-adaptive group testing schemes. The former schemes generate tests sequentially and exploit
the partial decoding results to attempt to reduce the overall number of tests required to label all
members of the population, whereas non-adaptive schemes perform all the test in parallel and
attempt to label as many subjects as possible.
Our contributions to the group testing problem are both theoretical and practical. We propose a
novel adaptive scheme aimed to efficiently perform the testing process. Furthermore, we develop
tools to predict the performance of both adaptive and non-adaptive schemes when the number
of subjects to be tested is large. These tools allow to characterize the performance of adaptive
and non-adaptive group testing schemes without simulating them.
The goal of the noiseless compressed sensing problem is to retrieve a signal from its lineal
projection version in a lower-dimensional space. This can be done only whenever the amount of
null components of the original signal is large enough. Compressed sensing deals with the design
of sampling schemes and reconstruction algorithms that manage to reconstruct the original signal
vector with as few samples as possible.
In this thesis we pose the compressed sensing problem within a probabilistic framework, as
opposed to the classical compression sensing formulation. Recent results in the state of the art
show that this approach is more efficient than the classical one.
Our contributions to noiseless compressed sensing are both theoretical and practical. We deduce
a necessary and sufficient matrix design condition to guarantee that the reconstruction is lossless.
Regarding the design of practical schemes, we propose two novel reconstruction algorithms based
on message passing over the sparse representation of the matrix, one of them with very low
computational complexity.


Full document




©UPC Universitat Politècnica de Catalunya
Signal Processing and Communications group
Powered by Joomla!.