- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper analyzes a randomized algorithm for maximizing a rank- Hermitian positive semidefinite quadratic form over -th roots of unity: sample directions uniformly in the factor space, round coordinatewise, and retain the best solution. It proves that samples suffice for a -approximation with probability at least , independently of the number of variables. It also establishes an additive objective-loss bound for noisy, approximately low-rank matrices without an eigengap assumption. Validation includes comparisons against enumerated rank-two optima, planted low-rank-plus-noise instances, and synthetic and real-world Max-3-Cut benchmarks at scales exceeding one million vertices. In the rank-two benchmarks, 100 samples achieve 99.8% of the surrogate optimum on average.
Critical strengths
The main strength is the geometric analysis showing that rounding loses only quadratically with angular error. This yields an explicit near-optimality guarantee for every low-rank factor and alphabet size, with a sample count independent of the number of variables. It provides a rigorous basis for replacing exhaustive enumeration with simple randomized approximation at fixed rank, which is the main reason I support acceptance.
Critical weaknesses
My main reservation is the limited conceptual advance over existing low-rank optimization methods. The direction-search framework is established, and the quadratic angular-loss principle already appears in the related zonotope analysis of Cao et al. (2026). The added value is concentrated in an explicit sampling guarantee for general roots-of-unity alphabets. This is useful, but the relatively narrow advance limits the strength of my support for acceptance.
Questions for authors
At the approximation level of Theorem 5, Lemmas 3.1 and 3.2 appear to give a constant success probability without the general position or incoherence assumptions, by considering a squared overlap above its mean and a phase error in the lower half of its range. Could the authors clarify what additional guarantee Appendix D provides? I would also appreciate clarification of the enumeration argument in Appendix A. For rank two and alphabet size four, a generic vertex with no repeated coordinate group has eight adjacent cells, whereas Lemma A.7 gives one. How is this discrepancy resolved, and how are the reference optima certified for degenerate factors handled by finite perturbation?
3 comments
Q2b. How the reference optima are certified.
The rank-2 optima of Section 5.1 do not use Algorithm 3. Instead, they come from the procedure of Appendix E.2 (now D.2), which visits every cell directly. (The exact rank-2 cuts of Section 5.2 come from a separate enumeration of sector partitions in Appendix E.1 (now D.1), which also does not use Algorithm 3.) We detail this procedure and its error below.
Consider , as in all our experiments, and an objective whose factor satisfies items 1 to 3 of Assumption 1. Then every cell of the rank-2 arrangement is a pointed cone whose vertex is where three hyperplanes meet. If the three hyperplanes come from distinct coordinates, the 8 cells around the vertex correspond to their 8 sign patterns, and the procedure steps into each of them. If two of the hyperplanes come from the same coordinate, then all three hyperplanes of that coordinate pass through the vertex, and 12 cells meet there. In this case, the procedure reaches each cell through the triple formed by two neighboring hyperplanes of that coordinate and the hyperplane of the other coordinate.
However, a real factor , such as that of a graph Laplacian, never satisfies items 2 and 3, since its rows in the real embedding with the same boundary index span only a plane. Some factors also have zero or parallel rows. We therefore run the procedure twice: once on , and once on , where for a complex Gaussian . This perturbed factor satisfies these conditions almost surely. We score the best labeling for with and report the larger of the two values, so the reference is always attained by a feasible labeling.
The error of this reference is explicit. For every , Therefore, the reference is at least , and it equals whenever is smaller than the gap between the two largest distinct values of . We also check the reference directly:
- on 204 inputs with , including zero, parallel and duplicate rows and tori with repeated eigenvalues, both runs equal the brute-force optimum over all labelings;
- on the 27 instances of Section 5.1 (one with a zero row, seven with parallel rows), is below , the two runs agree, and the best of the sampled draws equals the reference on every instance.
In the submission, Appendix E.2 (now D.2) already reported the first check and the agreement of the two runs. In the revision, we will add the argument above, the bound and its value on the 27 instances, and the comparison with the sampled draws.
On novelty relative to Cao et al. (2026).
We agree that our work shares the direction search and the quadratic loss near the optimum with the concurrent work of Cao, Qi and Wang (arXiv, August 2026), and acknowledge this in Sections 1, 3 and 6. Their deterministic algorithm for norm maximization over zonotopes applies to every even , since each row then contributes a centrally symmetric -gon, which is a sum of segments. With , its exponent matches our exponent . For odd , including Max-3-Cut, the convex hull of is in general not a zonotope.
Our guarantee holds for every , including the odd that the theorem of Cao et al. does not cover, such as Max-3-Cut. However, our main contribution is not the exponent, but the exact law of the comparison for a random direction (a Beta overlap and an independent uniform phase). This law gives a simple sampling algorithm with small explicit constants for every , the expectation bound , and the new constant-probability result. We also give a guarantee for noisy objectives (Proposition 4.1): running our algorithm on a rank- truncation of loses at most in the noiseless objective, with no eigengap condition. In the revision, we will correct Section 3 to say that the method of Cao et al. covers every even .
Thank you for the detailed responses and additional experiments. The new constant-probability result resolves my concern regarding Appendix D. I also appreciate the clarification of the enumeration argument, the acknowledgment of the issue in Lemma A.7, and the proposed corrections to the assumptions and certification procedure in Appendix A. The additional experiments further strengthen the empirical evaluation. These responses address my main concerns.
Thank you for your detailed review, close reading of our paper, and encouraging evaluation of our work. Your first question led us to a new constant-probability result, and your second allowed us to clarify the enumeration argument and identify two missing general-position assumptions. We address these questions and comment on the advances of our work compared to Cao et al. (2026).
Q1. What does Appendix D add?
Thank you for this insightful question. You are right that Theorem 5 in the former Appendix D is superseded by a simple corollary of Lemmas 3.1 and 3.2 that doesn't require any additional assumptions. We detail this new result as follows. Lemmas 3.1 and 3.2 give f(c)≥OPTrXcos2ψ with X∼Beta(1,r−1) and ψ∼Unif[0,π/K] independent. Here Pr[X≥1/r]=(1−1/r)r−1≥1/e and Pr[ψ≤π/(2K)]=1/2. On both events, f(c)≥cos2(2Kπ)rOPTr. Hence Pr[f(c)≥cos2(2Kπ)rOPTr]≥21(1−r1)r−1≥2e1 for every n, r, K and V, and S≥2eln(1/δ) draws reach this level with probability at least 1−δ. Because κK≤cos2(π/2K) (for example, κ3≈0.707 and cos2(π/6)=0.75), this bound also holds at the level κKOPTr/r of Theorem 5, without the factor (1−ε). In comparison, Theorem 5 needed μ-incoherence and general position and gave a success probability of order ε2/(μ4r6). We will state this new result as Corollary 3.3, remove the former Appendix D in future revisions, and acknowledge the reviewer.
Q2a. Lemma A.7.
Thank you for catching this error. You are right that Lemma A.7 is wrong as written. At a generic vertex with r=2, 8 cells meet, not one. In general, 22r−1 cells meet where 2r−1 hyperplanes from distinct coordinates meet. The factor (BK−1)p in the lemma instead counts the cells that the enumeration charges to a vertex. We detail this argument as follows.
As in Karystinos & Liavas (2010) and Kyrillidis & Karystinos (2014), each vertex produces the cells whose lowest point in the last auxiliary angle ϕ2r−1 is that vertex. When no two of the hyperplanes at the vertex come from the same coordinate, this is exactly one cell. When p coordinates contribute two hyperplanes each, the vertex produces (BK−1)p cells. To see this, note that the BK hyperplanes of such a coordinate share an axis. In the plane normal to this axis, they form 2BK wedges in opposite pairs, and BK−1 of these wedges lie entirely in the half-plane where ϕ2r−1 increases. For odd K, two neighboring wedges can give the same labeling, so there are fewer distinct candidates, as Appendix A notes.
Some cells have no such vertex inside the parameter box. These cells touch the boundary of the box, and we cover them in one of two ways. On the face ϕ2r−1=−π/K, the labeling of the cell is a rotation of a labeling found elsewhere. On a face ϕj=±π/2 with j≤2r−2, the last coordinate of c is zero, so the rank-(r−1) recursion covers the cell.
This count requires two general-position conditions that Assumption 1 did not include. Specifically, no further hyperplane can pass through a vertex, and ϕ2r−1 cannot be constant to first order along any edge through a vertex. We add these conditions as items 3 and 4 of Assumption 1. Further, because the rank-(r−1) recursion works on the leading blocks V:,1:d, Theorems 3 and 4 and Proposition 2.1 now require Assumption 1 to hold for every such block. We will rename the lemma and restate it in these terms.