Median K-Flats for hybrid linear modeling with many outliers

We describe the Median K-flats (MKF) algorithm, a simple online method for hybrid linear modeling, i.e., for approximating data by a mixture of flats. This algorithm simultaneously partitions the data into clusters while finding their corresponding best approximating ¿₁ d-flats, so that the cumulative ¿₁ error is minimized. The current implementation restricts d-flats to be d-dimensional linear subspaces. It requires a negligible amount of storage, and its complexity, when modeling data consisting of N points in ¿^D with K d-dimensional linear subspaces, is of order O(n_s · K · d · D + n_s · d² · D), where n_s is the number of iterations required for convergence (empirically on the order of 10⁴). Since it is an online algorithm, data can be supplied to it incrementally and it can incrementally produce the corresponding output. The performance of the algorithm is carefully evaluated using synthetic and real data.

1. Introduction

Many common data sets can be modeled by mixtures of fiats (i.e., affine subspaces). For example, feature vectors of different moving objects in a video sequence lie on different affine subspaces (see e.g., [14]), and similarly, images of different faces under different illuminating conditions are on different linear subspaces with each such subspace corresponding to a distinct face [1]. Such data give rise to the problem of hybrid linear modeling, i.e., modeling data by a mixture of fiats.