acceptodds
Under review as a conference paper at ICLR 2027

Exploiting Low-Rank Objective Structure in Discrete Quadratic Optimization

Abstract

We study the maximization of a positive semidefinite Hermitian quadratic form over vectors whose entries are -th roots of unity, for any , a problem that contains Max-Cut (), Max-3-Cut (), and -ary phase detection. When the objective matrix has rank , the problem reduces to a search over directions on the unit sphere of : rounding each coordinate of , where is the matrix factor of the given Hermitian matrix, to the nearest root turns a direction into a candidate, and some direction yields an optimum. Exact search enumerates candidates. In this paper, we analyze the simplest alternative, which rounds uniformly random directions and keeps the best. One random direction is -optimal with probability at least , for every , so samples and time give a -optimal solution with probability . For noisy objectives , rounding a rank- truncation loses at most , with no eigengap condition. In Max-3-Cut experiments, the number of samples needed for a near-best cut does not grow with on random regular graphs with up to vertices and on tori with up to , per our settings; on graphs small enough to solve exactly, 100 samples reach of the rank-2 optimum on average; and on planted three-community graphs, whose objective is low rank plus noise, the bound for noisy objectives becomes informative as grows.

Primary area:
optimization
Keywords:
discrete optimization, low rank models, quadratic maximization forms over describe alphabets

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 2 reviews, above 85% of the others.
Reviewer_vDMYOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper analyzes a randomized algorithm for maximizing a rank-rr Hermitian positive semidefinite quadratic form over KK-th roots of unity: sample directions uniformly in the factor space, round coordinatewise, and retain the best solution. It proves that O((2/ϵ)r−1/2log⁡(1/δ))O((2/\epsilon)^{r-1/2}\log(1/\delta)) samples suffice for a (1−ϵ)(1-\epsilon)-approximation with probability at least 1−δ1-\delta, 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

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)≥OPTrXcos⁡2ψf(\mathbf c)\ge\mathrm{OPT}_r X\cos^2\psi with X∼Beta(1,r−1)X\sim\mathrm{Beta}(1,r-1) and ψ∼Unif[0,π/K]\psi\sim\mathrm{Unif}[0,\pi/K] independent. Here Pr⁡[X≥1/r]=(1−1/r)r−1≥1/e\Pr[X\ge1/r]=(1-1/r)^{r-1}\ge1/e and Pr⁡[ψ≤π/(2K)]=1/2\Pr[\psi\le\pi/(2K)]=1/2. On both events, f(c)≥cos⁡2(π2K)OPTrr.f(\mathbf c) \ge \cos^2\big(\tfrac{\pi}{2K}\big)\frac{\mathrm{OPT}_r}{r}. Hence Pr⁡[f(c)≥cos⁡2(π2K)OPTrr]≥12(1−1r)r−1≥12e\Pr\Big[f(\mathbf c)\ge\cos^2\big(\tfrac{\pi}{2K}\big)\frac{\mathrm{OPT}_r}{r}\Big] \ge \tfrac12\big(1-\tfrac1r\big)^{r-1} \ge \frac{1}{2e} for every nn, rr, KK and V\mathbf V, and S≥2eln⁡(1/δ)S\ge2e\ln(1/\delta) draws reach this level with probability at least 1−δ1-\delta. Because κK≤cos⁡2(π/2K)\kappa_K\le\cos^2(\pi/2K) (for example, κ3≈0.707\kappa_3\approx0.707 and cos⁡2(π/6)=0.75\cos^2(\pi/6)=0.75), this bound also holds at the level κKOPTr/r\kappa_K\mathrm{OPT}_r/r of Theorem 5, without the factor (1−ε)(1-\varepsilon). In comparison, Theorem 5 needed μ\mu-incoherence and general position and gave a success probability of order ε2/(μ4r6)\varepsilon^2/(\mu^4r^6). 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=2r=2, 8 cells meet, not one. In general, 22r−12^{2r-1} cells meet where 2r−12r-1 hyperplanes from distinct coordinates meet. The factor (BK−1)p(B_K-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\phi_{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 pp coordinates contribute two hyperplanes each, the vertex produces (BK−1)p(B_K-1)^p cells. To see this, note that the BKB_K hyperplanes of such a coordinate share an axis. In the plane normal to this axis, they form 2BK2B_K wedges in opposite pairs, and BK−1B_K-1 of these wedges lie entirely in the half-plane where ϕ2r−1\phi_{2r-1} increases. For odd KK, 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\phi_{2r-1}=-\pi/K, the labeling of the cell is a rotation of a labeling found elsewhere. On a face ϕj=±π/2\phi_j=\pm\pi/2 with j≤2r−2j\le2r-2, the last coordinate of c\mathbf c is zero, so the rank-(r−1)(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\phi_{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)(r-1) recursion works on the leading blocks V:,1:d\mathbf 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.

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 K=3K=3, as in all our experiments, and an objective whose factor V\mathbf V 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 V\mathbf V, 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 V\mathbf V, and once on V′=V+Δ\mathbf V'=\mathbf V+\boldsymbol\Delta, where Δ=10−8max⁡ij∣Vij∣ G\boldsymbol\Delta=10^{-8}\max_{ij}|V_{ij}|\,\mathbf G for a complex Gaussian G\mathbf G. This perturbed factor satisfies these conditions almost surely. We score the best labeling for V′\mathbf V' with V\mathbf V 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 z∈AKn\mathbf z\in\mathcal A_K^n, ∣fV′(z)−fV(z)∣≤n∥Δ∥2(2∥V∥2+∥Δ∥2)=:η.|f_{\mathbf V'}(\mathbf z)-f_{\mathbf V}(\mathbf z)| \le n\|\boldsymbol\Delta\|_2\big(2\|\mathbf V\|_2+\|\boldsymbol\Delta\|_2\big)=:\eta. Therefore, the reference is at least OPTr−2η\mathrm{OPT}_r-2\eta, and it equals OPTr\mathrm{OPT}_r whenever 2η2\eta is smaller than the gap between the two largest distinct values of fVf_{\mathbf V}. We also check the reference directly:

  • on 204 inputs with n≤10n\le10, including zero, parallel and duplicate rows and tori with repeated eigenvalues, both runs equal the brute-force optimum over all 3n3^n labelings;
  • on the 27 instances of Section 5.1 (one with a zero row, seven with parallel rows), 2η2\eta is below 3×10−6 OPTr3\times10^{-6}\,\mathrm{OPT}_r, the two runs agree, and the best of the 2×1052\times10^5 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 η\eta 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 KK, since each row then contributes a centrally symmetric KK-gon, which is a sum of K/2K/2 segments. With d=2rd=2r, its exponent (d−1)/2(d-1)/2 matches our exponent r−1/2r-1/2. For odd KK, including Max-3-Cut, the convex hull of {V†z}\{\mathbf V^\dagger\mathbf z\} is in general not a zonotope.

Our guarantee holds for every KK, including the odd KK 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 KK, the expectation bound κKOPTr/r\kappa_K\mathrm{OPT}_r/r, and the new constant-probability result. We also give a guarantee for noisy objectives Q=Q⋆+H\mathbf Q=\mathbf Q^\star+\mathbf H (Proposition 4.1): running our algorithm on a rank-rr truncation of Q\mathbf Q loses at most 2n(λr+1⋆+2∥H∥2)2n(\lambda^\star_{r+1}+2\|\mathbf H\|_2) 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 KK.

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.

Reviewer_ZK8pOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the maximization of a Hermitian PSD quadratic form over KK-th roots of unity (e.g., MAX-CUT for K=2K=2, MAX-3-CUT for K=3K=3). For a rank-rr objective matrix QQ, the problem reduces to searching over directions on the unit sphere in Cr\mathbb{C}^r. The authors analyze a simple uniform sampling and rounding algorithm, proving that S=O((2/ϵ)r−1/2log⁡(1/δ))S = O((2/\epsilon)^{r-1/2} \log(1/\delta)) random draws guarantee a (1−ϵ)(1-\epsilon)-optimal solution with probability 1−δ1-\delta, independent of the vector dimension nn. They also establish a perturbation bound for noisy, approximately low-rank objectives without requiring an eigengap condition. The theoretical results are evaluated on MAX-3-CUT, synthetic planted graphs, and the GSet benchmark.

Critical strengths
  1. The paper refines the classical sampling complexity bound from O(ϵ−2r)O(\epsilon^{-2r}) down to O(ϵ−(r−1/2))O(\epsilon^{-(r-1/2)}) by exploiting the KK-fold rotational symmetry and the quadratic loss in the angle distance to optimal rotations. The proof using Beta and uniform distributions on sphere marginals is clean and elegant.
  2. Proposition 4.1 establishes a straightforward guarantee for Q=Q∗+HQ = Q^* + H by comparing objective values rather than eigenvectors, avoiding traditional matrix perturbation bounds that scale inversely with spectral gaps.
  3. Empirical Validation: Experiments on synthetic graphs (nn up to 10610^6) validate the nn-free sample complexity prediction and demonstrate the high accuracy of random sampling on genuinely low-rank instances.
Critical weaknesses
  1. While the theory applies to low-rank matrices, standard MAX-CUT or MAX-3-CUT benchmarks (such as general graph Laplacians or expanders) have flat spectra where the top few eigenvalues carry a negligible fraction of the trace. As candidly noted by the authors, Proposition 4.1 becomes vacuous for these instances. The class of real-world NP-hard problems where QQ is genuinely low-rank appears somewhat restricted (e.g., specific signal processing tasks or strong planted community graphs).
  2. Exponential Scaling in Rank rr: The sampling complexity exponent r−1/2r - 1/2 implies that the method is strictly limited to very small ranks (e.g., r≤3r \le 3). As rr grows moderately (e.g., r≥5r \ge 5), the sample budget SS explodes exponentially, rendering the uniform sampling approach impractical for higher-rank approximations.
  3. On general benchmark graphs (e.g., GSet), low-rank rounding alone lags behind state-of-the-art heuristics (such as MOH or Greedy). Although combining low-rank sweeps with Local Search (LS) improves performance, it is somewhat unclear how much of the final cut quality stems from the low-rank initialization versus the local refinement itself.
Questions for authors
  1. In Table 1, Rank-1 + LS performs well[8]. Could the authors provide a baseline comparing purely random initialization + LS vs. Rank-1 + LS to quantify the exact gain provided by the low-rank guide?
  2. How does the empirical performance degrade when rr is increased to r=4r=4 or r=5r=5 under fixed time/draw budgets?
  3. Beyond MIMO beamforming and planted graphs, are there other practical engineering or machine learning tasks where the objective QQ is naturally low-rank and NP-hard?
2 comments

Thank you for your detailed and encouraging review of our paper. We answer your questions and address your stated weaknesses below.

Q1. Random start + LS versus Rank-1 + LS.

This comparison is in Table 1 and in the full GSet tables (Tables 5 to 7), under the column title "LS". Specifically, "LS" is the same 1-opt local search started from a single set of uniform random labels. We will rename it "Random+LS". Both methods take under one second on every GSet graph. Over all 71 GSet graphs, Rank-1+LS gives the larger cut on 65, ties on 1, and is lower on 5, by at most 1.05%. The median gain is 1.2% and the largest is 10.6% (G21). Averaged over the 71 graphs, Rank-1+LS reaches 0.908 of the MOH value and Random+LS 0.889. On the large graphs (45 runs on 35 graphs, up to 1.4×1061.4\times10^6 vertices), the low-rank start improves local search on every run, by 0.4% to 3.9% (now Appendix D.5).

Q2. Larger rank at a fixed budget.

We ran additional experiments with a fixed sampling budget for higher constant ranks on all 71 GSet graphs. Specifically, we considered r=2,…,5r=2,\ldots,5 at budgets of 10410^4 and 10510^5 draws. For each graph, we take the median cut value that the rank-rr algorithms (both with and without the local search refinement) find across the five eigensolver starts from Table 1. In the first three rows of the following table, we report the mean ratio of this median to the MOH solution over the 71 graphs. The r=1r=1 column is the exact rank-1 sweep rather than sampling, which we include for comparison, so we do not compare it graph by graph with r=2r=2.

r=1r=1 (sweep)r=2r=2r=3r=3r=4r=4r=5r=5
cut / MOH, sampling alone, 10410^4 draws0.6810.6980.7040.7220.719
cut / MOH, sampling alone, 10510^5 draws0.7000.7100.7270.724
cut / MOH, 10410^4 draws then local search0.9080.9070.9090.9110.910
graphs where the 10410^4-draw cut beats / ties / trails r−1r-1-55 / 2 / 1447 / 3 / 2144 / 4 / 23

We find that the sampled rank-rr cuts usually improve upon the sampled rank-(r−1)(r-1) cuts, but that this effect is less apparent as rr increases. For example, rank 5 beats rank 4 on 44 of the 71 graphs, although its mean ratio to MOH is slightly lower (0.719 versus 0.722). After local search, all ranks give nearly the same cut (0.907 to 0.911 of MOH), so higher ranks add little once local search is applied. This is consistent with our analysis: as rr increases, the best cut that exact enumeration can find cannot decrease, since the rank-(r−1)(r-1) candidates are a subset of the rank-rr candidates. However, the number of draws required to approach this best value also increases with rr, as Theorem 1 shows for the rank-rr objective ff. We will add a summary table, with the time per draw, to Appendix D.7.

Q3. Other applications with exactly low-rank objectives.

In addition to MIMO beamforming and planted graphs, other applications with naturally low-rank objectives include L1-norm PCA, noncoherent sequence detection, and discrete-phase reflecting surfaces. We detail these cases below.

In each case, the problem fixes the rank while nn is large, so exact enumeration, which takes nO(r)n^{O(r)} time, is the bottleneck, and the number of draws we need does not depend on nn.

  • L1-norm PCA. The L1 principal component of a data matrix X∈RD×N\mathbf X\in\mathbb R^{D\times N} solves max⁡b∈{±1}N∥Xb∥22\max_{\mathbf b\in\{\pm1\}^N}\|\mathbf X\mathbf b\|_2^2. This matches our problem setup with K=2K=2 and Q=X⊤X\mathbf Q=\mathbf X^\top\mathbf X of rank at most DD.
  • Noncoherent detection. Joint channel estimation and detection of KK-PSK sequences maximizes z†YY†z\mathbf z^\dagger\mathbf Y\mathbf Y^\dagger\mathbf z. The rank of this problem grows with the number of receive antennas (Motedayen-Aval et al., 2007; Papailiopoulos & Karystinos, 2010).
  • Discrete-phase reflecting surfaces and phased arrays. With bb-bit phase shifters (K=2bK=2^b), the received power is a quadratic form over KK-th roots of unity. Again, the rank of this quadratic form is the number of receive antennas, and the dimension nn is the number of elements and can be hundreds to thousands (Ren et al., 2023).

Weakness 2: exponential dependence on rr.

Some superpolynomial growth in rr is unavoidable when we target a (1−ε)(1-\varepsilon)-approximation, unless NP ⊆\subseteq BPP. If we could achieve this approximation in time polynomial in both nn and rr, then we could approximate Max-Cut up to (1−ε)(1-\varepsilon) in polynomial time. This reduction is as follows:

For K=2K=2 and rr equal to the rank of a graph Laplacian, which can be as large as n−1n-1, OPTr\mathrm{OPT}_r is four times the Max-Cut value. So an algorithm, deterministic or randomized, that reaches (1−ε)OPTr(1-\varepsilon)\mathrm{OPT}_r for a fixed ε<1/17\varepsilon<1/17 in time polynomial in both nn and rr would approximate Max-Cut beyond its NP-hardness threshold of 16/1716/17 (Håstad, 2001). Unless NP ⊆ BPP, no such algorithm exists. We note that this argument rules out a polynomial dependence on rr, but not every subexponential one.

Weakness 3: GSet.

See our response to Q1.

Additional References.

Johan Håstad. Some optimal inapproximability results. Journal of the ACM, 48(4):798–859, 2001. doi: 10.1145/502090.502098.

Comments on the paper

3 comments

Thank you for the review and for the accurate summary of Theorem 1 and Proposition 4.1. The weaknesses field repeats the strengths, so we read it as though you have no outstanding concerns. We are glad to answer any questions you may have during the discussion.

You note that the near-optimality guarantee "is useful for very small r". In the revision, we add a companion result whose success probability does not depend on rr. We show that at a weaker target cos⁡2(π/2K) OPTr/r\cos^2(\pi/2K)\,\mathrm{OPT}_r/r, which does depend on rr, one draw succeeds with probability at least 1/(2e)1/(2e) for every nn, rr, KK and V\mathbf V. We note that for K=2K=2 and a fixed ε<1/17\varepsilon<1/17, no algorithm can reach (1−ε)OPTr(1-\varepsilon)\mathrm{OPT}_r in time polynomial in both nn and rr unless NP ⊆\subseteq BPP (see our reply to Reviewer ZK8p). The other changes are listed in the general response.

AuthorsOpenReview ↗

Summary of Revisions

We thank the reviewers for their careful reading and for recommending acceptance. We will revise the PDF with the following changes. We provide more details in the individual responses.

  1. A constant-probability bound with no assumptions (thanks to Reviewer vDMY). We replace Theorem 5 with a corollary to Lemmas 3.1 and 3.2 stating that one random direction reaches cos⁡2(π/2K)OPTr/r\cos^2(\pi/2K) \mathrm{OPT}_r/r with probability at least 1/(2e)≈0.181/(2e)\approx0.18, for every nn, rr, and KK. This implies that 2eln⁡(1/δ)2e\ln(1/\delta) samples can achieve this level with probability at least 1−δ1-\delta. This result (Corollary 3.3) replaces Theorem 5 and the former Appendix D, which gave a weaker bound and required incoherence and general position assumptions.
  2. Appendix A (Reviewer vDMY). Lemma A.7 is restated: it counts the cells the enumeration charges to a vertex, not the cells that meet there. Assumption 1 gains the two general-position conditions this count needs, and the enumeration results now assume it for every leading block of V\mathbf V. Appendix D.2 now explains how the rank-2 optima are certified and bounds their error. Neither change affects a reported number.
  3. What the low-rank start adds to local search (Reviewer ZK8p). The column "LS" of Table 1 and Tables 5 to 7 gives a baseline of random initialization and local search. Across all 71 GSet graphs, the rank-1 initialization finds a better cut than the random initialization on 65 of these graphs, the two methods tie on G6, and the random initialization finds a better cut on five graphs (G8, G12, G46, G65, G66). We agree that this is an important baseline and, for clarity, we rename these columns to "Random+LS".
  4. Larger rank (Reviewer ZK8p). We include the results of a sweep over r=2,…,5r=2,\ldots,5 on all 71 GSet graphs at budgets of 10410^4 and 10510^5 draws. We compare the cuts and time per draw of these results with the exact rank-1 sweep, with and without local search (now Appendix D.7). We find that higher ranks slightly improve the sampled cuts, but give nearly the same cuts after local search.
  5. Applications (Reviewer ZK8p). We further motivate our setting by adding L1-norm PCA to the list of objectives that are low rank by construction in the introduction.
  6. Why the (1−ε)(1-\varepsilon) target needs growth in rr (Reviewers ZK8p and Q3qY). We add a description of why the dependence on rr cannot be polynomial if we target a (1−ε)(1-\varepsilon)-approximation. Specifically, for K=2K=2 and a fixed ε<1/17\varepsilon<1/17, no algorithm reaches (1−ε)OPTr(1-\varepsilon)\mathrm{OPT}_r in time polynomial in both nn and rr unless NP ⊆ BPP, by reduction from Max-Cut (Håstad, 2001). This rules out a polynomial dependence on rr, but not every subexponential one. We add this statement to Section 3.

The review thanks for the detailed explanation and decide to keep the score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.