Noisy ℓ⁰-Sparse Subspace Clustering on Dimensionality Reduced Data

^aSparse subspace clustering methods with sparsity induced by ℓ⁰-norm, such as ℓ⁰-Sparse Subspace Clustering (ℓ⁰-SSC) [Yang et al., 2018], are demonstrated to be more effective than its ℓ¹ counterpart such as Sparse Subspace Clustering (SSC) [Elhamifar and Vidal, 2013]. However, the theoretical analysis of ℓ⁰-SSC is restricted to clean data that lie exactly in subspaces. Real data often suffer from noise and they may lie close to subspaces. In this paper, we show that an optimal solution to the optimization problem of noisy ℓ⁰-SSC achieves subspace detection property (SDP), a key element with which data from different subspaces are separated, under deterministic and semi-random model. Our results provide theoretical guarantee on the correctness of noisy ℓ⁰-SSC in terms of SDP on noisy data for the first time, which reveals the advantage of noisy ℓ⁰-SSC in terms of much less restrictive condition on subspace affinity. In order to improve the efficiency of noisy ℓ⁰-SSC, we propose Noisy-DR-ℓ⁰-SSC which provably recovers the subspaces on dimensionality reduced data. Noisy-DR-ℓ⁰-SSC first projects the data onto a lower dimensional space by random projection, then performs noisy ℓ⁰-SSC on the projected data for improved efficiency. Experimental results demonstrate the effectiveness of Noisy-DR-ℓ⁰-SSC.