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