Thesis Committee:
Octavia I. Camps(Ph.D. Advisor)
Mario Sznaier
Dana Brooks
Jennifer Dy

Thesis Title: Manifold Embedding with Dynamic and/or Classification Supervision

Abstract:
It has never been easier to collect data. Ubiquitous smart phones and home appliances, surveillance cameras in public spaces, electronic transactions, and browsing websites, are just a few examples of ways to generate large complex data that is easily shared through the internet. Access to these large datasets brings opportunities that range from providing a pleasant experience to an online customer, to developing smart environments that save energy, to preventing terrorist attacks. Yet, analyzing and visualizing large, highdimensional data to enable enhanced decision making and insight discovery remains very challenging. In this thesis, we propose a set of nonlinear manifold embedding tools that exploit supervised learning information to find low dimensional data embeddings that preserve spatial and/or temporal correlations characteristics hidden in high dimensional data such as videos and images. The proposed methods extend the maximum variance embedding objective used in the existing Semi-Definite Embedding(SDE) algorithm by incorporating large margin, low dynamic order and large margin dynamic classification objectives, respectively. These three different supervision objectives benefit the embeddings with linear separation between classes, simple dynamics and separation between different dynamics. The proposed algorithms are either formulated or relaxed as a convex Semi-Definite Programing(SDP) problem via polynomial optimization and/or low rank matrix approximation technology. The resulting embeddings provide compact, easier to analyze and visualize representations that capture well the relevant information, as well as their relationships, from the original data. The potential of these tools is illustrated through several challenging applications including classification, data visualization, tracking, video segmentation and manifold embedding of temporal (eg. videos) to recover missing data and forecast future measurements.