A block coordinate descent approach for sparse principal component analysis

There are mainly two methodologies utilized in current sparse PCA calculation, the greedy approach and the block approach. While the greedy approach tends to be incrementally invalidated in sequentially generating sparse PCs due to the cumulation of computational errors, the block approach is difficult to elaborately rectify individual sparse PCs under certain practical sparsity or nonnegative constraints. In this paper, a simple while effective block coordinate descent (BCD) method is proposed for solving the sparse PCA problem. The main idea is to separate the original sparse PCA problem into a series of simple sub-problems, each having a closed-form solution. By cyclically solving these sub-problems in an analytical way, the BCD algorithm can be easily constructed. Despite its simplicity, the proposed method performs surprisingly well in extensive experiments implemented on a series of synthetic and real data. In specific, as compared to the greedy approach, the proposed method can iteratively ameliorate the deviation errors of all computed sparse PCs and avoid the problem of accumulating errors; as compared to the block approach, the proposed method can easily handle the constraints imposed on each individual sparse PC, such as certain sparsity and/or nonnegativity constraints. Besides, the proposed method converges to a stationary point of the problem, and its computational complexity is approximately linear in both data size and dimensionality, which makes it well suited to handle large-scale problems of sparse PCA.