Median K-Flats for hybrid linear modeling with many outliers
Published 1 September 2009Open access
Teng Zhang, Arthur Szlam, Gilad Lerman
Citations152
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The MedianK-flats (MKF) algorithm is described, a simple online method for hybrid linear modeling, i.e., for approximating data by a mixture of flats, which simultaneously partitions the data into clusters while finding their corresponding best approximating ℓ1 d-Flats.
Abstract
We describe the Median K-Flats (MKF) algorithm, a simple online method for\nhybrid linear modeling, i.e., for approximating data by a mixture of flats.\nThis algorithm simultaneously partitions the data into clusters while finding\ntheir corresponding best approximating l1 d-flats, so that the cumulative l1\nerror is minimized. The current implementation restricts d-flats to be\nd-dimensional linear subspaces. It requires a negligible amount of storage, and\nits complexity, when modeling data consisting of N points in D-dimensional\nEuclidean space with K d-dimensional linear subspaces, is of order O(n K d D+n\nd^2 D), where n is the number of iterations required for convergence\n(empirically on the order of 10^4). Since it is an online algorithm, data can\nbe supplied to it incrementally and it can incrementally produce the\ncorresponding output. The performance of the algorithm is carefully evaluated\nusing synthetic and real data.\n
Keywords
Computer ScienceEngineering
Communications of the ACMRandom sample consensus
25,463 Citations1981Martin A. Fischler, Robert C. Bolles
New results are derived on the minimum number of landmarks needed to obtain a solution, and algorithms are presented for computing these minimum-landmark solutions in closed form that provide the basis for an automatic system that can solve the Location Determination Problem under difficult viewing.
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)Some methods for classification and analysis of multivariate observations
22,787 Citations1967James B. MacQueen
Journal of Electronic ImagingPattern Recognition and Machine Learning
21,976 Citations2007Christopher Bishop
Probability Distributions, linear models for Regression, Linear Models for Classification, Neural Networks, Graphical Models, Mixture Models and EM, Sampling Methods, Continuous Latent Variables, Sequential Data are studied.
Neural ComputationMixtures of Probabilistic Principal Component Analyzers
1,903 Citations1999Michael E. Tipping, Chris Bishop
PCA is formulated within a maximum likelihood framework, based on a specific form of gaussian latent variable model, which leads to a well-defined mixture model for probabilistic principal component analyzers, whose parameters can be determined using an expectation-maximization algorithm.
IEEE Transactions on Pattern Analysis and Machine IntelligenceLambertian reflectance and linear subspaces
1,568 Citations2003Ronen Basri, David W. Jacobs
IEEE Transactions on Pattern Analysis and Machine IntelligenceGeneralized principal component analysis (GPCA)
1,055 Citations2005Renè Vidal, Yi Ma +1 more
An algebro-geometric solution to the problem of segmenting an unknown number of subspaces of unknown and varying dimensions from sample data points and applications of GPCA to computer vision problems such as face clustering, temporal video segmentation, and 3D motion segmentation from point correspondences in multiple affine views are presented.
International Journal of Computer VisionA Multibody Factorization Method for Independently Moving Objects
688 Citations1998João Paulo Costeira, Takeo Kanade
A new method for separating and recovering the motion and shape of multiple independently moving objects in a sequence of images by introducing a mathematical construct of object shapes, called the shape interaction matrix, which is invariant to both the object motions and the selection of coordinate systems.
A Benchmark for the Comparison of 3-D Motion Segmentation Algorithms
679 Citations2007Roberto Tron, René Víctor Valqui Vidal
This paper compares four 3D motion segmentation algorithms for affine cameras on a benchmark of 155 motion sequences of checkerboard, traffic, and articulated scenes.
Clustering appearances of objects under varying illumination conditions
541 Citations2003J. Ho, Ming-Husang Yang +3 more
Two appearance-based methods for clustering a set of images of 3D (three-dimensional) objects into disjoint subsets corresponding to individual objects, based on the concept of illumination cones and another affinity measure based on image gradient comparisons are introduced.
Lecture notes in computer scienceA General Framework for Motion Segmentation: Independent, Articulated, Rigid, Non-rigid, Degenerate and Non-degenerate
506 Citations2006Jingyu Yan, Marc Pollefeys
This work proposes a general framework for motion segmentation under affine projections which utilizes two properties of trajectory data: geometric constraint and locality, and estimates a number of linear manifolds, whose dimensions are unknown beforehand.
IEEE Transactions on Pattern Analysis and Machine IntelligenceSegmentation of Multivariate Mixed Data via Lossy Data Coding and Compression
472 Citations2007Yi Ma, Harm Derksen +2 more
It is shown that a deterministic segmentation is approximately the (asymptotically) optimal solution for compressing mixed data and can be readily applied to segment real imagery and bioinformatic data.
Journal of Global Optimizationk-Plane Clustering
405 Citations2000Patricia Bradley, O. L. Mangasarian
A finite new algorithm is proposed for clustering m given points in n-dimensional real space into k clusters by generating k planes that constitute a local solution to the nonconvex problem of minimizing the sum of squares of the 2-norm distances between each point and a nearest plane.
International Journal of Computer VisionSpectral Curvature Clustering (SCC)
376 Citations2008Guangliang Chen, Gilad Lerman
An iterative sampling procedure to improve the uniform sampling strategy, an automatic scheme of inferring the tuning parameter from the data, a precise initialization procedure for K-means, as well as a simple strategy for isolating outliers are suggested.
Motion segmentation by subspace separation and model selection
353 Citations2002Kenichi Kanatani
A robust segmentation algorithm by incorporating such techniques as dimension correction, model selection using the geometric AIC, and least-median fitting is presented, demonstrating that oar algorithm dramatically outperforms existing methods.
SIAM ReviewEstimation of Subspace Arrangements with Applications in Modeling and Segmenting Mixed Data
257 Citations2008Yi Ma, Allen Y. Yang +2 more
This paper provides a comprehensive summary of important algebraic properties and statistical facts that are crucial for making the inference of subspace arrangements both efficient and robust, even when the given data are corrupted by noise or contaminated with outliers.
International Journal of Computer VisionMultiframe Motion Segmentation with Missing Data Using PowerFactorization and GPCA
224 Citations2007René Vidal, Roberto Tron +1 more
This algorithm involves projecting all point trajectories onto a 5-dimensional subspace using the SVD, the PowerFactorization method, or RANSAC, and fitting multiple linear subspaces representing different rigid-body motions to the points in ℝ5 using GPCA.
Segmenting Motions of Different Types by Unsupervised Manifold Clustering
197 Citations2007Alvina Goh, René Vidal
This work shows that for a union of separated manifolds, the LLE algorithm computes a matrix whose null space contains vectors giving the segmentation of the data, which leads to a new algorithm for clustering both linear and nonlinear manifolds.
Fast Non-Linear Dimension Reduction
97 Citations1993Nanda Kambhatla, Todd K. Leen
Experiments with speech and image data indicate that the local linear algorithm produces encodings with lower distortion than those built by five layer auto-associative networks.
Lecture notes in computer scienceEvaluation and Selection of Models for Motion Segmentation
61 Citations2002Kenichi Kanatani
An improvement of the subspace separation for motion segmentation by newly introducing the affine space constraint is presented and two measures using real images are tested: the standard F test, and the geometric model selection criteria.
Multi-Stage Unsupervised Learning for Multi-Body Motion Segmentation
28 Citations2004Yasuyuki Sugaya, Kenichi Kanatani
This paper proposes a multi-stage unsupervised learning scheme first assuming degenerate motions and then assuming general 3-D motions, which enables us to not only separate simple motions that the authors frequently encounter with high precision but also preserve the high performance for considerably general 3D motions.
Hilbert functions and applications to the estimation of subspace arrangements
15 Citations2005Ai‐Li Yang, Suyun Rao +3 more
A new mathematical framework for studying the subspace-segmentation problem is developed and an important class of invariants given by the Hilbert functions is introduced, showing that there exist rich relations between subspace arrangements and their corresponding Hilbert functions.