Greedy Feature Selection for Subspace Clustering

Eva L. Dyer; Aswin C. Sankaranarayanan; Richard G. Baraniuk

Source-linked AI summary

Greedy Feature Selection for Subspace Clustering

Eva L. Dyer, Aswin C. Sankaranarayanan, Richard G. Baraniuk

arXiv:1303.4778v2Mar 19, 2013cs.LGmath.NAstat.ML

TL;DR

The paper asks how to reliably identify same-subspace points in high-dimensional unions of subspaces, where nearest-neighbor selection can fail. It analyzes OMP for exact feature selection and compares it with sparse recovery and NN approaches. Sparse recovery is especially advantageous under sparse subspace sampling, while EFS rates do not necessarily predict spectral-clustering performance.

Problem
Subspace clustering requires identifying points from the same subspace, but nearest-neighbor approaches become unreliable as separation decreases, intersections grow, or sampling becomes sparse.
Method
The paper develops sufficient geometric conditions for OMP-based exact feature selection and empirically compares OMP, BP, BPDN, and nearest-neighbor feature selection.
Results
Sparse recovery methods provide significant advantages over nearest-neighbor methods when subspaces are sparsely sampled, although BPDN can obtain higher EFS rates than OMP when its noise parameter is tuned.
Takeaways & Limitations
OMP is a low-complexity alternative for feature selection that can exploit nonlocal relationships and often produce better clustering results than BPDN despite lower EFS rates.
Takeaways & Limitations
EFS does not necessarily predict spectral-clustering performance: OMP can have lower EFS rates than BP yet yield better clustering on the same dataset.

Abstract

from arXiv · show

Unions of subspaces provide a powerful generalization to linear subspace models for collections of high-dimensional data. To learn a union of subspaces from a collection of data, sets of signals in the collection that belong to the same subspace must be identified in order to obtain accurate estimates of the subspace structures present in the data. Recently, sparse recovery methods have been shown to provide a provable and robust strategy for exact feature selection (EFS)--recovering subsets of points from the ensemble that live in the same subspace. In parallel with recent studies of EFS with L1-minimization, in this paper, we develop sufficient conditions for EFS with a greedy method for sparse signal recovery known as orthogonal matching pursuit (OMP). Following our analysis, we provide an empirical study of feature selection strategies for signals living on unions of subspaces and characterize the gap between sparse recovery methods and nearest neighbor (NN)-based approaches. In particular, we demonstrate that sparse recovery methods provide significant advantages over NN methods and the gap between the two approaches is particularly pronounced when the sampling of subspaces in the dataset is sparse. Our results suggest that OMP may be employed to reliably recover exact feature sets in a number of regimes where NN approaches fail to reveal the subspace membership of points in the ensemble.

1. Introduction

The paper addresses subspace clustering for high-dimensional data by using sparse representations to identify same-subspace points, especially where nearest-neighbor selection becomes unreliable. It develops OMP-based EFS conditions and compares sparse recovery with NN approaches under different sampling densities.

Motivation: Unions of subspaces require simultaneous segmentation and subspace estimation, making reliable same-subspace point selection central to learning.Local subspace estimates can simplify subsequent estimation when the selected points come from a common subspace.
Limitations of NN selection: Nearest-neighbor methods become unreliable as subspace separation decreases or subspace dimension grows relative to the number of sampled points.Increasing intersection dimension makes Euclidean distance a poorer indicator of subspace membership.
Sparse feature selection: Sparse recovery forms endogenous representations from the data, aiming to select points from the same subspace and thereby achieve exact feature selection.The paper describes BP and OMP as approximate approaches to the combinatorial sparsest-representation problem.
Theoretical contribution: OMP analysis yields a geometric EFS condition trading off cross-subspace mutual coherence against within-subspace covering radius.The condition allows nearby or intersecting subspaces when points are distributed sufficiently well within each subspace.
Theoretical contribution: For uniformly bounded subspaces, EFS can still be guaranteed with nontrivial intersections when data points are incoherent with the principal vectors supporting subspace pairs.This extends separability analysis beyond sampling properties alone.
Empirical comparison: Sparse recovery and NN methods have comparable EFS rates under dense sampling, but sparse recovery has significant advantages when subspaces are sparsely sampled.The paper attributes this advantage to exploiting nonlocal relationships between points that may be far apart in Euclidean distance.

2. Greedy Feature Selection for Subspace Clustering

The method constructs normalized subspace data, applies sparse recovery or OMP to select same-subspace features, and forms affinity matrices for clustering. OMP provides a low-complexity alternative to ℓ1-based methods, with empirical tradeoffs against BPDN and clustering performance.

Data model: The data model samples points from multiple subspaces, normalizes them to the unit sphere, and partitions them into subspace-specific clusters.Each cluster is represented by points in a subspace span, while the complementary data form the remaining dictionary.
Sparse subspace clustering: SSC uses sparse representations of each point with respect to the remaining data, followed by affinity construction and spectral clustering.The affinity matrix is formed as W = |C| + |C^T|.
Orthogonal matching pursuit: OMP replaces ℓ1-minimization with greedy sparse feature selection and returns a k-sparse representation or stops when the approximation residual reaches the prescribed threshold.At each iteration it selects the atom most correlated with the residual, updates the orthogonal residual, and repeats.
Clustering pipeline: For each point, OMP produces a feature set indexing selected columns, after which spectral or consensus-based clustering can be applied.The selected coefficients are embedded into a sparse feature vector used to form the subspace affinity.
Method comparison: OMP offers reduced computational complexity relative to convex optimization, while BPDN can achieve higher EFS rates when its noise parameter is carefully tuned.The empirical discussion also reports cases where OMP produces better clustering despite lower EFS rates.

3. Exact Feature Selection from Unions of Subspaces

This section defines exact feature selection as the target property and develops sufficient conditions ensuring it for all points in a subspace cluster.

3. Exact Feature Selection from Unions of Subspaces: The analysis formalizes exact feature selection and derives sufficient conditions guaranteeing it for every point in a particular subspace cluster.EFS concerns whether selected features remain within the same underlying subspace.

3.1 Exact Feature Selection

Exact feature selection occurs when the feature set returned for a point contains only points from its own subspace cluster. This property supports local subspace estimation and downstream clustering analysis.

3.1 Exact Feature Selection: OMP is evaluated by whether its returned feature set contains only points belonging to the same subspace cluster as the represented point.This is the paper's operational criterion for exact feature selection.
3.1 Exact Feature Selection: When EFS occurs, the selected points yield a local subspace estimate that coincides with one of the true subspaces.This makes EFS a natural performance condition for consensus and spectral clustering methods.
3.1 Exact Feature Selection: Formally, a feature set for y ∈ Y_k contains exact features when every selected point belongs to Y_k, the set lying in the span of subspace S_k.The definition uses the projector P_k to identify points in the relevant subspace span.

3.2 Geometric Conditions for EFS

The OMP EFS guarantee compares cross-subspace mutual coherence with within-subspace coverage, using covering radius, inradius, and principal-angle geometry. Its proof requires residuals to favor points in the correct cluster, equivalently constraining projections of incorrect-cluster points.

Geometric quantities: Mutual coherence is the maximum absolute normalized inner product between unit-norm points from two different subspace clusters.It is defined as μc(Yi, Yj) = max |⟨u, v⟩| over u ∈ Yi and v ∈ Yj.
Geometric quantities: The covering radius measures the largest gap between points in a normalized cluster and unit vectors in its subspace.It equals half the maximum covering diameter and can be interpreted through a deep hole and its nearest neighbor.
Geometric quantities: Theorem 1 requires both cross-cluster separation and within-cluster coverage to guarantee exact feature selection with OMP.Mutual coherence measures cross-subspace similarity, while covering quantities measure how well points represent their own subspace.
Sufficient condition: The OMP condition requires cross-subspace mutual coherence to be smaller than an inradius term minus a covering-diameter penalty involving the minimum principal angle.The inradius captures within-cluster geometry, while the penalty couples inter-subspace angle and within-subspace coverage.
Proof geometry: The proof enforces that every residual has greater normalized inner product with a correct-cluster point than with any incorrect-cluster point.Geometrically, projections of incorrect-cluster points onto the target subspace must lie within the antipodal convex hull of normalized target points.
Special cases: For disjoint subspaces, the theorem simplifies using the principal-angle bound, while vanishing covering radius reduces the requirement to μc < 1.This excludes points from different subspaces lying exactly in their intersection.

3.3 Connections to Previous Work

The OMP guarantees connect to BP and classical sparse-recovery conditions through different coherence and geometry requirements. Unlike a global incoherence ERC, EFS uses local relations between clusters, with empirical evidence indicating a possible performance gap between BPDN and OMP.

Dimension dependence: Unlike a BP-related condition whose best-case bound worsens with subspace dimension, the OMP conditions do not depend on subspace dimension.They instead require enough points in each subspace to achieve sufficiently small covering.
Comparison with BP: The OMP condition is more restrictive than the comparable BP bound by subtracting an additional term linear in the covering diameter.The gap vanishes as the minimum principal angle approaches π/2 or the covering diameter approaches zero.
Comparison with BP: When BPDN is tuned through homotopy, it achieves higher EFS rates than OMP, although the methods are comparable across a wide range of noise parameters.This supports the possibility that the theoretical gap reflects an intrinsic performance difference rather than only an analysis artifact.
Connection to ERC: The exact recovery condition controls global support recovery through incoherence of all dictionary columns, whereas EFS requires a local incoherence relation between clusters.EFS also needs within-cluster coherence sufficient to produce a small covering radius.

4. EFS for Uniformly Bounded Unions of Subspaces

For uniformly bounded unions, the analysis relates EFS to higher-order principal angles and the distribution of data along shared directions. It predicts that avoiding concentration near small-angle directions can preserve EFS even when subspaces intersect, especially under sparse sampling.

Principal-angle structure: Principal angles are computed from the singular values of G = Φi^TΦj, with cross-spectra encoding the pairwise subspace geometry.The mth principal angle satisfies cos(θij(m)) = σij(m).
Uniformly bounded unions: A uniformly bounded union requires points to be incoherent with principal vectors spanning non-orthogonal directions between subspaces.The bounding constant limits inner products between data points and those principal vectors.
Assumption and limitation: The bounded-union analysis assumes equal nonzero cross-spectra, making each supporting principal-vector pair equally important in the EFS guarantee.The authors note that this assumption does not generally hold for non-uniform principal angles.
Non-uniform angles: With non-uniform principal angles, EFS requires sufficient incoherence primarily with principal vectors associated with small angles or large cross-spectra.This permits EFS despite non-trivial intersections when points are not concentrated along those directions.
Predicted behavior: Under sparse sampling, reducing point energy in subspace intersections dramatically increases the probability of EFS.The analysis also identifies cross-spectra decay as a factor likely to influence EFS.

5. Experimental Results

The experiments vary sampling density, subspace overlap, coefficient energy, and cross-spectra to evaluate exact feature selection (EFS) for OMP and nearest neighbors. OMP benefits especially when sampling is sparse or cross-spectra have favorable structure.

5.2 Phase Transitions for OMP: EFS probability undergoes a second-order phase transition as subspace overlap and sampling density vary.Dense sampling tolerates substantially greater overlap, whereas critical sampling permits only small overlap.
5.2 Phase Transitions for OMP: At dense sampling, EFS remains likely with overlap reaching δ = 0.7, while critical sampling tolerates only δ < 0.1.The phase boundary shifts because denser sampling reduces the covering radius.
5.2 Phase Transitions for OMP: Reducing common-component energy shifts the EFS phase boundary from δ = 0.45 to δ = 0.7 for k = 20 and k = 50.The bounded energy model restricts each point’s energy in the subspace intersection.
5.3 Comparison of OMP and NN: Structured cross-spectra reveal that OMP can maintain high EFS probability when nearest-neighbor EFS falls to 0.1 at maximal overlap.The gap is largest for the union whose cross-spectra produce this contrast.
5.3 Comparison of OMP and NN: When sampling is sparse, OMP significantly outperforms nearest neighbors, including regimes where NN EFS is zero but OMP EFS remains non-trivial.The same sparse-recovery advantage appears on half and quarter real-data subsets, although OMP can have lower EFS yet better clustering than BP.

6. Discussion

The discussion examines implications of the empirical and theoretical results for sparse recovery, dictionary learning, compressive sensing, and subspace clustering. It highlights sampling-dependent advantages over nearest neighbors, open questions about dictionary geometry, and limits of EFS as a clustering predictor.

6. Discussion: The study connects sparse recovery to structured sparse signals by learning the underlying subspaces directly from data.These learned subspaces may support models of block-sparse and other structured sparse signals.
6. Discussion: Principal angles and cross-spectra may provide richer geometric descriptions of dictionaries than maximum or cumulative coherence alone.The discussion suggests that sublinear and superlinear decay in principal angles or cross-spectra may correspond to different sparse-recovery phase transitions.
6. Discussion: For discriminative dictionary learning, minimizing the ℓ1-norm of cross-spectra may be more advantageous than minimizing only maximum coherence or Frobenius norms.The proposed direction first embeds each data class in a subspace and then minimizes cross-spectra.
6. Discussion: EFS does not necessarily predict spectral-clustering performance: OMP has lower EFS rates than BP on real-world data but better clustering results on that dataset.The source identifies explaining this discrepancy as an open research direction.
6. Discussion: Sparse recovery methods offer significant advantages over nearest-neighbor methods when subspaces are sparsely sampled, whereas nearest-neighbor performance is comparable under dense sampling.The gap between the methods depends on each subspace’s sampling density.
6. Discussion: Future work includes extending deterministic analysis to random or semi-random settings and studying OMP on noisy or corrupted unions of subspaces.These directions are stated as open questions rather than established capabilities.

7. Proofs

The proofs establish OMP’s exact feature-selection guarantee by maintaining a greedy selection condition throughout the iterations. The analysis bounds competing inner products using mutual coherence, covering radius, and geometric properties of pairs of subspaces.

7. Proofs: At each iteration, OMP chooses the point maximally correlated with the normalized residual and projects onto the span of the current feature set.The current feature set contains m − 1 points, and its projector defines the residual update.
7. Proofs: OMP selects a point from the correct subspace when the greedy selection criterion favors within-subspace points over points outside it.The proof establishes this criterion by separately bounding the left- and right-hand sides.
7. Proofs: Assuming previous selections came from the correct cluster keeps the residual in that subspace, allowing it to be decomposed into a nearest point and an error component.The decomposition is written as s_m = z + e, with both components lying in the correct subspace.
7. Proofs: The first OMP selection is correct when the nearest neighbor of the target point belongs to the same subspace cluster.Under that condition, the first selected point yields exact feature selection.
7. Proofs: An ε-covering assumption on the subspace cluster supplies a bound on the residual’s error component.The proof uses cover(Y_k) = ε/2 to control the ℓ2-norm of e.
7. Proofs: The induction closes once the mutual-coherence condition guarantees the greedy criterion at every step while the residual remains in the correct subspace.This establishes Theorem 1.
7. Proofs: For bounded unions, requiring γ ≪ 1 makes the relevant coherence term small, completing the stated bound.The simplification also uses that U is unitary with spectral norm one.