Deterministic coherence-based performance guarantee for noisy sparse subspace clustering using greedy neighbor selection

Jwo Yuh Wu, Wen Hsuan Li, Liang Chi Huang, Yen Ping Lin, Chun Hung Liu, Rung Hung Gau

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

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 l 1 -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.

Original languageEnglish
Title of host publication2020 IEEE 11th Sensor Array and Multichannel Signal Processing Workshop, SAM 2020
PublisherIEEE Computer Society
ISBN (Electronic)9781728119465
DOIs
StatePublished - Jun 2020
Event11th IEEE Sensor Array and Multichannel Signal Processing Workshop, SAM 2020 - Hangzhou, China
Duration: 8 Jun 202011 Jun 2020

Publication series

NameProceedings of the IEEE Sensor Array and Multichannel Signal Processing Workshop
Volume2020-June
ISSN (Electronic)2151-870X

Conference

Conference11th IEEE Sensor Array and Multichannel Signal Processing Workshop, SAM 2020
CountryChina
CityHangzhou
Period8/06/2011/06/20

Keywords

  • Coherence
  • Compressive sensing
  • Matching pursuit
  • Orthogonal matching pursuit
  • Sparse representation
  • Sparse subspace clustering
  • Subspace clustering

Fingerprint Dive into the research topics of 'Deterministic coherence-based performance guarantee for noisy sparse subspace clustering using greedy neighbor selection'. Together they form a unique fingerprint.

Cite this