Data Compression: Entropy and Sparsity Perspectives

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 the 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.