PaperlayerView exact revision on arXiv

Source-linked AI summary

Constructing the L2-Graph for Robust Subspace Learning and Subspace Clustering

Xi Peng, Zhiding Yu, Huajin Tang, Zhang Yi

arXiv:1209.0841v7cs.CVcs.MM

TL;DR

Graph-based subspace clustering and learning require similarity graphs that retain intra-subspace connections despite errors, but existing input-space error modeling requires error-structure assumptions and costly convex optimization. The paper removes error effects in projection space using IPD, constructs L2-Graph, and develops robust learning and clustering methods. Experiments report strong performance across feature extraction, image clustering, and motion segmentation, including higher recognition rates on corrupted facial images.

  • Problem

    Existing graph methods can connect points from different subspaces under corruption, while error-removal approaches require prior error-structure knowledge and expensive convex optimization.

  • Method

    The paper removes error effects from projection space using IPD and constructs an ℓ2-based sparse similarity graph, L2-Graph, for subspace learning and clustering.

  • Results

    L2-Graph outperforms tested methods, with recognition rates 5.8% and 7.5% higher than the second-best method for two facial disguises.

  • Takeaways & Limitations

    The proposed graph supports robust subspace learning and clustering across feature extraction, image clustering, and motion segmentation.

Abstract

from arXiv · show

Under the framework of graph-based learning, the key to robust subspace clustering and subspace learning is to obtain a good similarity graph that eliminates the effects of errors and retains only connections between the data points from the same subspace (i.e., intra-subspace data points). Recent works achieve good performance by modeling errors into their objective functions to remove the errors from the inputs. However, these approaches face the limitations that the structure of errors should be known prior and a complex convex problem must be solved. In this paper, we present a novel method to eliminate the effects of the errors from the projection space (representation) rather than from the input space. We first prove that $\ell_1$-, $\ell_2$-, $\ell_{\infty}$-, and nuclear-norm based linear projection spaces share the property of Intra-subspace Projection Dominance (IPD), i.e., the coefficients over intra-subspace data points are larger than those over inter-subspace data points. Based on this property, we introduce a method to construct a sparse similarity graph, called L2-Graph. The subspace clustering and subspace learning algorithms are developed upon L2-Graph. Experiments show that L2-Graph algorithms outperform the state-of-the-art methods for feature extraction, image clustering, and motion segmentation in terms of accuracy, robustness, and time efficiency.

I. INTRODUCTION

Graph-based subspace learning depends on a similarity graph that preserves intra-subspace connections despite errors. The paper proposes eliminating errors in projection space through IPD and building L2-Graph for robust clustering and learning.

  • I. INTRODUCTION: Graph-based methods seek a sparse block-diagonal affinity matrix whose nonzero entries connect data points from the same subspace.This graph supports subspace clustering and subspace learning.
  • I. INTRODUCTION: Errors can create strong connections between points from different subspaces, degrading graph-based methods.This occurs when data lie near intersections of multiple dependent subspaces.
  • I. INTRODUCTION: Existing error-removal approaches model errors in the input-space objective, requiring prior knowledge of error structure and solving computationally expensive convex problems.Their complexity is at least proportional to the cube of the data size.
  • I. INTRODUCTION: The paper instead removes error effects from the projection space and uses Intra-subspace Projection Dominance to construct L2-Graph.The approach targets ℓp- and nuclear-norm-based projection spaces, with p = {1, 2, ∞}.
  • I. INTRODUCTION: L2-Graph has a closed-form solution and is incorporated into graph embedding to produce robust subspace learning and subspace clustering algorithms.The paper reports applications in feature extraction, image clustering, and motion segmentation.

III. INTRA-SUBSPACE PROJECTION DOMINANCE

The section establishes Intra-subspace Projection Dominance (IPD): projection coefficients for intra-subspace points exceed those for inter-subspace points under stated ℓp-norm conditions. The result connects this dominance to subspace geometry through the first principal angle.

  • IPD in ℓp-norm based Projection Space: IPD requires intra-subspace coefficients to be larger than inter-subspace coefficients in ℓp-norm projection spaces.The analysis considers p = 1, 2, and ∞ and distinguishes points from the same versus different subspaces.
  • IPD in ℓp-norm based Projection Space: Theorem 1 establishes the coefficient dominance for nonzero points in a subspace outside its intersection with the inter-subspace span.Its conclusion identifies the relevant ordering of the largest coefficient magnitudes for the optimal representation.
  • IPD in ℓp-norm based Projection Space: Lemma 1 gives a necessary and sufficient condition for IPD when a point lies in the intersection of the two subspaces.The condition compares the ℓp-norms of representations over intra-subspace and inter-subspace dictionaries.
  • IPD in ℓp-norm based Projection Space: Theorem 2 relates IPD to the first principal angle, singular values, and the maximum column norm of the inter-subspace dictionary.The first principal angle satisfies cos θmin ∈ [0, 1), providing a geometric separation quantity in the sufficient condition.

B. IPD in Nuclear-norm based Projection Space

The nuclear-norm projection space also satisfies IPD, extending the theoretical dominance property beyond ℓp-norm representations. This supports removing error effects by retaining dominant representation coefficients.

  • IPD in Nuclear-norm based Projection Space: The nuclear-norm projection space shares the IPD property according to theoretical results based on low-rank representations.The analysis uses singular-value decompositions and optimal low-rank solutions.
  • IPD in Nuclear-norm based Projection Space: The low-rank analysis assumes the data matrix is free of errors in the relevant lemma.The paper separately formulates observed data as clean data plus an error matrix in D = D0 + De.
  • IPD in Nuclear-norm based Projection Space: The nuclear-norm construction relies on truncated singular-value decompositions that retain the leading singular components.The truncation operator keeps the first k elements and sets the remainder to zero.
  • IPD in Nuclear-norm based Projection Space: The IPD-based error-handling strategy keeps k largest entries and zeros the others, with k generally set to the corresponding subspace dimensionality.A toy ℓ2 example shows thresholding removes inter-cluster connections and separates the dependent-subspace clusters.

IV. CONSTRUCTING THE L2-GRAPH FOR ROBUST SUBSPACE LEARNING AND SUBSPACE CLUSTERING

The paper constructs L2-Graph from IPD in the ℓ2-norm projection space and extends it to robust subspace learning and subspace clustering.

  • Constructing the L2-Graph: L2-Graph is based on the IPD property of the ℓ2-norm projection space.The framework is generalized by incorporating the resulting graph into spectral clustering and subspace learning.

A. Algorithms Description

The algorithms obtain linear representations, hard-threshold them to suppress error effects, symmetrize the retained coefficients into an affinity matrix, and use that graph for learning or clustering.

  • Algorithms Description: For each data point, L2-Graph computes a representation over a dictionary containing the other data points.The dictionary excludes the point being represented by placing zero at its corresponding position.
  • Algorithms Description: The representation objective uses squared reconstruction error plus an ℓ2 penalty, subject to a zero-sum coefficient constraint.The objective is described as a ridge regression problem and is solved using a Lagrangian formulation.
  • Algorithms Description: Hard thresholding keeps k largest representation entries and zeros the others to eliminate error effects in projection space.The generally optimal k equals the dimensionality of the corresponding subspace.
  • Algorithms Description: After graph construction, the method performs subspace learning and subspace clustering using the resulting affinity graph.The two procedures are summarized in the paper’s Algorithms 1 and 2.
  • Algorithms Description: The affinity matrix is symmetrized as Wij = |cij| + |cji| and each column is normalized to unit ℓ2-norm.Here cij denotes the jth entry of the representation ci.

B. Computational Complexity Analysis

L2-Graph has computational complexity O(mn^2+n^3), lower than the stated costs of sparse-representation and low-rank-representation alternatives.

  • O(mn^2+n^3) is the total computational complexity of L2-Graph for data X ∈ R^(m×n).This includes computing P and Q, projecting data points, and finding the k largest coefficients.
  • L2-Graph requires O(mn^2+n^3) storage and computation for P and Q, followed by O(mn) projection and O(k log k) thresholding.
  • Sparse-representation methods require O(tm^2n^2 + tmn^3), while low-rank representation requires O(tnm^2 + tn^3).Here, t denotes the iterative number of the corresponding optimizer.

C. Estimating the Structure of Data Space with L2-Graph

L2-Graph estimates latent data structure by constructing and processing an affinity graph, enabling estimates of subspace count, sub-manifolds, and intrinsic dimensionality.

  • C. Estimating the Structure of Data Space with L2-Graph: L2-Graph estimates the number of subspaces, sub-manifolds, and subspace dimensionality from the graph.
  • C. Estimating the Structure of Data Space with L2-Graph: DBSCAN discretizes Laplacian eigenvalues when the affinity matrix is not strictly block-diagonal, enabling subspace-number estimation.
  • C. Estimating the Structure of Data Space with L2-Graph: The method computes representations, removes error effects by retaining k largest coefficients, and constructs a normalized affinity matrix from reciprocal coefficient magnitudes.
  • C. Estimating the Structure of Data Space with L2-Graph: It forms a Laplacian from the affinity matrix, extracts eigenvectors associated with its smallest nonzero eigenvalues, and clusters their rows with k-means.
  • C. Estimating the Structure of Data Space with L2-Graph: 10 unique nonzero eigenvalues identify 10 subjects in the Extended Yale B example, matching the ground truth.
  • C. Estimating the Structure of Data Space with L2-Graph: The affinity matrix reveals two light-source sub-manifolds, while its energy concentrates in six components, indicating intrinsic dimensionality around 6.

V. EXPERIMENTAL VERIFICATION AND ANALYSIS

The experiments evaluate L2-Graph for subspace learning and clustering across face and motion-segmentation tasks, focusing on accuracy, robustness, and computational cost.

  • V. EXPERIMENTAL VERIFICATION AND ANALYSIS: Experiments assess L2-Graph in subspace learning, face clustering, and motion segmentation.
  • V. EXPERIMENTAL VERIFICATION AND ANALYSIS: The evaluation considers accuracy, robustness, and computational cost.

A. Subspace Learning

The subspace-learning experiments compare L2-Graph with established feature-extraction methods using facial-image benchmarks and recognition or classification performance.

  • A. Subspace Learning: The comparison includes LPP, NPE, Eigenfaces, L1-Graph, LRR, and LatLRR for robust feature extraction.
  • A. Subspace Learning: Fig. 3 reports classification accuracy as training AR1 images increase and 1-NN recognition rates across subspace-learning methods over ExYaleB.
  • A. Subspace Learning: The experiments use the ExYaleB, AR, and MPIE facial data sets.

2) Data Sets:

The experiments use facial-image datasets and evaluate subspace learning and clustering under clean, noisy, corrupted, and disguised conditions. Comparisons use shared data partitions, tuned parameters, standard clustering metrics, and several competing graph methods.

  • Datasets: ExYaleB, AR, and MPIE provide facial-image benchmarks spanning multiple subjects, clean samples, disguises, illuminations, and sessions.AR includes clean images and sunglasses- or scarf-disguised images; MPIE contains images from four sessions.
  • Protocol: Training data learns a projection matrix, while each test sample is assigned to its nearest training sample in the projected feature space.All algorithms use the same training and testing partitions.
  • Corruption settings: Robustness tests use white Gaussian noise and random pixel corruption, with corruption rates illustrated from 10% to 90%.Gaussian noise is additive, whereas random pixel corruption replaces randomly selected pixel values.
  • Disguised images: AR2 and AR3 evaluate sunglasses and scarf disguises, with approximate occlusion rates of 20% and 40%, respectively.Each subset contains 600 clean and 600 disguised images.
  • Clustering evaluation: Subspace clustering compares L2-Graph with SSC, LRR, LSR variants, and LLR using spectral clustering and tuned parameters.Accuracy and NMI measure clustering quality, with 1 indicating perfect matching and 0 perfect mismatch.

2) Evaluation Metrics:

The evaluation examines preprocessing, parameter sensitivity, recognition, clustering, and robustness across clean and corrupted facial-image settings. Results emphasize L2-Graph’s accuracy, robustness, and parameter behavior.

  • Preprocessing: Images are downsized and reduced by PCA while retaining 98% energy; AR1 experiments use 167 extracted features.AR1 images are reduced from 165 × 120 to 55 × 40 before PCA.
  • Parameters: L2-Graph uses balance parameter λ and thresholding parameter k, with larger λ generally suited to corrupted images and k related to subspace dimensionality.The parameters depend on the data distribution.
  • Parameter sensitivity: Accuracy and NMI remain almost unchanged as λ increases from 0.1 to 1.0 while k ranges from 4 to 9.This sensitivity test uses a corrupted ExYaleB subset containing 580 images from 10 individuals.
  • Parameter sensitivity: Thresholding k improves robustness by retaining informative coefficients while removing trivial coefficients associated with errors.The optimal k is reported near the corresponding subspace’s intrinsic dimensionality; for the first Extended Yale B subject, that dimensionality is 6.
  • Image clustering: At L = 100 subjects, L2-Graph’s Accuracy is at least 1.8% higher than LSR1, 2.7% higher than LSR2, 24.5% higher than SSC, 8.8% higher than LRR, and 42.5% higher than LLR.On the same experiment, NMI varies slightly from 93.0% to 94.3% as subject number increases.
  • Image clustering: Across six image datasets, L2-Graph achieves the best clustering results except on MPIE-S4, where it ranks second, while showing robustness advantages over tested alternatives.On ExYaleB, its Accuracy exceeds LSR by about 10.28% and LLR by 34.96%.

7) Clustering on Corrupted Images:

Corrupted-image and motion-segmentation experiments test L2-Graph against challenging noise, pixel corruption, disguises, and multiple-motion trajectories. L2-Graph generally achieves stronger robustness, especially under harder corruption and three-motion settings.

  • Corrupted images: Non-additive random pixel corruption is more challenging than additive white Gaussian noise for all investigated methods.This comparison uses ExYaleB with half the images corrupted by either corruption type.
  • Corrupted images: Under white Gaussian noise, L2-Graph’s Accuracy gain over LSR2 ranges from 14.0% to 22.8%, compared with 5.0% to 13.2% under random pixel corruption.L2-Graph is also reported as more robust than LSR1, SSC, LRR, and LLR.
  • Disguised images: For sunglasses occlusion, L2-Graph’s Accuracy is 30.59% higher than SSC-Homotopy, 40.17% higher than SSC, 13.92% higher than LRR, and 48.59% higher than LLR.For scarf occlusion, the corresponding gains are 40.25%, 44.00%, 17.58%, and 54.31%.
  • Motion segmentation: On Hopkins155, L2-Graph outperforms the other tested methods on three-motion data and performs comparably on two-motion data.The benchmark contains 155 independent clustering tasks: 120 with two motions and 35 with three motions.
  • Motion segmentation: All algorithms perform better on two-motion data than on three-motion data.The reported metric is segmentation error, defined as 1-Accuracy.
  • Conclusion: The conclusion frames L2-Graph as a representation-space error-removal approach validated for unsupervised feature extraction, image clustering, and motion segmentation.Its basis is the Intra-subspace Projection Dominance property.
Loading 1209.0841v7…