Sparse PCA from Sparse Linear Regression
Sparse Principal Component Analysis (SPCA) and Sparse Linear Regression (SLR) have a wide range of applications and have attracted a tremendous amount of attention in the last two decades as canonical examples of statistical problems in high dimension. A variety of algorithms have been proposed for both SPCA and SLR, but an explicit connection between the two had not been made. We show how to efficiently transform a black-box solver for SLR into an algorithm for SPCA: assuming the SLR solver satisfies prediction error guarantees achieved by existing efficient algorithms such as those based on the Lasso, the SPCA algorithm derived from it achieves near state of the art guarantees for testing and for support recovery for the single spiked covariance model as obtained by the current best polynomialtime algorithms. Our reduction not only highlights the inherent similarity between the two problems, but also, from a practical standpoint, allows one to obtain a collection of algorithms for SPCA directly from known algorithms for SLR. We provide experimental results on simulated data comparing our proposed framework to other algorithms for SPCA.
The paper proposes an approach to reduce solving a special sparse PCA to a sparse linear regression (SLR) problem (treated as a black-box solution). It uses the spiked covariance model [17] and assumes that the number of nonzero components of the direction (u) is known, plus some technical conditions such as a restricted eigenvalue property. The authors propose algorithms for both hypothesis testing and support recovery, as well as provide theoretical performance guarantees for them. Finally, the paper argues that the approach is robust to rescaling and presents some numerical experiments comparing two variants of the method (based on SLR methods FoBa and LASSO) with two alternatives (diagonal thresholding and covariance thresholding).  Strengths:  - The addressed problem (sparse PCA) is interesting and important. - The paper is well-written, the general idea is relatively simple and easy to understand (the implementation of Algorithms 1 and 2 also looks straightforward). - As the underlying sparse linear regression (SLR) approach is treated as a black-box (as long as it satisfies Condition 2.4), the approach has several variants depending on the SLR used. - Both hypothesis testing and support recovery are addressed and the paper provides theoretical performance guarantees for them. - The authors also present experimental comparisons to demonstrate the advantages of the method over some previous solutions.  Weaknesses: - It is obvious that there is a strong connection between PCA and linear regression (see for example [41]), thus the originality of the general idea is limited. - The spiked covariance model for PCA is quite restrictive (for example, Gaussian white noise) and unlikely to be met in practical applications. In fact Gaussianity is crucial for this approach, which makes the results less significant. - The assumption that the number of nonzero components of u are known is strong (though the authors argue that there are adaptive methods to adjust this). - It is not clear how easy it is to check / verify for a particular problem and SLR method that Condition 2.4 holds. It looks like a strong assumptions which is hard to verify. Ideally, the authors should have demonstrated verifying this condition on an example.  - The fact that the underlying SLR method is treated as a black-box might hide the problem of selecting the appropriate SLR method. Which one should be used for various problems?  Minor comments: - The authors argue that though random design matrices for linear regression can arise, it makes no difference to assume that it is deterministic (by conditioning). This argument is a bit misleading, as it is only true if the design matrix (\mathbb{X}) and the noise vector (w) affecting the observations are independent. This is not the case, for example, if the linear regression problem arises from a time-series problem, such as estimating the parameters of an autoregressive model (in which case the design matrix cannot be assumed to be deterministic). - It is not a good practice to cite works that are only available on arXiv (as they did not go through any review process, they could contain unsupported claims, etc.).  Post-rebuttal comments: Thank you for your replies. It is a nice feature that the presented approach can turn a black-box SLR to a SPCA solver. Nevertheless, it requires strong assumptions, for example, the spiked covariance model, knowledge of sparsity, and RE, which limit its theoretical and practical relevance. I understand that these assumptions could be relaxed a bit, for example, the method could be extended to sub-Gaussian variables and unknown sparsity could be handled by binary search (for hypothesis testing). It would be good to discuss these issues in more detail in the revised paper.