Computation and Applications of Euclidean and Normed Representations of Massive Data

• Yury Makarychev is identified as the thesis advisor.Source: TOYOTA TECHNOLOGICAL INSTITUTE AT… · p. 1
• Haotian Jiang and Lorenzo Orecchia are listed.Source: TOYOTA TECHNOLOGICAL INSTITUTE AT… · p. 1

Introduction

• Massive-data representations can preserve salient properties while reducing data size for downstream methods and revealing structure not apparent in the original data.Source: Introduction · p. 9

1.1 ℓ2-Representations of Convex Polytopes

• Approximating a normed space's unit ball by an ellipsoid represents that space in ℓ2, and the best such approximation factor equals its Banach–Mazur distance to ℓ2.Source: §1.1 · p. 10
• For a convex hull of n points, the streaming algorithms use one pass and space for d^2 real numbers, with approximation nearly best possible up to logarithmic aspect-ratio dependence.Source: §1.1 · p. 10

1.2 Approximating ℓp-Matrix Block Norms

• Block norm sampling sparsifies grouped matrix rows by selecting and scaling whole groups, using block Lewis weights and efficient weight-computation algorithms in certain norm-parameter regimes.Source: §1.2 · p. 11
• The sparse approximation supports sums-of-Euclidean-norms regression schemes whose runtime depends on intrinsic dimensionality rather than the number of groups.Source: §1.2 · p. 11

1.3 ℓ2-Embeddings of Metric Spaces and ℓ2-Configuration

• For metric data, the thesis develops a geometry-independent-runtime algorithm for lowest-distortion ℓ2 embeddings and a graph-constrained configuration problem for selected distance pairs.Source: §1.3 · pp. 11–12
• The embedding solver also targets the rounding SDP in sparsest-cut approaches; the preceding relaxation remains a separate task.Source: §1.3 · p. 12
• The introduction relates sparse distance constraints to distance-matrix completion and notes that efficient specialized recovery algorithms may inform future Euclidean distance recovery methods.Source: §1.3 · p. 12

2.1 Introduction

• Ellipsoidal summaries can represent bodies using O(d^2) floats, while prior algorithms such as require the full dataset in memory and cannot handle streaming.The motivation includes summarizing datasets too large to fit in memory and updating summaries as new data arrives.Source: §2.1 · pp. 13–14

2.1.1 Main Result

• The streaming algorithms achieve α = O(d log(R/r + 1)) and use O(d^2) floating-point numbers to approximate symmetric convex hulls.The input points arrive one at a time, and the number of points need not be known beforehand; each output ellipsoid covers the points seen so far.Source: §2.1.1 · pp. 14–15

2.2 Preliminaries and Notation

• The algorithms also apply when the stream consists of slabs defining the body rather than points.The section frames the approximation task for centrally symmetric convex bodies and defines the body’s aspect ratio as the ratio of its enclosing and inscribed ball radii.Source: §2.1.1 · pp. 14–15, §2.2 · p. 17

2.1.1 Main Result

• Composing the ellipsoidal approximation procedures with Gaussian cooling yields an eO(nd^2 + d^3 log(R/r) + d^3)-time algorithm for estimating symmetric convex-polytope volume.The stated guarantee is comparable to preprocessing with [CCLY19a] and improves on the guarantee suggested by.Source: §2.1.1 · p. 15
• For a natural class of monotonic streaming algorithms, no method can approximate John’s ellipsoid better than a √d factor, limiting that route to an O(d) approximation of the body.Monotonic algorithms maintain ellipsoids that cover each current hull and are nested over time.Source: §2.1.1 · p. 15, §2.2 · p. 17

2.3 Scale-Dependent Algorithm for Ellipsoid Approximation

• The scale-dependent algorithm maintains covering ellipsoids by expanding the current ellipsoid to include each new point, and its analysis uses a non-increasing potential.Its guarantee depends on knowing a lower bound r for the body’s inscribed-ball radius; without an estimate for r, the initial potential can be arbitrarily large.Source: §2.1.1 · pp. 15–16, §2.3 · p. 17
• Algorithm 2.3’s approximation guarantee depends linearly on log(R/r), where R is the radius of the smallest ball containing X.Source: §2.3 · p. 17
• Algorithm 2.3 updates the smallest-volume centered ellipsoid containing the previous ellipsoid and each new point, using O(nd^2) time and O(d^2) floating-point numbers.Source: §2.3 · pp. 17–18

2.4 Scale-Independent Algorithm

• With an upper bound ξ on the aspect ratio but no scale estimate, Algorithm 2 adds a singular-value correction that raises semi-axes to at least M_t/ξ to keep its matrix well-conditioned.Source: §2.4 · p. 21
• 2√3 + 14d log ξ + 8d is the stated approximation bound when ξ ≥ κ(X); Algorithm 2 runs in O(nd^2 log^2 d) time and stores O(d^2) floats.Source: §2.4 · p. 22
• The scale-independent analysis groups consecutive Q_t values so they do not increase significantly within a group, enabling a bound on the final ellipsoid relative to E*.The resulting inclusion is obtained by applying part 2 of Lemma 2.13 to the bound on the final singular value.Source: §2.4 · pp. 22–23

2.5 Proof of Claim 2.8

• After a linear transformation, Claim 2.8 reduces to finding the minimum-volume ellipsoid containing the unit ball and a point; an optimal ellipsoid has one semi-axis along that point and unit-length orthogonal axes.The proof derives the formula using linear algebra rather than relying on this geometric characterization.Source: §2.5 · p. 23

2.6 Proof of Theorem 2.10: Approximating Convex Polytopes with Ellipsoids

• The intersection A_q of ellipsoids containing X with aspect ratio at most qκ(X) satisfies (1/(1+δ))A_q ⊆ X ⊆ A_q.Here q ≥ 1/κ(X) and δ is the parameter defined in the proof.Source: §2.6 · pp. 23–24

2.7 Proofs from Section 2.4

• The singular-value correction step is equivalent to injecting d ghost points into the update procedure, yielding the same matrix A_t.Each ghost point is placed along a semi-axis, with length determined by the correction threshold or the corresponding pre-correction axis length.Source: §2.7 · p. 24
• For non-decreasing Q_t, the potential satisfies S_t ≤ S_u + Q_t(P_t − P_u) for every u ≤ t.Source: §2.7 · p. 26

2.8 Tracking the Minimum-Volume Outer Ellipsoid

• A one-pass monotonic algorithm α-approximates the minimum-volume outer ellipsoid when its output E_n satisfies E_n ⊆ α·J(X).J(X) denotes the minimum-volume outer ellipsoid for X.Source: §2.8 · p. 28
• Every one-pass monotonic deterministic streaming algorithm for minimum-volume outer-ellipsoid approximation has factor at least d for infinitely many d.Source: §2.8 · p. 28

2.9 Dual Problem – Inner Ellipsoidal Approximation

• Primal point-input and dual constraint-input streaming formulations yield algorithms for one another, with approximation factors preserved through polarity.Treat each incoming constraint as a primal point ±xi and polarize the primal outer ellipsoid to obtain a dual inner ellipsoid.Source: §2.9 · p. 30

3.1 Introduction

• Streaming approximations target big-data settings where storing the full polytope exceeds available memory, replacing it with a succinct proxy for downstream use.A coreset can also make the representation interpretable as selected important datapoints.Source: §3.1 · pp. 31–32

3.1.2 Related work and open questions

• Earlier streaming ellipsoid guarantees addressed centrally symmetric polytopes, leaving analogous results for asymmetric polytopes unresolved.The cited symmetric-case bounds are O(d log(nκOL)) and O(√d log κ) and, respectively.Source: §3.1 · p. 32

Algorithmic results

• With an initialization ball, the streaming ellipsoid algorithm achieves approximation factor O(min(R(Z)/r0, d log(R(Z)/r0))) and uses eO(nd^2) time and O(d^2) storage.Its final inner and outer ellipsoids sandwich Z.Source: Algorithmic results · p. 33
• The initialization-free algorithm maintains inner and outer ellipsoid bounds at every timestep, using eO(nd^2) time and O(d^2) storage, but may have a larger aspect-ratio term.It also provides a guarantee when the input points have integer coordinates in [-N, N] that is independent of aspect ratio and stream length.Source: Algorithmic results · pp. 33–34
• For convex-hull approximation, the streaming coreset has size O(dt log(dN)) for integer-coordinate inputs and changes by either retaining its prior set or adding the current point.The algorithm uses eO(nd^2) time and stores O(d^2) floating point numbers.Source: Algorithmic results · p. 34

Approximability lower bound

• Theorem 3.10 establishes that the approximation factor of Theorem 3.6 is nearly optimal for a wide class of monotone algorithms.Monotonicity constrains how the outer and inner ellipsoids can change as points arrive.Source: Approximability lower bound · p. 34

3.2.1 Monotone algorithms

• Monotonicity requires each outer ellipsoid to contain its predecessor and each inner ellipsoid to lie within the convex hull of the previous inner ellipsoid and the new point.These invariants make the final outer ellipsoid cover the stream while keeping the inner one inside the data hull.Source: §3.2.1 · p. 36, §3.2.2 · p. 37

3.2.2 Streaming ellipsoidal rounding (Theorems 3.6, 3.7, and 3.8)

• Affine normalization and symmetry reduce a regular update to two-dimensional geometry, where the update balances outer coverage against inner containment.The proposed update is parameterized by γ, with 1/α′ = 1/α + 2γ; γ is chosen so the new outer ellipsoid covers the arriving point.Source: §3.2.2 · pp. 37–38
• The update analysis ties growth in approximation factor to ellipsoid volume, while irregular updates handle points that increase the span and add 1 to the reciprocal approximation factor.There are at most d − 1 irregular updates; for integer-coordinate inputs, determinant and lattice-volume bounds remove aspect-ratio dependence.Source: §3.2.2 · pp. 38–40

3.2.3 Coresets for convex hull (Theorem 3.9)

• The coreset criterion selects a point when it triggers an irregular update or makes the ellipsoid volume much larger, preserving the selected-point algorithm's output.A volume argument bounds the coreset size.Source: §3.2.3 · p. 40

3.2.4 Lower bound (Theorem 3.10)

• For the lower bound, an adversary feeds points a constant factor away from the previous ellipsoid; Steiner symmetrization reduces the analysis to two dimensions.The resulting constraints force a reverse evolution condition for monotone updates.Source: §3.2.4 · p. 40

3.3.1 Notation

• Ellipsoids are represented as EA = {x: ||Ax|| ≤ 1}; singular values describe their semiaxes, and lower-dimensional ellipsoids may be restricted to subspaces.The section also fixes notation for Euclidean and Frobenius norms, singular values, and standard basis vectors.Source: §3.3.1 · p. 41

3.3.2 Geometry

• The geometric tools include the fact that five distinct intersections determine a planar ellipse and that Steiner symmetrization preserves volume, containment, and ellipsoid structure.Symmetrizing a body of revolution perpendicular to its axis leaves it unchanged.Source: §3.3.2 · pp. 41–42

3.4.1 Monotone algorithms solve Problem 3.1

• Preserving the ellipsoid invariants suffices for a valid solution: the final outer ellipsoid contains the input points, and the final scaled inner ellipsoid lies in their convex hull.The inner-containment argument allows the initial ellipsoid to be included with the points at intermediate steps; their convex hull equals Z.Source: §3.4.1 · p. 42

3.4.2 Special case

• In the two-dimensional special case, the update maintains both containments: the previous outer ellipse lies in the next outer ellipse, and the next inner ellipse lies in conv(αE ∪ {z}).The update assumes α ≤ 1/2; the inner-containment proof uses the tangent-angle condition and boundary-intersection argument.Source: §3.4.2 · pp. 42, 43, 45, 47

3.4.3 Generalizing to high dimension and arbitrary previous ellipsoids

• For a unit-ball previous ellipsoid, the inner and outer invariants extend to higher dimensions because the relevant sets are bodies of revolution with the two-dimensional cross-sections.The cross-section containments established in the special case imply the corresponding containments for the bodies of revolution.Source: §3.4.2 · pp. 43, 47, §3.4.3 · p. 48
• For an arbitrary previous ellipsoid c° + E_A and next point z°, the update is set up using u = A(z° − c°), an orthogonal alignment W, and a transformed next outer ellipsoid.The passage defines the transformed ellipsoid using E′ = E W D W⊤ A.Source: §3.4.3 · p. 48
• For arbitrary previous ellipsoids, the generalized update preserves the inner and outer ellipsoid invariants; choosing γ so c + a = ∥u∥ makes z coincide with z◦.The proof transforms the inclusions to the corresponding ones for the unit ball and diagonal ellipsoid.Source: §3.4.3 · p. 48

3.4.4 General algorithm

• Algorithm 3 is a monotone update satisfying the inner and outer ellipsoid invariants, and its volume bound supports analysis of the full algorithm's approximation factor.Claim 3.26 bounds ellipsoid volume below using exp(γ*).Source: §3.4.4 · pp. 48–49
• The algorithm starts with a local phase that maintains ball ellipsoids, switching to full updates when its approximation factor reaches 1/(d log d); the phases favor different aspect-ratio regimes.The local phase does better when R/r ≤ d log d, while the full update is near-optimal when R/r ≥ d log d.Source: §3.4.4 · p. 49
• The final approximation is 2R/r when the local phase suffices, O(d(log d + log(R/r))) = O(d log(R/r)) for R/r > d log d, and O(R/r) in the transition range.The transition range has the O(R/r) guarantee whether or not the algorithm enters Phase II.Source: §3.4.4 · p. 52
• The general algorithm uses O(d^2) memory and processes each point in eO(d^2) time.An SVD representation enables the full update to avoid repeated matrix inversion.Source: §3.4.4 · p. 53

Efficient implementation of the full update step

• The full update is implemented with a rank-one SVD update, giving Algorithm 5 a runtime of O(d^2 log d).The scalar search for γ* is one-dimensional and monotone, so binary search can find an approximate value while preserving monotonicity after a slight increase in αt.Source: Efficient implementation of the full… · p. 53

3.4.5 Fully-online asymmetric ellipsoidal rounding algorithm

• The fully online algorithm maintains an ellipsoidal approximation to the convex hull of all points seen, including when an update increases the ellipsoid’s dimension.For an irregular update, the approximation factor increases by exactly 1.Source: §3.4.5 · pp. 55–56

3.4.6 Aspect ratio-independent bounds and proof of Theorem 3.8

• The proof of aspect ratio-independent bounds combines the update evolution condition with a bound on irregular-step increases and uses integer coordinates bounded in magnitude by N.The supplied passages give the proof setup and coordinate assumptions but not the resulting bound.Source: §3.4.6 · p. 58
• The proof of Theorem 3.8 concludes with a final estimate of ≲ d n log(dN).The supplied passages do not identify the quantity being bounded.Source: §3.4.6 · p. 58

3.5 Forming Small Coresets for Convex Bodies (Proof of Theorem 3.9)

• Algorithm 7 processes the stream and updates the coreset set S_t when its update condition is met.Otherwise, the algorithm retains the previous ellipsoid and set.Source: §3.5 · p. 59
• For integer-coordinate inputs in [-N,N], |S_t| is O(d_t log(dN)).The proof bounds the number of selected points by counting steps where the test ellipsoid’s volume increases by at least a factor of e.Source: §3.5 · p. 59
• The selected-point body retains the inner ellipsoid c_t + α_t E_t, while the streamed points lie within c_t + (2e + 1)E_t.The proof derives the outer containment using monotonicity when a point does not trigger an update.Source: §3.5 · p. 60

3.6.1 Lower bound adversary

• The adversary shows that a monotone algorithm cannot achieve an approximation better than eΩ(d log κ) on a sequence with κ(conv(z1, . . . , zn)) ≤ κ.The construction keeps the inner radius r = 1 and uses R = κ.Source: §3.6.1 · p. 60
• The adversary first feeds the algorithm a simplex’s vertices, then points at distance 2 from the previous ellipsoid; an ε-net version makes it non-adaptive, so randomization does not help.The adaptive construction chooses each later point based on the ellipsoid output by the algorithm.Source: §3.6.1 · p. 60
• After the simplex phase ensures A_t ≥ d, every monotone algorithm incurs a constant lower bound on ΔA/ΔP, established by reducing the update to a two-dimensional case.Volume-preserving symmetrizations reduce the general update to the reduced case while preserving monotonicity.Source: §3.6.1 · pp. 61, 63

3.6.2 Analysis of the reduced case

• In the reduced case, a geometric argument establishes the lower bound for ΔA/ΔP; the analysis also shows α′b ≤ α, equivalently A′ ≥ bA.Figure 3.6 depicts the ellipses and points used in the two-dimensional argument.Source: §3.6.2 · pp. 64–65, Figure 3.6 · p. 65
• In Case I, the area increase satisfies ΔA ≥ 4/11 A.This is the case where the new ellipse is close to the previous one.Source: §3.6.2 · p. 66
• For a≤16, A≤2, and b≤100, compactness gives a strictly positive lower bound on ΔA.The proof bounds the parameters in a compact set and shows that the minimum of the continuous function ΔA cannot be zero.Source: §3.6.2 · p. 68
• When a≤16 and b>100, the interval constraint on the next inner ellipse yields a lower bound on the progress ratio.The argument uses the constraint that its horizontal axis lies within [−α, 2].Source: §3.6.2 · p. 68
• For a>16, the two term-minimum cases yield respective lower bounds of 1/35 and 1/65 in the progress argument.The bounds correspond to Term I and Term II, respectively, being the smaller term in (3.41).Source: §3.6.2 · p. 69

3.7 Details of Analysis in Section 3.4.2

• A separate exponential bound is justified by expanding e^x in a Taylor series and checking that the relevant remainder expression is increasing for x ≥ 0.The proof then uses that x^3 ≥ 0 for x ≥ 0.Source: §3.7 · p. 70
• The proof of Claim 3.55 reduces to an analytic inequality and verifies it by splitting into cases based on γ.The displayed argument applies separate bounds when γ is at least 2/3 and when it is below that threshold.Source: §3.7 · p. 70
• Under α ≤ 1/2, the update parameters satisfy relations used to establish inequalities among a, b, and α′.The proof uses exponential bounds, including 1 + x ≤ e^x, to establish these relations.Source: §3.7 · pp. 70–71
• The proofs of Claims 3.19 and 3.20 eliminate auxiliary variables and reduce the required inequalities to polynomial expressions.The resulting argument uses positivity of two quadratics and α ≤ 1 to finish one inequality.Source: §3.7 · pp. 71, 73

4.1 Introduction

• Randomized sampling of groups aims to preserve the block p-norm objective for all x while producing a sparse weighted subset.The paper frames this as an importance-sampling problem and uses its new results to obtain faster algorithms for commonly implemented optimization tasks.Source: §4.1 · pp. 74–75

4.1.1 Our results

• Block Lewis weight distributions exist under either equal group exponents p_i = p or inner exponents p_i = 2, with high-probability preservation guarantees.The stated regimes require the relevant exponent to be at least 1/log d; the paper also reports improved sparsity over [JLLS23] by a factor of ψ_d log(d/ε)^min(p−1,2).Source: §4.1.1 · p. 75
• The polynomial terms in the block-sampling sparsity bounds are optimal, since [LWW21] prove a matching-order lower bound on the number of rows required.Their lower bound is Ω(d^max(1,p/2) + ε^-2 polylog(ε^-1)d).Source: §4.1.1 · p. 75
• Algorithms compute the sampling distributions in the theorem’s exponent regimes using only polylogarithmically many leverage-score overestimates or linear-system solves.For 1 ≤ p ≤ 2, the paper contrasts this with the eO(m + d^5) runtime of [JLLS23] and notes faster runtimes for its algorithms.Source: §4.1.1 · p. 76
• For minimizing sums of Euclidean norms, the sampling construction yields an objective with eO(ε^-2 d) terms that approximates the original within a (1 ± ε) factor.The construction uses eO(1) linear-system solves, and the paper states that its iteration complexity improves on known bounds when m ≫ d.Source: §4.1.1 · p. 77

Concentration

• The concentration argument reduces the preservation guarantee to controlling a subgaussian process, then uses chaining to bound it through entropy numbers of the relevant body.The entropy numbers quantify how finely the body can be covered in the process metric.Source: Concentration · p. 78

Covering numbers

• For covering numbers, generalized dual Sudakov methods incur losses tied to KLS-dependent concentration and subexponential one-dimensional conditionals; for p < 2, direct Euclidean-ball duality also leaves an intractable gauge.The analysis seeks to use the original dual Sudakov inequality with Gaussian concentration instead.Source: Covering numbers · p. 79

The change-of-measure principle and norm interpolation

• Changing the measure used to define norms identifies a linear transformation of a Euclidean ball that approximates B_p, extending the singleton-group approach of and to block norms.This provides the paper’s conceptual route for handling the p < 2 covering-number problem.Source: The change-of-measure principle and… · p. 79

4.1.4 Prior results, related works, and connections

• Theorem 4.2 implies a finite-dimensional subspace embedding result for subspaces of Lp(ℓr) when r is finite.When all p_i equal q, the vectors with finite block p-norm form a subspace of a mixed ℓp(ℓq) space.Source: §4.1.4 · p. 82
• Block norms connect to hypergraph Laplacians, structured solutions of underdetermined systems, and potential faster norm-constrained optimization algorithms.The cited passages identify active block-norm regression as a candidate application and relate the motivation to geometric understanding of Lewis weights.Source: §4.1.4 · p. 82
• For singleton groups, satisfying (4.2) is equivalent to an ℓp subspace embedding, a problem studied using Lewis weights since Bourgain, Lindenstrauss, and Milman.The passage points to [BLM89, Section 7] and for details.Source: §4.1.4 · p. 82
• Theorem 4.2 improves on [JLLS23] sparsity by a factor of ψd log(d/ε)^min(p−1,2), while [JLLS23] has logarithmic-factor improvements over this work when p=2.Here ψd is the KLS constant, currently √log d; [JLLS23] does not address block Lewis-weight sparsification when inner norms p_i≤2 or outer p≤1.Source: §4.1.4 · pp. 82–83

4.2.1 Linear algebra background

• Row leverage scores are defined for matrix A, with scaling invariance and an SVD characterization among the properties reviewed.The section also relates them to statistical whitening.Source: §4.2.1 · pp. 83–84

4.2.2 Convex geometry background

• The convex-geometry toolkit includes covering numbers, entropy numbers, the dual Sudakov inequality, and a Gaussian-width bound.Covering numbers count translates needed to cover a set; entropy numbers give the radius at which the covering number is bounded.Source: §4.2.2 · p. 84

4.2.3 Probability background

• The probability review defines subgaussian variables and collects their characterization, maximum, decentering, and Gaussian Lipschitz facts.These facts are drawn largely from Vershynin [V18].Source: §4.2.3 · pp. 84–85

4.3.1 Notation and general formula

• The notation formalizes block-constant measure matrices, rounding matrices, and group-importance weights; the transformed Euclidean ball is the object used in the covering estimates.The section also notes that the relevant norm is log-convex in 1/r.Source: §4.3.1 · pp. 85–86, We also define · p. 87

We also define

• Theorem 4.22 applies when one of three stated exponent and block-size conditions holds, with sampling probabilities satisfying Hρ_i ≥ α_i^p.The conditions cover singleton blocks with p > 1/log d, uniform p_i=p<2, or p_i=2 with 1/log d ≤ p < ∞.Source: We also define · p. 87
• Under those assumptions, the covering estimate scales as η^-min(2,p) H^2/max(p,2) C(p)p⋆F⋆ log max{em,F⋆}, where p⋆=max{1,max_i min{p_i,log|S_i|}}.C(p) depends only on p.Source: We also define · p. 87

4.3.2 Block Lewis weights

• Block Lewis-weight constructions instantiate the overestimate with F⋆=d in the p_i≥2 case and F⋆=n in the stated cases not covered by that construction.The latter cases are uniform p_i=p<2 or p_i=2 with 1/log d≤p<∞.Source: §4.3.2 · pp. 88–89

4.3.3 Covering numbers for 0 < p < 2

• For 0 < p < 2, Lemma 4.27 bounds log N(Bp, ηcB2) by a term scaling as η^-(2-p) C(p) max_i min(p_i,log|S_i|) F⋆log F⋆.C(p) depends only on p.Source: §4.3.3 · p. 90
• The proof reduces the bound to covering a transformed Euclidean ball, applies dual Sudakov, and controls Gaussian norms by Lipschitzness and a subgaussian estimate.The change of basis maps W^1/2Λ^(1/2−1/p)AR to a matrix with orthonormal columns.Source: §4.3.3 · pp. 90–92
• For 0 < p < 2, the covering-number characterization distinguishes the case where every S_i is a singleton from the case where some S_i has multiple elements.A preliminary estimate degrades when r is larger than about log d, motivating a second estimate for that regime.Source: §4.3.3 · p. 94

Putting everything together

• The 0 < p < 2 entropy estimate makes its dependence on p explicit through C(p) and max_i min{p_i + 1, log |S_i|}.The initial calculation’s constant explodes as p approaches 2; for 1 < p < 2, a variant using θ = 1 addresses this issue.Source: Putting everything together · pp. 96–97

4.3.4 Covering numbers for p ≥2

• For p ≥ 2, Theorem 4.22 gives a covering bound involving H^(2/p), F⋆, log(em), and min{p_i, log |S_i|}.For p < 2 with all p_i ≥ 2, the bound instead involves C(p), H, η, and p⋆ = max_i min{p_i + 1, log |S_i|}.Source: §4.3.4 · p. 99

4.3.5 Volume-based metric entropy

• A volume-based argument establishes a covering-number guarantee as part of the volume-based metric-entropy analysis.The subsection introduces Lemma 4.38 as an easy consequence of that argument.Source: §4.3.5 · p. 100
• Setting F*∼d gives the dependence on d stated in Theorem 4.2.The passage also gives the expression H(F*)^max(1,p/2), though its preceding context is missing.Source: §4.3.5 · p. 101
• For p≥2, Lemma 4.38 permits C=H(F*)^max(1/p,1/2) to ensure B_p⊆C^1/pK.C is defined so that (Cρ_i)^−1/p∥A_Si x∥_pi≤∥Ax∥_Gp for all i∈S and x∈R^d.Source: §4.3.5 · p. 101

4.4 Concentration analysis

• Theorem 4.39 states a general concentration result for partitioned groups when at least one of its specified parameter regimes holds.The listed regimes include equal inner exponents p_i=p with p≥1/log d, or p_i=2 with outer p≥1/log n.Source: §4.4 · p. 102
• The sufficient sample size is set using log(1/δ), ε^-2, (log d)^2, log(d/ε), H, and P(F⋆)^max(1,p/2) to bring the bound below ε.The theorem concerns a sampled multiset and gives a probability guarantee of at least 1−δ.Source: §4.4 · pp. 102, 107
• The proof reduces the analysis to Rademacher fluctuations, establishes subgaussian behavior in a chosen distance, and applies a chaining theorem.The distance is selected so the random process is subgaussian with respect to it.Source: §4.4 · pp. 102–103
• Entropy estimates combine a rapidly converging tail for large indices with a separate bound for indices whose entropy numbers are large.The proof then combines these bounds and uses the chaining theorem to complete the concentration argument.Source: §4.4 · pp. 105–107

4.5.1 Block norm approximations via block Lewis weights (Proof of Theorem 4.2)

• Theorem 4.2 constructs a sampling distribution whose sampled multiset satisfies its stated guarantee with probability at least 1 − δ.The theorem applies under either of its stated exponent conditions; the guarantee’s formula is not legible in the supplied passages.Source: §4.5.1 · p. 108

4.5.2 Efficient computation of block Lewis weight overestimates (Proof of Theorem 4.3)

• Theorem 4.3 gives an algorithm to output a sampling distribution using at most polylog(k, n, m) leverage-score-overestimate computations or linear-system solves.The theorem covers the stated exponent conditions, and sampling from the output distribution satisfies its stated guarantee with probability 1 − δ.Source: §4.5.2 · p. 109
• For equal inner exponents p_i = 2, Algorithm 9 yields a 1.1n-block Lewis weight overestimate for 0 < p < 4, using a contractive update.The update is contractive for 0 < p < 4.Source: Special case – p > 0, p1 = · · · = pm… · p. 110
• For p = 2 and p_i ≥ 2, Algorithm 11 returns an F⋆-block Lewis overestimate with F⋆ = max_i |S_i|^(1/T) · ν; choosing T = max_i log |S_i| and ν ≤ (4/e)d gives F⋆ = 4d.The bound assumes the leverage-score-overestimate routine returns estimates whose sum is at most ν.Source: Special case – p = 2, p1, . . . , pm ≥2 · p. 114
• Theorem 4.3 obtains block Lewis weight overestimates for p1 = · · · = pm = 2 with 0 < p < 4 or p ≥ 2, and for p = 2 with p1, . . . , pm ≥ 2.The three guarantees follow respectively from Algorithms 9, 10, and 11 and their associated lemmas.Source: Special case – p = 2, p1, . . . , pm ≥2 · pp. 116–117

4.5.3 Minimizing sums of Euclidean norms (Proof of Theorem 4.4)

• Theorem 4.4 improves iteration complexity for minimizing sums of Euclidean norms when m ≫ n.With probability at least 1 − δ, the algorithm uses linear-system solves in A⊤DA, where D is block diagonal with blocks of size (|Si| + 1) × (|Si| + 1).Source: §4.5.3 · p. 117
• The minimizing-sums algorithm sparsifies the objective using Theorem 4.3, then applies a primal-dual interior point method.The sparsified objective has em = O(ε^-2 · d(log d)^2 log(d/ε)) terms and requires eO(1) linear-system solves.Source: §4.5.3 · pp. 117–118

5.1 Introduction

• The graph-constrained ℓ2-configuration problem seeks vectors whose distances satisfy given lower and upper bounds on each constrained pair, allowing sparse, partially specified, or nonmetric data.It connects multidimensional scaling, metric embeddings, and Euclidean distance geometry while retaining an SDP formulation.Source: §5.1 · p. 119
• The first-order SDP solver scales with the number m of constrained pairs rather than n^2, returning an ε-approximately feasible configuration on feasible instances or certifying infeasibility with probability at least 1 −δ.The guarantee depends on the input condition parameter α, which is the candidate distortion in the all-pairs minimum-distortion setting and may be unbounded for general sparse or nonmetric instances.Source: §5.1 · p. 120

5.1.1 Related Work

• The minimum-distortion embedding application gives an n^3-time bound up to logarithmic factors and, to the authors’ knowledge, is the first first-order algorithm to improve on ’s dense all-pairs dependence.The adaptive local-norm runtime removes the geometric condition parameter κ, at the cost of worse dependence on ε^-1; it is faster for moderate-accuracy embeddings than interior-point methods.Source: §5.1.1 · p. 121
• The configuration problem can be reduced to a sequence of positive SDPs, a class with fast algorithms, although it is not itself in a class known to have good width-independent algorithms.The SDP constraints are represented by positive semidefinite Laplacian matrices.Source: §5.1.1 · p. 122

5.2.1 Graphs

• Graph Laplacians are formed from weighted edge-vertex incidence matrices, and Laplacian system solvers provide randomized nearly-linear-time solutions to Lx = b.The cited solver runs in eO(m log(1/ε) log(1/δ)) time.Source: §5.2.1 · p. 122, §5.2.2 · p. 122

5.2.2 Numerical Linear Algebra

• Generalized Lanczos is adapted to find finite generalized eigenvalues for a symmetric matrix paired with a Laplacian, returning a normalized vector with a near-nonnegative quadratic form when the leading eigenvalue is nonnegative.The simulation stores vectors in a different coordinate frame rather than materializing the transformed matrix or intermediate vectors.Source: §5.2.2 · pp. 123–124
• Each H Laplacian system solve takes eO(n) time, and the final Lanczos step takes O(n), yielding the stated time-complexity bounds.The preceding work consists of a constant number of O(n) vector operations, M matrix-vector products, and Laplacian solves for H.Source: §5.2.2 · p. 124

5.2.3 Algorithms for Ellipsoidal Rounding

• The graph-specialized ellipsoid algorithm returns a Laplacian on the same edge set with high probability and runs in eO(m) time.The ellipsoid construction is motivated by approximating the Lipschitz body associated with a weighted graph.Source: §5.2.3 · pp. 124–125

5.2.4 Multiplicative Weights

• A local-norm regret bound yields an iteration bound for small average regret when the per-round local quadratic term is uniformly bounded.The section derives this form for exponentiated gradient from the local-norm regret analysis.Source: §5.2.4 · pp. 125–126

5.3 Algorithm for Graph-Constrained ℓ2-Configuration

• The solver runs as a game between a regret-minimizing dual player and an oracle-based primal player, returning the concatenation of the oracle’s x values.The dual player uses (y, z), while the primal player uses x; the game proceeds for T rounds.Source: §5.3 · p. 127

5.3.1 Existence of oracle solution

• A feasible multidimensional solution implies a one-dimensional solution with average-case guarantees; Johnson-Lindenstrauss projection reduces the width dependence to logarithmic in n.The existence argument applies the Johnson-Lindenstrauss lemma to the feasible vectors.Source: §5.3.1 · p. 127

5.3.2 Local norm-bounded oracle

• The local-norm oracle is an (O(nρ), O(nρ²))-bounded, ε-approximate, δ-sure oracle.When the minimum loss over EH is at most ε/2, the oracle returns a witness with probability at least 1 − δ.Source: §5.3.2 · pp. 128, 130

5.3.3 Full algorithm for ℓ2-configuration

• With probability at least 1 − δ, the ℓ2-configuration algorithm returns a 2ε-approximately feasible solution in eO(nmα^5ε^-7.5) time.For feasible instances, it returns vectors; the runtime uses separate processing of disconnected constraint-graph components when m ≪ n.Source: §5.3.3 · pp. 131–133

5.4.1 Approximating Minimum Distortion Embedding into ℓ2

• Binary search over ℓ2-configuration feasibility probes yields a (1 + O(ε))-approximate minimum-distortion embedding into ℓ2.A certified probe either supplies an embedding with distortion at most (1 + 2ε)D or certifies that the candidate D is infeasible.Source: §5.4.1 · p. 133

5.4.2 Generalized sparsest-cut rounding

• At constant accuracy, the Euclidean rounding stage runs in eO(m_round n) time, but this is not an end-to-end sparsest-cut algorithm because the SDP must still be solved.The configuration constraints encode capacity and demand pairs; the cited rounding distortions are O(√log n log log n) for ALN and O(√log n) for the current optimal Goemans–Linial result [CNR24].Source: §5.4.2 · pp. 133–134

5.5.1 Improving dependence on accuracy

• The ℓ2-configuration and minimum-distortion algorithms have ε^-7.5 accuracy dependence, and accelerated optimization integrated with the oracle could improve it by at least an ε factor.The local-norm multiplicative-weights regret bound contributes an ε^-2 dependence.Source: §5.5.1 · p. 134

5.5.2 Relation to Covering SDPs

• Dualizing only the upper-bound constraint reduces ℓ2-configuration to a sequence of covering SDPs, motivating width-independent solvers for covering SDPs.Packing and covering SDPs are distinct families rather than duals of one another, unlike packing and covering LPs.Source: §5.5.2 · p. 134