image of UIUC logo

ECE 598YM - Sparse Representation and High-Dimensional Geometry
with Applications in Signal Processing and Pattern Recognition

Fall 2008, ECE, University of Illinois at Urbana-Champaign

 
"It is vain to do with more what can be done with less."          

                              ---- William of Ockham

[ Announcements | Administrative | Handouts | Homeworks | Resources]

Announcements

Administrative Information

 Instructor: Professor Yi Ma
Lectures: Tuesday & Thursday 10:30am-11:50am, 170 Everitt Lab
Office hours: Tu 1:30pm-3:00pm, 145 Coordinated Science Lab
Office: 145 CSL, Phone: 244-0871
Email: yima@uiuc.edu
After hour appointments: through email.

Teaching Assistant: John Wright
Office hours: Friday 2-3pm, 146 Coordinated Science Lab
Email: jnwright@uiuc.edu
Course Discription:
This course covers recent developments of the new mathematical theory of sparse representation and compressed sensing in statistical signal processing, especially the concepts and results that can be readily applied to pattern recognition, computer vision, and signal (image, speech) processing. As this is a fastly evolving aera, it is my intension to study these new results together with all of the participants throughout the semester. So you do not have to be afraid that you do not know much about this topic, because neither do I.

Recommended Texts:
However, this course does not follow closely any textbook or lecture notes. Very often will we be presenting and discussing papers published recently on this topic. Related papers will be listed below.

Grading Policy: Homework & Paper Reading (60%), and Final Project (40%). The final project can be done in a group of 2 or 3 students. The project can be theoretical, experimental or a mixture of both. It consists of a midterm proposal, a final presentation (in class) and a web-based report.

Course Outline: ECE598YM Course Outline (tentative).

Handouts

 Incoherence and Pursuit Algorithms:
  • A Generalized Uncertainty Principle and Sparse Representation in Pairs of R^N Bases , Michael Elad, Arie Feuer, and Alfred M. Bruckstein, 2001.
  • From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images, Alfred M. Bruckstein, David L. Donoho, and Michael Elad, 2007.

    Ristricted Isometry and L1 Minimization:
  • Decoding by Linear Programming, Emmanuel Candes and Terrence Tao, 2004.
  • Enhancing Sparsity by Reweighted L1 Minimization, Emmanuel Candes, Michael Wakin and Stephen Boyd, 2007.
  • A Simple Proof of the Restricted Isometry Property for Random Matrices, Richard Baraniuk, Mark Devenport, Ronald DeVore, and Michael Wakin, 2008.
  • An Elementary Proof of a Theorem of Johnson and Lindenstrauss, Sanjoy Dasgupta and Anupam Gupta, 2002.
  • Dense Error Correction via L1 Minimization, John Wright and Yi Ma, 2008.

  • Tight Bounds for Distributed Selection, Fabian Kuhn, Thomas Locher, and Roger Wattenhofer, 2007. (This paper is for pleasure reading and not necessarily related).

    Almost Euclidean Subspaces, Combinatorics, and Coding Theory:
  • Euclidean Subspaces and Compressed Sensing, Lecture by Venkat Guruswami, 2007.
  • Almost Euclidean Subspaces of L1 via Expander Codes, Venka Guruswami, James R. Lee, and Alexander Razborov, 2007.
  • Combining Geometry and Combinatorics: A Unified Approach to Sparse Signal Recovery, R. Berinde, A.C. Gilbert, P. Indyk, H. Karloff, and M.J. Strauss, 2008.

    Rank Minimization and Nuclear Norm:
  • Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization, Benjamin Recht, Maryam Fazel, and Pablo Parrilo, 2007.
  • Exact Matrix Completion via Convex Optimization, Emmanuel Candes and Benjamin Recht, 2008.

    High-Dimensional Polytope Geometry:
  • Neighborly Polytopes and Sparse Solution of Underdetermined Linear Equations, David L. Donoho, 2004.
  • High-Dimensional Centrally-Symmetric Polytopes with Neighborliness Proportional to Dimension, David L. Donoho, 2005.
  • Neighborliness of Randomly-Projected Simplices in High Dimensions, David L. Donoho and Jared Tanner, 2005.
  • Counting Faces of Randomly-Projected Polytopes with the Projection Radically Lowers Dimension, David L. Donoho, and Jared Tanner, 2005.
  • Counting Faces of Randomly-Projected Hypercubes and Orthants, with Applications, David L. Donoho and Jared Tanner, 2008.
  • Sharp Concentration of Random Polytopes, V.H. Vu, 2005.
  • Minimum Sum of Distance Estimator: Robustness and Stability, Yoav Sharon, John Wright, and Yi Ma, 2008. (Computing the breakdown of a deterministic matrix).

    Algorithms:
  • Fast Solution of L1-norm Minimization Problems Whent the Solution May be Sparse, David L. Donoho and Yaaokov Tsaig, 2006.

    Applications:
  • Robust Face Recognition via Sparse Representation, John Wright et. al., PAMI, 2008.
  • Image Supre-Resolution as Sparse Representation of Raw Image Patches, Jianchao Yang, John Wright et. al., CVPR, 2008
  • Face Hallucination via Sparse Coding, Jianchao Yang, et. al., ICIP, 2008.
  • Motion Segmentation via Robust Subspace Separation in the Presence of Outlying, Incomplete, or Corrupted Trajectories, Shankar Rao et. al., CVPR, 2008.
  • Distributed segmentation and classification of human actions using a wearable motion sensor network, Workshop on Human Communicative Behavior Analysis, CVPR 2008. Allen Yang et. al., 2008.
  • Learning to Sense Sparse Signals: Simultaneous Sensing Matrix and Sparsifying Dictionary Optimization, Julio Martin Duarte-Carvajalino and Guillermo Sapiro, 2008.

    Useful Resources

    Homeworks & Solutions


    Yi Ma | yima@uiuc.edu
    Last updated 08/24/08