Sparse nonnegative CP decomposition with graph regularization and ℓ0-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 ℓ0-norm regularization, as the ℓ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 ℓ0-norm constraints (ℓ0-SGNCP) method, which directly employs the ℓ0-norm constraints to explicitly control the sparsity of the factor matrices in NCP. Furthermore, ℓ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 ℓ0-norm constraints make optimizing ℓ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 ℓ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.