Sparse nonnegative CP decomposition with graph regularization and ℓ₀-constraints for clustering

Sparse nonnegative CP decomposition is one of the most popular tools for tensor data representation. However, most existing sparse NCP (nonnegative CP decomposition) methods promote the sparsity of the factor matrices by using a relaxation scheme of \ell_0-norm regularization, as the \ell_0-norm is nonconvex and nonsmooth. This prevents these sparse NCP methods from directly and explicitly controlling the sparsity of the factor matrices, reducing the feature extraction ability. To overcome this defect, we propose a novel sparse and graph-regularized nonnegative CP decomposition with \ell_0-norm constraints (\ell_0-SGNCP) method, which directly employs the \ell_0-norm constraints to explicitly control the sparsity of the factor matrices in NCP. Furthermore, \ell_0-SGNCP incorporates graph regularization to preserve the manifold structure of data. Although the nonconvex nature of NCP and the nonconvex and nonsmooth nature of the \ell_0-norm constraints make optimizing \ell_0-SGNCP an NP-hard problem, we propose an Alternating Proximal Gradient Linearized (APGL) algorithm which provides a practical convergent scheme to directly solve the original \ell_0-SGNCP instead of solving its relaxed version. We also establish the global convergence of our proposed algorithm and analyze the per-iteration complexity. Experimental results on eight real-world image datasets show that our method outperforms some state-of-the-art methods for clustering.