Do algorithms and barriers for sparse principal component analysis extend to other structured settings?
This work addresses structured PCA for scenarios like graph sparsity, extending insights from vanilla sparse PCA, but it is incremental as it generalizes existing phenomena to new settings.
The paper tackles the problem of structured sparse principal component analysis (PCA) under the spiked Wishart model, showing that fundamental limits depend on problem geometry and that a projected power method achieves near-optimal statistical performance with local convergence.
We study a principal component analysis problem under the spiked Wishart model in which the structure in the signal is captured by a class of union-of-subspace models. This general class includes vanilla sparse PCA as well as its variants with graph sparsity. With the goal of studying these problems under a unified statistical and computational lens, we establish fundamental limits that depend on the geometry of the problem instance, and show that a natural projected power method exhibits local convergence to the statistically near-optimal neighborhood of the solution. We complement these results with end-to-end analyses of two important special cases given by path and tree sparsity in a general basis, showing initialization methods and matching evidence of computational hardness. Overall, our results indicate that several of the phenomena observed for vanilla sparse PCA extend in a natural fashion to its structured counterparts.