PaperlayerView exact revision on arXiv

Source-linked AI summary

Scalable Semidefinite Programming

Alp Yurtsever, Joel A. Tropp, Olivier Fercoq, Madeleine Udell, Volkan Cevher

arXiv:1912.02949v2math.OCmath.CO

TL;DR

Large SDPs can be difficult to solve while limiting storage and arithmetic, particularly when their matrix variables are huge. SketchyCGAL combines primal–dual optimization with randomized matrix sketching; its MaxCut guarantee uses O(n/ζ) working storage, and reported comparisons show it scaling beyond conventional solvers.

  • Problem

    Large SDP matrix variables make storage a challenge, while the paper seeks algorithms that exploit low-rank structure with limited storage and arithmetic.

    Source: §1 · p. 1

  • Method

    SketchyCGAL combines a primal–dual optimization method with randomized matrix sketching and approximate eigenvector computations.

    Source: §1 · p. 1, §6.5 · p. 15

  • Results

    SketchyCGAL handles MaxCut instances with n ≈ 2.2 · 10^7, while conventional convex solvers do not scale beyond n = 10^4.

    Source: §7.2.3 · p. 17

  • Takeaways & Limitations

    The method is reported effective across MaxCut, phase retrieval, and quadratic assignment applications, including SDP instances with very large matrix variables.

    Source: §1 · p. 1, §7.4.1 · p. 20, §7.5 · p. 20

    The method is limited by the arithmetic cost of increasingly accurate large eigenvalue problems and falters on SDPs with many constraints.

    Source: §9 · p. 25

Abstract

from arXiv · show

Semidefinite programming (SDP) is a powerful framework from convex optimization that has striking potential for data science applications. This paper develops a provably correct randomized algorithm for solving large, weakly constrained SDP problems by economizing on the storage and arithmetic costs. Numerical evidence shows that the method is effective for a range of applications, including relaxations of MaxCut, abstract phase retrieval, and quadratic assignment. Running on a laptop equivalent, the algorithm can handle SDP instances where the matrix variable has over $10^{14}$ entries.

1. Motivation.

SketchyCGAL targets large SDPs whose solutions are low-rank or well approximated by low-rank matrices, using randomized sketches to reduce storage and arithmetic. The paper gives convergence guarantees and reports scaling beyond conventional solvers on a MaxCut benchmark.

1.3.3. Algorithms?

  • SketchyCGAL combines primal–dual optimization with randomized matrix sketching, using a low-precision randomized eigenvector calculation as the primary expense per iteration.It stores a compressed representation rather than the full matrix variable.Source: §1 · p. 1, §1.4 · p. 5

1.1.1. MaxCut.

  • A MaxCut SDP can require O(n^2) matrix storage even though its input and desired rank-one output together require O(m+n) representation.A graph with one million vertices yields a trillion real matrix variables.Source: §1.1.2 · p. 2

1.1.3. A storage-optimal algorithm for the MaxCut SDP.

  • Figure 1.1 compares storage cost and runtime of SketchyCGAL with sketch size R = 10 against four standard SDP solvers, using relative error tolerance 10^-1 for each solver; each marker represents one dataset.Source: Figure 1.1 · p. 3

1.1.2. What’s the issue?

  • For any ε, ζ > 0, SketchyCGAL returns a (1+ζ)-optimal rank-one approximation of an ε-optimal MaxCut SDP point using O(n/ζ) working storage and ˜O(ε^-2.5) Laplacian matrix-vector multiplies, with high probability.The guarantee applies to every Laplacian L.Source: §1.1.2 · p. 3

1.2.1. The trace-constrained SDP.

  • The model problem covers applications in statistics, signal processing, quantum information, combinatorics, computer vision, microscopy, robotics, and neural-network robustness certification.MaxCut is a special case of the model problem.Source: §1.2.2 · p. 4

1.3.2. Low-rank solutions of SDPs.

  • Many SDPs have low-rank solutions because they are weakly constrained, and SketchyCGAL is designed for such problems without requiring weak constraints.Weakly constrained means the number of linear equalities is much smaller than the number of matrix-variable components.Source: §1.3.2 · p. 4

1.3.3. Algorithms?

  • Fixing a rank constraint makes the model problem NP-hard, so the paper instead seeks a rank-r matrix approximating an ε-optimal solution.The approximation target is easier to compute and store than the ε-optimal point itself.Source: §1.3.3 · p. 5

1.4. Contributions.

  • SketchyCGAL returns a near-optimal low-rank approximation under strong duality, with storage O(d + rn/ζ) and ˜O(ε^-2.5) matrix-vector products per problem-data matrix.The algorithm succeeds with high probability.Source: §1.4 · p. 5

2. Scalable semidefinite programming.

The section formulates SDPs through their linear constraints and identifies a low-rank approximation target that can reduce the cost of representing solutions. It also treats problem data as black boxes and illustrates the desired storage scale for MaxCut.

2.1. Abstract form of the model problem.

  • The model SDP minimizes ⟨C, X⟩ subject to A X = b and X ∈ α∆n, with instances specified by (C, A, b, α).The constraint map A collects the linear equalities.Source: §2.1 · p. 6

2.2. Approximate solutions.

  • An ε-optimal point has constraint residual at most ε and objective suboptimality at most ε; the section uses its low-rank approximation as the computational target.The rank-r approximation is bounded relative to the best rank-r approximation in nuclear norm.Source: §2.2 · p. 6

2.3. Black-box presentation of problem data.

  • The algorithm accesses C and A through three primitive operations and assumes those operations can be implemented with minimal storage and arithmetic.Without efficient primitives, an efficient overall algorithm may be impossible.Source: §2.3 · pp. 6–7

2.4. Example: The MaxCut SDP.

  • For MaxCut, the target rank-one solution has O(n) degrees of freedom, motivating Θ(n) working storage rather than storing the full matrix.The graph Laplacian remains input data, and the algorithm accesses it through the primitives.Source: §2.4 · p. 7

3. An algorithm for the model problem.

The section augments the SDP objective with a penalty for constraint violations, producing a smooth dual problem with the same optimal set. It then describes alternating primal minimization and dual updates as the basis of the CGAL strategy.

3.1. The augmented problem.

  • The augmented problem preserves the original problem’s optimal value and optimal set while penalizing infeasible points and yielding a smooth dual.The penalty term is added to the objective while retaining the affine constraint.Source: §3.1 · p. 7

3.2. The augmented Lagrangian.

  • The augmented Lagrangian supports alternating primal minimization and a gradient step that updates the dual variable.The primal variable is minimized over X and the dual variable is updated by gradient ascent.Source: §3.2 · p. 7, §3.3 · p. 8

3.3. The augmented Lagrangian strategy.

  • CGAL initializes a primal–dual pair and iteratively applies a primal step followed by a dual step to produce an approximate solution.The presented algorithm uses the problem primitives and a specified iteration count.Source: §3.3 · p. 8, §3.2 · p. 8

3. Dual step: yt+1 = yt + β(A X −b).

CGAL replaces costly primal minimization with linearized updates and uses approximate eigenvector computations. Under strong duality, its iterates have a convergence guarantee, though the CGAL error bound based on the surrogate gap is not proven to vanish.

3. Dual step: yt+1 = yt + β(A X −b).

  • CGAL avoids the costly augmented-Lagrangian primal step by choosing a direction from a linear proxy and taking a small primal step.The dual variable is advanced by a small gradient step, while the smoothing parameter follows a fixed schedule.Source: §3.4 · p. 8, §3 · p. 8

3.4.1. Initialization.

  • The iteration increases its smoothing parameter according to a fixed schedule, starting from an initial parameter β0.Initialization also uses a bound K on the dual-variable size.Source: §3.4 · p. 8, §3.4.1 · p. 8, §3.4.2 · p. 8

3.4.2. Primal updates via linear minimization.

  • Each primal update uses a minimum-eigenvector direction and a small step, and the eigenvector need not be computed accurately.The update is a convex combination of the current iterate and a feasible point.Source: §3.4.2 · p. 9

3.4.3. Dual updates via gradient ascent.

  • The dual update takes a gradient step proportional to the constraint residual and is skipped if it would make the dual variable exceed K.Its step size must satisfy the specified residual- and operator-norm-based conditions.Source: §3.4.3 · p. 9

3.4.4. Assessing solution quality.

  • The surrogate duality gap offers a practical early-convergence check, but the authors have not proved that its CGAL error bound converges to zero.The gap is analogous to the Frank–Wolfe duality gap.Source: §3.4.4 · p. 9

3.5. Convergence guarantees for CGAL.

  • Under strong duality, CGAL with approximate eigenvector computations produces an ε-optimal primal iterate after O(ε^-2) iterations.Numerical work cited in the paper reports O(ε^-1) iterations on realistic instances.Source: §3.5 · p. 10

4. Approximate eigenvectors.

SketchyCGAL needs approximate minimum eigenvectors, but clustered eigenvalues challenge standard eigenvector software. The paper uses randomized Lanczos with regenerated vectors to reduce storage.

4.1. Krylov methods.

  • Clustered eigenvalues in CGAL matrices Dt challenge standard eigenvector software such as ARPACK, motivating an alternative to ordinary Krylov methods.Krylov methods apply because they use repeated matrix–vector products, but the clustered spectrum poses difficulty.Source: §4.1 · p. 10
  • Randomized Lanczos uses a random start and regenerates rather than stores Lanczos vectors, enabling approximate eigenvector computation with minimal storage.The method has convergence error bounds; retaining vectors can roughly halve flop count but raises storage to O(qn).Source: §4.1 · p. 10, §4.2 · p. 11

4.2. A storage-optimal randomized Lanczos method.

  • The randomized Lanczos method computes a unit approximate minimum eigenvector; its arithmetic uses at most q matrix–vector multiplies plus O(qn) operations, with O(n+q) working storage.The stated iteration threshold and error guarantee are not fully present in the supplied passage.Source: §4.2 · p. 10
  • SketchyCGAL’s evolving psd matrix is tracked through a compressed Nyström sketch, which is later used to report a provably accurate low-rank approximation.The algorithm’s primary per-iteration expense is a randomized eigenvector calculation.Source: §5 · p. 11

5. Sketching and reconstruction of a psd matrix.

The paper sketches a psd matrix through its products with a fixed random test matrix, updates that sketch alongside rank-one matrix changes, and reconstructs a low-rank Nyström approximation with error guarantees.

5.1. Sketching and updates.

  • A fixed standard-normal test matrix Ω forms the sketch S = XΩ, which supports construction of a rank-R approximation of X.The sketch size R controls storage cost and approximation quality.Source: §5.1 · p. 11, §5.2 · p. 12
  • The Nyström sketch supports linear rank-one updates, so it can track an evolving psd matrix without storing the full matrix.For X ← (1−η)X + ηvv*, the sketch update costs Θ(Rn) operations and the test matrix plus sketch use 2Rn numbers.Source: §5.1 · p. 11

5.2. The reconstruction process.

  • The Nyström reconstruction takes Θ(R^2n) operations and Θ(Rn) storage, and the resulting approximation is described as a provably good estimate of X.The reconstruction can be truncated to its best rank-r approximation.Source: §5.2 · p. 12, §5.3 · p. 12

5.3. A priori error bounds.

  • For standard-normal Ω and r < R−1, the Nyström approximation has an a priori error bound that also holds after rank-r truncation; similar results hold with high probability.The supplied passages do not include the bound’s formula.Source: §5.3 · p. 12

5. Sketching and reconstruction of a psd matrix.

  • SketchyCGAL extends CGAL by controlling storage while using the sketch to recover a low-rank approximation of the implicitly updated matrix.The method tracks the evolving psd matrix rather than retaining the full iterate.Source: §5.3 · p. 12

6. Scalable semidefinite programming via SketchyCGAL.

SketchyCGAL replaces explicit matrix iterates with a primal state and Nyström sketch while tracking CGAL’s trajectory. Under strong duality, it returns an ε-optimal low-rank approximation with stated storage and iteration guarantees.

6. Scalable semidefinite programming via SketchyCGAL.

  • SketchyCGAL tracks CGAL using the primal state zt and dual variable yt while storing a Nyström sketch instead of the full matrix iterate.The sketch has storage Θ(Rn); the strong storage guarantee applies when d≪n^2 and R≪n.Source: §6 · pp. 12–13

6.1. The SketchyCGAL iteration.

  • Each iteration computes an approximate minimum eigenvector and uses it to update the primal state and sketch; the dual step is bounded by stated step-size conditions.The method initializes the state, sketch, and dual variable at zero.Source: §6.1.2 · p. 13, §6.1.3 · p. 13, §6.1.1 · p. 13

6.2. Connection with CGAL.

  • SketchyCGAL’s implicit matrix iterates follow a trajectory that could also be generated by CGAL, so they inherit CGAL’s behavior.The sketch allows a rank-R approximation of an implicit iterate to be formed.Source: §6.2 · p. 13, §6.2.1 · p. 14

6.2.1. Approximating the CGAL iterates.

  • The rank-R reconstruction approximates an implicit iterate insofar as that iterate is well-approximated by low-rank matrices; optional trace correction can at most double Nyström error.The analysis does not include the optional trace-projection step, though the authors describe it as valuable in practice.Source: §6.2.1 · p. 14

6.2.2. Assessing solution quality.

  • The implicit iterates converge at CGAL’s rate, while the discrepancy between rank-R approximations and implicit iterates depends on their low-rank approximability.The paper describes tracking infeasibility and a surrogate duality gap to assess solution quality.Source: §6.2.2 · p. 14, §6.3 · p. 15

6.5. Theoretical performance of SketchyCGAL.

  • With strong duality and sketch size R ≥ ζ^-1r + 1, SketchyCGAL returns a rank-r approximation to an ε-optimal solution after O(ε^-2) iterations with constant probability.The stated total storage is O(d + Rn) floats.Source: §6.5 · p. 15
  • In practice, SketchyCGAL uses T = O(ε^-1) iterations on real-world instances, better than the O(ε^-2) theoretical iteration guarantee suggests.The theoretical analysis assumes strong duality.Source: §6.5 · pp. 15–16
  • Experiments report faster-than-theorem convergence, competitiveness on small SDPs, and scaling to problems standard methods cannot handle.The stated storage cost is O(d + Rn), with eigenvector computation as the arithmetic bottleneck.Source: §6.4 · p. 15, §7 · p. 16

7. Numerical examples.

The numerical examples evaluate SketchyCGAL on MaxCut, abstract phase retrieval, Fourier ptychography, and quadratic assignment relaxations, comparing resource use and solution quality across these applications.

7.2.3. Storage and arithmetic comparisons.

  • Conventional convex solvers do not scale beyond n = 10^4, while SketchyCGAL handles MaxCut instances with n ≈ 2.2 · 10^7; it misses tolerance on 9 datasets within 5 days.The comparison stops SketchyCGAL when relative suboptimality and infeasibility are below 10^-1.Source: §7.2.3 · p. 17

7.2.4. Empirical convergence rates.

  • On the G67 MaxCut instance, residual and infeasibility decay as O(t^-1), faster than the theorem’s O(t^-1/2) bound; sketch size R = 10 suffices for excellent cuts after a few hundred iterations.The cut values are compared with a high-accuracy SDPT3 solution.Source: Figure 7.1 · p. 17, §7.2.4 · p. 18

7.2.5. Primal–dual convergence.

  • On constructed hard MaxCut instances, SketchyCGAL solves with R = 2 and Θ(n) storage, while Burer–Monteiro usually fails in the optimal-storage regime.Burer–Monteiro requires R = Θ(√n), giving Θ(n^1.5) storage on these instances.Source: §7.2.6 · p. 18

7.3.3. Dataset and evaluation.

  • SketchyCGAL solves every tested synthetic phase-retrieval instance to relative error below 10^-2; CGAL fails at n = 10^5 and 10^6, and ThinCGAL at n = 10^6.The experiment uses sketch size R = 5 and 20 independent datasets per dimension.Source: §7.3.4 · p. 19, §7.3.3 · p. 19

7.4.3. FP imaging.

  • For Fourier ptychography, SketchyCGAL produces a good-quality image after 1,000 iterations in 5 hours and a sharper image after 10,000 iterations in 59 hours.The simulated target has 102,400 pixels and is observed through 921,600 intensity-only measurements.Source: §7.4.3 · p. 20, §7.4.2 · p. 20

7.5.2. Relaxations.

  • For QAP, choosing G to extract only nonzero entries of B ⊗ 11* reduces constraints to O(n^3) when B has O(n) nonzeros; SketchyCGAL solves the relaxation directly up to n = 150.The Zhao et al. relaxation uses the identity map for G and has O(n^4) constraints.Source: §7.5.2 · p. 22

7.5.3. Rounding.

  • QAP rounding reshapes factor columns into matrices and projects them to feasible permutations with the Hungarian method, selecting the permutation with the lowest objective value.The evaluation uses instances with known optima and permutation sizes n = 12 to 150.Source: §7.5.3 · p. 22, §7.5.4 · p. 22

7.5.5. Solving QAPs.

  • SketchyCGAL solves a tighter QAP relaxation than CSDP and PATH, yielding significantly smaller gaps for most instances.The reported comparison uses CSDP with clique sizes k ∈ {2, 3, 4} and PATH.Source: §7.5.5 · p. 22

8. Related work.

The related work contrasts scalable first-order methods and storage-saving approaches with conventional SDP solvers, whose memory or arithmetic demands limit large problems. SketchyCGAL builds on CGAL and sketching, while factorization-based alternatives trade convexity and guarantees for lower storage.

8.1. Standard methodologies.

  • Interior-point methods offer quadratic convergence and high precision but require dense-matrix storage and substantial per-iteration arithmetic; augmented-Lagrangian SDP methods typically need Ω(n^2) storage.The cited IPM bounds are Θ(n^3 + d^2n^2 + d^3) arithmetic and Θ(n^2 + dn + d^2) memory per iteration.Source: §8.1 · p. 23

8.2. First-order methods.

  • First-order SDP methods include conditional-gradient variants, primal–dual subgradient methods, and matrix multiplicative weights; most provably correct methods still store full-dimensional matrices.The standard conditional-gradient method does not directly handle affine constraints, so CGAL applies it to an augmented-Lagrangian formulation; SketchyCGAL extends CGAL for its empirical performance and robustness to inexact eigenvectors.Source: §8.2 · pp. 23–24, §8.3 · p. 24
  • Matrix multiplicative weights uses repeated feasibility problems and approximations to the matrix exponential, but its feasibility reduction is described as impractical for general SDPs.The authors report knowing of only one computational evaluation of the approach.Source: §8.2 · p. 24

8.3. Storage considerations.

  • Some first-order methods keep iterates as convex combinations of rank-one updates, but their iteration counts can make the apparent storage efficiency misleading.The related SketchyCGM work combines conditional-gradient methods with sketching for a special class of low-rank matrix problems and claims provably optimal storage for that class.Source: §8.3 · p. 24
  • SketchyCGAL combines sketching with CGAL to target standard-form SDPs; reducing storage also reduces arithmetic and communication costs.The paper contrasts this with SketchyCGM for a special class of low-rank problems and with approximate complementarity, which has more limited guarantees and was still under numerical evaluation.Source: §8.3 · pp. 24–25

8.4. Nonconvex Burer–Monteiro methods.

  • Burer–Monteiro factorization saves storage by replacing the matrix variable with a low-rank factor, but sacrifices convexity and its guarantees.Its costs depend on factorization rank; below a rank threshold, spurious second-order critical points can occur, and bad instances may have positive measure.Source: §8.4 · p. 25
  • Manopt implements manifold optimization for Burer–Monteiro formulations and is limited to cases where the factorized problem defines a smooth manifold.Although every rank-R-or-less SDP solution solves the factorized problem, the latter can also have local minima that are not global SDP minima; a cited guarantee requires generic C, a smooth constraint manifold, and R ≥ 2(d + 1).Source: §8.4 · p. 25

9. Conclusion.

The conclusion identifies arithmetic cost, many constraints, and gaps in the convergence analysis as limitations of SketchyCGAL. The accompanying CGAL analysis specializes to a model SDP, describes its primal–dual updates, and addresses convergence, resource use, and distributed computation.

9. Conclusion.

  • SketchyCGAL remains limited by increasingly accurate large eigenvalue computations and falters on SDPs with many constraints; its analysis does not fully explain several observed convergence behaviors.The unresolved behaviors include primal-variable convergence rates, dual-variable convergence, and the surrogate duality gap.Source: §9 · p. 25

Appendix A. Analysis of the CGAL Algorithm.

  • The CGAL analysis specializes to the paper’s model problem, adapts earlier convergence results, and adds analysis of approximate eigenvectors and detailed model-problem results.Empirical work suggests the analysis remains qualitatively suboptimal.Source: Appendix A · p. 26

A.1. The model problem.

  • The model problem minimizes a linear matrix objective subject to affine equalities and a positive-semidefinite trace constraint.Its objective matrix is C, the constraints use A and b, and the feasible matrices lie in αΔ_n.Source: §A.1 · p. 26

A.2. Elements of Lagrangian duality.

  • CGAL uses an augmented-Lagrangian method with a conditional-gradient-inspired primal step, under an assumed Lagrangian saddle point.Slater’s condition guarantees this saddle-point hypothesis.Source: §A.3 · p. 26, §A.2 · p. 26

A.3. The CGAL iteration.

  • CGAL alternates primal and dual updates while increasing smoothing; the smoothing parameter controls tolerated inexactness, and dual steps obey a bounded-travel condition.The dual update adds a step-size-scaled constraint residual, γ_t(A X_{t+1} − b), to the current dual variable.Source: §A.3 · pp. 26–27

A.4. Distributed computation.

  • When there are many constraints, CGAL can partition constraint matrices and associated dual variables across workers, with a structure similar to ADMM.The analysis develops results on CGAL convergence and arithmetic resource use.Source: §A.4 · p. 27, §A.5 · p. 27

A.5. Theoretical analysis of CGAL.

The theoretical analysis establishes convergence and error guarantees for CGAL and derives approximation-error bounds and statistical guarantees for Nyström methods, including how spectral structure, trace correction, and sketch parameters affect approximation quality.

A.5.1. Convergence.

  • O(eps^-2) iterations suffice for the stated convergence guarantee, and CGAL converges to a primal optimal solution of the model problem.The big-O constants depend on problem data and algorithm parameters.Source: §A.5.1 · p. 28

A.5.2. Problem scaling.

  • Theorem A.1 suggests setting K = 0 and keeping the dual variable fixed, but numerical work reports substantial performance improvements from CGAL’s dual updates.The cited theory does not explain this performance difference.Source: §A.5.3 · p. 29

A.6. Proof of Theorem A.1.

  • The proof combines primal-update, smoothing, and dual-update analyses into a recursion for the augmented Lagrangian, then solves it to bound suboptimality.The recursion is established as the iterates and smoothing parameter evolve; the derived objective bound also uses the bounded-travel condition.Source: §A.6.3 · p. 31, §A.6.4 · p. 32, §A.6.5 · p. 32

A.6.5. Bound for the suboptimality of the objective.

  • The proof controls superoptimality through feasibility and bounds the infeasibility of the iterates, assuming exact linear minimization.The iterates may be infeasible and therefore superoptimal; the proof’s infeasibility analysis explicitly assumes no error in the linear minimization.Source: §A.6.5 · p. 32, §A.6.6 · p. 33, §A.6.7 · p. 33

A.7. Computable bounds for suboptimality.

  • The computable duality gap bounds primal-iterate suboptimality using the feasibility gap and dual variable, with an extension for approximate linear minimization.The additional error term converges to zero, although the paper reports the exact-minimization bound as more informative in practice.Source: §A.7 · p. 34

Appendix B. Sketching and reconstruction of a positive-semidefinite matrix.

  • The Nyström sketch tracks an evolving positive-semidefinite matrix and yields a provably accurate low-rank approximation with an exact Schatten 1-norm error formula.The paper identifies its error-estimation material as new.Source: Appendix B · p. 34, §B.3 · p. 35

B.3. The approximation error.

  • For every r ≤ R, ||X − JXKr||_* ≤ err(Jc XKr), and large drops in this error estimate indicate large eigenvalue drops in X.Source: §B.3 · p. 36

B.4. Trace correction.

  • Trace correction gives fX the same trace as X and ensures ||X − fX||_* ≤ 2||X − cX||_*, so it can at most double the original error.Source: §B.4 · p. 36

B.5. Statistical properties of the Nyström sketch.

  • Expected truncated-Nyström error decreases monotonically with sketch size R and truncation rank r, and is zero with probability one when rank(X) = r ≤ R.The Nyström approximation also yields a provably good estimate of X [102, Thms. 4.1].Source: §B.4 · p. 36, §B.6 · p. 36

B.6. A priori error bounds.

The appendix analyzes error and statistical properties of truncated Nyström approximations, trace correction, and SketchyCGAL’s solution-quality estimates. Its guarantees depend on sketch size, truncation rank, spectral decay, and assumptions such as the input rank being no greater than the sketch size.

B.7. Discussion.

  • When 5r + 1 ≤ R, the expected Schatten 1-norm error is at most 1.25× the error of the best rank-r approximation; spectral decay can make the error smaller.The authors report that spectral decay is typical for matrices generated by CGAL iterations.Source: §B.7 · p. 37

B.8. Representation of the truncated Nyström approximation.

  • The Nyström approximation can be represented as X^1/2 P X^1/2, with P the projector onto the range of X^1/2Ω; rank truncation yields a corresponding projector representation.This representation provides the basis for relating truncated approximations and analyzing their errors.Source: §B.8 · p. 37

B.6. A priori error bounds.

  • For fixed sketch size, truncated Nyström error decreases with rank, and replacing the approximation by its rank-r truncation preserves the stated error bound, including with high probability.The truncated approximation also has a stronger error bound when the input matrix exhibits spectral decay.Source: §B.6 · pp. 36–37, §B.9 · p. 38

B.9. Approximation errors: Analysis.

  • For a fixed sketch size, the nuclear-norm error of the truncated Nyström approximation is monotone decreasing as the approximation rank increases.The error equals the trace deficit between X and its rank-r approximation.Source: §B.9 · pp. 37–38

B.10. Trace correction: Analysis.

  • The trace-corrected approximation minimizes nuclear-norm distance to the Nyström approximation among PSD matrices with matching trace, and its error relative to X is at most twice the original approximation error.Among the variational solutions, the authors select one that also minimizes Frobenius-norm error.Source: §B.10 · p. 38

B.11. Statistical properties: Analysis.

  • If rank(X) = r ≤ R, the rank-r truncated Nyström approximation equals X with probability one; expected approximation error also decreases as sketch size increases.The sketch uses a standard normal test matrix.Source: §B.11 · pp. 38–39

Appendix C. SketchyCGAL: Additional results.

  • The appendix develops estimates for the quality of SketchyCGAL solutions by adapting the approach used for CGAL.The supplied passage states the approach but gives no further estimate details.Source: §C.1 · p. 39

C.1. Assessing solution quality.

  • A computable error estimate is obtained from the solution-quality expression using the loop invariant z_t = A X_t.The procedure tracks the primal objective and can use a high-accuracy eigenvalue solve when estimating error.Source: §C.1 · p. 39

C.2. Convergence theory.

The appendix gives convergence guarantees for SketchyCGAL and outlines how to extend it beyond the model SDP. The convergence results include a conditional guarantee when the implicit iterates converge, while the extensions require suitable structured subproblems and projections.

C.2. Convergence theory.

  • When the implicit iterates converge to X_cgal with rank at most R, the computed iterates converge to the solution set; the same stated bound also holds for their truncated approximations.The theorem assumes convergence of the implicit iterates.Source: §C.2 · p. 40

D.1. A more general template.

  • The broader template minimizes a linear matrix objective subject to a convex inclusion A X ∈ K and a compact convex matrix constraint, with X PSD.SketchyCGAL can be tailored to this template, which includes additional computational challenges.Source: §D.1 · p. 41, Appendix D · p. 41
  • Extensions to symmetric indefinite or rectangular matrices are possible, but require replacing the Nyström sketch with a more general sketching technique.Matrix completion via nuclear-norm minimization is given as an example.Source: §D.1 · p. 41

D.2. The convex constraint set.

  • The convex matrix constraint requires a linear-minimization subroutine with a structured, for example low-rank, approximate solution.Trace-bounded PSD matrices and trace-fixed PSD contractions are described as settings where this can be possible.Source: §D.2 · p. 41, §1 · p. 41, §2 · p. 42

1. Trace-bounded psd matrices.

  • For trace-bounded PSD matrices, an approximate minimum eigenpair gives a solution to the linear-minimization subproblem, while small trace-fixed orthoprojectors can use randomized subspace iteration or block Lanczos.These are examples of structured subproblems for the broader template.Source: §1 · p. 41, §2 · p. 42

2. Relaxed orthoprojectors.

  • For a standard-form SDP without an available trace bound, the authors propose repeatedly doubling a trace bound until consecutive primal objectives match; the procedure terminates in Õ(1) iterations if a bounded solution exists.Extending the termination argument to approximate solutions is described as nontrivial because those solutions are infeasible.Source: §2 · p. 42

D.3. Convex inclusions.

  • The inclusion constraint A X ∈ K requires an efficient Euclidean projection onto K; examples include componentwise upper bounds and norm-bounded deviations from b.The projection is readily computed for several norms, including ℓ1, ℓ2, and ℓ∞.Source: §D.3 · p. 42, §1 · p. 42, §2 · p. 42

D.4. The CGAL iteration for the general template.

  • For the general template, the iteration replaces the original linear-minimization subroutine with the constrained subproblem and revises the dual update using the projection onto K.The paper describes extending SketchyCGAL by applying the same sketching program to the generalized CGAL iteration.Source: §D.4 · pp. 42–43

Appendix E. Details of MaxCut experiments.

The appendix details MaxCut evaluation procedures and reports a comparison between SketchyCGAL and Burer–Monteiro methods. It also discusses how the dual objectives and solution-quality measures are interpreted for the trace-bounded model.

E.1.2. Details for SketchyCGAL.

  • The SketchyCGAL stopping test uses an inexact eigenvalue computation in practice, which the authors report did not significantly differ from a high-accuracy approximation and avoids added cost.The theoretical bound requires a high-accuracy minimum-eigenvalue computation.Source: §E.1.2 · p. 44
  • Terminating under the stated test gives the implicit variable the claimed quality guarantee.The supplied passage identifies this as the sought guarantee but does not include its formula.Source: §E.1.2 · p. 44

E.2. Convergence of SketchyCGAL for the MaxCut SDP.

  • The MaxCut solver comparison measures storage and computation time against a high-accuracy SDPT3 solution, with storage estimated from process virtual memory, including swapped memory.The estimate can exceed 16 GB.Source: §E.2 · p. 45
  • The average relative cut-weight discrepancy across benchmark datasets is less than 1.5%, which the authors characterize as a small price for scalability.Positive relative values mean the rounded cut has higher weight than the cut rounded from X⋆.Source: §E.2 · p. 45

E.3. Primal–dual convergence.

  • The appendix evaluates primal and dual suboptimality and infeasibility with Euclidean-scaled DIMACS errors, and also computes the sixth error for complementary-slackness violation.SketchyCGAL and SeDuMi do not explicitly maintain Z, so the evaluation sets Z = C + A*y.Source: §E.3.1 · p. 46

E.3.1. DIMACS errors.

  • For the DIMACS comparison, the testbed relaxes tr X = n to tr X ≤ 1.05·n and uses target accuracy ε = 10^-3 for each solver.The passage says Table 8 reports the outcomes but supplies no cell values.Source: §E.3.1 · p. 46

E.3.2. The dual of the model problem.

  • The authors observed that SketchyCGAL’s dual objective converges to p⋆ even though its dual sequence y does not converge to a solution of the standard-form dual.The accompanying lemma equates solution sets of the trace-bounded and standard duals under technical conditions.Source: §E.3.2 · p. 47

E.4. Failure of the Burer–Monteiro heuristic.

  • SketchyCGAL solves all tested random MaxCut instances with sketch size R = 2, while the cited analysis indicates Burer–Monteiro reliability for these instances requires Θ(n3/2) storage.The experiment used n = 100, 10 random instances, ranks 2–13, and 100 Manopt initializations per instance; failure meant an objective 10^-3 above optimum.Source: §E.4 · p. 47

F.1. Synthetic phase retrieval data.

The section specifies synthetic phase-retrieval data and a Fourier-ptychography measurement setup, then details QAP experiments and related limitations.

F.1. Synthetic phase retrieval data.

  • For n from 10^2 through 10^6, the synthetic phase-retrieval study generates 20 datasets per size using d = 12n coded-diffraction measurements.The measurements use 12 independent modulating waveforms and Fourier transforms implemented with the fast Fourier transform.Source: §F.1 · p. 48

F.2. Fourier ptychography.

  • Fourier ptychography models an unknown high-resolution image filtered by the lens aperture, yielding low-resolution measurements from multiple illumination angles.The reconstruction target is the complex-valued image vector, which can be transformed back to a high-resolution image with an inverse Fourier transform.Source: §F.2 · p. 48

Appendix G. Details for QAP.

  • The QAP experiment tables report rounded upper bounds, objective values, feasibility gaps, iterations, memory, and runtime, with runs capped at 10^6 iterations or 72 hours.Feasibility gaps are computed on original, unscaled problem data without normalization.Source: Appendix G · p. 48, Table 5 · p. 61, Table 7 · p. 63
  • Because SketchyCGAL iterates are infeasible, their objective values are not lower bounds; sublinear convergence may also make high-accuracy use impractical.The text gives branch-and-bound procedures as an example of a setting requiring high accuracy.Source: Appendix G · p. 48
  • Tables 4 and 6 compare SketchyCGAL relative gaps with CSDP clique sizes k = 2, 3, 4 and PATH results for QAP instances from QAPLIB and TSPLIB.The supplied captions identify these comparisons but do not provide cell values.Source: Appendix G · p. 49, Table 4 · p. 60, Table 6 · p. 62
  • On MaxCut dataset C1, Manopt with R = 2 reaches a spurious solution, while SketchyCGAL computes a rank-1 approximation of the global optimum.The figure plots Manopt gradient norm and suboptimality, and SketchyCGAL suboptimality and infeasibility; its dashed curve tracks implicit iterates.Source: Figure G.1 · p. 50
Loading 1912.02949v2…