Source-linked AI summary
Median K-flats for hybrid linear modeling with many outliers
Teng Zhang, Arthur Szlam, Gilad Lerman
TL;DR
Hybrid linear modeling requires fitting mixtures of flats despite challenges from outliers and difficult subspace structure. The paper introduces Median K-flats, an online stochastic-gradient method using an ℓ1 objective, and reports strong performance, especially with many outliers or large intrinsic dimension. Its current implementation is limited to linear subspaces, and its initialization is less effective when noise or outliers obscure local structure.
Problem
Hybrid linear modeling seeks to represent data as mixtures of flats, while K-flats can be inaccurate when intrinsic dimension or outlier content is large.
Method
Median K-flats replaces the K-flats ℓ2 objective with an ℓ1 objective and uses stochastic gradient descent to learn best linear d-flats online.
Results
Median K-flats performs well on synthetic and real data, with a clear advantage over studied methods when outliers are numerous or intrinsic dimension is large.
Takeaways & Limitations
The online algorithm can receive points incrementally, produce output incrementally, and uses O(K · d · D) storage.
Takeaways & Limitations
The implementation is restricted to linear subspaces, and its specialized initialization loses its advantage when noise or outliers obscure local structure.
Abstract
from arXiv · showhide
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.
1. Introduction
Hybrid linear modeling represents data as mixtures of flats, but standard K-flats can settle at poor local minima and often fails with large intrinsic dimensions or many outliers. The paper proposes Median K-flats, an online ℓ1-based alternative, and reports strong performance on synthetic and real data.
- Mixtures of affine or linear subspaces model data such as moving-object features and faces under varying illumination.
- K-flats partitions data among d-flats and alternates nearest-flat assignment with PCA-based least-squares flat fitting.
- K-flats is fast and locally convergent, but often reaches poor local minima and fails when d is large or outliers are substantial.
- Median K-flats replaces the K-flats objective with an ℓ1 objective and uses stochastic gradient descent to approximate best ℓ1 d-flats online.
- The online design accepts data incrementally and incrementally produces output, while experiments report strong performance across synthetic and real data.
2. The MKF algorithm
MKF is an online stochastic-gradient method that partitions data into clusters represented by d-dimensional linear subspaces while minimizing an ℓ1 energy. It updates subspaces from sampled points, requires little storage, and supports several initialization and stopping choices.
- MKF partitions data into K clusters, each approximated by a d-dimensional linear subspace, and minimizes an associated energy function.
- The algorithm represents each subspace with a d × D orthogonal-basis matrix and uses stochastic gradient descent to minimize the energy.
- Each iteration samples a random point, assigns it to the nearest subspace, updates that subspace, and repeats until convergence before assigning final clusters.
- O(K · d · D) storage is sufficient, while total running time is O(ns · K · d · D + ns · d^2 · D).The reported sampling count is typically about 10^4 and did not exceed 3 · 10^4 in the experiments.
- Initialization: A farthest-insertion initialization selects points farthest from available planes and spans each new affine space using nearest neighbors.
- Scope and limitations: The method works best for clean linear-subspace data; true affine modeling remains under development, and mixed dimensions are handled by setting d to their maximum.
3. Simulation and experimental results
Experiments on synthetic mixtures of linear subspaces and the Hopkins 155 motion-segmentation database evaluate MKF against several hybrid linear-modeling methods. MKF performs especially well with many outliers and high dimensions, has dimension-insensitive running time relative to several competitors, and remains accurate and stable on Hopkins 155.
- Experimental setup: MKF was compared with MoPPCA, KF, LSA, LSCC, and GPCA using misclassification rates, running times, and standard deviations.The experiments used synthetic and real data, with multiple initialization and restart settings.
- Synthetic simulations: Synthetic data comprised 100 randomly generated hybrid linear models, with 250 samples per subspace and either 5% or 30% uniformly distributed outliers.Mean misclassification rates, standard deviations, and running times were recorded across the instances.
- Synthetic simulations: MKF performs especially well with many outliers and high dimensions, although its Algorithm 2 initialization performs worse than random initialization under high noise and outlier percentages.Algorithm 2 nevertheless reduces the running time of both KF and MKF.
- Synthetic simulations: MKF running time is less sensitive to ambient or intrinsic dimension than the running time of GPCA, LSA, and LSCC.
- Synthetic simulations: Without restarts, KF and MKF have large misclassification-rate standard deviations because they can converge to local minima.GPCA and MoPPCA usually have larger standard deviations, while the other algorithms are more stable.
- Hopkins 155 applications: On Hopkins 155 motion segmentation, MKF with Algorithm 2 initialization exceeds many more complex algorithms and remains superior to KF on clean, low-dimensional data.The database contains 155 sequences, and trajectory vectors are modeled using linear subspaces of dimension at most four.
- Hopkins 155 applications: MKF’s misclassification-rate standard deviation is below 0.002 for two-motions and below 0.013 for three-motions.
4. Conclusion and future work
MKF is an online algorithm for approximating data by K best ℓ1 d-flats, with performance advantages for mixtures of linear subspaces containing many outliers or high-dimensional flats. Future work targets affine subspaces, model-selection decisions, mixed dimensions, applications to streaming and semi-supervised learning, and convergence analysis.
- MKF performs well on synthetic and real data distributed around mixtures of equal-dimensional linear subspaces.
- MKF has a clear advantage over other studied methods when the data contains many outliers or the intrinsic dimension d is large.
- Future work includes extending MKF to affine subspaces, improving initialization, selecting K and d, and handling mixed dimensions.The authors also identify applications in semi-supervised learning and large or streaming data as future directions.
- Further work will comparatively analyze convergence of MKF, an ℓ1 K-flats variant, and K-flats, while developing theory for ℓ1 robustness.The theory is intended to identify settings where ℓ1 flats are not robust to outliers and careful initialization is necessary.