Robust Subspace Segmentation by Low-Rank Representation
Published 21 June 2010
Guangcan Liu, Zhouchen Lin, Yong Yu
Citations1,430
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
Both theoretical and experimental results show that low-rank representation is a promising tool for subspace segmentation from corrupted data.
Abstract
We propose low-rank representation (LRR) to segment data drawn from a union of multiple linear (or affine) subspaces. Given a set of data vectors, LRR seeks the lowestrank representation among all the candidates that represent all vectors as the linear combination of the bases in a dictionary. Unlike the well-known sparse representation (SR), which computes the sparsest representation of each data vector individually, LRR aims at finding the lowest-rank representation of a collection of vectors jointly. LRR better captures the global structure of data, giving a more effective tool for robust subspace segmentation from corrupted data. Both theoretical and experimental results show that LRR is a promising tool for subspace segmentation. 1.
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.
IEEE Transactions on Pattern Analysis and Machine IntelligenceNormalized cuts and image segmentation
15,696 Citations2000Jianbo Shi, Jitendra Malik
Cambridge University Press eBooksTopics in Matrix Analysis
9,501 Citations1991Roger A. Horn, Charles R. Johnson
IEEE Transactions on Pattern Analysis and Machine IntelligenceRobust Face Recognition via Sparse Representation
9,444 Citations2009John Wright, A. Yang +3 more
This work considers the problem of automatically recognizing human faces from frontal views with varying expression and illumination, as well as occlusion and disguise, and proposes a general classification algorithm for (image-based) object recognition based on a sparse representation computed by C1-minimization.
Foundations of Computational MathematicsExact Matrix Completion via Convex Optimization
5,061 Citations2009Emmanuel J. Candès, Benjamin Recht
IEEE Transactions on Pattern Analysis and Machine IntelligenceAcquiring linear subspaces for face recognition under variable lighting
2,422 Citations2005Kuang-Chih Lee, J. Ho +1 more
This paper shows how to arrange physical lighting so that the acquired images of each object can be directly used as the basis vectors of a low-dimensional linear space and that this subspace is close to those acquired by the other methods.
Journal of Structural BiologyA collaborative framework for 3D alignment and classification of heterogeneous subvolumes in cryo-electron tomography
2,245 Citations2012Oleg Kuybeda, Gabriel A. Frank +4 more
The genetic identity of each virus particle present in the mixture can be assigned based solely on the structural information derived from single envelope glycoproteins displayed on the virus surface by the nuclear norm-based, collaborative alignment method presented here.
Proceedings of the IEEEMatrix Completion With Noise
1,739 Citations2010Emmanuel J. Candès, Yaniv Plan
This paper surveys the novel literature on matrix completion and introduces novel results showing that matrix completion is provably accurate even when the few observed entries are corrupted with a small amount of noise, and shows that, in practice, nuclear-norm minimization accurately fills in the many missing entries of large low-rank matrices from just a few noisy samples.
2009 IEEE Conference on Computer Vision and Pattern RecognitionSparse subspace clustering
1,283 Citations2009Ehsan Elhamifar, Renè Vidal
This work proposes a method based on sparse representation (SR) to cluster data drawn from multiple low-dimensional linear or affine subspaces embedded in a high-dimensional space and applies this method to the problem of segmenting multiple motions in video.
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.
IEEE Transactions on Pattern Analysis and Machine IntelligenceMotion Segmentation in the Presence of Outlying, Incomplete, or Corrupted Trajectories
354 Citations2009Suyun Rao, Roberto Tron +2 more
A robust subspace separation scheme is developed that deals with practical issues in a unified mathematical framework and gives surprisingly good performance in the presence of the three types of pathological trajectories mentioned above.
arXiv (Cornell University)Robust Principal Component Analysis?
305 Citations2009Emmanuel J. Candès, Xiaodong Li +2 more
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.
Multibody factorization with uncertainty and missing data using the EM algorithm
206 Citations2004Amit Gruber, Yaakov Weiss
This paper presents a multibody factorization algorithm that can handle arbitrary noise covariance for each feature as well as missing data and derive an expectation-maximization based maximum-likelihood algorithm.
Median K-Flats for hybrid linear modeling with many outliers
152 Citations2009Teng Zhang, Arthur Szlam +1 more
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.
arXiv (Cornell University)A Singular Value Thresholding Algorithm for Matrix Completion
131 Citations2008Jian‐Feng Cai, Emmanuel J. Candès +1 more
Robust Statistical Estimation and Segmentation of Multiple Subspaces
86 Citations2006Ai‐Li Yang, Suyun Rao +1 more
A comprehensive survey of robust statistical techniques in the literature is provided, and three main approaches for detecting and rejecting outliers are identified: random sample consensus, the influence function, and multivariate trimming.
Combined central and subspace clustering for computer vision applications
70 Citations2006Le Lü, René Vidal
This paper proposes a generalization of Kmeans and Ksubspaces that clusters the data by minimizing a cost function that combines both central and subspace distances.
arXiv (Cornell University)Robust Recovery of Signals From a Union of Subspaces
62 Citations2008Yonina C. Eldar, Moshe Mishali
International Journal of Computer VisionRobust Algebraic Segmentation of Mixed Rigid-Body and Planar Motions from Two Views
51 Citations2010Shankar Rao, Allen Y. Yang +2 more
It is proved that the joint distribution of image correspondences is uniquely determined by a set of (2K)-th degree polynomials, a global signature for the union of K motions of possibly mixed type, which helps to recover the association of the individual image samples to their respective motions.
SIAM Journal on Imaging SciencesClassification via Minimum Incremental Coding Length
13 Citations2009John Wright, Yi Ma +3 more
A simple new criterion for classification, based on principles from lossy data compression, and its kernel and local versions perform competitively on synthetic examples, as well as on real imagery data such as handwritten digits and face images.
Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign)Classification via Minimum Incremental Coding Length (MICL)
13 Citations2007John Wright, Yangyu Tao +3 more
This simple classification criterion and its kernel and local versions perform competitively against existing classifiers on both synthetic examples and real imagery data such as handwritten digits and human faces, without requiring domain-specific information.