Fall 2012 CAAM 654: Sparse Optimization

Monday and Wednesday, 4:15PM-5:30PM, Duncan 1042.
Instructor: Wotao Yin / Co-Instructor: Ming Yan
(Friendly note: Spring 2013 CAAM 654 is on Optimization in Health Care, 4-5PM Tuesday, DCH 1046)


If you need a signature on your special registration form, please send the pdf form to wotao.yin@rice.edu.

Lecture notes are password-protected. If you are auditting the class, email yanm@rice.edu for the password.


Click to view/download


Exploiting sparsity and other structures of solutions has become a common task in various computational and engineer areas including signal/image processing, compressed sensing, statistics, machine learning, data mining, and so on. Sparsity not only makes it possible to reconstruct high-dimensional signals and discover its salient information from a small number of measurements, but also makes optimization faster and enables extremely large-scale computation. A large number of novel applications have emerged to take advantages of sparsity. Starting from some application problems with structured solutions, this course gives an overview of sparse optimization theory, algorithms, and several applications. In addition, it covers implementational aspects of large-scale, parallel, and distributed computation.

Topics convered

Basics of sparse representation, compressive sensing theory such as incoherence, exact recovery, stable recovery, RIP, null-space analysis, etc.

Sparse optimization models, primal algorithms, dual algorithms, splitting and ADM algorithms, block coordinate descent algorithms, homotopy algorithms, non-convex algorithms, greedy pursuit algorithms, support detection algorithms, hard-thresholding algorithms, low-rank matrix recovery algorithms. The course will not be a boring comprehensive review of all the algorithms.

Emphasis is given to comparing different algorithms in terms of recovery accuracy, convergence speed, implementation difficulties, generalization potential, parallel and distributed computing abilities, etc.

Office hours

After class or by appointment


Linear algebra and MATLAB programming. Convex optimization (recommended but not required).


none, but lecture notes and papers will be available

Course workload

No homework. Students will code and compare algorithms. One final project that requires programming and presentation.


3 credit hours.

Exceptional situations

Per the “No Note” policy, you should notify your instructor as soon as possible should any illness, emergency situation, travels, or other tasks arise that may cause you to miss the deadline for any assignment or exam. Extension requests will not be granted in case of late (e.g., last minute) notifications.

Any student with a disability requiring accommodations in this class is encouraged to contact her/his instructor after class or during offi cehour s,a ndal so toconta cttheDisability Support Services officein the Student Center.