Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: ## Summary
The authors study the semi-definite relaxation of the sparse principal component analysis (PCA) under missingness and establish the sufficient conditions for support recovery of the first principal component. 

## Novelty
Support recovery of the semi-definite relaxation of the sparse PCA with complete observations was established by Lei and Vu (2015), this work extends the analysis to incomplete observations.  

## Overview of Comments

I really appreciate the clarity and the level of detail, but describing all these in the main paper devoids it of context and seems like a listing of constants and their mathematical form. Due to this, the paper is somewhat unreadable and does not (because of space) address the key difference in analysis and specific challenges it had to overcome (and how) over the previous works. This description is key for the readers to gauge the merits. For instance, the details of how the analysis differs from Lei and Vu (2015) under the missingness is unclear. 
strengths_and_weaknesses: ## Strengths

* Precise about the analysis

## Weaknesses

* While the paper is precise about the analysis, it focuses on listing these results and quantities in the main paper, distracting the readers from the key points of the paper. This makes the paper difficult to read. This also makes it difficult to parse the main result and its implications.
* The paper does not highlight the key differences in analysis and challenges in establishing the results for this case over the prior art.
* Applicability of the model for real-world applications in unclear (see detailed comments/questions).
questions: ## Comments

1. Applicability of the model in case of missing observations. The paper considers decomposition of a symmetric matrix with noisy and potentially missing observations. Arguably in real-world for a data matrix $Y$, this symmetric matrix was derived by performing $M = Y'Y$. But decomposition of $M$ may be ill-posed when columns of data matrix $Y$ have a few observed entries [See Park & Zhao 2019]. It seems that the theoretical results must impose some additional conditions on $Y$ to avoid such a situation. 
   - 1(a) The paper discusses these indirectly in section 3, but implications for original data $Y$ is not discussed. Although it seems these must depend on the incoherence and the sampling probability, these issues must be directly addressed.
   - 1(b) The bound on p would be more interpretable if directly expressed, than an upper bound on $\sqrt(1-p/p)$
   - 1(c) the various notions of incoherence employed must be introduced in the model description since these are inherent assumptions about the matrix $M$. 


2. In Lei and Vu (2015) the exact support recovery relies on Sparse Principal Subspace (SPS) condition, which includes 1) spectral gap and 2) $supp(diag(\Pi)) = J$, where $J = Union_{j=1}^{k} supp(u_j)$, where $u_j$ are the eigenvectors. In essence, $J$ is not the support of the principal eigenvector as the proposed work but a union of all eigenvectors. 

   - 2 (a) Since the proposed model does not impose sparsity of other principal components and they can be dense, it is unclear if support recovery is even possible if other eigenvectors are dense. What are the additional conditions required even for the complete observation setting. 

   - 2(b) This also seems like a special case of sparse PCA when only the learning principal vector is sparse. 

3. Writing -- majority of the write-up is dedicated to definitions of constants and results. I appreciate this level of details, but these are best left to the appendix. In the current form these are extremely distracting tending to unreadable. 

   - 3(a) Since the papers relies on Landau notation, these need to further simplified. This is also important for the experiments where the paper claims a that the results are "tight" but these relationships are not plotted for reference.

   - 3(b) What are the differences in analysis over Lei and Vu (2015)? What do the incoherence conditions imply in practice?   

limitations: N/A
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposes a SDP relaxation of the non-convex L1-regularized sparse PCA problem under small noise and incomplete data. The resulting convex program can exactly recover the true support of the sparse leading eigenvector with high probability, under certain conditions. Experiments verify the efficacy of the proposed method.
strengths_and_weaknesses: Strengths: the work provides theoretical guarantee in terms of exactly recovering the true support of the sparse leading eigenvector.

Weakness: 

1. There is no comparison with any baseline methods. If I understand correctly, the method simply uses 0 for the missing entries to get matrix M. Then, the existing sparse PCA methods without the consideration of missing entries can also be applied on this matrix M, for comparison.

2.  The proposed method can only guarantee recovering the support of the sparse leading eigenvector, not the value. 

questions: 1. Given a n*d  data matrix D with missing entries (say uniformly at random), can you please provide details on how to get the d*d matrix M? 

2. Since M^* is assumed to be symmetric, why not using M_ij to impute M_ji ? I think this should also be compared in the experiments.
limitations: Yes
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper considers the sparse principal component analysis problem for incomplete and noisy data. In particular, it considers its semidefinite programming reformulated problem and develops a new algorithm with theoretical discussions on the uniqueness of the optimal solution with large probability. Numerical justification including the experiments on synthetic and realistic gene data sets have demonstrated the effectiveness. The work looks interesting with insightful theories. 
strengths_and_weaknesses: Strengths: In the main result, several conditions have been proposed to guarantee the success of the SDP algorithm. There are some theoretical contributions. The application of gene expression is interesting and useful. 

Weaknesses: The proposed algorithm is based on the SDP reformulation of the original sparse PCA problem, and the algorithmic development may be limited. In Section 4.1, there are no other related methods being compared. 
questions: 1. In Section 2.2, do the eigenvectors $\mathbf{u}_i$'s need to be normalized?
2. In the SDP reformulation in p.2, does it guarantee that the solution is rank-one and even $X=\mathbf{x}\mathbf{x}^T$?
3. In Theorem 1, what is $p$? How is it defined? Also, the existence of the optimal solution is not discussed. 
limitations: The sparse principal component problem assumes that the optimal solution has sparse leading eigenvector which may not be the case in real applications and thus limit its applicability.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies sparse PCA with incomplete and noisy data, and proposes a SDP relaxation algorithm. This relaxation formulation was previously applied to sparse PCA with complete data, and this paper shows that the same exact formulation can be applied to incomplete observations. Sufficient conditions for exact support recovery are proposed, and experiments on both synthetic and real-world data.
strengths_and_weaknesses: - Overall, this is a well-written paper. It discusses the problem of sparse PCA with incomplete data, and presents a solid and novel theoretical approach to it via SDP relaxation. 
- The experiment on gene expression data is another highlight, though it feels somewhat insufficiently illustrated.
- I don't see any major weaknesses of this paper.
questions: - This is likely out of scope for this paper, but I am curious about how the proposed SDP method compares with other possible approaches to solving sparse PCA with incomplete data, such as various imputation methods. Such an experiment that evaluates the performance of the proposed method will further enhance the results of this paper.
- It may be helpful to expand on the gene expression data experiment, by showing some relevant visualizations of the data and/or results, for example in the Appendix.
limitations: Yes.
review_title: null

Meta-review: metareview: The paper studies the sparse PCA problem — finding sparse direction of large variance. It studies the natural convex relaxation, in which we lift the outer product xx^T to a matrix X, drop the rank constraint, and apply L1 regularization. In contrast to much existing work, here, the covariance matrix is partially observed. The proposal is to apply the convex relaxation, with the covariance matrix M^* replaced by a censored and noisy version M. The paper assumes that M^* has a sparse lead eigenvector, and ask when this approach correctly recovers the support of that vector. 

Reviewers found the paper to be technically solid, with novel results on sparse PCA with missing data. The main concerns center around the presentation: the style is dense with definitions and conditions, perhaps to the detriment of the reader’s insight. Arguably, with a better chosen set of sufficient conditions would lead to a more readable collection of results, leaving more space to convey what the results mean and how they were achieved. 

confidence: Less certain
Decision: Accept