Computer Science Department
School of Computer Science, Carnegie Mellon University


Robust Subspace Computation Using L1 Norm

Qifa Ke, Takeo Kanade

August 2003

Keywords: Subspace, robust, L1 norm, L2 norm, weighted median, quadratic programming, SVD

Linear subspace has many important applications in computer vision, such as structure from motion, motion estimation, layer extraction, object recognition, and object tracking. Singular Value Decomposition (SVD) algorithm is a standard technique to compute the subspace from the input data. The SVD algorithm, however, is sensitive to outliers as it uses L2 norm metric, and it can not handle missing data either. In this paper, we propose using L1 norm metric to compute the subspace. We show that it is robust to outliers and can handle missing data. We present two algorithms to optimize the L1 norm metric: the weighted median algorithm and the quadratic programming algorithm.

17 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by