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

研究成果: Conference contribution同行評審

摘要

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.

原文English
主出版物標題2020 IEEE 11th Sensor Array and Multichannel Signal Processing Workshop, SAM 2020
發行者IEEE Computer Society
ISBN(電子)9781728119465
DOIs
出版狀態Published - 六月 2020
事件11th IEEE Sensor Array and Multichannel Signal Processing Workshop, SAM 2020 - Hangzhou, China
持續時間: 8 六月 202011 六月 2020

出版系列

名字Proceedings of the IEEE Sensor Array and Multichannel Signal Processing Workshop
2020-June
ISSN(電子)2151-870X

Conference

Conference11th IEEE Sensor Array and Multichannel Signal Processing Workshop, SAM 2020
國家China
城市Hangzhou
期間8/06/2011/06/20

指紋 深入研究「Deterministic coherence-based performance guarantee for noisy sparse subspace clustering using greedy neighbor selection」主題。共同形成了獨特的指紋。

引用此