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

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.