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 analogtodigital
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 largescale 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
seminarstyle 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 firstorder methods
(Nesterov's algorithm), complexity analysis
 Nonsmooth convex optimization: smooth
approximations of nonsmooth functions, proxfunctions,
Nesterov's algorithm
 Mirrordescent algorithms
 Applications in magnetic resonance imaging (MRI)
 Applications in analogtodigital conversion
 Lowrank matrix recovery
 Nuclearnorm 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 23 ( (Building 380, room 380T)

Yaniv Plan () T 2:153: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 writeup.
Course policies:
Use of sources (people, books, internet and so on)
without citing them in homework sets results in failing
grade for course.
