Noisy ℓ0-Sparse Subspace Clustering on Dimensionality Reduced Data

Sparse subspace clustering methods with sparsity induced by ℓ0-norm, such as ℓ0-Sparse Subspace Clustering (ℓ0-SSC)~citepYangFJYH16-L0SSC-ijcv, are demonstrated to be more effective than its ℓ1 counterpart such as Sparse Subspace Clustering (SSC)~citepElhamifarV13. However, the theoretical analysis of ℓ0-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 ℓ0-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 ℓ0-SSC in terms of SDP on noisy data for the first time, which reveals the advantage of noisy ℓ0-SSC in terms of much less restrictive condition on subspace affinity. In order to improve the efficiency of noisy ℓ0-SSC, we propose Noisy-DR-ℓ0-SSC which provably recovers the subspaces on dimensionality reduced data. Noisy-DR-ℓ0-SSC first projects the data onto a lower dimensional space by random projection, then performs noisy ℓ0-SSC on the projected data for improved efficiency. Experimental results demonstrate the effectiveness of Noisy-DR-ℓ0-SSC.