Source-linked AI summary
Hybrid Linear Modeling via Local Best-fit Flats
Teng Zhang, Arthur Szlam, Yi Wang, Gilad Lerman
TL;DR
The paper addresses HLM settings where data must be partitioned among multiple affine subspaces and existing methods may require initialization or deviation parameters. It estimates local best-fit flats using automatically selected neighborhoods, then forms global models with LBF or SLBF. Experiments report accurate performance across real and synthetic problems, fast LBF execution, and uses for parameter and subspace-count estimation.
Problem
HLM requires partitioning noisy or outlier-corrupted data among affine subspaces, while many existing algorithms require initial subspaces or parameters describing deviations from the model.
Method
The method estimates local best-fit flats in approximately optimal neighborhoods selected using Jones' β_2 numbers, then processes candidate flats with energy minimization or a spectral method.
Results
Experiments on motion segmentation, face clustering, handwritten digits, synthetic data, and artificial data report accurate LBF/SLBF performance, state-of-the-art SLBF accuracy, and very fast LBF execution.
Takeaways & Limitations
The local best-fit heuristic can initialize or parameterize other HLM algorithms and, with the elbow method, quickly estimate the number of subspaces.
Takeaways & Limitations
The work theoretically justifies its initializer but does not yet provide a complete theory or rigorous quantification of algorithmic limitations, including in settings with nonlinear structures, noise, and outliers.
Abstract
from arXiv · showhide
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' $β_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.
1 Introduction
Hybrid Linear Modeling targets data lying on multiple affine subspaces, as in motion segmentation and face clustering. The paper proposes local best-fit subspaces, theoretically motivated neighborhood selection, and LBF/SLBF algorithms, with experiments across real and synthetic datasets.
- Motivation: Hybrid Linear Modeling represents data by multiple affine subspaces and seeks the partition corresponding to those underlying flats.The formulation allows additive noise and outliers; the initial setting assumes known, equal flat dimension and known number of flats.
- Motivation: Existing HLM methods often require initialized subspaces or carefully chosen data points, while some require parameters describing noise or model deviations.Examples include initialization for K-flats and SCC, and noise-level parameters for RANSAC and ALC.
- Limitations: The paper theoretically justifies the initializer but leaves a more complete theory for the algorithms and rigorous quantification of their limitations as future work.The discussion identifies additional noise, restricted outlier fractions, and nonlinear structures as settings relevant to future analysis.
- Method: The paper formalizes local best-fit neighborhoods using Jones' β_2 numbers and proves that approximately optimal neighborhoods can be found under certain geometric conditions.The optimal neighborhood is the largest ball around a point containing only samples from its own cluster; smaller or larger neighborhoods can produce mismatched flats.
- Method: LBF and SLBF build global HLM models from best-fit flats of locally optimal neighborhoods, using energy minimization and spectral processing, respectively.The methods first generate candidate flats from local neighborhoods and then process those candidates into the final model.
- Evaluation: Experiments cover motion segmentation, face clustering, handwritten digits, and synthetic data, reporting accurate performance for both methods and especially fast execution for LBF.The paper also reports state-of-the-art accuracy for SLBF with reasonable runtimes and identifies a fundamental issue for local methods on cropped face data, alongside a dataset-specific workaround.
- Extensions: The local best-fit heuristic also initializes K-flats, estimates parameters for RANSAC and ALC, and combines with the elbow method to determine the number of subspaces quickly.These uses extend the heuristic beyond the complete LBF and SLBF algorithms.
2 The local best-fit flats heuristic and the LBF and SLBF algorithms
The method estimates local affine subspaces from automatically selected neighborhoods, then combines candidate flats using either greedy energy minimization or a spectral approach. Its neighborhood criterion uses scale-invariant β2 behavior, with theoretical and computational guarantees under stated conditions.
- Candidate construction and global modeling: LBF and SLBF first construct candidate flats from locally optimal neighborhoods, then use energy minimization or a spectral method to process them.LBF uses greedy energy minimization, whereas SLBF uses a spectral approach.
- Local neighborhood selection: An optimal neighborhood is the largest ball around a point containing only samples from its cluster, avoiding neighborhoods dominated by local noise.Smaller neighborhoods may primarily capture noise around the underlying subspace.
- Local neighborhood selection: The algorithm increases neighborhood size over nearest-neighbor sets and selects the first local minimizer of the scale-invariant β2 error.β2 normalizes best-fit ℓ2 approximation error by the neighborhood scale.
- Theoretical justification: Under tube-mixture assumptions, the first local minimum of β2 occurs between r0 and 1.09 r0, approximately identifying the distance to the nearest other cluster.The probabilistic extension is expected to hold with high probability for sufficiently large samples.
- Computational complexity: When T is of order N, neighborhood-size selection has total complexity O((d · D + log N) · N).The preprocessing cost includes neighbor sorting, while β2 computation uses top d singular values of local data matrices.
- LBF energy minimization: LBF can use l1 energy because it is more robust to outliers than mean squared error in some scenarios, while evaluating candidate configurations rather than directly minimizing difficult energies.Its candidate-flat strategy also differs from RANSAC, which fits flats from arbitrarily chosen d + 1 points.
3 Experimental results
Experiments on artificial and real hybrid linear-modeling data show that the proposed methods are generally fast and accurate, with SLBF variants often strongest in accuracy and LBF variants strongest in speed. The results also expose a failure mode on sparsely sampled, nearby face subspaces that can be mitigated by whitening.
- Experimental setup: The experiments evaluate the proposed algorithms on artificial data, Hopkins 155 motion segmentation, extended Yale face clustering, and MNIST.The artificial experiments include linear and affine subspaces, while Hopkins represents trajectories of moving objects and background.
- Artificial data: On artificial hybrid linear data, the proposed methods perform well, especially with many outliers and affine subspaces.The reported robustness is attributed to ℓ1 loss and random sampling, while SLBF variants benefit from spectral clustering in affine cases.
- Artificial data: LBF and LBF-MS run faster than most compared algorithms, while SLBF and SLBF-MS require more time for large N because they construct an N × N spectral-clustering matrix.LBF variants are slower than a single K-flats run but can be advantageous against repeated K-flats restarts; SLBF remains comparable to LSA and faster than SSC.
- Motion segmentation: On Hopkins 155, SLBF-MS and SSC-N are the most accurate tested methods, while LBF-MS is more than 100 times faster than SSC-N and SLBF-MS is more than 10 times faster than SSC.The authors suspect that spectral information combined with subspace clustering helps explain the stronger SLBF performance over LBF.
- Face clustering: On extended Yale face data, local methods fail when sampling is sparse and affine subspaces are nearby, but removing the first two principal components greatly improves LBF/SLBF results.The failure reflects the small relative fitting-error penalty of representing the data with one subspace; more sophisticated whitening improves results further.
- MNIST: On MNIST, SLBF and SLBF-MS have the best misclassification rates, while LBF, LBF-MS, and K-flats are fastest; SLBF errors increase when K = 3.These results are reported from experiments using the correct number of clusters.
K SOD(ln WK), . (14)
The paper evaluates methods for clustering hybrid linear data and estimating the number of clusters, including artificial, face, and MNIST experiments. Results show trade-offs between accuracy and runtime, with local methods often computationally efficient but sensitive to difficult data geometry.
- Cluster-number estimation: SOD compares LBF-, SLBF-, SCC-, and SSC-based variants with ALC and GPCA for estimating cluster counts.The experiments record incorrectness rates and computation times on artificial, face, and MNIST data.
- Cluster-number estimation: For artificial data, ALC (oracle) and ALC (ε from LBF) work best in dimensions d = 1, 2, 3, although the oracle noise level is usually unknown.The local best-fit heuristic estimates the distortion rate and helps ALC reduce running time.
- Cluster-number estimation: For artificial data, SOD (LBF) and SOD (LBF-MS) provide reasonable cluster-count estimates with an obvious computing-time advantage.ALC suffers from computational complexity, especially its voting variant, while GPCA is fast but performs poorly.
- Cluster-number estimation: On the extended Yale face database, SOD performs well with SSC only when K is smaller than 4, whereas several methods detect K perfectly for K ≤ 10 on uncropped Yale faces.The cropped database is described as difficult; the uncropped database does not use whitening.
- Cluster-number estimation: On MNIST, determining K becomes very difficult for real K larger than 3; for K ≤ 3 after projection to 10 dimensions, SLBF, SLBF-MS, and SSC-based SOD outperform other methods.These methods are not very efficient in this setting.
- Neighborhood selection: The local neighborhood heuristic selects smaller neighborhoods near intersections of planes, illustrating spatially varying scale selection.The figure color encodes the number of neighbors chosen at each point.
4 Conclusions and future work
The method automatically selects local best-fit flats for hybrid linear modeling and achieves state-of-the-art accuracy and speed on synthetic and real data. Its current scope is unions of affine flats; extending it to unions of curved manifolds remains future work.
- The method selects local best-fit flats automatically using ℓ2 β numbers and approximately finds optimal neighborhoods under certain geometric conditions.
- Extensive experiments report state-of-the-art accuracy and speed on synthetic and real hybrid linear data.
- The method cannot successfully handle unions of curved manifolds, motivating adaptation for multi-manifold clustering.
- The local estimation can fail when data are locally lower-dimensional and highly curved, even if clusters are globally d-dimensional.
A Proof of Theorem 1
The proof analyzes how β2 changes with neighborhood radius around intersecting affine clusters. Under the stated geometric assumptions, it establishes monotonic decrease before the transition scale and bounds the first local minimum near the optimal radius.
- For radii r1≤r2≤r0, the proof concludes that β2(x∗,r1)>β2(x∗,r2), so β2 is strictly decreasing on [w,r0].
- At r∗, the minimizing flat has a prescribed intersection geometry with L2, and the proof identifies leading eigenvectors of the centered covariance matrix.
- The proof verifies the theorem’s geometric inequalities for d=1 and extends them to d≥2 under the stated conditions.
- As w/r0→0, the selected radius r∗ approaches r0, while the first local minimum can exceed r0.