A recursive divide-and-conquer approach for sparse principal component
  analysis
  In this paper, a new method is proposed for sparse PCA based on the recursive
divide-and-conquer methodology. The main idea is to separate the original
sparse PCA problem into a series of much simpler sub-problems, each having a
closed-form solution. By recursively solving these sub-problems in an
analytical way, an efficient algorithm is constructed to solve the sparse PCA
problem. The algorithm only involves simple computations and is thus easy to
implement. The proposed method can also be very easily extended to other sparse
PCA problems with certain constraints, such as the nonnegative sparse PCA
problem. Furthermore, we have shown that the proposed algorithm converges to a
stationary point of the problem, and its computational complexity is
approximately linear in both data size and dimensionality. The effectiveness of
the proposed method is substantiated by extensive experiments implemented on a
series of synthetic and real data in both reconstruction-error-minimization and
data-variance-maximization viewpoints.
