Gegevenscompressie: Entropie en Sparsiteitsperspectieven

The course covers a comprehensive overview of data compression and its connections to information
theory and compressed sensing. The course content is presented in two parts: the first part covers data
compression based on entropy, and the second part discusses compression based on sparsity.
The first part introduces the fundamentals of the mathematical theory of information developed by
Shannon. The course starts from probability theory and discusses how to mathematically
model information sources. Entropy is established as a natural measure of efficient description length of
optimally compressed data. Then, Shannon's source coding theorem is discussed, followed by the entropy
encodings of Huffman and arithmetic coding used in lossless data compression.

The second part introduces the notion of sparsity and gives an overview of the area of compressed
sensing. It starts with the classical techniques to solve underdetermined linear systems. Then, the core
problem of compressed sensing, namely the L0 norm minimization with linear constraints, is introduced.
The compressed sensing problem is motivated using example applications from wireless communication,
control, and image processing. The L0 norm is shown to be NP-hard, and several classical approximate
algorithms like L1 norm minimization, orthogonal matching pursuit, and thresholding algorithms are
discussed. Building on the classical solutions, more advanced solution techniques are then covered. The
first approach is the sparse Bayesian framework that introduces general statistical tools such as
majorization-maximization and expectation-maximization. The next state-of-the-art approach is the deep
learning framework based on autoencoders and generative adversarial networks. This part closes with
the theory of compressed sensing. Here, the mathematical concepts of spark, null space property, and
restricted isometric property are introduced. Using these concepts and properties, the theoretical
performance guarantees of the standard compressed sensing algorithms are studied.