Truncated Power Method for Sparse Eigenvalue Problems

The sparsity is controlled by the values of k and can be viewed as a design parameter. In machine learning applications, e.g., principal component analysis, this problem is motivated from the following perturbation formulation of matrix A: A Ā E, (1.2) where A is the empirical covariance matrix, Ā is the true covariance matrix, and E is a random perturbation due to having only a finite number of empirical samples. If we assume that the largest eigenvector x of Ā is sparse, then a natural question is to recover x from the noisy observation A when the error E is "small". In this context, the problem (1.1) is also referred to as sparse principal component analysis (sparse PCA). 1 In general, problem (1.1) is non-convex. In fact, it is also NPhard because it can be reduced to the subset selection problem for ordinary least squares regression (Moghaddam et al., 2006), which is known to be NP hard.