Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma

1 Introduction

• The authors dequantize Quantum OR for sparse SDPs, matching optimal classical dimension dependence up to logarithmic factors and improving accuracy dependence with stochastic updates for both players.The resulting stochastic analysis controls feedback and approximation errors over the optimization trajectory, yielding approximate saddle-point iterates.Source: §1 · pp. 4–5

1.1 Comparison with Prior Works

• For fixed γ and sparsity s, both solvers have additive n-and-m dependence and run sublinearly in the saturated sparse input size.Unlike some prior sublinear methods, they require neither low-rank constraints nor favorable Frobenius-norm bounds; full-input interior-point methods instead trade sublinear input dependence for better very-high-accuracy scaling.Source: §1.1 · p. 6

1.2 Main Result 1: Dequantizing the Quantum OR Lemma for SDPs

• For sparse Hamiltonians and sparse observables, the paper replaces quantum search with classical simultaneous estimation of Gibbs expectations, using standard sparse access and operator-norm bounds.The method uses Lanczos approximation and avoids both direct simulation of gentle measurement and materializing dense n × n matrices.Source: §1.2 · p. 7

1.2.1 The Fast Quantum OR Lemma and Its Reduction to Expectation Estimation

• Rather than only deciding whether a violated constraint exists, the SDP reduction estimates the entire Gibbs-expectation vector, whose thresholded entries identify violations or certify approximate feasibility.This stronger estimation task lets the Hamiltonian-dependent computation be reused across all observables.Source: §1.2.1 · p. 8

1.2.2 A Classical Simultaneous Gibbs Expectation Estimator

• A classical estimator uses sparse input descriptions to approximate filtered random vectors and reuses each vector to estimate all m observables to additive accuracy α with probability at least 1 − δ.It neither prepares Gibbs-state copies nor accesses the dense Gibbs operator entrywise.Source: §1.2.2 · p. 8
• One coordinate sampled from the Gibbs-state vector estimates all m constraint energies in O(ms) time, using only sparse-row access to each constraint matrix.The estimator is unbiased and its second moment is bounded by the operator norm squared.Source: §1.2.2 · p. 9
• Under ∥Aj∥≤1, fixed-additive-accuracy sampling is independent of n, remaining efficient for full-rank constraints even when ∥Aj∥²_F = Θ(n).The operator-norm second-moment bound avoids the dimension dependence that Frobenius-controlled estimators can incur.Source: §1.2.2 · pp. 9–10
• O(α⁻² log(m/δ)) random starts yield simultaneous high-probability estimates by taking coordinatewise medians of group-level ratio estimates.Observables may be correlated through shared samples; independence is required only across random starts.Source: §1.2.2 · p. 9
• Randomized Lanczos approximates the dense filtered vector, separating an n-dependent filtering cost from an m-dependent readout cost.The resulting vectors are explicitly computed and stored, and sampling from them costs O(n), included in the filtering term.Source: §1.2.2 · p. 9
• Unlike standard sample-and-query dequantization [Tan19], the method uses only sparse-row access and classically realizes Quantum OR sample reuse for structured SDP Gibbs states.Its speedup uses neither stronger access assumptions nor low-rank structure, and it does not simulate arbitrary gentle measurements on unknown quantum states.Source: §1.2.2 · p. 10

1.3 Main Result 2: Quantum-Inspired Classical Sublinear-Time SDP Solvers

• A shared-coordinate estimator classically realizes Quantum OR sample reuse by simultaneously estimating sparse-observable Gibbs expectations from a shared sample collection.The estimator combines randomized Lanczos filtering with a sampling-based estimator.Source: §1.3 · p. 10, §1.3.2 · p. 12

1.3.1 SDP Feasibility as a Two-Player Game

• Feasibility games solved to normalized accuracy Θ(1/γ), combined with game-value certificates and gapped binary search, yield an additive-ε SDP solution.Here γ := Rr/ε, and the dual-radius bound r determines the required feasibility-game accuracy.Source: §1.3.1 · p. 11

1.3.3 From One-Sided to Two-Sided Stochastic SDP Solving

• The stochastic solver improves on one-sided stochastic methods by sampling constraints and payoff feedback, removing dense per-round operations and preserving additive dimension dependence.The preceding sparse-row implementation retained multiplicative dependence on m and n.Source: §1.3.1 · p. 11, §1.3.3 · p. 13

1.3.2 Oracle-Based MMWU with Simultaneous Gibbs Estimation

• In the bounded-radius, constant-accuracy regime, the solver scales as eO(n + m), recovering classically the additive dimension dependence arising from Quantum OR without reproducing its square-root search speedup. Its accuracy dependence is eO(ε−6.5), compared with eO(ε−5) for the corresponding quantum solver.Source: §1.3.2 · p. 12

1.3.3 From One-Sided to Two-Sided Stochastic SDP Solving

• The two-sided solver samples one constraint for the primal update and one coordinate of a rank-one action for stochastic payoff estimates across all constraints.Both players update from sampled information, and convergence is controlled over the optimization trajectory rather than by accurate per-round responses.Source: §1.3.3 · p. 14
• When γ^2 ≤ min{m,n/s}, the two-sided stochastic solver runs in eO(nsγ^4.5 + msγ^2) time.It returns normalized primal and dual actions with original-scale saddle-point gap at most ε after rescaling.Source: §1.3.3 · p. 14

1.4 Discussion

• The classical realization is specific to sparse SDP access, not a general dequantization of the Quantum OR lemma for arbitrary states and measurements.It uses sparse Hamiltonian representations for randomized Lanczos and sparse-row queries for the constraint energy estimator.Source: §1.4 · p. 15
• For fixed accuracy and sparsity, the remaining dimension dependence is essentially optimal classically: known sparse-oracle lower bounds require Ω(n + m) classical queries versus Ω(√n + √m) quantum queries.The paper identifies this remaining separation as the standard quadratic Grover speedup.Source: §1.4 · p. 15
• Both regret-based updates and violated-constraint search can approximate the optimum while touching only a small fraction of the input.The regret-based approach uses stochastic feedback rather than constructing or inspecting the entire input.Source: §1.4 · p. 16
• Sublinear runtimes return succinct or implicit primal certificates rather than a materialized generic dense matrix, whose construction would require Ω(n²) time.The two-sided stochastic solver returns an average of at most Õ(γ²) rank-one factors and an empirical distribution over sampled constraints.Source: §1.4 · p. 16
• The two-sided stochastic solver improves accuracy dependence by using stochastic feedback across the optimization trajectory, motivating a possible stochastic architecture for quantum SDP solvers.The paper presents the quantum extension as an open direction requiring matrix-valued dynamic sampling and cumulative-feedback methods.Source: §1.4 · p. 16

2.2 Sparse-row oracle and arithmetic model

• The sparse-row oracle charges for queried rows and entries rather than requiring an upfront scan of the sparse input representation.A saturated instance may contain Θ(mns) scalar nonzeros; the arithmetic model assumes O(1)-time access to stored scalar parameters and omits finite-precision and bit-complexity costs.Source: §2.2 · p. 17

2.3 Squared-Magnitude Sampling from Explicit Vectors

• Squared-magnitude sampling from an explicitly stored vector takes O(d) time, samples exactly from the desired distribution, and requires no sample-and-query access to input vectors or constraint matrices.The procedure uses O(1) additional space.Source: §2.3 · p. 18

2.4 Properties of Haar-Random Vectors

• Haar-random unit-vector moment identities provide symmetry facts used to bound the variance of random estimators.The first moment makes the expected rank-one projector proportional to the identity.Source: §2.4 · p. 18

2.5 The Zero-Sum Game Framework

• An approximate saddle-point gap at most ε certifies an additive-ε approximate saddle point for the radius-scaled matrix-versus-constraint game.The matrix player uses a trace-bounded spectrahedron and the constraint player a scaled probability simplex; their payoff is the constraint-weighted aggregate of matrix values.Source: §2.5 · pp. 18–19

2.6 Mapping SDPs to Zero-Sum Games

• The standard SDP reduction tests candidate objective values through feasibility games, while the original dual-radius bound determines the accuracy needed to distinguish values around OPT.The reduction recovers an approximately optimal primal solution by gapped binary search.Source: §2.6 · p. 20

2.6.2 The Target-Value Feasibility Game

• Each target-value game's derived payoff matrices are (s + 1)-row-sparse, and their rows can be generated in O(s) time from original rows and a diagonal term.The reduction preserves sparse access up to constant factors and uses a uniform operator-norm scale across threshold values.Source: §2.6.2 · p. 21

2.6.3 From Approximate Saddle Points to SDP Solutions

• A target game's returned strategies provide lower and upper value certificates: attainable thresholds have nonnegative lower certificate, while thresholds at least (1 + r)τ above OPT have lower certificate at most −τ.If the upper certificate is at least −ζ, the leading principal block yields a primal solution with objective and constraint errors bounded using the saddle-point gap and ζ.Source: §2.6.3 · pp. 21–22

The computation uses

• Randomized Lanczos supplies a one-sided approximation to the matrix player's upper certificate, enabling a gapped binary search that uses O(log(2 + R/η)) game solves.The test eug + ζ ≥ 0 retains attainable thresholds and, when retained, implies the condition for primal recovery.Source: §2.6.3 · p. 22, The computation uses · p. 23
• Bisection over [-R, R] updates an accepted saved matrix or the rejection endpoint, stopping at width η in O(log(2 + R/η)) game solves.Rejected thresholds are strictly above OPT, preserving the upper-endpoint invariant.Source: The computation uses · p. 24
• With η = ε/2 and ξ = ζ = ε/(8(1 + r)), the recovered primal matrix has objective error at most ε and constraint violations at most ε/r.The reduction uses O(log(2 + R/ε)) target-value game solves and upper-certificate computations; allocating failure probability across calls and applying a union bound preserves the overall success probability.Source: The computation uses · p. 24
• The reduction uses logarithmically many spectrahedron–simplex games with matrix radius R, simplex radius one, and payoff matrices of operator norm at most two.The dual radius r determines the game solver and target-value certificate accuracy, Θ(ε/(1 + r)); sparse certificate implementation cost is included in Section 7.8's runtime analysis.Source: The computation uses · p. 24

Estimator guarantees

• The coordinate estimator is unbiased and has an operator-norm-bounded second moment, so its guarantee does not require Frobenius-norm dependence and remains effective for generic full-rank observables.The same sampled coordinate is reused across all constraint matrices.Source: §3 · p. 24

Estimator construction

• One sampled coordinate yields all m sparse-observable estimates in O(n + ms) time, rather than accessing every row of every constraint matrix at O(nms) cost.The shared coordinate is sampled according to its squared vector magnitude, and each estimate reads only the sampled row of its constraint matrix.Source: §3 · p. 24

Clipping for stochastic feedback

• Individual estimates can be arbitrarily large when the sampled coordinate has small magnitude, so the stochastic solver clips feedback to enforce a uniform bound, at the cost of bias.The raw estimator's second-moment control is sufficient for applications using robust averaging, but the online learner requires bounded feedback.Source: §3 · p. 25

4 L´anczos Approximation of Matrix-Exponential–Vector Products

• Lanczos avoids forming the generally dense matrix exponential by projecting the matrix-exponential–vector product onto a low-dimensional Krylov space, leaving repeated matrix–vector multiplication as the high-dimensional work.Both algorithms use this primitive for Gibbs-state estimation or stochastic matrix learning.Source: §4 · p. 26

4.2 Random-Start L´anczos Approximation

• A random starting direction has high-probability overlap with a top eigendirection, enabling relative-error control after normalizing the Lanczos output when a fixed start may not suffice.The deterministic bound controls absolute error, which need not imply the relative error required after normalization.Source: §4 · p. 26, §4.2 · p. 28

4.1 Deterministic L´anczos Approximation

• The deterministic Lanczos approximation uses a tridiagonal compression of the matrix and bounds its error through best uniform polynomial approximation on the matrix's spectral interval.If the Krylov space becomes invariant, the procedure returns the matrix-function product exactly.Source: §4.1 · p. 27

4.2 Random-Start L´anczos Approximation

• The stochastic learner uses a real-symmetric random-start guarantee, while the Gibbs expectation estimator requires a separate complex-Hermitian Haar-random analogue.The real result is not directly applicable to the latter estimator.Source: §4.2 · p. 28

5 Simultaneous Gibbs Expectation Estimation

• One collection of Hamiltonian-filtered random vectors estimates all m Gibbs expectations, with the Hamiltonian-dependent cost incurred once and sparse observable-dependent cost scaling linearly with m.For each random start, the filtered vector e−H/2u is reused across observables.Source: §5 · p. 29

5.1 Recovering Gibbs Expectations from Filtered Random Vectors

• The Gibbs expectation of an observable is a ratio of expectations over filtered random vectors: its numerator uses the observable, while its denominator is a shared normalization factor.Averaging filtered outer products recovers the unnormalized Gibbs operator, and averaging their squared norms supplies its normalization.Source: §5.1 · pp. 30–31

5.2 Unnormalized Gibbs Moments

• The same sampled coordinate can be reused for every observable, producing weighted samples whose means match the Gibbs-expectation numerators and whose second moments are controlled by observable norms.The samples may be correlated across observables; independence across observables is not required.Source: §5.2 · pp. 31–32

5.3 Simultaneous Ratio Estimation via Median-of-Means

• Median-of-means estimates all m ratios with probability at least 1−δ using a common denominator estimate, even when the numerator and denominator variables are unbounded and dependent.The construction uses Θ(log(2m/δ)) groups and Θ(κω²/α²) samples per group under the stated moment bounds.Source: §5.3 · p. 33

5.4 Stability Under L´anczos Approximation

• Replacing exact filtered vectors with relative-error approximations preserves accuracy of the weighted ratio estimator, with its ratio perturbation bounded by 2βω for β=2ζ+ζ².This stability result transfers guarantees for exact filtered vectors to their finite-Krylov Lanczos approximations.Source: §5.4 · pp. 35, 37

5.5 Proof of the Simultaneous Gibbs Estimator

• Each Haar-random start is approximately filtered using Lanczos, then one sampled coordinate is reused to estimate all m observables, with median-of-ratios aggregation.The method combines numerator and denominator samples using the median-of-ratios construction.Source: §5.5 · p. 37
• Algorithm 5’s estimates satisfy the claimed guarantee simultaneously for all m observables.The proof combines the Lanczos-success event with the statistical-success event to establish the simultaneous guarantee.Source: §5.5 · pp. 37, 40
• The proof avoids conditioning on all Lanczos runs succeeding, using a pointwise-valid approximation and a union bound to establish simultaneous correctness.Conditioning would change the distribution of the Haar-random starting vectors; the pointwise-valid approximation permits the analysis without that conditioning.Source: §5.5 · pp. 38–40
• Runtime accounts for N random starts, filtering each vector, O(n) sampling-distribution construction, and O(msA) evaluation of all observables at one sampled coordinate.The total running time follows by multiplying the per-start cost by the number of random starts.Source: §5.5 · p. 41

6 Oracle-Based SDP Solving via Simultaneous Gibbs Estimation

• The section uses simultaneous Gibbs estimation to implement the Gibbs-state oracle interfaces of van Apeldoorn and Gilyén [vAG19] in an end-to-end classical sparse-oracle solver.The resulting solver has sublinear dependence on the product of matrix dimension n and constraint count m.Source: §6 · p. 41

6.1 Classical Gibbs-State Constraint Search

• After simultaneous Gibbs-expectation estimates are computed, constraint search compares them with thresholds and becomes a deterministic scan.The estimates come from the same filtered random vectors, so Hamiltonian-dependent filtering is reused across constraints.Source: §6.1 · pp. 41–42

6.2 Direct Gibbs–MMWU Solver

• The classical implementation reuses Gibbs-dependent filtering but does not reproduce the quantum solver's Grover-type constraint-search advantage.The classical routine estimates all constraint expectations and scans them explicitly.Source: §6.1 · p. 42, §6.2 · p. 44
• When OPT ≥ g + ε, the solver returns a primal certificate; when OPT ≤ g − ε, it returns a dual certificate, with either output permitted between those thresholds.The primal certificate satisfies ⟨C, X⟩ ≥ g − ε and ⟨Aj, X⟩ ≤ bj + ε/r for every constraint.Source: §6.2 · p. 45
• Each MMWU round filters for an O(t)-term Hamiltonian and extracts all m constraint expectations from the shared samples.These are the two costs summed over the rounds to obtain the solver's runtime bound.Source: §6.2 · p. 46
• For constant γ and s, the direct solver runs in eO(n + m) time and returns a valid primal or dual certificate with probability at least 1 − δ.The coefficient representation has support eO(γ^2).Source: §6.2 · pp. 45–46

• Single noisy samples let both players update without constructing the dense objects required by deterministic implementations.The matrix player avoids the dense mixture A*z, while the constraint player avoids evaluating the full payoff vector.Source: §7 · p. 46
• Both players incur O(sqrt(T)) regret, yielding an O(1/sqrt(T)) saddle-point gap for averaged actions while each round accesses only sparse matrix data.Source: §7 · p. 46
• T=O(γ^2Λ) rounds suffice for an ε-accurate saddle point, with γ=Rrω/ε and Λ=log(16mn/δ).Theorem 7.1 states the guarantee holds with probability at least 1−δ.Source: §7 · pp. 46–47
• For fixed γ and s, the solver runs in eO(n+m) without rank or Frobenius-norm assumptions on constraint matrices.Source: §7 · p. 47

7.1 The Stochastic Algorithm

• The matrix player uses a randomized rank-one learner, whose expected action is generally not the Gibbs state used by standard MMWU.The cited analysis provides a regret guarantee for this learner and treats a fresh rank-one sample as a zero-mean fluctuation.Source: §7.1 · p. 47
• The constraint player uses exponential weights on cumulative stochastic feedback to sample one constraint, whose matrix supplies the sparse gain for the matrix player.Source: §7.1 · p. 47
• One coordinate sampled from the matrix response is reused to estimate every constraint payoff, with estimates clipped and accumulated for later updates.Source: §7.1 · p. 48
• A one-round lag adds the newly sampled gain only after the current matrix action, making that action independent of the current constraint sample once prior rounds are fixed.Source: §7.1 · p. 48
• The averaged primal output has rank at most min(T,n), and the dual output is represented by sampled-constraint counts with support at most min(T,m).Source: §7.1 · pp. 48–49

7.2 Regret Decomposition

• The averaged-output saddle-point gap decomposes exactly into the realized regrets of the matrix and constraint players.Source: §7.2 · pp. 49–50
• Each regret compares a player’s cumulative payoff with the best fixed matrix or constraint action chosen in hindsight.Source: §7.2 · pp. 49–50
• The decomposition uses true payoff vectors for the matrix actions actually played, not the stochastic feedback supplied to the constraint learner.The two players’ sampled actions give the same realized payoff each round.Source: §7.2 · pp. 49–50

7.3 Stochastic History and Concentration Tools

• The history filtration fixes the accumulated Hamiltonian, feedback, and mixed constraint action before the round’s constraint and random direction are drawn; the coordinate sample comes afterward.Source: §7.3 · p. 50
• Conditioning on the appropriate half-step history makes the matrix-side and constraint-side sampling errors conditionally unbiased, enabling martingale concentration control.Source: §7.3 · p. 50
• Azuma–Hoeffding controls bounded action-sampling increments, while Freedman uses conditional second moments for clipped feedback whose threshold can exceed typical estimator size.Source: §7.3 · pp. 50–51

7.4 Coupling the Computed L´anczos and Exact Matrix Responses

• The matrix-player analysis separates rank-one sampling error from the numerical error of replacing the exact sampled response with its Lanczos approximation.The comparison uses the same realized Hamiltonian and random direction on each round, so prior approximation errors are incorporated into the conditioned history.Source: §7.4 · pp. 51–52
• Algorithm 7’s round-dependent Lanczos iteration count accounts for the growing exponential-argument norm and guarantees the desired approximation accuracy simultaneously on every round t ∈ [T], with probability at least 1 − δ_L.Source: §7.4 · p. 52
• Relative vector accuracy of order 1/T suffices for the trace-norm accuracy required by the regret analysis.The analysis converts vector approximation to normalized-response accuracy, then bounds the resulting cumulative payoff error.Source: §7.4 · p. 53

7.5 The Matrix-Player Guarantee

• A single exact rank-one response need not be close to its mean, but its payoff error is unbiased on every round.Conditioning on the history and sampled constraint leaves the random direction as the remaining randomness.Source: §7.5 · p. 54
• The matrix-side guarantee holds with probability at least 1 − δX − δL, combining mean-response regret, rank-one sampling fluctuation, and Lanczos approximation error.The mean-response term is controlled deterministically, sampling fluctuation by concentration, and numerical error by the Lanczos guarantee.Source: §7.5 · pp. 54–55
• The sampling fluctuation is controlled by Azuma–Hoeffding, while the average-projection regret bound applies deterministically to every realized gain sequence.The matrix-side analysis treats sampling error and Lanczos approximation error as distinct contributions.Source: §7.5 · pp. 54–55

7.6 Exponential Weights with Stochastic Feedback

• Starting from equal weights, the learner multiplies each constraint’s weight by exp(−ηy[bct]j) and normalizes the weights into its next-round distribution.Constraints with smaller cumulative feedback retain relatively larger weight.Source: §7.6 · p. 56
• The lemma shows that the usual exponential-weights guarantee remains stable when exact payoff feedback is replaced by a random approximation; its additional error depends on the feedback’s range, second moment, and bias.Under ηyB ≤ 1, the cited result holds with probability at least 1 − δF for every δF in (0,1).Source: §7.6 · p. 56
• The regret analysis separates exponential-weights regret on observed feedback, centered stochastic noise, and the deterministic bias caused by clipping.The random terms are controlled using concentration; clipping bias is bounded directly.Source: §7.6 · pp. 56, 60

7.7 The Constraint-Player Guarantee

• The learner plays a sampled constraint but updates its distribution using clipped feedback from a shared-coordinate estimator, not the exact payoff vector.The feedback’s range, second moment, and clipping bias are the properties used in the stochastic exponential-weights bound.Source: §7.7 · pp. 60–61
• Sampling one constraint changes an individual round’s payoff but introduces no systematic bias.Conditioned on the history and random direction, the sampled constraint remains a fresh draw from the learner’s distribution.Source: §7.7 · p. 60
• The constraint-side guarantee combines control of pure-constraint sampling error with control of mixed-action regret under stochastic feedback.The analysis balances the clipping threshold and learning rate before combining the two bounds.Source: §7.7 · pp. 61–62

7.8 Proof of the Main Theorem

• The proof combines matrix- and constraint-side bounds so that, with probability at least 1 − δ, both hold simultaneously for the accuracy analysis.A union bound combines failure probabilities 2δ/3 and δ/3.Source: §7.8 · pp. 62–63
• T = eO(γ^2) rounds suffice to make the output gap at most ε.The round count follows from the bound on the cumulative error divided by the number of rounds.Source: §7.8 · p. 63
• Reusing each sampled coordinate across all m constraints computes the feedback vector in O(ms) time, with O(n + ms) total work outside Lanczos per round.Updating exponential weights and sampling the constraint costs O(m); state-vector and coordinate-sampling work costs O(n).Source: §7.8 · p. 64
• Hamiltonian-vector products use the cheaper of sparse products over distinct sampled constraints and dense matrix-vector multiplication.The sparse cost grows with the number of distinct constraints used; the dense representation becomes an option at the crossover described in the proof.Source: §7.8 · p. 64
• The end-to-end solver returns an implicit primal representation using rank-one factors and a dual representation using sampled constraints.The target-value reduction and upper-certificate computations preserve the game solver’s running time up to polylogarithmic factors.Source: §7.8 · pp. 65–66
• The runtime guarantee uses implicit outputs and sparse-oracle access; explicitly materializing a generic primal matrix costs Ω(n^2), while reading explicit sparse input costs Θ(mns).The algorithm charges only for input portions accessed along its realized trajectory.Source: §7.8 · pp. 65–66

A Hermitian Inputs via “Realification”

• Realification preserves feasibility, trace, constraint payoffs, and objective values, and the original and realified SDPs have the same optimum.The primal correspondence uses a factor of 1/2 when mapping a Hermitian primal matrix to its real representative.Source: A Hermitian Inputs via “Realification” · pp. 70–71
• The real and Hermitian games have the same saddle-point value and pointwise primal–dual gaps.The proof combines feasible-set and payoff correspondence with spectral correspondence.Source: A Hermitian Inputs via “Realification” · pp. 70, 72
• Realification respects matrix products and real-coefficient analytic functions, so solver operations can be performed directly on the realified matrices.The analysis does not require identifying the learner’s real unit vectors with complex Haar directions.Source: A Hermitian Inputs via “Realification” · p. 72
• Realification preserves operator norms and increases row sparsity from at most s to at most 2s, so iteration and arithmetic bounds change only by constant factors.A realified row can be produced from an original complex row in O(s) time.Source: A Hermitian Inputs via “Realification” · pp. 71–72
• Replacing each Hermitian matrix by its block realification lets the stochastic solver run in dimension 2n and map its primal output back without changing the gap.The constraint-player output is unchanged.Source: A Hermitian Inputs via “Realification” · pp. 69, 72