Median K-flats for hybrid linear modeling with many outliers

Abstract

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 l1 d-flats, so that the cumulative l1 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-dimensional Euclidean space with K d-dimensional linear subspaces, is of order O(n K d D+n d^2 D), where n is the number of iterations required for convergence (empirically on the order of 10^4). 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.

Cited by in corpus (35)

• Robust Recovery of Subspace Structures by Low-Rank Representation
• A geometric analysis of subspace clustering with outliers
• Structured Sparse Subspace Clustering: A Joint Affinity Learning and Subspace Clustering Framework
• Robust subspace clustering
• Hybrid Linear Modeling via Local Best-fit Flats
• An Overview of Robust Subspace Recovery
• A Novel M-Estimator for Robust PCA
• Robust computation of linear models by convex relaxation
• RPCA-KFE: Key Frame Extraction for Consumer Video based Robust Principal Component Analysis
• Robust Subspace Clustering with Compressed Data
• Sketched Subspace Clustering
• Innovation Pursuit: A New Approach to Subspace Clustering
• Robust recovery of multiple subspaces by geometric l_p minimization
• Fast, Robust and Non-convex Subspace Recovery
• Randomized hybrid linear modeling by local best-fit flats
• Scalable and Robust Sparse Subspace Clustering Using Randomized Clustering and Multilayer Graphs
• A Well-Tempered Landscape for Non-convex Robust Subspace Recovery
• A New Approach To Two-View Motion Segmentation Using Global Dimension Minimization
• Robust Subspace Recovery Layer for Unsupervised Anomaly Detection
• Tangent-based manifold approximation with locally linear models
• 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
• Neither Global Nor Local: A Hierarchical Robust Subspace Clustering For Image Data
• Subspace Clustering via Optimal Direction Search
• Robust Subspace Recovery with Adversarial Outliers
• Subspace Clustering using Ensembles of $K$-Subspaces
• Novelty Detection via Robust Variational Autoencoding
• Subspace clustering based on low rank representation and weighted nuclear norm minimization
• Laplacian regularized low rank subspace clustering
• Estimating a Manifold from a Tangent Bundle Learner
• Three-Stage Subspace Clustering Framework with Graph-Based Transformation and Optimization
• Constructing the F-Graph with a Symmetric Constraint for Subspace Clustering
• Kernel Two-Dimensional Ridge Regression for Subspace Clustering
• PMSSC: Parallelizable multi-subset based self-expressive model for subspace clustering