Data Compression, Compressive Sensing, and Modern Coding

  • RS

    Instructor:  Prof. Dr.-Ing. Werner Henkel

    Many sensing applications come with an enormous amount of data, be it, e.g., MRI scans which require a patient to lie completely still for in the order of 20 minutes under stressful noise, distributed sensing for geo or pollution data, or when describing disturbances in wireless transmission. One could go for classical data compression schemes which already offer the possibility to make use of correlations between sources by the so-called Slepian-Wolf coding. Compressive sensing, however, allows to exploit sparsity properties of the data in some transform domain. A relaxation leads to algorithms based on convex programming, just as linear programming, known as basis pursuit. Sparsity is, however, a general principle and is also used in modern coding schemes, like Low-Density Parity-Check codes or Luby-Transform codes, used in many transmission schemes and networking applications. The course should provide the basics of all those fields to work out common properties, finally providing the foundation for a joint treatment, e.g., using decoding algorithms for compressive sensing tasks.

    Lecture at Jacobs University [Campusnet link].


    • Basics of probability, Entropy definition, binary entropy function
    • Conditional entropy, mutual information
    • Examples entropy and conditional entropy, Markov models and its entropy, stationary state, periodic and irreducable Markov chains, shortly, Fano’s lemma, typical sequences, uniquely and instantaneously decodable codes
    • Huffman coding, Lempel-Ziv 77, 78, and Lempel-Ziv-Welch 84 alg.
    • Shannon-Fano-Elias coding, Arithmetic coding
    • Burrows-Wheeler transform, run-length encoding, move-to-front encoding, PPM, Context Tree Weighting
    • Application of source coding argorithms in gene compression
    • Basics of error-correcting codes, Slepian-Wolf coding
    • Concepts of compressive sensing (norms, sparsity, linear program) and link to the parity-check equation
    • Fourier series and transform, DFT, sampling theorem
    • Wavelets, time-frequency methods, Gabor transform, Wigner-Ville distribution, …
    • Deterministic compressive sensing and Reed-Solomon codes, uncertainty principle
    • Basis Pursuit and Restricted Isometry Property
    • Convex optimization
    • Selected applications (student / instructor presentations)
    • LDPC codes
    • LT and network coding
    • Message Passing and Approximate Message Passing

    Please Login or Register for access.

  • Please Login or Register for access.