A greedy anytime algorithm for sparse PCA

Understand

The taxing computational effort that is involved in solving some high-dimensional statistical problems, in particular problems involving non-convex optimization, has popularized the development and analysis of algorithms that run efficiently (polynomial-time) but with no general guarantee on statistical consistency.

• In light of the ever-increasing compute power and decreasing costs, a more useful characterization of algorithms is by their ability to calibrate the invested computational effort with various characteristics of the input at hand and with the available computational resources.
• For example, design an algorithm that always guarantees statistical consistency of its output by increasing the running time as the SNR weakens.
• We propose a new greedy algorithm for the $\ell_0$-sparse PCA problem which supports the calibration principle.