MATH 555: Compressed Sensing (2018 WT2)


Announcements

First meeting: Thursday, Jan 3rd, 3:30 pm in room MATH 202.

Jan 8 New time/classroom: We will meet Thursdays, 2-5pm in room MATX 1102.
   
Instructor Information
Instructor: Ozgur Yilmaz
Email : oyilmaz-at-math.ubc.ca
Office: Math Annex 1113
Hours:  By appointment

Course Information

Class times and location: Th, 2-5pm, MATX 1102


Course outline

This is a course is on the mathematical theory of compressed sensing focusing on both mathematical and algorithmic aspects.

A (tentative) detailed outline is as follows:


1. General overview

  • Sparse approximation and compressed sensing: motivation, mathematical framework, and examples from applications 

2.  Sparse solutions of underdetermined systems

  • Sufficient conditions for recovery of sparse signals, stability and robustness issues, computational complexity
  • Tractable algorithms for sparse recovery: one-norm minimization (basis pursit), greedy algorithms

3.  Theoretical recovery guarantees for one-norm minimization: deterministic analysis

  • Null space property
  • Coherence
  • Restricted isometry property (RIP)

4. Random matrices and the RIP

  • Concentration of measure for sub-Gaussian matrices
  • The Johnson-Lindenstrauss lemma (a detour)
  • Bounded orthonormal systems (e.g., partial Fourier sampler)

5. Some approximation theory: optimality and Gelfand widths

6. Generalizations and extensions

  • Low-rank matrix and tensor recovery
  • Quantized compressed sensing
  • ...     



Text Book.  I will generally follow "A mathematical introduction to compressive sensing" (Simon Foucart and Holger Rauhut). This book is available as an e-book at the UBC Library.




Grading
There will be homework assignments (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.