PaperlayerView exact revision on arXiv

Source-linked AI summary

Scalable Sparse Subspace Clustering by Orthogonal Matching Pursuit

Chong You, Daniel P. Robinson, Rene Vidal

arXiv:1507.01238v3cs.CVcs.LGstat.ML

TL;DR

Subspace clustering needs both broad subspace-preservation guarantees and computational efficiency, but existing regularizers typically favor one. This paper studies SSC-OMP, which uses orthogonal matching pursuit, and reports a favorable accuracy–computation trade-off with theoretical guarantees and large-scale empirical support.

  • Problem

    Existing methods either require large-scale convex optimization for broad guarantees or stronger assumptions for efficient closed-form solutions.

  • Method

    SSC-OMP uses orthogonal matching pursuit instead of SSC-BP’s ℓ1-based basis pursuit to find sparse self-expressive representations.

  • Results

    SSC-OMP has broader guarantees than ℓ2 or nuclear-norm methods, is slightly less accurate than SSC-BP but orders of magnitude faster, and supports experiments with 100,000 points.

  • Takeaways & Limitations

    SSC-OMP provides the paper’s reported best accuracy-versus-computation trade-off for the evaluated subspace-clustering tasks.

  • Takeaways & Limitations

    A deterministic condition comparison favors a tighter but algorithm-specific residual-based condition over a looser data-point-based condition.

Abstract

from arXiv · show

Subspace clustering methods based on $\ell_1$, $\ell_2$ or nuclear norm regularization have become very popular due to their simplicity, theoretical guarantees and empirical success. However, the choice of the regularizer can greatly impact both theory and practice. For instance, $\ell_1$ regularization is guaranteed to give a subspace-preserving affinity (i.e., there are no connections between points from different subspaces) under broad conditions (e.g., arbitrary subspaces and corrupted data). However, it requires solving a large scale convex optimization problem. On the other hand, $\ell_2$ and nuclear norm regularization provide efficient closed form solutions, but require very strong assumptions to guarantee a subspace-preserving affinity, e.g., independent subspaces and uncorrupted data. In this paper we study a subspace clustering method based on orthogonal matching pursuit. We show that the method is both computationally efficient and guaranteed to give a subspace-preserving affinity under broad conditions. Experiments on synthetic data verify our theoretical analysis, and applications in handwritten digit and face clustering show that our approach achieves the best trade off between accuracy and efficiency.

1. Introduction

Subspace clustering partitions data drawn from unions of low-dimensional subspaces, while existing regularizers trade computational efficiency against broad subspace-preservation guarantees. The paper introduces SSC-OMP to target both properties.

  • Motivation: Subspace clustering partitions data into groups whose points belong to the same subspace.Applications include motion segmentation, handwritten digit clustering, and face clustering.
  • Sparse and Low Rank Methods: Self-expressiveness represents each point as a linear combination of other points, enabling construction of an affinity matrix for spectral clustering.A representation is subspace preserving when nonzero coefficients connect only points from the same subspace.
  • Sparse and Low Rank Methods: ℓ2 and nuclear-norm methods compute coefficients efficiently from the SVD of noiseless data, but guarantee subspace preservation only under independent subspaces and uncorrupted data.This motivates methods combining broad guarantees with computational efficiency.
  • Paper Contributions: SSC-OMP replaces SSC-BP’s ℓ1-based basis pursuit with orthogonal matching pursuit to obtain sparse representations.The paper studies theoretical preservation conditions and large-scale efficiency for this approach.
  • Paper Contributions: SSC-OMP is shown to preserve subspaces under deterministic separation or distribution conditions and random-model dimensional conditions, while being orders of magnitude faster than SSC-BP and handling up to 100,000 points.The authors report that SSC-OMP is slightly less accurate than SSC-BP but much faster.

2. SSC by Orthogonal Matching Pursuit

SSC-OMP finds sparse self-expressive representations with orthogonal matching pursuit instead of ℓ1 minimization. It then symmetrizes the coefficient matrix into an affinity matrix and applies spectral clustering.

  • Sparse Representation: SSC represents each point using other points, seeking a sparse coefficient vector because each point can be expressed using few points from its subspace.The ideal sparsity-constrained problem is difficult, motivating tractable alternatives.
  • Sparse Representation: SSC-BP denotes the original SSC algorithm because it solves the basis pursuit problem, an ℓ1-minimization relaxation of sparsity.Compressed-sensing equivalence results do not directly apply because coefficient solutions may be nonunique on unions of subspaces.
  • Subspace Preservation: A representation is subspace preserving when every nonzero coefficient corresponds to a point in the target point’s subspace.This property prevents cross-subspace connections in the representation.
  • Orthogonal Matching Pursuit: OMP greedily selects dictionary columns with largest residual correlations, recomputes coefficients on the selected support, and stops after kmax selections or when the residual falls below ϵ.The resulting coefficients need not be the unique sparse solution sought in conventional sparse recovery.
  • SSC-OMP Algorithm: For each point x_j, SSC-OMP computes c*_j = OMP(X−j, x_j), inserting a zero at position j.X−j removes the point being represented from the dictionary.
  • SSC-OMP Algorithm: SSC-OMP forms W = |C*| + |C*^⊤| from all representations and obtains the final segmentation by spectral clustering.This affinity construction is shared with SSC-BP.

3. Theoretical Analysis of SSC-OMP

Theoretical analysis establishes conditions under which SSC-OMP produces subspace-preserving representations, first for independent subspaces and then for arbitrary deterministic and random subspaces. The conditions require separation between subspaces and sufficient within-subspace point distribution, with success improving as data density increases.

  • Assumptions: SSC-OMP is analyzed under noiseless data, unit-norm columns, zero residual tolerance, and a sufficiently large iteration limit.The analysis covers deterministic subspaces, including both independent and arbitrary configurations, and random subspaces and data points.
  • Independent deterministic subspaces: OMP outputs a subspace-preserving representation when the subspaces are independent.This follows because exact representation over independent subspaces cannot use nonzero coefficients from other subspaces.
  • Arbitrary deterministic subspaces: The geometric condition requires points from different subspaces to be sufficiently separated and points within each subspace to be well distributed.Coherence controls inter-subspace separation, while the inradius measures the relevant within-subspace coverage.
  • Arbitrary deterministic subspaces: OMP preserves subspaces when cross-subspace coherence of residual directions is below the within-subspace inradius.Theorem 2 formalizes this as max k:k≠i µ(Wi, Xk) < ri for every subspace i.
  • Arbitrary deterministic subspaces: The data-only sufficient condition is weaker in tightness but easier to evaluate than the residual-based condition.Corollary 1 depends directly on X, whereas Theorem 2 uses algorithm-specific residual points Wi.
  • Arbitrary random subspaces: Under the random union-of-subspaces model, SSC-OMP succeeds with high probability when subspace dimension, ambient dimension, number of subspaces, and point density satisfy the stated condition.The success probability and the condition depend on N(n,ρ,d), with c(ρ)>0 depending only on ρ; increasing density makes the condition easier to satisfy and raises success probability beyond a threshold.

4. Relationships with Other Methods

SSC-OMP matches competing methods on independent subspaces, while comparisons for arbitrary and random subspaces reveal stricter conditions but diminishing differences at scale. A prior SSC-OMP condition is also more restrictive than the paper’s Theorem 2.

  • Independent Subspaces: Under independent subspaces, SSC-BP, LRR, LRSC, LSR, and SSC-OMP all produce subspace-preserving representations.The paper characterizes independence as a strong assumption involving trivial intersections with every other subspace and their union.
  • Arbitrary Subspaces: For arbitrary subspaces, SSC-OMP’s condition is not directly comparable to SSC-BP’s because their direction sets differ in size and construction.The compared sets have cardinalities N_i for V_i and N_i d_i for W_i, with no general relationship known between them.
  • Arbitrary Subspaces: SSC-OMP’s arbitrary-subspace condition is more difficult to satisfy than SSC-BP’s under the stated comparison, although the difference is expected to vanish for large-scale problems.The comparison attributes this to the larger expected coherence for W_i and the smaller right-hand side r_i^2.
  • Random Subspaces: For random subspaces, SSC-BP and SSC-OMP require exactly the same condition for success with high probability, while SSC-BP has a higher success probability when d > 1.The probability gap tends to zero as the density ρ increases, so the performance difference vanishes as problem scale grows.
  • Other Results for SSC-OMP: A prior SSC-OMP guarantee incorporates subspace angles but is more restrictive than condition (10), making Theorem 2 stronger.The earlier condition also couples the intra-class quantity r_i with the inter-class angle θ∗i,k, complicating interpretation.

5. Experiments

Experiments compare SSC-OMP with SSC-BP, LSR, LRSC, and SCC on synthetic, handwritten-digit, and face-clustering tasks using subspace-preservation, connectivity, accuracy, and running time. SSC-OMP generally trades some representation quality for substantially lower computation and strong clustering performance.

  • 5. Experiments: The experiments conclude that SSC-OMP provides the best trade-off between clustering accuracy and computational efficiency for large-scale subspace clustering.The comparison includes representation quality, connectivity, accuracy, and running time across synthetic and real datasets.
  • 5.1. Synthetic Experiments: Synthetic experiments vary five six-dimensional subspaces in nine dimensions from 150 to 99,990 points, while SSC-BP is limited to 6,000 points by computation time.The reported experimental values are averages over 20 trials.
  • 5.1. Synthetic Experiments: As data density increases, SSC-OMP’s probability of producing a subspace-preserving solution increases, but SSC-BP outperforms it on this metric.The authors attribute this to SSC-OMP requiring a stronger condition for subspace preservation.
  • 5.1. Synthetic Experiments: 3 to 4 orders of magnitude faster at 6,000 points, SSC-OMP reduces its clustering-accuracy gap with SSC-BP as dataset density increases.SSC-OMP has weaker connectivity and lower accuracy than SSC-BP on synthetic data, but appears to achieve arbitrarily good accuracy for large N.
  • 5.2. Clustering Images of Handwritten Digits: On MNIST, SSC-OMP and SSC-BP have much smaller subspace-preserving representation errors than the other methods, with SSC-BP better than SSC-OMP.SSC-OMP nevertheless achieves higher clustering accuracy than SSC-BP, which outperforms LSR and LRSC; SCC performs worst.
  • 5.3. Clustering Face Images with Varying Lighting: On Extended Yale B, SSC-BP is slightly better than SSC-OMP for subspace-preserving recovery, while SSC-OMP performs better when the number of subjects exceeds 10.As subjects increase from 10 to 38, LSR and LRSC remain near 60% accuracy, whereas SSC-OMP and SSC-BP retain reasonably good but gradually declining performance.

6. Conclusion and Future Work

The paper concludes that SSC-OMP offers a favorable accuracy–computation trade-off for large-scale subspace clustering, while leaving comparison with a scalable elastic-net method for future work.

  • 6. Conclusion and Future Work: SSC-OMP has broader theoretical conditions than ℓ2- and nuclear-norm methods, but slightly weaker conditions than SSC-BP.Its experiments support strong accuracy relative to ℓ2- and nuclear-norm methods and slightly lower accuracy than SSC-BP.
  • 6. Conclusion and Future Work: SSC-OMP is about twice as slow as ℓ2- and nuclear-norm methods but orders of magnitude faster than SSC-BP.The paper reports experiments involving up to 100,000 points.
  • 6. Conclusion and Future Work: SSC-OMP provides the best accuracy-versus-computation trade-off for large-scale subspace clustering problems.A comparison with the authors’ scalable elastic-net subspace-clustering method is left for future research.

A. Proof of Theorem 1

Theorem 1 proves subspace preservation when the subspaces are independent. Under zero-error termination and a full dictionary budget, OMP’s selected points remain in the target subspace and terminate with a valid representation.

  • A. Proof of Theorem 1: Under independent subspaces, OMP gives a subspace-preserving representation for every data point.The proof considers x_j in S_i and shows that OMP selects only points from S_i.
  • A. Proof of Theorem 1: The proof sets ε = 0 and kmax = N − 1, ensuring termination once the residual becomes zero.The resulting iteration count is bounded by the available dictionary size.
  • A. Proof of Theorem 1: The proof assumes enough samples on each subspace to support the required rank condition.This assumption is stated as applying to every point in every subspace.
  • A. Proof of Theorem 1: Independence makes S_i and the union of the other subspaces intersect only at the origin, forcing the relevant coefficients outside S_i to vanish.This establishes that the final coefficient vector is subspace-preserving.

B. Proof of Lemma 1

Lemma 1’s proof compares OMP on the full dictionary with a fictitious OMP restricted to the target subspace. Under the stated residual-separation condition, both procedures follow the same path and produce a subspace-preserving representation within at most d_i iterations.

  • B. Proof of Lemma 1: The proof maintains equal residuals and target-subspace selections between full-dictionary OMP and fictitious OMP restricted to S_i.This invariant is established inductively from the empty initial support and equal initial residuals.
  • B. Proof of Lemma 1: Lemma 3 guarantees subspace preservation for x_j ∈ S_i in at most d_i iterations when target-subspace correlations dominate all other-subspace correlations.The condition compares every residual direction with points in S_i and points outside S_i.
  • B. Proof of Lemma 1: The residual-direction condition forces the next arg-max selection to come from S_i, preserving the support’s subspace membership.The selected point and subsequent residual are the same in both OMP procedures.
  • B. Proof of Lemma 1: Because the selected points are linearly independent within S_i and dim(S_i) = d_i, OMP terminates after at most d_i iterations.The proof combines the shared computation path with linear independence and the subspace dimension.

C. Proof of Lemma 2

The proof bounds cross-subspace coherence for residual directions by relating each residual direction to a representation using points from its own subspace.

  • For any residual direction ˆw in Wi, the proof represents ˆw as Xi·c for a coefficient vector selected by an optimization program.This representation enables bounding its interactions with points from another subspace.
  • Cauchy-Schwarz applied to Y⊤ = Xk⊤·Xi reduces the cross-subspace interaction bound to a term involving the coefficient norm ∥ˆc∥1.The proof defines Y and its columns before applying the inequality.
  • A bound on ∥ˆc∥1 follows from the optimization definition and a result involving Pi := conv(±Xi).The argument also uses that residual directions in Wi have unit norm.
  • The proof concludes that µ(Wi, Xk) ≤ µ(Xi, Xk)/ri for every k ≠ i.This establishes the required bound uniformly over the other subspaces.

D. Proof of Theorem 2 and Corollary 1

The theorem gives a sufficient condition for OMP to produce a subspace-preserving output, while the corollary supplies a stronger condition based directly on the data-point coherence.

  • Theorem 2: OMP is subspace preserving when, for every i, max k:k̸=i µ(Wi, Xk) < ri.The condition compares cross-subspace coherence of residual directions with the inradius ri.
  • Corollary 1: The corollary gives a sufficient condition using max k:k̸=i µ(Xi, Xk) < r2.It replaces residual-direction coherence with coherence between the original point sets.
  • Proof strategy: The proof derives both results from Lemma 1's criterion for subspace-preserving SSC-OMP solutions and Lemma 2's bounds on the two sides of that criterion.The inequalities are therefore inherited from the preceding lemmas.

E. Proof of Theorem 3

Under a random model with equal-dimensional subspaces and density ρ, the proof bounds inradius and cross-subspace coherence before applying a union bound to establish high-probability subspace preservation.

  • Random model: The random model uses equal subspace dimension d and ρd+1 points per subspace, with ρ > 1 and N = n(ρd+1).Points are independently and uniformly distributed on the ambient unit sphere.
  • Inradius bound: The inradius bound involves a constant c(ρ) that depends only on the density parameter ρ.The supplied bound is stated through c(ρ) and logarithmic and dimensional factors.
  • Proof strategy: The proof establishes the sufficient condition ∀i, max k:k̸=i µ(Wi, Xk) < ri by separately bounding coherence and inradius.This is the theorem condition used to guarantee subspace preservation.
  • Coherence bound: Independent uniform sampling makes residual directions and points from other subspaces independent, allowing spherical-cap bounds for the coherence term.The argument then controls the relevant inner-product pairs using a union bound.
  • Probability guarantee: When condition (E.1) holds, the inradius bound is below the coherence bound, and a second union bound yields the probability guarantee in the theorem.The proof states the resulting probability as p > 1 − p̄µd − p̄r.
  • Comparison with prior work: The paper presents its theorem condition as stronger than an earlier SSC-OMP sufficient condition because (F.3) implies (F.1).The comparison states that the prior result is weaker under the cases discussed for ri.

G. Parameters for real experiments

The real-data experiments use explicitly reported OMP and baseline parameters, with selected normalization preprocessing and post-processing allowed for fair comparison.

  • OMP parameters: OMP uses ϵ = 10^-3, with kmax set to the true subspace dimension for synthetic data, 10 for digit clustering, and 5 for face clustering.These settings are reported for reproducibility.
  • Baseline parameters: LSR uses LSR2 with λ = 60 for digit clustering and λ = 0.3 for face clustering, while LRSC uses model P3 with task-specific parameters.The passage reports the baseline configurations alongside OMP.
  • Pre/post-processing: Fair comparisons allow ℓ2 normalization of original data points and ℓ∞ normalization of coefficient vectors when these improve clustering accuracy.Synthetic experiments use no pre/post-processing; digit experiments apply preprocessing to SSC-BP and SCC and post-processing to SSC-OMP and SSC-BP.
Loading 1507.01238v3…