Sparse PCA via Bipartite Matchings
We consider the following multi-component sparse PCA problem: given a set of data points, we seek to extract a small number of sparse components with disjoint supports that jointly capture the maximum possible variance. Such components can be computed one by one, repeatedly solving the single-component problem and deflating the input data matrix, but this greedy procedure is suboptimal. We present a novel algorithm for sparse PCA that jointly optimizes multiple disjoint components. The extracted features capture variance that lies within a multiplicative factor arbitrarily close to 1 from the optimal. Our algorithm is combinatorial and computes the desired components by solving multiple instances of the bipartite maximum weight matching problem. Its complexity grows as a low order polynomial in the ambient dimension of the input data, but exponentially in its rank. However, it can be effectively applied on a low-dimensional sketch of the input data. We evaluate our algorithm on real datasets and empirically demonstrate that in many cases it outperforms existing, deflation-based approaches.
I have read the paper "Sparse PCA via Bipartite matching".The paper studies the problem of sparse PCA in the setting of multi-components with disjoint supports. The paper is generally well-written.The main idea is well presented and is generally easy to digest. However, the major problem of the paperis the focus on the case of"disjoint components".In detail,  in equation (2) and the line below, the paper requires all supports of X^{(i)} are disjoint with each other; all the methods theory are built upon such a constraint. This raises serious doubt on how the algorithm can be used (or to be advantageous over existing ones),especiallyfrom a practical perspective.Take gene microarray datafor example (the paper presents some examples on the microarray data),it is believed that the support of different components are monotone: the support of genes differentially expressed between a normal patient and a patient with a malignant tumor is usually a subset of that between a normal patient and a patient with a malicious tumor. In other words, if we have two principal components $\mu_1$ and $\mu_2$, then it is more likely that \[\mathrm{supp}(\mu_1) \subset \mathrm{supp}(\mu_2), \]instead of\[ \mathrm{supp}(\mu_1) \cap \mathrm{supp}(\mu_2)= \emptyset.\] Even from a theoretical viewpoint,assuming the supports are disjoint is rather strong. While I appreciate the paper has made a fair contribution in terms of algorithm (which isnot that significant though, given the existing literature on sparse PCA), I think the paper lacks a good motivation, which largely down-weights the importance of the paper. To patch up such a weakness, I would suggest the authors make a serious discussion on the following problems, especially in methods and theory. \begin{itemize}\item How broad is the model in equation (2) and the line below.\item In case of overlapping supports, how would wedeal with it? If theres isaconvenient extension of the presentedapproach, would the promised advantages continue to exist?  \end{itemize}   Overall, while I like some of ideas inthe paper, I think there are serious drawbacks. Based on these, I would like to recommend rejection with resubmission.