Stats 330 (CME 362)
An Introduction to Compressed Sensing
Spring 2010

fully sampled	6X undersampled	6X undersampled with CS reconstruction

Photographs courtesy of Trzasko, Manduca, Borisch

Catalog description: Compressed sensing is a new sampling/data acquisition theory asserting that one can exploit sparsity or compressibility when acquiring signals of general interest, and that one can design nonadaptive sampling techniques that condense the information in a compressible signal into a small amount of data. This fact may change the way engineers think about signal acquisition in areas ranging from analog-to-digital conversion, digital optics, magnetic resonance imaging, and seismics. The discoveries made in this field inform a number of statistical problems related to parameter estimation in high dimensions, and problems having to do with the recovery of large data matrices from incomplete sets of entries (the famous Netflix Prize). Course covers 1) fundamental theoretical and mathematical ideas 2) efficient numerical methods in large-scale convex optimization for reconstructing signals and images from compressive samples 3) progress in implementing compressive sensing ideas into acquisition devices. The course will emphasize the many connections with information theory, statistics, and probability theory. Course objectives: This is a seminar-style course with the following goals: to present the basic theory and ideas showing when it is possible to reconstruct sparse or nearly sparse signals from undersampled data to expose students to recent ideas in modern convex optimization allowing rapid signal recovery or parameter estimation to give students a sense of real applications that might benefit from compressive sensing ideas The overarching theme is to expose students to a novel active field of research and give them the tools to make theoretical and/or practical contributions. Prerequisite: Familiarity with the following subjects: probability theory, and especially ideas from large deviations theory statistical estimation, model selection, and especially ideas from decision theory linear algebra basic convex analysis and optimization Syllabus: Sparsity L1 minimization Probabilistic approach to compressed sensing Deterministic approach to compressed sensing Robustness vis a vis noise Sparse regression Smooth convex optimization: optimal first-order methods (Nesterov's algorithm), complexity analysis Nonsmooth convex optimization: smooth approximations of nonsmooth functions, prox-functions, Nesterov's algorithm Mirror-descent algorithms Applications in magnetic resonance imaging (MRI) Applications in analog-to-digital conversion Low-rank matrix recovery Nuclear-norm minimization Textbooks: There is no required text but the following titles may prove useful Probability and Random Processes by G. Grimmett and D. Stirzaker, 3rd. ed., Oxford University Press Random Matrices by M. Mehta, 3rd ed., New York: Academic Press Function Estimation and Gaussian Sequence Models by I. Johnstone (PDF), Chapter 13 (PDF) All of Statistics by L. Wasserman, Springer Numerical Linear Algebra by LLoyd N. Trefethen and David Bau, III, SIAM Convex Optimization by S. Boyd and L. Vandenberghe, Cambridge University Press Introductory Lectures on Convex Optimization: A Basic Course by Y. Nesterov, Kluwer Academic Publisher A Wavelet Tour of Signal Processing by S. Mallat, 3rd ed., Academic Press Discrete Time Signal Processing by A. Oppenheim and R. Schafer, Prentice Hall Handouts: All handouts will be posted online. Course assistant and office hours: Xiaodong Li () MW 2-3 ( (Building 380, room 380-T) Yaniv Plan () T 2:15-3:45 (Building 380, room 383H2) Grading: Homework assignments account for 100% of the final grade. There will be a maximum of three problem sets. Late homeworks will NOT be accepted for grading (medical emergencies excepted with proof). It is encouraged to discuss the problem sets with others, but everyone needs to turn in a unique personal write-up. Course policies: Use of sources (people, books, internet and so on) without citing them in homework sets results in failing grade for course.