Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: They address sparse quadratic optimization over the Stiefel manifold with application to permutation synchronization.
main_review: Existing solvers, e.g. based on eigenvalue decomposition, are unable to account for sparsity while at the same time maintaining global optimality guarantees. They fill this gap and propose a simple yet effective sparsity-promoting modification of the Orthogonal Iteration algorithm for finding the dominant eigenspace of a matrix. 
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper the authors propose a modification of a well-known algorithm, in order to maximize a quadratic function over the Stiefel manifold, promoting sparsity at the same time. The base method is not a gradient-retraction over a manifold algorithm (although some tools are used in the middle), but a QR type of method, specifically the Orthogonal Iteration algorithm. The modification is the addition of a right multiplicative matrix, which is selected in order to promote sparsity. This is done for a maximization problem, and the $l_p$ norm (with $p>2$) is used to that end. The method is tested for the permutation synchronization problem.


main_review: The method is a clever modification of a very well-known algorithm. The novelty is the product with a matrix $Z(U_t)$, which doesn't affect the convergence of the original method, and at the same time it allows to incorporate a second objective function, which is chosen as the $l_p^p$ norm of the vectorized matrix.
The existing literature is correctly described, and the difference with respect to existing approaches is discussed.


The presented theoretical results seem to be correct. The proofs of the first part are simple, using basically linear algebra tools, but this is sufficient to prove the convergence and the bahaviour of the method in general.

The paper is correctly written, and it provides sufficient elements to reproduce the results. I wouldn't say is an "easy to follow" paper. I had to go back and forth several times in order to understand some parts. At one point I kept reading even though I was not completely understanding the goal of some points, with the hope to understand it later, which I think I did. I think this is in part due to the method itself, and not fault of the authors.

I think that the contributions are significant, in the sense that the problem is relevant, this method seems to perform well for some difficult tasks, and the modifications are simple but clever. I'm not sure if those ideas could be used for other methods, not based on the QR methodology. Maybe they can.

Some comments and minor comments:
In the experimental section, I would have liked to see an experiment showing the effect of the sparsity promoting addition. Maybe comparing the sparsity of resulting matrix from the original Orthogonal Iteration algorithm (which will be dense most likely), with sparsity resulting from your method.

In lines 112-113, the sentence might be read as if $l_p$ norms with $p<1$ are smooth (I know the observation is about the convexity).

Post rebuttal: The authors addressed my concerns

limitations_and_societal_impact: The limitations are correctly stated in Section 5, but specially the one regarding the equal eigenvalues is easy to overlook in the rest of the text.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a novel algorithm to solve the permutation synchronization problem which can be formulated as minimizing a quadratic function over the Stiefel manifold. The algorithm is modified from the Orthogonal Iteration method with sparsity promotion. The proposed algorithm is shown to perform better than existing methods in terms of both efficiency and accuracy. Moreover, the limitation  of the work  is also discussed. 
main_review: 1. The proposed algorithm has strong intuitions. And the presentation of this work is easy to follow.   To promote the sparsity, the objective function $g(UQ)$ is introduced. The authors point out that $g(UQ)$ is a relaxation of the sparsity and non-negativity.    Since $g(UQ)$ is nonconvex, the step (7) may converge to the local minimum points of (5). The related discussions are given in Appendix. It's better to mention this in the main paper. 

2. There is also a post-processiong step after algorithm 1  as stated in Section 4.2. It would be better to put them together in the Algorithm environment. 

3. The reviewer is curious about the numerical results of the case $p=4$ and minimizing the following function $\sum_{ij} |(UQ)_{ij}|$. For the latter nonsmooth function, you may try  the Riemannian subgradient method [Li. et al 2021] with QR retraction.

Minor:
1. The proofs of Lemma 1 and 2 are trivial. I suggest putting them in the Appendix. 
2. Line 138: 'solution to (1)'

Reference:
[Li. et al 2021] Xiao Li, Shixiang Chen, Zengde Deng, Qing Qu, Zhihui Zhu, Anthony Man-Cho So. Weakly Convex Optimization over Stiefel Manifold Using Riemannian Subgradient-Type Methods. SIAM Journal on Optimization (2021) 31(3):1605-1634.

-----------------------------------------------------------------------
Post rebuttal:
The authors sucessfully address my concerns.
limitations_and_societal_impact: Limitations:
The limitations have been discussed by the authors.

Societal Impact:
Not apply.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The paper is concerned with pursuing sparse optimal solutions to optimization problems of the form max Trace(U^T W U) [*] where U is an orthonormal matrix, that is U lies in the Stiefel manifold. This problem is meaningful since it typically arises as a relaxation over the Stiefel manifold of combinatorial problems such as spectral clustering and permutation synchronization. It this latter problem that occupies the application aspect of the paper. A global (not necessarily sparse) solution to [*] can be obtained in closed form from the eigendecomposition of W. Algorithmically, this can be computed by the power iteration algorithm. The paper proposes a variation of the power iteration algorithm (Algorithm 1), which includes a sparsity promoting step, forcing the basis matrix U to be close to a power of U. Permutation synchronization experiments with synthetic data and on the CMU "house" sequence for finding correspondences in two views,  show that this approach gives better permutation synchronization than several other existing alternatives. 
main_review: The idea of forcing sparsity on U towards recovering a solution of the original problem (the one whose relaxation is [*]) is interesting and important. Moreover, the idea of modifying the power iteration method with the sparsity promoting step of (4) is interesting as well. 

On the other hand, a weakness in the paper is that the authors do not treat the attribute "sparse" precisely.  In page 4, line 136, when they introduce their algorithm, they say that they are interested in an optimal solution of [*] which is sparse "in some relaxed sense". Only in the discussion section at page 7 they write "In turn, we rather interpret sparsity in some looser sense, meaning that there are few elements that are large, whereas most elements are close to zero." I feel that this should have been clarified very early on. 

Another weakness is that the authors do not provide any experimental analysis of Algorithm 1 alone.  
I run the code of the authors on a very simple case, where W=diag(1,1,1,0.5,0.5,0.5), with d=3 and various values of p ranging from 2 to 20. Ideally, the algorithm should be converging to the matrix E=[e1, e2, e3] where e1,e2,e3 are the first three standard basis vectors of R^6. The algorithm converges very quickly (in two iterations or so) to a matrix that is far from E (in fact most elements in the matrix seem to have the same order of magnitude), but if one only selects the largest in magnitude element per column and sets the rest to zero, then one does get E M, where M is a diagonal matrix (this is more clear for larger values of p). More precisely, if one runs the linear assignment post-processing step that the authors propose, then we get back E for p=10, but a wrong result for p=2,3. This shows that both 1) the linear assignment step  and 2) the value of p, are crucial. I also did another experiment at the other extreme, where I chose W to be a generic 6x6 positive semi-definite matrix. With d=5 one expects 4+3+2+1 zeros (this is the highest sparsity of an orthonormal basis of a generic 5-dimensional subspace of R^6). With p=10, while again most elements have the same order of magnitude, there is indeed a clear cluster of 10 smaller elements. 

In conclusion, Algorithm 1 is an interesting heuristic, but more investigation is needed.
Since it is so simple, perhaps it is possible to actually provide a precise mathematical analysis. For this, the authors should define their approximate notion of sparsity rigorously and prove that if the d-th principal eigenspace of W admits an orthonormal basis of sparsity level \alpha, then for p large enough, Algorithm 1 converges to an orthonormal basis with approximate sparsity \alpha. 
I believe this would make a strong paper. 

Three more suggestions:
1) I think it would be more interesting to apply permutation synchronization to a less explored and modern application, such as record linkage, instead of feature matching in computer vision, where there is a vast literature. 
2) Lemmas 1 and 2 are textbook level, there is no need to include the proofs (in fact the given proof of Lemma 2 is not complete). 
3) The notation U* \in im(bar(U)) is not precise. 

**** Post-Rebuttal ****

I thank the authors for their responses. I would like to keep my rating as is, in anticipation of a stronger version of this work. 
limitations_and_societal_impact: No issues as far as I can see.
review_title: null

Meta-review: The proposed method for sparse quadratic optimization over the Stiefel manifold and its analysis are interesting. However, the technical presentation and theoretical results have to be strengthened.
Decision: Accept (Poster)