Faster Dynamic Matrix Inverse for Faster LPs

1 Introduction

• Dynamic inverse maintenance also appears in applications including directed reachability, empirical risk minimization, routing, and electrical-flow computation.Prior work achieved max{tu, tq}=O(n^1.529) for row queries under row/column updates, while exact versions have a conditional Ω(n^1.5) worst-case lower bound.Source: §1 · p. 2
• The data structure supports rank-one updates and inverse queries for vectors that may be dense but change sparsely over time.It allows approximate answers with small relative ℓ∞ error and uses heavy amortization, unlike exact row-query settings.Source: §1 · p. 2
• Interior-point methods repeatedly update a matrix by low-rank changes, making dynamic inverse maintenance a bottleneck in solving LPs.The paper frames this as a way to avoid recomputing the inverse from scratch at each iteration.Source: §1 · p. 3
• O*(n^2.055) under ω≈2 and α≈1, improving on O*(n^2.166) for previous IPM algorithms.The result answers the open question of whether the additive n^2.166 term could be improved or removed.Source: §1 · p. 3
• The approach combines bootstrapped lazy updates, randomized compression, and a sophisticated amortized analysis of the dynamic process.The paper identifies projection maintenance as a central application of the resulting data structure.Source: §1 · p. 4

2 Bootstrapping low-rank updates via cascading lazy updates

• The update vectors must come from a fixed set of size O(n), and the data structure can also handle slowly changing query vectors.Sparse changes to the query vector are easier to handle than low-rank matrix updates.Source: §2 · pp. 4–5
• The method bootstraps Woodbury’s identity across K update epochs, grouping rank-one updates under decreasing thresholds n_k and maintaining each epoch’s rank within its threshold.The low-rank inverse maintenance problem supports updates M(t) = M(t−1) + c(t)u(t)v(t)^T and queries for M(T)^−1h.Source: §2 · pp. 4–5
• When a level exceeds its rank threshold, updates cascade to the next level; unchanged upper-left LU blocks can be reused to reduce query recomputation.Rebuilding the changed parts and maintaining the query vector costs time proportional to the level’s update size, subject to preprocessing for the fixed update-vector set.Source: §2 · p. 6
• For LP projection maintenance, slowly changing weights and robustness to small relative ℓ∞ error support thresholded updates and randomized compression.The framework uses three levels; its final level can be maintained in O(n_(K−1)·n_K) time rather than the O(n·n_K) brute-force cost.Source: §2 · pp. 6–7
• For K = 3 levels, the framework gives an O*(n^(2+1/18)) runtime, improving on the K = 2 bound of O*(n^(2+1/6)).The analysis uses the LP algorithm’s Õ(√n) iterations.Source: §2 · p. 7
• Extending the predicted runtime to K = ω(1) levels would reach O*(n^ω), but maintaining the LU decomposition efficiently beyond three levels remains a major challenge.The authors leave this broader program beyond the paper’s scope.Source: §2 · p. 7

3 Background

• Section 3 frames recent LP solvers, the interior-point optimization framework, and their relation to dynamic inverse problems.Source: §3 · p. 8

3.1 Recent developments in LP solvers

• Under ω = 2 and α = 1, prior solver bounds still have an O*(n^(2+1/6)) polynomial gap to O*(n^2), while combining stochastic Central Path, lazy updates, and rectangular matrix multiplication improves runtimes.The prior algorithm uses subsampling to obtain o(n^2) query time per iteration.Source: §3.1 · p. 8

3.2 Optimization: The stochastic central-path algorithm

• The stochastic Central Path algorithm iteratively reduces the duality gap and has O(√n) iterations; its robustness permits coordinate-wise approximations to w and h.The stated approximation parameter satisfies ε_mp < 1/4.Source: §3.2 · pp. 8–9

3.3 Data structures: Projection maintenance

• Projection maintenance is the main bottleneck: prior work uses lazy updates and right- or left-side sparsification, while this approach combines both transformations with cascading updates.The paper says two randomized sources would complicate error analysis, motivating a deterministic alternative to right-hand sampling.Source: §3.3 · pp. 9–10

4 Detailed Technical Overview

• For any δ in (0, 1], the algorithm returns x with objective error at most δ∥c∥∞R and constraint residual at most δ(R∥A∥1 + ∥b∥1).Assuming no redundant constraints and ∥x∥1 ≤ R for feasible x, the stated running time is O(n^ω+o(1)) when ω > 2.055 and α > 5 − 2ω; for ω = 2 and α = 1, it is n^2.055.Source: §4 · p. 10

4.1 Our Query Algorithm

• Three query bottlenecks are addressed by compressing projections, using cascading lazy updates, and recursively maintaining second-level components.The approach targets the n^(1+a), n^(aω), and n^(2a) terms in prior query time; the query algorithm maintains components of the two-level structure.Source: §4.1 · pp. 11–13

4.1.1 Technique for removing n1+a

• Sketching on the left and maintaining the previous query answer make the new query vector sparse, breaking the n^(1+a) query-time barrier.The resulting intermediate algorithm solves general LPs in expected time O*(n^ω + n^(2.5−a/2) + n^(0.5+aω)); for ω = 2 and α = 1, it yields n^(2+1/10).Source: §4.1 · pp. 11–12, §4.1.1 · p. 14

4.1.2 Technique for removing nωa

• A second-level proxy, updated at sparsity thresholds, lets cascading lazy updates compute inverse changes and remove the n^(aω) query term.The resulting intermediate expected running time is O*(n^ω + n^(2.5−a/2) + n^(0.5+2a)) for any a ≤ α.Source: §4.1.2 · pp. 14–15

4.1.3 Technique for removing n2a

• Recursing first-level maintenance into second-level matrix-products, vectors, and sets removes the n^(2a) query term by exploiting sparse differences between proxies.The maintained second-level members include S, ∆, Γ, and ξ; the differences between the current query approximation and the second-level proxy have sparsity at most n^ea.Source: §4.1.3 · pp. 15–16
• The query takes O(na+(ω−1)ea) time by avoiding dense matrix-vector products and reducing the remaining multiplication to Tmat(nea,na,nea).Maintaining E = B(MS)⊤ lets the procedure extract BU′ efficiently; the remaining product determines the query time.Source: §4.1.3 · p. 17

4.2 Our Update Algorithm

• The update scheme uses two proxy levels for w, with distances na and nea, and bounds its costs through algorithmic modifications and a more sophisticated amortized analysis.The analysis treats cascading lazy updates as a random process under the sketching of the CP.Source: §4.2 · p. 17, §4.2.1 · p. 17

4.2.1 Cascading updates subroutines

• PartialMatrixUpdate costs Tmat(n,na,ek) per call, while cascading to MatrixUpdate costs Tmat(n,n,k); the vector-update procedures play analogous roles for h.PartialMatrixUpdate updates second-level members until the allowable changes trigger the more expensive first-level update.Source: §4.2.1 · p. 18

4.2.2 Synchronizing two-level soft thresholding

• Two SoftThreshold calls use Adjust to restore threshold gaps and synchronize errors, so the two levels’ updates produce the potential decrease needed for amortization.Adjust restores a separation of ϵmp/(100 log n) between differing proxy coordinates; the v update uses a smaller error threshold than Adjust.Source: §4.2.2 · pp. 18–19

4.2.3 Amortized analysis based on high-order martingales

• Amortized costs are O(n^(ω−1/2+o(1)) + n^(2−a/2+o(1))) for MatrixUpdate, O(n^(1+a−ea/2)) for PartialMatrixUpdate, and O(n^1.5) for VectorUpdate.The text also gives O(n^(2a−ea/2)) for the PartialVectorUpdate amortized cost.Source: §4.2.3 · p. 21

4.3 Putting it all together

• The LP algorithm runs in O(n^(2+1/18)) time; its stated total is √n times query plus update costs, expanded as n^(0.5+a+(ω−1)ea) + n^ω + n^(2.5−a/2) + n^(1.5+a−ea/2).The expansion follows from O(√n) iterations and the stated query and update times.Source: §4.3 · p. 21

A Preliminaries

• The LP input is assumed full-rank with d = Ω(n) and d ≤ n; the standard transformation of [YTM94] initializes x and s, and inverse updates use the Woodbury identity.The identity expresses (M + UCV)^−1 using M^−1 and a smaller matrix inverse.Source: A Preliminaries · pp. 28–29
• The central-path method reduces the duality-gap parameter t by a factor of 1 − O(1/√n) per iteration, while updating µ with a decrease term and a potential-gradient term.The potential bound ensures µ remains approximately t.Source: A Preliminaries · p. 29

B Optimization

• An induction hypothesis establishes Assumption B.5 at each iteration’s start; the analysis proves data-structure guarantees and a potential bound to preserve its two parts.Section G later combines the central-path and data-structure guarantees to re-establish the assumption at iteration end.Source: B Optimization · p. 30

B.1 Definitions

• The data structure returns approximations to w and µ, under assumptions that bound their errors and keep µ within a factor of 0.1 of t.The definitions also specify the next-iteration update t_new := (1 − ϵ/(3√n))t and form µ_new and w_new from the sketched changes.Source: §B.1 · pp. 31–32

B.2 Facts

• Potential-function facts give its gradient and Hessian and bound its behavior under perturbations whose infinity norm is at most 1/(30λ).The cited lemmas also state properties for perturbations bounded by 1/λ and a lower bound on the gradient norm in terms of Φλ(r) − n.Source: §B.2 · p. 33
• A subsampled randomized Hadamard transform gives a coordinate-wise embedding with α = 1 and β = O(log(n/δ)) [LSZ19].For Part 4 of Lemma B.16, the summary table states probability 1 − 1/poly(n) and requires b ≥ 1000 log² n.Source: §B.2 · p. 33, Table 5 · p. 35

• Under Assumption B.5, ∥s^-1eδs∥2 and ∥x^-1eδx∥2 are each at most 2ε.Source: §B.3 · p. 35
• With b ≥1000 log^2 n, ∥μ^-1eδμ∥∞ ≤5ε and ∥x^-1bδx∥∞, ∥s^-1bδs∥∞ ≤3ε hold with probability 1−1/n^4.Source: §B.3 · pp. 35, 38
• For a fresh subsampled Hadamard matrix R independent of h, each coordinate satisfies |(R⊤Rh)i−hi| ≤5.5ε with probability at least 1−1/n^4.Source: §B.3 · p. 38

B.4 Bounding µnew −µ

• For µnew, the residual mean is bounded by 9ϵmpϵ + 4ϵ^2 + 2ϵ^2√n/b, while the normalized update has mean norm at most 6ϵ + 2ϵ^2√n/b and infinity norm at most 6ϵ with probability at least 1 − 1/poly(n).The residual is µ−1(µnew − µ − δt − eδΦ); the normalized update is µ−1(µnew − µ).Source: §B.4 · pp. 39–41

B.5 Potential martingale

• Under Assumptions B.1, B.5, and B.26, the expected potential is at most Φλ(µ/t − 1) − λϵ/(15√n)(Φλ(µ/t − 1) − 10n).This gives the potential bound for the update analyzed in Lemma B.27.Source: §B.5 · pp. 42, 45

B.6 Bounding the movement of w

• Each coordinate of w changes relatively by at most 10ϵ: |wnew_i/wi − 1| ≤ 10ϵ.Source: §B.6 · p. 45

B.7 Bounding the movement of µ

• Each coordinate of µ changes relatively by at most 10ϵ: |µnew_i/µi − 1| ≤ 10ϵ.Source: §B.7 · p. 47
• Lemma B.16 bounds coordinatewise perturbations and second-moment terms used to control movement in µ.The proof invokes bounds on expected scaled perturbations and their variances.Source: §B.7 · p. 47

B.8 One step of central path

• Algorithm 3’s returned perturbations match their definitions, and its two data-structure calls are the runtime bottleneck.All other operations in the one-step central-path procedure take linear time in n.Source: §B.8 · pp. 48–49

C.1 Preliminary and Definitions

• The L operators extend and align matrix blocks up to size 6n^a, while L* appends an identity block so extended square matrices remain invertible.Lr and Lc extend rows and columns, respectively; L combines them.Source: §C.1 · pp. 49–50

C.2 Facts

• A structured symmetric matrix N can be decomposed as U′CU⊤ with inner dimension 3|S2|, computable in O(|S1|·|S2|) time.The decomposition applies when the nonzero entries occupy the three specified blocks and |S1 ∪ S2| ≤ 2n^a.Source: §C.2 · pp. 51–52
• For the structured change in inverse, the decomposition of N enables Woodbury’s identity to maintain the inverse, and the constructed intermediate satisfies Utmp = BU′.The inverse-update result assumes |S ∪ ∂S| ≤ 2n^a.Source: §C.2 · pp. 53–54
• BU′ = Utmp follows from BU1 = B∂S and BU2 = ∂E.The passage states the first identity and concludes the second yields the claimed equality.Source: §C.2 · p. 55
• For BU2, columns in ∂S\S and S′ are expressed using E and M terms, while the remaining columns are zero.These cases establish BU2 = ∂E.Source: §C.2 · p. 55
• Woodbury identity gives a direct update formula for M when the diagonal change has support S.The lemma considers M = A⊤(AV A⊤)−1A and a changed diagonal matrix Ṽ, with S = supp(Ṽ − V).Source: §C.2 · p. 55

• The data structure uses n^2+o(1) space.Source: §C.3 · p. 56
• Initialize takes O(n^ω) time.Source: §C.3 · p. 56
• Query takes O*(Tmat(n^ea, n^a, n^ea) + n^(1+b)) worst-case time per iteration.Source: §C.3 · p. 57

D Data structure : correctness

• UpdateQuery returns approximations wappr ≈_ϵmp wnew and happr ≈_ϵmp hnew, while its proof establishes that the data-structure invariants continue to hold.The approximation argument uses the properties of vnew and evnew and the condition ϵfar < ϵmp; invariants hold initially and are preserved by updates.Source: D Data structure : correctness · p. 61
• The proof maintains the invariants inductively: initialization establishes them, updates preserve them, and Query does not modify data-structure members.Before Query, the section establishes |S ∪ ∂S| ≤ 2na using |∂S| ≤ nea, |S| ≤ na, and ea ≤ a.Source: D Data structure : correctness · pp. 61–63

D.1 Correctness of Query

• Query is correct when |S ∪ ∂S| ≤ 2na and all invariants hold, yielding the stated formula for r with Mnew = A⊤(A W appr A⊤)−1A.The bound ensures the sketching operators and Decompose function used by Query are well-defined.Source: §D.1 · p. 65
• The query proof derives closed-form expressions for intermediate terms and combines r1–r4 to establish the returned r.The derivation uses the update-set identities and the stated matrix-operator properties.Source: §D.1 · pp. 66, 68

D.2 Correctness of UpdateV and UpdateG

• UpdateV and UpdateG preserve all invariants; before PartialMatrixUpdate, the proof ensures |S ∪ ∂S| ≤ 2na.UpdateV’s correctness follows from the guarantees for MatrixUpdate and PartialMatrixUpdate, while UpdateG’s follows from VectorUpdate and PartialVectorUpdate.Source: §D.2 · p. 69

D.3 Correctness of MatrixUpdate

• MatrixUpdate sets v = ev = wappr, leaves g and eg unchanged, and preserves all invariants when they held before the procedure.The guarantee that g and eg remain unchanged follows because Algorithm 13 does not modify them.Source: §D.3 · pp. 70–71

D.4 Correctness of PartialMatrixUpdate

• Given valid initial invariants and |S ∪ ∂S| ≤ 2na, PartialMatrixUpdate sets ev = wappr, leaves v, g, and eg unchanged, and preserves all invariants.The size condition ensures the operators and Decompose function used by the procedure are well-defined.Source: §D.4 · p. 72
• After PartialMatrixUpdate, all invariants of Assumption D.1 are satisfied.The claim applies after Algorithm 14 completes.Source: §D.4 · p. 74

D.5 Correctness of VectorUpdate

• After VectorUpdate, v and ev remain unchanged, g = eg = happr, and all invariants of Assumption D.1 remain satisfied.These guarantees hold when the invariants are satisfied before Algorithm 15 begins.Source: §D.5 · pp. 74–75

D.6 Correctness of PartialVectorUpdate

• After PartialVectorUpdate, v, ev, and g remain unchanged, eg = happr, and all invariants of Assumption D.1 remain satisfied.These guarantees hold when the invariants are satisfied before Algorithm 16 begins.Source: §D.6 · pp. 75–76

D.7 Correctness of Initialize

• Upon initialization, all invariants of Assumption D.1 are satisfied.The proof checks the initial assignments of the data structure members against their invariant requirements.Source: §D.7 · p. 77

E Data structure : time per call

• Section E bounds worst-case time per call for MatrixUpdate, PartialMatrixUpdate, VectorUpdate, PartialVectorUpdate, and Query, excluding vector addition, which costs O(n).The amortized running times are deferred to Section F.Source: E Data structure : time per call · p. 77

E.1 Sparsity guarantees

• Lemma E.1 establishes sparsity guarantees for data-structure members and local variables entering the procedures, with the bounds recorded in Tables 12 and 13.The guarantees support the section's subsequent per-call time analysis.Source: §E.1 · pp. 77–78, Table 12 · p. 77, Table 13 · p. 78

E.2 Running time of Query

• Computing r = r1 + r2 + r3 + r4 takes O(n^(1+b) + Tmat(n^ea, n^a, n^ea)) time.The analysis combines the costs of the steps used to compute r.Source: §E.2 · p. 80
• Query's listed initial quantities and sparse corrections take O(n^(1+b) + n^(a+ea)) and O(n^(a+ea)) time, respectively.These bounds apply to the initial computations and the sparse correction computations described in the analysis.Source: §E.2 · pp. 80–82
• Query's listed matrix-multiplication stages take O(Tmat(n^a, n^ea, n^ea)) and O(Tmat(n^ea, n^a, n^ea)), respectively.The analysis bounds these stages separately; it does not provide an overall Query running-time bound in the supplied passages.Source: §E.2 · p. 82
• Query computes r in O(n^(1+b) + Tmat(n^ea, n^a, n^ea)) time.The bound follows by summing the costs of the intermediate computations.Source: §E.2 · p. 83

E.3 Running time of MatrixUpdate

• MatrixUpdate runs in O(Tmat(n^(1+o(1)), k, n)) time, with Mtmp and Qtmp each taking O(k^(ω+o(1)) + Tmat(n, k, n)) and O(k^(ω+o(1)) + Tmat(n^(1+o(1)), k, n)), respectively.The remaining listed computations take O(n^(2+o(1))) and O(n^2) time, with all other computation taking O(n).Source: §E.3 · pp. 84–85

E.4 Running time of PartialMatrixUpdate

• PartialMatrixUpdate runs in O(Tmat(n^(1+o(1)), n^a, e^k)) time; its Ftmp computation has the same asymptotic bound.The other listed steps include costs O(e^k n^a), O(Tmat(e^k, n^a, n^a)), O(n^(2a)), and O(Tmat(n, n^a, e^k)).Source: §E.4 · pp. 86, 87, 89
• PartialMatrixUpdate takes O(Tmat(n, na, ek)) time overall.Its total bound is O(ekna + Tmat(ek, na, na) + n + n2a + Tmat(n, na, ek)), which simplifies to the stated bound.Source: §E.4 · p. 89

E.5 Running time of VectorUpdate

• VectorUpdate’s listed computations take O(pn1+o(1)), O(n), and O(n2a) time for each of its two remaining steps.Because p ≥ na, the source states that O(pn1+o(1) + n2a) simplifies to O(pn1+o(1)).Source: §E.5 · pp. 90–91

E.6 Running time of PartialVectorUpdate

• PartialVectorUpdate takes O(n2a + epna) time overall.The procedure’s listed computations take O(n), O(n2a + epna), and O(epna) time.Source: §E.6 · pp. 91–92

E.7 Running time of Initialize

• Initialize takes O(nω+o(1)) time.The bottlenecks are computing M and Q; other operations take at most O(n2+o(1)) time.Source: §E.7 · p. 93

F Data structure : amortized time

• The amortized analysis of MatrixUpdate, PartialMatrixUpdate, VectorUpdate, and PartialVectorUpdate builds on [CLS19].Source: F Data structure : amortized time · p. 93

F.1 Definitions and Preliminaries

• The preliminaries use iteration-indexed notation for the input and evolving approximation sequences, and define k_j and ek_j as the outputs k and ek of UpdateV on UpdateQuery’s line 4.Source: §F.1 · p. 93

F.2 Facts based on Adjust and two level of SoftThreshold

• The facts based on Adjust and two-level SoftThreshold give sorting-based guarantees for ek and describe how evtmp and evnew are obtained.For coordinates meeting the stated threshold, the sorting guarantee places them among the first ek entries.Source: §F.2 · p. 94
• MatrixUpdate runs in Tmat(kj, n1+o(1), n) time when kj > 0, with kj either n or a threshold drop in the sorted y values.The threshold is yπ(kj) < (1 − 1/log n) · yπ(kj/1.5).Source: §F.2 · p. 98
• PartialMatrixUpdate runs in Tmat(ekj, na, na) time when ekj > 0, with ekj either n or a threshold drop in the sorted y values.The threshold is yπ(ekj) < (1 − 1/log n) · yπ(ekj/1.5).Source: §F.2 · p. 99

F.3.1 Definitions

• For MatrixUpdate, x tracks coordinate changes in v and ev, y tracks changes in w, and τj sorts the coordinates of x(j).The definitions distinguish changes to v and ev from changes to w and introduce sorting permutations for the coordinates.Source: §F.3.1 · p. 100
• The MatrixUpdate analysis defines g for a parameter a ≤ α and introduces a potential function Φ.α is identified as the dual exponent of matrix multiplication.Source: §F.3.1 · p. 100

F.3.2 Main result

• The MatrixUpdate analysis bounds expected amortized running time by tracking potential changes across successive iterations.The proof separates increases from changes to w and decreases from changes to v and ev.Source: §F.3.2 · pp. 101–102
• The potential starts at zero and remains nonnegative, allowing the analysis to bound cumulative increases by decreases over the update sequence.Initially v(0) = ev(0) = w(0), so Φ0 = 0.Source: §F.3.2 · p. 101

F.3.3 w move

• The w-move analysis bounds the potential increase for each iteration, while separate lemmas bound the v and ev moves.The generalized w-move lemma also permits v(j) to depend only on w(j) and v(j−1).Source: §F.3.3 · pp. 102, 105

F.3.5 ℓ2-norm of g

• For g ∈ R^n as defined in Definition F.17, Lemma F.25 gives the bound ∥g∥2 = O(n^-a/2 + n^(ω-5/2)).Source: §F.3.5 · p. 106

F.4.2 Main result

• The section derives an expected amortized running-time bound for PartialMatrixUpdate using a potential function and separate bounds on its changes.The proof bounds potential increases from w changes and decreases from ev changes.Source: §F.4.2 · p. 108

F.4.3 w move

• The w-move analysis bounds potential increases, while the ev-move analysis bounds potential decreases during PartialMatrixUpdate.The ev-move argument considers changes in the coordinates affected by the partial update.Source: §F.4.3 · pp. 109–110

F.4.5 ℓ2-norm of g

• For the defined weighting vector, ∥g∥2 = O(n^-ea/2 + n^(aω-5a/2)).The proof transfers the corresponding norm argument from MatrixUpdate with n replaced by n^a and n^a replaced by n^ea.Source: §F.4.5 · p. 111

F.5 Amortized analysis for VectorUpdate

• The amortized bound is stated in expectation under a condition on the input sequence.The supplied condition is stated for every iteration, though its expression is not included here.Source: §F.5 · p. 111
• The expected amortized running-time expression for VectorUpdate includes a log n · n^(1.5+o(1)) factor.The analysis combines two parts and uses n^(1.5a) ≤ n^(1.5+o(1)).Source: §F.5 · pp. 111–112
• The VectorUpdate analysis uses separate weighting-vector choices for its two parts, including an all-ones vector in the first part.For the first part, the text gives ∥g∥2 = √n.Source: §F.5 · pp. 111–112

F.6 Amortized analysis for PartialVectorUpdate

• The expected amortized running-time expression for PartialVectorUpdate includes a log n · n^(1.5+o(1)) factor.The proof combines two parts and uses n^(1.5a) ≤ n^1.5.Source: §F.6 · pp. 112–113
• The partial-update analysis uses weighting vectors supported on different coordinate ranges in its two parts.One choice is the indicator vector on the first 2n^a coordinates; another has entries n^-ea through coordinate n^ea.Source: §F.6 · pp. 112–113

F.7 Potential function ψ

• The potential function ψ is symmetric, non-decreasing in |x|, and constant when |x| ≥ 2ϵmp.Its stated derivative bounds are |ψ′(x)| = Ω(1) for |x| ≤ 1.5ϵmp and maxx ψ′′(x) = 1/ϵmp.Source: §F.7 · p. 113, Figure 9 · p. 113

G Combining data structure with optimization

• Each iteration executes ClassicalStep with probability at most 10/n^2 and executes the repeat-loop at most twice in expectation.The analysis derives the ClassicalStep bound from the expected potential bound and Markov’s inequality.Source: G Combining data structure with… · pp. 114–115
• The parameter choices in Table 15 satisfy the stated error-parameter assumptions used in the running-time proof.The analysis also verifies the assumptions relating the approximations of μ and w to their target values.Source: G Combining data structure with… · pp. 114–115, Table 15 · p. 115
• The algorithm outputs x ≥ 0 with objective value at most δ∥c∥∞R above optimum and constraint residual at most δ(R∥A∥1 + ∥b∥1).The guarantee assumes no redundant constraints and an ℓ1-diameter bound R on the feasible polytope.Source: G Combining data structure with… · p. 116
• When ω = 2 and α = 1, the running time is eO(n^(2+1/18)).For the general case, the analysis bounds the exponent by about 2.0598.Source: G Combining data structure with… · pp. 116–118

H.2 Online low-rank inverse and the oMV conjecture.

• Online low-rank inverse multiplication and online matrix-vector multiplication are essentially equivalent in the word-RAM model with polynomial preprocessing.Lemmas H.3 and H.4 give reductions in both directions with query-time overhead bounded by a constant factor.Source: §H.2 · p. 119

H.3 Optimizing the parameters of Eq. (3)

• The multilevel parameter optimization gives exponents a_i = 1 − 1/(3 · 2^(K−i)) + (2 − 2^(−K+i+1)) · p for i ∈ [K].The proof sets p = 1/(6 · (2^(K−1) − 1)).Source: §H.3 · p. 120

I A feasible algorithm

• The feasible algorithm implicitly maintains x = Gu1 + u2 and s = Mu3 + u4, postponing expensive matrix-vector multiplication until every √n iterations.It avoids left-multiplying by the sketching matrix when computing updates, so Ax = b remains satisfied.Source: I A feasible algorithm · p. 120

I.1 Analysis

• The feasible algorithm maintains approximations wappr ≈ 2ϵmp w and happr ≈ 2ϵmp μ, while μnew ≈ 0.2t.These bounds preserve the corresponding central-path assumptions up to constant factors.Source: §I.1 · p. 124
• With high probability, the implicit and explicit x and s vectors remain entry-wise within ϵtiny of one another.This closeness is used to establish the modified algorithm’s other guarantees.Source: §I.1 · p. 124
• The modified analysis still yields a polynomial upper bound on the potential, with only a constant-factor loss in the approximation of μ relative to t when the final term is O(n^2) instead of O(n).The potential contracts according to the stated recurrence for Φλ.Source: §I.1 · p. 125

I.2 Correctness of feasible algorithm

• The feasible algorithm’s central-path step satisfies the stated output guarantee, and MakeFeasible satisfies its stated condition when invoked.The theorem also specifies iteration-level update guarantees for the algorithm.Source: §I.2 · p. 127
• With high probability, x and s remain entry-wise within ϵtiny of their implicitly maintained counterparts.This guarantee is part of the feasible algorithm’s correctness theorem.Source: §I.2 · p. 127

I.3 Bounding x and x

• For a fixed coordinate and up to √n iterations, the explicit and implicit x values stay within the stated error bound with probability at least 1 − δ, under the lemma’s listed conditions.Those conditions include a bounded change in t and approximations wappr staying within a factor of two of a fixed w.Source: §I.3 · p. 131

I.4 Running time of feasible data structure

• ScalarC takes O(n) time to execute.Source: §I.4 · p. 133
• Refreshing G, u1, and u2 together takes O(n^2) time.Source: §I.4 · p. 133
• Two PartialMatrixUpdate computations—updating G and updating u1—each take O(n^(1+a)) time.Source: §I.4 · p. 133
• Refreshing G, u1, u2, and u4 takes O(n^(1+a)) time.Source: §I.4 · p. 133
• Query computations for u1, u2, and u4 take O(n^a+e^a) time.Source: §I.4 · p. 134
• The amortized time of MakeFeasible is dominated by that of MatrixUpdate.Source: §I.4 · p. 135

J History of Matrix Multiplication and LP

• Table 16 records the history of ω and α, while Table 17 presents LP algorithm runtimes for dense, full-rank instances with d = Θ(n).Source: Table 16 · p. 136, Table 17 · p. 136