| It has never been easier to collect data. Ubiquitous smart phones and home appliances, surveillance cameras in public spaces, electronic transactions, and websites browsing, are just a few examples of ways to generate massive quantities of 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, high dimensional data to enable enhanced decision making and insight discovery remains very challenging. In this dissertation, 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 (e.g., videos) to recover missing data and forecast future measurements. |
