Fantope Projection and Selection: A near-optimal convex relaxation of sparse PCA
We propose a novel convex relaxation of sparse principal subspace estimation based on the convex hull of rank-d projection matrices (the Fantope). The convex problem can be solved efficiently using alternating direction method of multipliers (ADMM). We establish a near-optimal convergence rate, in terms of the sparsity, ambient dimension, and sample size, for estimation of the principal subspace of a general covariance matrix without assuming the spiked covariance model. In the special case of d = 1, our result implies the near-optimality of DSPCA (d'Aspremont et al. [1]) even when the solution is not rank 1. We also provide a general theoretical framework for analyzing the statistical properties of the method for arbitrary input matrices that extends the applicability and provable guarantees to a wide array of settings. We demonstrate this with an application to Kendall's tau correlation matrices and transelliptical component analysis.
The authors consider the Sparse PCA problem, i.e., PCA 
      with the assumption that the "principal vectors" depend on only a few of 
      the variables. They propose a convex relaxation for solving this problem 
      and analyze its performance. An ADMM based method is also developed for 
      solving the resulting SDP efficiently. Finally they show theoretical 
      results when a Kendall's tau matrix is used as input instead of the usual 
      sample covariance matrix. The paper is clearly written and the 
      authors have done a good job in explaining various concepts as they become 
      used in their exposition. The results presented in this paper appear to be 
      correct. I like the convex formulation. The techniques used to 
      achieve it are simple and this might certainly be considered one of the 
      strengths of the paper. It also goes along nicely with the ADMM 
      formulation and Lemma 4.1. I have a minor suggestion : it would be nice if 
      the authors mention the fact that they have a closed form expression for 
      the projection onto the fantope a little earlier in the paper (possibly 
      along with the motivation of a convex relaxation). However, the 
      statistical analysis seems a little weak, particularly in the near low 
      rank and low rank cases. If there were only d non zero eigenvalues, the 
      bound the authors present could potentially be very far away from the 
      minimax bound. On a related note, the authors should consider rephrasing 
      the statement "It is possible (with more technical work) to tighten the 
      bound..." in the last paragraph of page 5; it does not appear to 
      contribute constructively without a discussion about what this technical 
      work could be. Even if the Appendix contains all the proofs, it 
      would be helpful if the authors present the reader with a small proof 
      sketch after each result has been stated (also note that reviewers are not 
      required to read the supplementary material). The section on 
      Simulation Results again seems a little weak. The figures need reworking 
      as Figure 1(a) is just too hard to see on a printed version of the paper. 
      On a related note, it will be nice to explain (in the text and/or in the 
      caption) what "overlapping" and "non-overlapping" sparsity patterns mean 
      precisely. It will also be helpful to insert an intuitive explanation as 
      to why the performance is so different in these cases and when it matters. 
      Minor point : The authors should consider rephrasing ".. has a 
      wide range of applications - Science, engineering, ... ". It would be much 
      more helpful to point the reader to a few specific applications with 
      references.