Angular Embedding: A Robust Quadratic Criterion

TitleAngular Embedding: A Robust Quadratic Criterion
Publication TypeConference Paper
Year of Publication2012
AuthorsYu, S. X.
Published inIEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE
Volume34
Issue1
Page(s)158-173
Keywordsclustering, constrained optimization, east squares methods, graph algorithms, linear programming, modeling and recovery of physical attributes, spectral methods, statistical computing
Abstract

Given the size and confidence of pairwise local orderings, angular embedding (AE) finds a global ordering with a near-global optimal eigensolution. As a quadratic criterion in the complex domain, AE is remarkably robust to outliers, unlike its real domain counterpart LS, the least squares embedding. Our comparative study of LS and AE reveals that AE's robustness is due not to the particular choice of the criterion, but to the choice of representation in the complex domain. When the embedding is encoded in the angular space, we not only have a non-convex error function that delivers robustness, but also have a Hermitian graph Laplacian that completely determines the optimum and delivers efficiency. The high quality of embedding by AE in the presence of outliers can hardly be matched by LS, its corresponding $L_1$ norm formulation, or their bounded versions. These results suggest that the key to overcoming outliers lies not with additionally imposing constraints on the embedding solution, but with adaptively penalizing inconsistency between measurements themselves. AE thus significantly advances statistical ranking methods by removing the impact of outliers directly without explicit inconsistency characterization, and advances spectral clustering methods by covering the entire size-confidence measurement space and providing an ordered cluster organization.

Acknowledgment

This research was funded by US National Science Foundation (NSF) CAREER IIS-0644204 and a Clare Boothe Luce Professorship. The author would like to thank Francis Bach and anonymous reviewers for thoughtful comments and excellent suggestions.

URLhttp://www1.icsi.berkeley.edu/~stellayu/publication/doc/2012aePAMI.pdf
ICSI Research Group

Vision