Sparse Optimization, July 2013

Instructor: Wotao YIN
Teaching assistants: Wei SHI and Kun YUAN
Time: 9:00 am - 12:00 noon (except 9:45 am for July 3)
Dates: July 3/4/5, 10/11/12, 17/18/19, and 24 (possibly extending to July 25/26)
 

Announcements

  • The first class begins at 9:45am on July 3rd.

  • Lectures will be recorded. The videos will be open to the USTC campus.

Scope

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.

This short summer course gives an overview to sparse optimization with a focus on its high-performance computational methods.

Topics convered

  • Overview of convex optimization and sparse optimization (motivations, applications, and basic formulations)

  • Sparsity, dictionary, low-rank matrices, low-dimensional manifolds

  • Sparse signal recovery guarantees (only briefly)

  • Sparse optimization algorithms

    • subgradient, gradient, accelerated gradient, proximal, operator splitting, and stochastic methods

    • methods for problems with single, separable, and partially separable objective functions with or without constraints

    • primal, dual, and primal/dual operator splitting methods

    • smoothing methods

    • greedy methods

    • parallel and distributed methods and implementations for big data

Open questions, including difficult ones, will be assigned as homework and project assignments.

Online discussion

Textbook

none, but lecture notes and papers will be posted before each class

Credit

3 credit hours.