Deterministic Coherence-Based Performance Guarantee for Noisy Sparse Subspace Clustering using Greedy Neighbor Selection
ID:53 View Protection:ATTENDEE Updated Time:2020-08-05 10:17:00 Hits:442 Oral Presentation

Start Time:2020-06-09 14:30(Asia/Shanghai)


Session:R Regular Session » R02Compressed Sensing and Sparse Signal Processing

Video No Permission

Tips: Only the registered participant can access the file. Please sign in first.

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.
subspace clustering; sparse subspace clustering; compressive sensing; coherence; matching pursuit; orthogonal matching pursuit
Jwo-Yuh Wu
National Chiao Tung University, Taiwan

Submission Author
Jwo-Yuh Wu National Chiao Tung University, Taiwan
Wen-Hsian Li National Chiao Tung University, Taiwan
Liang-Chi Huang National Chiao Tung University, Taiwan
Yen-Ping Lin National Chiao Tung University, Taiwan
Chun-Hung Liu Mississippi State University, USA
Rung-Hung Gau National Chiao Tung University, Taiwan
Submit Comment
Verify Code Change Another
All Comments
Important Date
  • Conference Date

    Jun 08



    Jun 11


  • Jan 12 2020

    Draft paper submission deadline

  • Apr 15 2020

    Early Bird Registration

  • Dec 31 2020

    Registration deadline

Sponsored By
IEEE Signal Processing Society
Contact Information