CMU VASC talk: Subspectral Algorithms for Sparse Learning, Optimization & Inference

Baback Moghaddam
MERL
Monday, Jan 29, 3:30pm, NSH 1507

Subspectral Algorithms for Sparse Learning, Optimization & Inference

I will present a class of "subspectral" algorithms (i.e. sparse eigenvector techniques) for solving NP-hard combinatorial optimization problems in three general applied domains: (1) Supervised/unsupervised learning, in the traditional or orthodox sense (e.g. PCA & LDA), (2) Quadratic/Entropic Optimization (e.g. Least-Squares & MaxEnt) and (3) Inference, in the strict probabilistic/Bayesian sense (e.g. Automatic Relevance Determination and variational methods like Expectation Propagation). Subspectral algorithms for both exact (optimal) and greedy (approximate) solutions of these general sparse optimization problems are derived using analytic eigenvalue bounds. Specifically, an efficient "dual-pass" greedy algorithm is shown to yield near-optimal solutions for all possible cardinalities (at once) in a fraction of the time it takes for most continuous relaxation methods to find solutions of comparable quality for a single cardinality. I will present sample applications of subspectral optimization techniques in .sparse PCA. for feature selection (statistics), .sparse LDA. for classification (gene discovery), sparse kernel regression (robotics & control), sparse quadratic programming (portfolio optimization), graph model selection (sensor networks) as well as sparse Bayesian inference for computer vision (face recognition & OCR).

Bio:
Baback Moghaddam's research interests are in computational vision with a main focus on probabilistic visual learning. His related areas of interest and expertise include statistical modeling, Bayesian data analysis, machine learning and pattern recognition. He obtained his PhD in Electrical Engineering and Computer Science (EECS) from the Massachusetts Institute of Technology (MIT) in 1997 where he was a member of the Vision and Modeling Group at the MIT Media Laboratory where he developed a fully-automatic vision system which won DARPA's 1996 "FERET" Face Recognition Competition.

Dr. Moghaddam was the winner of the 2001 Pierre Devijver Prize from the International Association of Pattern Recognition for his "innovative approach to face recognition" and received the Pattern Recognition Society Award for "exceptional outstanding quality" for his journal paper "Bayesian Face Recognition." He currently serves on the editorial board of the journal Pattern Recognition and has contributed to numerous textbooks on image processing and computer vision including the core chapter in Springer-Verlag's latest biometric series, "Handbook of Face Recognition."

Dr. Moghaddam's past research included infrared (IR) image analysis for the Office of Naval Research (ONR), segmentation of synthetic aperture radar (SAR) imagery for MIT Lincoln Laboratory as well as designing a micro-gravity experiment for laser annealing of amorphous silicon which was flown aboard the US Space Shuttle in 1990.

http://www.merl.com/people/baback