Robust and Efficient Subspace Segmentation via Least Squares Regression

By Canyi Lu, Hai Min, Zhongming Zhao, Ling Zhu, De-shuang Huang, Shuicheng Yan. European Conference on Computer Vision, 2012

707 citations recorded by the source corpus.

This paper studies the subspace segmentation problem which aims to segment data drawn from a union of multiple linear subspaces. Recent works by using sparse representation, low rank representation and their extensions attract much attention. If the subspaces from which the data drawn are independent or orthogonal, they are able to obtain a block diagonal affinity matrix, which usually leads to a correct segmentation. The main differences among them are their objective functions. We theoretically show that if the objective function satisfies some conditions, and the data are sufficiently drawn from independent subspaces, the obtained affinity matrix is always block diagonal. Furthermore, the data sampling can be insufficient if the subspaces are orthogonal. Some existing methods are all special cases. Then we present the Least Squares Regression (LSR) method for subspace segmentation. It takes advantage of data correlation, which is common in real data. LSR encourages a grouping effect which tends to group highly correlated data together. Experimental results on the Hopkins 155 database and Extended Yale Database B show that our method significantly outperforms state-of-the-art methods. Beyond segmentation accuracy, all experiments demonstrate that LSR is much more efficient.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Media Technology

View Paper: https://www.semanticscholar.org/paper/29308c1bcccbdd5fd5d008b92d45bc04f0338a59

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Media Technology

Citations in the corpus

Structured AutoEncoders for Subspace Clustering (2018, methodology): “With the simplifications shown in Theorem 1, for example, StructAE will degrade to SSC [7] with the sparsity prior, to LRR [8] with the low rank prior, to LSR [6] and L2graph [14] with the L2-norm based prior.”
Multi-Task Learning for Subspace Segmentation (2015, methodology): “(7) Current SSC algorithms (as well as LSR and CASS) all decompose into (7) for each task xj , and the solutions are computed completely independently of one another and then later merged together to form A.”
Structured Graph Learning for Scalable Subspace Clustering: From Single View to Multiview (2021, positive): “For new samples, SLSR [32] projects them into the union of subspaces spanned by in-sample data.”
Nonconvex Nonsmooth Low Rank Minimization via Iteratively Reweighted Nuclear Norm (2015, methodology): “After solving (27) or (37), we follow the settings in [48] to construct the affinity matrix by W = (|P3 | + |P3 |)/2.”
Finding Global Homophily in Graph Neural Networks When Meeting Heterophily (2022, background): “Finally, we mathematically show that both Z(l) and the generated node embedding matrix H(l) have the grouping effect (Lu et al., 2012), i.e., for any two nodes in a graph, no matter how distant they are, if they share similar features and local structures, their embedding vectors will be close to…”
Multi-Scale Fusion Subspace Clustering Using Similarity Constraint (2020, methodology): “, 1 norm [4, 5], nuclear norm [20, 19], and Frobenius norm [12, 21].”
Deep Subspace Clustering Networks (2017, methodology): “The resulting methods can then be roughly divided into three categories [42]: factorization methods [7, 17, 44, 29, 16], higher-order model based methods [49, 6, 33, 37], and self-expressiveness based methods [9, 24, 26, 46, 15, 12, 22, 52].”
Consistent and Specific Multi-View Subspace Clustering (2018, methodology): “Besides, we apply l2 norm to the specific term to ensure connectedness property, thus the representation matrices are generally dense, which alleviates the connectivity issue (Lu et al. 2012).”
Subspace Clustering by Block Diagonal Representation (2018, methodology): “We give the procedure of BDR for subspace clustering as previousworks [10], [21], [28].”
Scalable Sparse Subspace Clustering by Orthogonal Matching Pursuit (2015, methodology): “Overall, SSC-OMP provided the best accuracy versus computation trade-off for large scale subspace clustering problems.”