Deterministic Coherence-Based Performance Guarantee for Noisy Sparse Subspace Clustering using Greedy Neighbor Selection

Sparse subspace clustering (SSC) using greedy-based neighbor selection, such as matching pursuit (MP) and orthogonal matching pursuit (OMP), has been known as a popular computationally-efficient alternative to the conventional L1-minimization based solutions. Under deterministic bounded noise corruption, in this paper we derive coherence-based sufficient conditions guaranteeing correct neighbor identification using MP/OMP. Our analyses exploit the maximum/minimum inner product between two noisy data points subject to a known upper bound on the noise level. The obtained sufficient condition clearly reveals the impact of noise on greedy-based neighbor recovery. Specifically, it asserts that, as long as noise is sufficiently small and the resultant perturbed residual vectors stay close to the desired subspace, both MP and OMP succeed in returning a correct neighbor subset. Extensive numerical experiments are used to corroborate our theoretical study. A striking finding is that, as long as the ground truth subspaces are well-separated from each other, MP-based iterations, while enjoying lower algorithmic complexity, yields smaller perturbed residuals, thereby better able to identify correct neighbors and, in turn, achieving higher global data clustering accuracy.