Hybrid Linear Modeling via Local Best-fit Flats

Abstract

We present a simple and fast geometric method for modeling data by a union of affine subspaces. The method begins by forming a collection of local best-fit affine subspaces, i.e., subspaces approximating the data in local neighborhoods. The correct sizes of the local neighborhoods are determined automatically by the Jones' ${\beta }_2$ numbers (we prove under certain geometric conditions that our method finds the optimal local neighborhoods). The collection of subspaces is further processed by a greedy selection procedure or a spectral method to generate the final model. We discuss applications to tracking-based motion segmentation and clustering of faces under different illuminating conditions. We give extensive experimental evidence demonstrating the state of the art accuracy and speed of the suggested algorithms on these problems and also on synthetic hybrid linear data as well as the MNIST handwritten digits data; and we demonstrate how to use our algorithms for fast determination of the number of affine subspaces.

This version adds some clarifications and numerical experiments as well as strengthens the previous theorem. For face experiments, we use here the Extended Yale Face Database B (cropped faces unlike previous version). This database points to a failure mode of our algorithms, but we suggest and successfully test a workaround

References in corpus (3)

• A geometric analysis of subspace clustering with outliers
• Robust recovery of multiple subspaces by geometric l_p minimization
• Foundations of a Multi-way Spectral Clustering Framework for Hybrid Linear Modeling

Cited by in corpus (18)

• A geometric analysis of subspace clustering with outliers
• Structured Sparse Subspace Clustering: A Joint Affinity Learning and Subspace Clustering Framework
• Robust subspace clustering
• An Overview of Robust Subspace Recovery
• A Novel M-Estimator for Robust PCA
• Cloud K-SVD: A Collaborative Dictionary Learning Algorithm for Big, Distributed Data
• Sketched Subspace Clustering
• Robust recovery of multiple subspaces by geometric l_p minimization
• 3D Rigid Motion Segmentation with Mixed and Unknown Number of Models
• Algebraic Clustering of Affine Subspaces
• LogDet Rank Minimization with Application to Subspace Clustering
• A New Approach To Two-View Motion Segmentation Using Global Dimension Minimization
• lp-Recovery of the Most Significant Subspace among Multiple Subspaces with Outliers
• Learning the nonlinear geometry of high-dimensional data: Models and algorithms
• Subspace clustering without knowing the number of clusters: A parameter free approach
• Effective Sampling: Fast Segmentation Using Robust Geometric Model Fitting
• Better Feature Tracking Through Subspace Constraints
• Restricted Connection Orthogonal Matching Pursuit For Sparse Subspace Clustering