CMSC828J Advanced Topics in Information Processing:
Subspaces and Manifolds for Computer Vision
and Machine Learning
General Information 


Announcements:
Midterm is here. Data for problem 4 is here, with readme. Due on Wed. April 3.
Review for final is here.
Description
Linear subspaces and other manifolds are widely used to represent data. Dimensionality reduction is often a driving motivation. For example, Principal Component Analysis (PCA) represents data by projecting it into a lowdimensional space that best captures the data, providing a representation that captures the intrinsic dimensionality of the data. Many other linear approaches exist, which used supervised information (eg., LDA) or attempt to represent multiple data sets in a common space (eg., CCA, PLS). Manifold learning approaches represent data using lowdimensional, nonlinear manifolds. Even when they don’t perform dimensionality reduction, Riemannian manifolds offer the opportunity to make use of nonEuclidean metrics that better capture the relationship between data elements. These approaches have been widely studied and used in machine learning, computer vision and other application areas, such as Natural Language Processing.
In this class we will study these
techniques. The class will be a mix
between lectures, in which we study the mathematics behind linear subspaces and
Riemannian manifolds, and reading and discussion of papers that develop and
apply these methods to various application areas. We will emphasize their use in computer
vision (because that’s what the instructor knows about) but will be happy to
discuss a range of other application areas that may be of interest to the
students of the class.
Prerequisites
Knowledge of and comfort with mathematics
will be very helpful. At a minimum,
students should know multivariable calculus and linear algebra. No knowledge of manifolds, Riemannian
geometry, or differential geometry will be assumed.
Here is my current plan for the workload of the class. This may change during the first two weeks, as the number of students settles down.
1) Reports. There will be some classes in which we discuss research papers. Prior to each of these classes, students must turn in a one page report on the papers to be discussed. I prefer if you turn in a hardcopy to me at the start of class. Late papers will not be accepted, since the goal of these reports is to get you to think about papers before we discuss them. However, each student need not turn in a report on days when they are presenting a paper. The current schedule calls for ten classes with discussions, but this number may change as the semester evolves. Students will be required to turn in no more than 8 reports. 10% of grade
2) Presentations. Students will be divided into six groups. Each group will take charge of one class. They are responsible for selecting papers on a specific topic, presenting these papers and leading a discussion on them. In running a successful class, you will be expected to accomplish four things: 1) Clearly explain material in the papers you have chosen. Your presentation should be clearer than the papers, not just a regurgitation of them. 2) You should bring in material that goes beyond that in the papers chosen for discussion. This may include, for example, reimplementing methods in the papers and describing new experiments with them, or describing relevant work in additional papers. 3) You MUST bring your own insights to the presentation. 4) You must lead a discussion involving the class. All teams should schedule a one hour meeting with me at least one week before the class they are leading, in which they will give a dry run of their presentation. 15 % of grade.
3) Midterm, Final. These will be based on material from the lectures, and required reading for the lectures. Notice that all readings are divided into required and background. Exams will draw from material in the required reading. 50% of grade
4) Project. Student will choose one: 25% of grade
a) For three of the algorithms discussed in class, implement these algorithms and experiment with them on some real data. Talk with me about the algorithms you choose to implement before hand. Algorithms cannot be too easy (ie., implementing PCA in one line of Matlab code won’t really count). The number of algorithms you will implement is negotiable, if you choose some that are particularly complex. For each algorithm, turn in a writeup fully explaining your results, and email me a zip file with your code. The intent is that this should be the equivalent of three medium sized problem sets.
b) Programming/research project: This is meant to be a more openended project for students interested in research in topics covered in this course. It should involve implementation of existing or novel algorithms and experiments on a realworld data set.
Please hand in your solution to the problem sets, including: 1) A document, with pictures when appropriate, describing your results; 2) Your code. I would prefer to receive your code by email in a zip file, and a hardcopy of the document, but I'll accept everything by email. Projects are due on the last day of class, May 8.
Class Schedule
This schedule should be considered more of a guideline than a rigid plan.
Lectures
Class 
Presenters 
Topic 
Required 
Background 
1. 1/23 
Introduction 



2. 1/28 
Lecture 
Linear Projections: PCA, Mahalanobis distance, LDA, Multidimensional Scaling 
Slides from Olga Veksler: Notes
on MDS, Ali Ghodsi (First section only). Also described in On
a Connection between Kernel PCA and Metric Multidimensional Scaling by Christopher Williams, Section 2.1. Abhishek has written up some more complete notes. 

3. 1/30 
Lecture 
Sparse coding, change of basis, Fourier and Wavelet Transforms 


4. 2/4 
Lecture 
Applications of PCA and LDA in Vision; Analytic Linear Subspaces 
Eigenfaces for Recognition Turk and Pentland Eigenfaces vs. Fisherfaces: recognition using class specific linear projection Belhumeur, Hespanha, and Kriegman Recognition by Linear Combinations of Models Ullman and Basri A Morphable Model for the Synthesis of 3D Faces Blanz and Vetter Lambertian Reflectance and Linear Subspaces Basri and Jacobs 

5. 2/6 
Lecture 
Applications (cont’d) 


6. 2/11 
Lecture 
Random Projections, JohnsonLindenstrauss theorem, locality sensitive hashing, 
An elementary proof of the JohnsonLindenstrauss Lemma, by Dasgupta and Gupta (This provides some useful intuitions, you needn’t master the whole proof). Locality sensitive hashing for finding nearest neighbors by Slaney and Casey 
Experiments with Random Projections for Machine Learning, by Fradkin and Madigan Approximate nearest neighbors: towards removing the curse of dimensionality, by Indyk and Motwani. 
7. 2/13 
Lecture 
Sparse methods 
Introduction
to Compressed Sensing, by 

8. 2/18 
Lecture 
Catching up 


9. 2/20 
Lecture – Abhishek Sharma 
Multimodal projections: CCA, PLS, Bilinear Model 
Overview and recent advances in partial least squares by Rosipal and Kramer Canonical correlation analysis: an overview with applications to learning methods by Hardoon, Szedmak and ShaweTaylor 

10. 2/25 
Papers – Students (Rastegari, Fakhraei,

Sparse Methods 
KSVD: An algorithm for Designing Overcomplete Dictionaries for Sparse Representations by Aharon, Elad and Bruckstein Selftaught
Learning: Transfer Learning from Unlabeled Data by Raina,


11. 2/27 
Lecture 
Manifolds  Tangent spaces 

An Introduction to Riemannian Geometry by Sigmundur Gudmundsson, chapters 2 and 3. Or Riemannian Geometry by Do Carmo (not available online), chapters 0 and 1. 
12. 3/4 
Lecture 
Riemannian Manifolds, Connections  Geodesics 


13. 3/6 
Snow day 



14. 3/11 
Lecture 
Riemannian manifolds cont’d 


15. 3/13 
Lecture 
Kernel methods and Kernel PCA 
Kernel Principal Component Analysis by Scholkopf, Smola and Muller A tutorial on kernel methods for categorization by Jakel, Scholkopf and Wichmann 

SPRING BREAK 




16. 3/25 
Lecture 
Manifold Learning: Isomap and LLE and relation to kernel PCA 
A global geometric framework for nonlinear dimensionality reduction by Tenenbaum, de Silva and Langford Think globally, fit locally: unsupervised learning of low dimensional manifolds, by Saul and Roweis A kernel view of the dimensionality reduction of manifolds by Ham, Lee, Mika and Scholkopf 

17. 3/27 
Papers – Students (Michael, Guangxiao, Arijit,
Jason, Garrett) 
Manifold Learning 
Maximum
Variance Unfolding by Weinberger and Saul. Laplacian eigenmaps for
Dimensionality reduction and data representation by Belkin
and Niyogi Manifold Parzen Windows by Vincent and Bengio 

18. 4/1 
Papers –DWJ 
Metric learning 
Distance
metric learning, with application to clustering with sideinformation, by
Xing, Information
theoretic metric learning, by Davis, Kulis,
Jain, Sra and Dhillon Distance
metric learning for large margin nearest neighbor classification, by
Weinberger and Saul 

19. 4/3 
Lecture 
Exponential maps Steifel and Grassmanian manifolds  Quotient manifolds 
The geometry of algorithms with orthogonality constraints, by Edelman, Arias and Smith. 

20. 4/8 
Papers  DWJ 
Manifolds of positive definite matrices 
Human detection via classification on Riemannian manifolds by Tuzel, Porikli and Meer A Riemannian framework for tensor computing, by Pennec, Fillard and Ayache. 

21. 4/10 
Finish talking about matrix manifolds; go over midterm 



22. 4/15 
Papers – Students: Jain, Manjunatha, Ng, Vageeswaran, Zhang 
Domain adaptation and crossmodal methods. 
K. Saenko, B. Kulis, M. Fritz and
T. Darrell, "Adapting Visual
Category Models to New Domains" R. Gopalan,
R. Li, and R. Chellappa, "Domain Adaptation for
Object Recognition: An Unsupervised Approach", 

23. 4/17 
Papers – Students: Santhanam, Vemulapalli, Zampogiannis 
Manifolds of linear subspaces 
The geometry of algorithms with orthogonality constraints, by Edelman, Arias and Smith. "Affine
Invariance Revisited", E. Begelfor and M. Werman,

"Riemannian geometry of Grassmann manifolds with a view on algorithmic computation", P.A.Absil, R. Mahony and R.Sepulchre. 
24. 4/22 
Lecture 

Shape Statistics: Procrustes Superimpositions and Tangent Spaces by Rohlf 

25. 4/24 
Papers – Students: Ball, Chen (Xi), Li (Hao), Stearns, Yang (Fan) 
Statistical Analysis on Manifolds 
Statistical
Analysis on Stiefel and Grassmann
Manifolds with Applications in Computer Vision by Turaga, Veeraraghavan and Chellappa Population
Shape Regression from Random Design Data by Davis, Fletcher, Bullitt and
Joshi Intrinsic Mean Shift for Clustering on Stiefel and Grassmann Manifolds by Cetingul and Vidal 
Intrinsic
Statistics on Riemannian Manifolds: Basic Tools for Geometric Measurements Summer
School on Manifold Learning in Image and Signal Analysis 
26. 4/29 
Papers – Students: Chen (ChingHui), Hara, Li (Ang), Sun, Yang 
Learning on Manifolds 
Sparse Manifold Clustering and Embedding by Elhamifar and Vidal Semisupervised
Learning on Riemannian Manifolds by Belkin and Niyogi 
Learning
an image manifold for retrieval by He, Ma and Zhang 
27. 5/1 
Papers – DWJ 
Manifolds for shape and intensity comparison. 
Durrleman, Pennec, Trouvé, Thompson and Ayache. Inferring Brain Variability from Diffeormorphic Deformations of Currents: an Integrative Approach On shape of plane elastic curves. Mio, Srivastava, Joshi. A fast illumination and deformation insensitive image comparison algorithm using waveletbased geodesics. Jorstad, Jacobs and Trouve. 

28. 5/6 
Papers – DWJ 
Final Papers 
A Simple Priorfree Method for NonRigid StructurefromMotion Factorization by Dai, Le and He. Diffusion
Kernels on Graphs and Other Discrete Input Spaces by Kondor
and Lafferty 

29. 5/8 
Conclusions 



5/14 
Final Exam 
1:303:30 

