MATH 555: Compressed Sensing


Announcements

    First meeting: Thursday, Jan 5th, 2:00 pm in room MX 1102
    Jan 9: We will meet Tuesdays and Thursdays, 12:30-1:50 pm in room MATH 225.

Instructor Information
Instructor: Ozgur Yilmaz
Email : oyilmaz-at-math.ubc.ca
Office: Math Annex 1113
Hours:  By appointment
Phone: 822-5963

Course Information

Class times and location: Tue-Th, 12:30-1:50 pm in room MATH 225


Course outline

This course is on mathematical signal processing. After a review of the classical processing paradigm (first two sections of the outline below)---which is well-established and based heavily on ideas from harmonic analysis---we will discuss sparse approximations and compressed sensing, focusing on both mathematical and algorithmic aspects.

In the first part, I will discuss the big picture and provide the basic mathematical framework that is used to decompose certain types of signals in an efficient manner that is crucial to practical applications such as analog-to-digital conversion and compression. The only result I will give a formal proof in this part is the classical sampling theorem.

A (tentative) detailed outline is as follows:

Part 1: Classical mathematical signal processing: sampling and transform coding

1. An overview of mathematical preliminaries
        Banach and Hilbert spaces (basics)
        Bases and frames in Hilbert spaces
        Fourier series and Fourier transforms

2. Some results from classical mathematical signal processing
        Classical sampling theorem    
        Time-frequency analysis and wavelets
        Applications (image, audio, etc)

Part 2: Sparse approximations and compressed sensing

3. Sparse approximations (related reference material)
        Sparsity and redundant dictionaries (e.g., union of two orthonormal bases)
        Greedy algorithms for sparse approximation -- theoretical and practical issues
        1-norm minimization for sparse approximation -- theoretical and practical issues
        Applications

4. Compressed sensing (related reference material)
        Connection to sparse approximations
        Compressive measurement matrices -- deterministic criteria for stable and robust recovery
            Null-space property
            Restricted isometry property
            Recovery guarantees for 1-norm minimization
            Recovery guarantees for greedy algorithms
        Compressed sensing with random matrices
            - (sub-)Gaussian matrices and measure concentration
            -  random Fourier sampler (i.e., use only a small number of randomly selected DFT coefficients) 
        Some approximation theory: optimality results
        Compressed sensing and quantization       

Text Book.  There is no required textbook. Relevant material will be posted on this web page.

Supplementary Text.

A wavelet tour of signal processing -- the sparse way (Third Edition), Stephane Mallat

More reference material will be posted here.



Grading
There will be homework assignments (one every two weeks) (50%) and a term project (50%).

Prerequisites
I intend the course to be (more or less) self contained. It would be beneficial to have some background in functional analysis and harmonic analysis as well as in signal processing and information theory. Contact me if you have specific questions.