Convex optimization on moment polytopes: Hadamard mirror descent and efficient algorithms for quantum functionals and other tensor parameters

Mahmut Levent Doğan; Keiya Sakabe; Michael Walter

Source-linked AI summary

Convex optimization on moment polytopes: Hadamard mirror descent and efficient algorithms for quantum functionals and other tensor parameters

Mahmut Levent Doğan, Keiya Sakabe, Michael Walter

arXiv:2609.06633v1Sep 6, 2026cs.CCmath-phmath.MPmath.OCquant-ph

TL;DR

Efficient convex optimization over implicitly described moment polytopes has been elusive, despite their role in quantum information and algebraic complexity. The paper extends mirror descent to Hadamard manifolds and applies the resulting framework to moment polytopes, yielding algorithms for important tensor parameters. Its scope is constrained by an invariance assumption and by unresolved precision analysis for continuous operations.

Problem
Efficient optimization over implicit polytopes is difficult, and effective methods for computing tensor parameters such as quantum functionals have been elusive.
Source: §1 · p. 3
Method
Hadamard mirror descent extends mirror descent to optimize suitable convex functions over gradient sets of geodesically convex functions, including moment polytopes.
Source: §1 · p. 5, §1.2 · p. 8
Results
The framework gives O(k^-1) convergence under natural hypotheses and yields the first efficient algorithm for quantum functionals, with algorithms for other tensor parameters.
Source: §1 · p. 5, §1.2 · p. 8
Takeaways & Limitations
The algorithms cover the symmetric quantum functional, G-stable rank, and non-commutative rank, whose new direct algorithm is described as conceptually simpler than prior work.
Source: §1 · p. 5
The moment-polytope result does not directly give a polynomial-time Turing-model algorithm because the iteration uses continuous operations requiring precision analysis, and it assumes K-invariance of the objective.
Source: §1.3 · p. 11

Abstract

from arXiv · show

Convex optimization on polytopes arises in many areas of science. When the polytope is given implicitly or has exponentially many vertices and facets, standard methods may not apply or be ineffective. This is the case for moment polytopes, such as the entanglement polytopes, which play a foundational role in quantum information and algebraic complexity. They give rise to important entanglement measures and tensor parameters such as the quantum functionals, yet general effective methods for computing these quantities have been elusive. In this paper we address this challenge. We develop a first-order framework called Hadamard mirror descent to optimize suitable convex functions over moment polytopes and, more generally, the gradient sets of geodesically convex functions. It operates locally and does not rely on any explicit description of the polytope. Our framework extends mirror descent, an effective and widely used framework for convex optimization, from the Euclidean setting to Hadamard manifolds, and is motivated by a recent work by Hirai, which we interpret as a Hadamard version of mirror flow. Applying the framework to entanglement polytopes yields the first efficient first-order algorithms to compute the quantum functionals, the symmetric quantum functional, and the G-stable ranks, as well as a new direct algorithm for the non-commutative rank.

1 Introduction

Convex optimization over implicitly described polytopes is difficult because standard methods may depend on explicit vertices or facets. The paper develops a gradient-based route to this problem and applies it to moment polytopes and tensor parameters.

1 Introduction

Representing a polytope as the closure of a convex function's gradient set can avoid enumerating its vertices or facets.The introduction illustrates this with a log-sum-exp function and notes that such a function can succinctly encode a polytope with exponentially many vertices.Source: §1 · p. 3
Mirror descent in dual variables uses step size η = 1/L and minimizes ϕ at rate O(k^-1) under the cited standard results.The dual-variable formulation uses the Bregman-divergence ratio defining relative smoothness.Source: §1 · p. 4
Moment polytopes arise in settings including entanglement, Brascamp–Lieb inequalities, quantum marginals, invariant theory, and matrix eigenvalue relations.Entanglement polytopes characterize local quantum states attainable from multipartite states within an entanglement class.Source: §1 · pp. 4–5
Implicit polytopes with many vertices or facets make standard convex optimization methods inapplicable or inefficient, leaving efficient optimization over moment polytopes a major open problem.Prior general membership algorithms are inefficient, while earlier algorithmic progress addresses important special cases.Source: §1 · p. 5
The paper introduces Hadamard mirror descent for convex objectives over gradient sets of geodesically convex functions, with O(k^-1) convergence under natural hypotheses.The framework applies to moment polytopes without requiring an explicit description of the polytope.Source: §1 · p. 5
The framework yields the first efficient algorithm for quantum functionals and algorithms for the symmetric quantum functional, G-stable rank, and non-commutative rank.The non-commutative rank algorithm is described as conceptually simpler than prior work.Source: §1 · p. 5

1.1 Motivation: Moment polytopes, non-commutative gradients, and mirror descent

The tensor example shows how a moment polytope can arise from a geodesically convex function on a curved space. Parallel transport and unitarily invariant data make its gradient information usable, while a mirror-flow interpretation motivates the paper's optimization framework.

1.1 Motivation: Moment polytopes, non-commutative gradients, and mirror descent

For a tensor T, the Kempf–Ness function fT on positive-definite matrices is geodesically convex under the affine-invariant Riemannian metric.It is a non-commutative generalization of log-sum-exp.Source: §1.1 · p. 6
Parallel transport to a common tangent space depends on the chosen curve, so the construction uses unitarily invariant data to address the resulting ambiguity.In this setting, different transports can conjugate the matrix tuple by unitary matrices.Source: §1.1 · p. 6
The entanglement polytope is obtained from the closure of sorted eigenvalue spectra of gradients parallel-transported to the identity.The resulting polytope lies in a product of probability simplices.Source: §1.1 · p. 7
More generally, moment polytopes arise as closures of gradient sets of Kempf–Ness functions on nonpositively curved spaces associated with suitable group actions.The cited setting uses rational representations of self-adjoint matrix groups [BFG+19].Source: §1.1 · p. 7
Optimizing a permutation-symmetric convex objective over an entanglement polytope can be reformulated as unconstrained optimization over gradients of the Kempf–Ness function.The objective is lifted to a unitarily invariant convex function of matrix tuples.Source: §1.1 · p. 7
Hirai's Q-gradient flow decreases Q(df(x_t)) under geodesic convexity, and the paper interprets this flow as a Hadamard-manifold mirror flow.This interpretation motivates extending mirror descent to obtain quantitative convergence guarantees for continuous- and discrete-time methods.Source: §1.1 · p. 8

1.2 Framework and general results: Hadamard mirror descent

Hadamard mirror descent extends mirror descent’s dual formulation to Hadamard manifolds, minimizing objectives of the form Q(df(x)) for geodesically convex f and holonomy-invariant convex Q. Its convergence is governed by a natural step-size condition, with dual-smoothness providing the manifold analogue of smoothness in relative-smoothness criteria.

Framework

The framework considers geodesically convex f and a holonomy-invariant convex objective Q on the cotangent bundle.The objective’s restrictions to cotangent spaces are lower semicontinuous and Euclidean convex, and are related by parallel transport.Source: §1.2 · p. 8

Convergence

The continuous-time Q-gradient flow has an O(t^-1) convergence result under natural hypotheses on arbitrary Hadamard manifolds.The paper presents this as a quantitative generalization of Hirai’s qualitative convergence result.Source: §1.2 · p. 8

Step size

In the manifold setting, relative smoothness uses dual-smoothness in place of smoothness of f, and η = 1/L applies when the relative-smoothness parameter is L.Dual-smoothness is not generally equivalent to the corresponding notion along geodesics; the quantum-functional pair satisfies the step-size condition for all η in (0, 1] despite not being 1-relatively smooth.Source: §1.2 · p. 9

Framework

Hadamard mirror descent generalizes mirror descent’s dual expression to minimize Q(df(x)) on a Hadamard manifold.The framework is distinct from approaches that minimize a geodesically convex objective directly on a Riemannian manifold.Source: §1.2 · pp. 8, 10

1.3 Convex optimization on moment polytopes

The paper represents moment polytopes through a group action and the moment map, then optimizes suitable K-invariant convex objectives using a vector update equivalent to Hadamard mirror descent. Under a natural step-size condition, the method converges at an inverse-iteration rate; the section also gives a general O(k^-1) result for norm minimization and states scope and implementation caveats.

Moment-polytope construction

The moment polytope is the closure of the Weyl-chamber image of the moment-map image of the group orbit of v.The group intersection with the positive-definite matrices forms a Hadamard symmetric space, linking the construction to optimization on that space.Source: §1.3 · p. 10

Vector update

The Hadamard mirror descent method can be represented as a vector update that preserves unitary symmetries of the input.If u·v = v for u in K, then u·v_k = v_k at every iteration.Source: §1.3 · p. 11

Convergence parameters

Kempf–Ness functions are D(π)^2/2-dual-smooth, and their associated function gap is polynomially bounded in input bit-length for the stated classes of actions and inputs.The bit-length bound applies to vectors with Gaussian integer or rational entries for broad classes of general linear group actions.Source: §1.3 · p. 11

Moment-polytope optimization

Hadamard mirror descent minimizes suitable K-invariant convex objectives over the moment polytope at a rate proportional to the inverse iteration count.The stated step-size condition includes η ≤ 2/(D(π)^2L) when Φ is L-smooth.Source: §1.3 · pp. 10–11

Caveats

The moment-polytope result does not establish Turing-model polynomial time and does not cover arbitrary convex objectives, because it assumes K-invariance.The iteration uses continuous operations such as matrix exponentials, requiring a precision analysis not carried out here.Source: §1.3 · p. 11

Norm minimization

The section applies the moment-polytope theorem to Frobenius-norm minimization, addressing an open problem on quantitative convergence.The cited result is presented as improving prior work that covered only special cases or lacked quantitative guarantees.Source: §1.3 · pp. 11–12
For norm minimization, Corollary 1.3 gives O(k^-1) convergence for η = 2/D(π)^2, regardless of whether the optimization minimum is zero.The cited prior result established convergence to the infimum even when it is positive, but gave no quantitative rate.Source: §1.3 · p. 12

1.4 Convex optimization on entanglement polytopes of tensors

This section applies Hadamard mirror descent to convex optimization on entanglement polytopes, establishing guarantees and algorithms for quantum functionals and tensor ranks. It also contrasts the paper’s direct computation of non-commutative rank with an earlier operator-scaling approach.

1.4 Convex optimization on entanglement polytopes of tensors

Hadamard mirror descent minimizes suitable convex objectives over a tensor’s entanglement polytope under a natural step-size condition, including η ≤ 1/(dL) for L-smooth objectives.The guarantee assumes a lower semicontinuous convex objective, symmetric in each argument, differentiable on its domain’s interior, with spectra in the domain’s interior.Source: §1.4 · p. 13

1.4.1 Quantum functionals

Entropic tensor scaling gives a finite-step algorithm with polynomial iteration complexity for approximating logarithmic quantum functionals of arbitrary tensors.For concise tensors, the negative-entropy objective satisfies the required step-size condition at η = 1, established through a quantum entropy inequality.Source: §1.4.1 · p. 14
With uniform θ, entropic tensor scaling preserves permutation symmetries and gives meaningful guarantees even for unstable tensors; it also directly proves multiplicativity and sub-additivity of Fθ.The direct proof follows from the scaling algorithm and entropy additivity, bypassing representation-theoretic reasoning.Source: §1.4.1 · p. 15

1.4.2 Symmetric quantum functional

Symmetric entropic tensor scaling approximates the symmetric quantum functional with polynomial iteration complexity, even for nonsymmetric tensors, when the symmetric moment map is nonsingular.Unlike ordinary entropic scaling, its update uses the average of the quantum marginals; for symmetric tensors it coincides with uniform-weight entropic tensor scaling.Source: §1.4.2 · p. 16

1.4.3 G-stable rank

O_T(d log(n_sum)/(α_min ε)^2) Hadamard mirror descent iterations approximate the inverse G-stable rank to additive error ε.The method smooths the nonsmooth convex objective; n_sum = ∑ℓ nℓ and α_min = minℓ αℓ.Source: §1.4.3 · p. 17

1.4.4 Non-commutative rank

For Gaussian-integer matrix tuples satisfying the kernel condition, Hadamard mirror descent computes non-commutative rank in poly(n, ⟨A⟩) iterations, followed by rounding.The method smooths the convex objective and approximates the rank to arbitrary additive error before rounding to its exact integer value.Source: §1.4.4 · p. 18
The algorithm is a conceptual descendant of the operator-scaling approach in, but directly computes ncrk(A) rather than reducing to the decision problem ncrk(A) ≥ r.Source: §1.4.4 · p. 18

1.5 Organization of the paper

The paper proceeds from geometric preliminaries and the Hadamard mirror descent framework to applications on moment polytopes and tensor parameters, then collects supporting material in appendices.

Sections 2–5

Sections 2–5 develop the geometric preliminaries, define and analyze Hadamard mirror flow and descent, and establish convergence conditions.The discussion also relates the framework to relative smoothness and Euclidean mirror descent.Source: §1.5 · p. 18

Section 6

Section 6 applies the framework to moment polytopes, including those of tensors and homogeneous polynomial actions, and gives a capacity-based bound on the convergence constant.Source: §1.5 · p. 18

Section 7 and appendices

Section 7 explores applications including quantum functionals, G-stable ranks, non-commutative ranks, and norm minimization; the appendices cover matrix scaling and omitted proofs.Source: §1.5 · pp. 18–19

2 Preliminaries

The preliminaries establish notation and the geometry of Hadamard manifolds, then specialize that geometry to positive-definite matrices and symmetric spaces arising from self-adjoint groups.

2 Preliminaries

The preliminaries fix notation for vector spaces, operators, norms, and groups used throughout the paper.Source: §2 · p. 19

2.1 Hadamard manifolds

A Hadamard manifold is complete, simply connected, and nonpositively curved, so any two points have a unique connecting geodesic.The section also introduces geodesic convexity, parallel transport, holonomy, and boundary-at-infinity notions.Source: §2.1 · pp. 19–20

2.2 Positive-definite matrices

Positive-definite matrices form a Hadamard manifold under the affine-invariant metric, with explicit exponential, logarithm, distance, and parallel-transport formulas.Source: §2.2 · p. 20

2.3 Hadamard symmetric spaces and self-adjoint subgroups

Intersecting positive-definite matrices with a self-adjoint subgroup yields a Hadamard symmetric space; its adjoint orbits correspond to finite Weyl-group orbits, with a unique representative in a Weyl chamber.For products of general linear groups, the chamber representation sorts each Hermitian matrix’s eigenvalues in nonincreasing order.Source: §2.3 · pp. 20–21

3 Holonomy-invariant objectives and generalized gradients

This section develops holonomy-invariant convex objectives on Hadamard manifolds, characterizing them on symmetric spaces and introducing their associated Q-gradient for geodesically convex functions. It also interprets the differential df(x) as an element of T∗.

3.1 Holonomy-invariant convex objectives

A holonomy-invariant convex objective is lower-semicontinuous and convex on each cotangent space, invariant under parallel transport, and determined by a holonomy-invariant restriction to any one cotangent space.For a Busemann function, evaluating Q on its differential is independent of the point on the manifold.Source: §3.1 · pp. 22–23

3.2 Objectives on Hadamard symmetric spaces

A convex Weyl-group-invariant function on the Cartan subspace extends to a holonomy-invariant convex objective, with smoothness preserved and its matrix gradient given by conjugating the Cartan gradient.Convexity on a Weyl chamber alone is insufficient: for example, the extension of x ↦ −x1 is −λmax(X), which is nonconvex for n ≥ 2.Source: §3.2 · pp. 23–24
On positive-definite matrices, the examples provide smooth approximations to ℓ∞ and operator norms, and to ℓ1 and trace-norm distances from uniform and normalized-identity targets, respectively.These objectives are building blocks for the quantum functionals, G-stable rank, and non-commutative rank.Source: §3.2 · p. 25

3.3 Generalized gradient

For a geodesically convex function f, the Q-gradient is defined from the differential of Q at df; its negative is a natural descent direction, and Q(df) is nonincreasing under the corresponding flow.The definition assumes f is continuously differentiable and df lies in the interior of the domain of Q at every point.Source: §3 · p. 22, §3.3 · p. 26
If f and the fiber objectives Qx are twice continuously differentiable, the Q-gradient is continuously differentiable and locally Lipschitz.The conditions are that f be twice continuously differentiable on M and Qx twice continuously differentiable on the interior of its domain.Source: §3.3 · p. 26
The differential df(x) is interpreted as an element of T∗.Source: §3.3 · p. 26

4 Hadamard mirror flow

The section interprets the Q-gradient descent flow as a Hadamard mirror flow and proves that its objective value is nonincreasing. Under an all-time existence assumption, it also establishes an O(t^-1) convergence result.

4.2 Convergence analysis

O(t^-1) convergence is established when the Hadamard mirror flow is defined for all t ≥ 0.The stated bound allows both sides to be −∞.Source: §4 · p. 27, §4.2 · p. 28

4.1 Definition and Euclidean interpretation

The Q-gradient descent flow is interpreted as a Hadamard mirror flow, generalizing the Euclidean mirror-flow interpretation.It is defined as the unique maximal forward solution from an initial point.Source: §4.1 · p. 27
Q(df(x_t)) is nonincreasing along the Hadamard mirror flow.When the flow exists for all times and f_ξ is bounded below, its limit inferior is at most Q(ξ); for a minimizer ξ, it reaches the minimum in the limit inferior.Source: §4.1 · p. 27

4.2 Convergence analysis

The Lyapunov function f_ξ decreases at a rate bounded by the gap between Q(df(x_t)) and Q(ξ).The convergence analysis combines this decrease with the monotonicity of Q(df(x_t)).Source: §4.1 · p. 27, §4.2 · p. 28

5 Hadamard mirror descent

Hadamard mirror descent is the discrete-time counterpart of the Hadamard mirror flow and recovers mirror descent in Euclidean dual coordinates. A step-size condition gives O(1/k) convergence, and relative smoothness provides a sufficient condition for that guarantee.

5.2 Convergence analysis

Under the step-size condition, Hadamard mirror descent has an O(1/k) convergence guarantee.The objective Q(df(x_k)) is also nonincreasing under this condition.Source: §5 · p. 29, §5.2 · pp. 30–31

5.1 Definition and Euclidean interpretation

Hadamard mirror descent is the discrete-time Q-gradient method and recovers standard mirror descent in Euclidean dual coordinates.Its convergence analysis extends to Hadamard manifolds the dual-coordinate formulation of mirror descent.Source: §5.1 · pp. 29–30

5.3 Relative smoothness and dual smoothness

L-relative smoothness ensures the step-size condition for any η ≤ 1/L.This allows the convergence theorem to apply.Source: §5.3 · p. 32
In Hadamard settings, smoothness and dual-smoothness are distinct: smoothness alone need not imply dual-smoothness with the same parameter.In Euclidean space, the two notions coincide.Source: §5.3 · p. 33
If f is L_f-dual-smooth and Q is L_Q-smooth, the pair is L_f L_Q-relatively smooth.Consequently, the convergence theorem applies for η ≤ 1/(L_f L_Q).Source: §5.3 · p. 34

6 Convex optimization on moment polytopes

This section develops and analyzes Hadamard mirror descent and flow for optimization over moment and entanglement polytopes, using Kempf–Ness functions without requiring an explicit polytope description. It establishes smoothness, convergence, and iteration guarantees for tensor and tensor-power actions, reduces symmetric optimization to an ordinary entanglement-polytope problem, and extends polynomial capacity bounds to homogeneous polynomial representations.

6 Convex optimization on moment polytopes

Across the settings considered, Hadamard mirror descent has O(k^-1) convergence, the mirror flow has analogous rates, and convergence is polynomial in the input bit-length.The section also states general O(k^-1) convergence results for convex optimization on moment polytopes.Source: §6 · p. 34

6.1 Moment polytopes and Kempf–Ness functions

For any nonzero vector, its moment polytope is a rational convex polytope, and its Kempf–Ness function is geodesically convex with differential related to the moment map.The moment map image itself need not be convex, but intersecting it with the Weyl chamber yields a polytope.Source: §6.1 · p. 35

6.2 Convex optimization on moment polytopes

Hadamard mirror descent updates can be represented by group elements or vectors in the representation space, with vector iterates tracking the corresponding projective orbit points and objective values.The equivalent update forms can behave differently numerically: matrix iterates may become ill-conditioned, while vector updates can drift outside the original orbit and thus target a different moment polytope.Source: §6.2 · pp. 37–38
A point p belongs to the moment polytope exactly when some g in G, equivalently some u in K, gives log cap_p(g · v) > −∞.This membership characterization is the shifting trick used in the convergence analysis.Source: §6.2 · p. 40
Moment-polytope optimization achieves O(t^-1) convergence for the flow and O(k^-1) for descent, with constants depending on the minimizer’s K-invariant capacity.The bounds also depend on the initial vector norm and, for discrete time, the inverse step size.Source: §6.2 · p. 41
Under Theorem 6.14’s hypotheses, accumulation points of the discrete iterates and continuous flow are minimizers in the orbit closure.Source: §6.2 · p. 41
Unitary symmetries compatible with the representation and objective are preserved by both dynamics, including symmetries induced by K.Source: §6.2 · p. 42

6.3 Smoothness and dual-smoothness of Kempf–Ness functions

Every Kempf–Ness function is D(π)^2/4-smooth, and this smoothness constant is optimal.Source: §6.3 · p. 44
Kempf–Ness functions are D(π)^2/2-dual-smooth, yielding step sizes η ≤ 2/(D(π)^2L) for smooth moment-polytope descent.The stated dual-smoothness parameter is not generally optimal.Source: §6.3 · pp. 45–46
For the standard GL(n) action on C^n, Kempf–Ness functions can be 1/2-smooth yet fail to be (1−δ)-dual-smooth for every δ>0, with optimal dual-smoothness approaching 1.This demonstrates that the two smoothness parameters can differ and that the stated dual-smoothness bound is tight.Source: §6.3 · pp. 46–47
For polynomial representations of GL(n1) × ··· × GL(nd) that are multi-homogeneous of degrees m1,...,md, the paper bounds weight diameter and norm, improving degree-based smoothness bounds in [BFG+19].Source: §6.3 · p. 47

6.4 Tensor action and entanglement polytopes

Tensor-tuple updates optimize objectives over entanglement polytopes and converge under the stated step-size condition; for L-smooth objectives, η=1/(dL) is allowed.The tensor action's moment map gives the normalized one-body quantum marginals.Source: §6.4 · pp. 48–49
For Gaussian-integer tensor tuples, a polynomial-in-bit-length lower bound on K-invariant logarithmic capacity holds uniformly over the entanglement polytope, yielding a polynomial iteration bound.The theorem's stated convergence bound uses the tensor tuple's bit-length.Source: §6.4 · p. 50

6.5 Tensor power action and symmetric entanglement polytopes

The tensor power action can be interpreted as a special case of the tensor action by using cyclic index shifts of each tensor in the tuple.Source: §6.5 · p. 52
The minimum over the symmetric entanglement polytope equals the minimum over the shift-stack tensor tuple’s entanglement polytope, giving a direct reduction between the two optimization problems.The equality holds even when the objective has no step size satisfying the step-size condition.Source: §6.5 · p. 53
The symmetric optimization sequence converges to its minimum if and only if the corresponding shift-stack sequence converges to the ordinary-polytope minimum.Source: §6.5 · p. 53
The convergence corollary applies without requiring symmetric tensors; for an L-smooth objective, step size η = 1/(d^2L) is permitted.For Gaussian integer entries, the paper also obtains a polynomial bound for the symmetric optimization problem.Source: §6.5 · p. 55

6.6 Polynomial actions of general linear groups

For homogeneous polynomial representations, the paper proves a polynomial lower bound on invariant logarithmic capacity for Gaussian-integer vectors, parameterized by degree, coefficient size, and distortion factor.With a list-of-partitions specification and the Gelfand–Tsetlin basis, the bound is polynomial in the representation and vector bit-lengths and the degree, yielding a polynomial iteration bound.Source: §6.6 · pp. 55–56

7 Applications

This section applies Hadamard mirror descent to optimization and computation problems involving moment polytopes, including norm minimization, quantum functionals, G-stable rank, and non-commutative rank. It presents entropic tensor scaling and smoothing-based algorithms, with convergence guarantees or approximation-error control for the applications described.

7.1 Norm minimization over moment polytopes

Norm minimization over a moment polytope achieves O(k^-1) convergence to its minimum-norm point for arbitrary optimum values, with step size η = 2/D(π)^2.For Gaussian-integer inputs in specified tensor, tensor-power, or homogeneous polynomial actions, the numerator in the bound can be replaced by a polynomial in the input bit-length.Source: §7.1 · pp. 57–58

7.2 Quantum functionals and entropic tensor scaling

An entropy inequality establishes the step-size condition for every η ∈ (0, 1], enabling η = 1 entropic tensor scaling despite the entropy objective’s lack of smoothness.The paper notes that numerical experiments suggest 1-relative smoothness does not hold, motivating a direct proof of the step-size condition.Source: §7.2 · pp. 60–61
Entropic tensor scaling with η = 1 converges at O(k^-1) toward the logarithmic quantum functional for concise tensor tuples.For Gaussian-integer entries, the bound is polynomial in d, nmax, and input length, divided by k.Source: §7.2 · p. 62
For Gaussian-integer tensors, entropic tensor scaling approximates the logarithmic quantum functional to additive error ε in O(1/ε) iterations, polynomial in input size.Source: §7.2 · p. 63
The algorithmic result also yields a new succinct proof that quantum functionals are universal spectral points.Source: §7.2 · p. 63
Entropic tensor scaling gives an algorithmic proof that Fθ is a universal spectral point, deriving multiplicativity from product scaling and sub-additivity from entropy recursion and Jensen’s inequality.Monotonicity, normalization, super-multiplicativity, and super-additivity follow from the entanglement-polytope definition and elementary properties.Source: §7.2 · pp. 63–64

7.3 Symmetric quantum functional

Symmetric entropic tensor scaling computes the symmetric quantum functional through ordinary quantum-functional scaling with uniform θ, converging at O(k^-1) when µS(T) is nonsingular.For Gaussian-integer tensor tuples, the objective gap is also bounded by poly(d, n, ⟨T⟩)/k.Source: §7.3 · p. 65

7.4 G-stable rank via smoothing

Smoothing the nonsmooth G-stable-rank objective makes its inverse approximately computable with arbitrarily small additive error via Hadamard mirror descent.For Gaussian-integer tensor tuples, poly(nsum, ⟨T⟩)/(αmin ε)^2 iterations suffice for additive error ε.Source: §7.4 · pp. 66–67

7.5 Non-commutative rank by 1-norm minimization

For non-commutative rank, the paper derives a new Hadamard-mirror-descent algorithm by minimizing an ℓ1 objective over the entanglement polytope using Hirai’s formula under a kernel condition.The objective is nonsmooth, so the section begins constructing a smooth approximation of its absolute-value terms.Source: §7.5 · pp. 68–69
The smoothed objective ϕδ approximates the original minimization within additive error O(nδ), enabling the original problem to be solved to that accuracy.The paper establishes that ϕδ is convex, 1/δ-smooth, and permutation-symmetric, then applies Hadamard mirror descent with step size δ/2.Source: §7.5 · p. 69
For Gaussian-integer inputs, poly(n, ⟨A⟩) iterations compute the non-commutative rank exactly; choosing δ = 1/(2n^2) also permits exact recovery by rounding.The method’s polynomial iteration bound does not directly imply polynomial time in the Turing model, because it uses exact real arithmetic.Source: §7.5 · pp. 69–70
The algorithm targets non-commutative rank directly with a single simple update, unlike prior methods that use operator-scaling decisions or more complex steps.The paper notes that exact real arithmetic prevents its polynomial iteration bound from directly yielding a polynomial-time Turing-model algorithm.Source: §7.5 · p. 70
The G-stable rank method also computes non-commutative rank, but its iteration bound has an additional factor n log n compared with the direct method.The identification uses α = (ℓ, 1, 1) for ℓ ≥ n and then takes the limit ℓ → ∞.Source: §7.5 · pp. 70–71

A Matrix scaling via marginal entropy maximization

The appendix formulates matrix scaling as maximizing the sum of marginal entropies over scalings of a nonnegative matrix. It identifies entropic matrix scaling as a mirror-descent iteration and establishes relative smoothness with the sharp parameter L = 1.

A Matrix scaling via marginal entropy maximization

The problem is to transform a nonnegative matrix into an approximately doubly-stochastic matrix by left- and right-scaling with positive diagonal matrices.Here, “doubly-stochastic” also covers rectangular matrices whose row and column sums are uniform distributions.Source: A Matrix scaling via marginal entropy… · p. 71
The entropic matrix scaling algorithm maximizes the sum of marginal entropies at a rate inversely proportional to the iteration count, solving the scaling problem whenever possible.It also applies to non-scalable matrices, for which the scaling target cannot be achieved to arbitrarily small error.Source: A Matrix scaling via marginal entropy… · pp. 71–72
Maximizing the marginal entropies is formalized as minimizing ϕ composed with ∇fA over pairs of probability distributions, with ∇fA giving the scaled matrix’s row and column sums.The marginal entropies are Shannon entropies; the objective captures their maximization over all scalings of A.Source: A Matrix scaling via marginal entropy… · p. 72
Hadamard mirror descent for this objective coincides with ordinary mirror descent for h = fA*, and step size η = 1 yields the entropic matrix scaling iteration.Relative smoothness holds with L = 1, and this parameter cannot be improved for all matrices when n, m ≥ 2.Source: A Matrix scaling via marginal entropy… · pp. 72–73
The convergence theorem assumes every row and column of A has a positive entry and uses κA, a condition number defined from the positive entries of A.The proof bounds a numerator using log κA; the supplied theorem passage does not include its full rate expression.Source: A Matrix scaling via marginal entropy… · p. 73

B Technical proofs

The technical proofs establish geometric facts used in the paper’s results, including a criterion for finite log capacity and the well-definedness of a function on the visual boundary. They use asymptotic geodesics and compactness of group orbits.

B Technical proofs

The asymptotic direction Y of the geodesic g†e^(tX)g lies in the K-orbit of X, which is compact and therefore closed.The proof obtains the orbit relation through parallel transport and a limiting sequence of conjugations by elements of K.Source: B Technical proofs · p. 74
Finite log capacity at X for some G-transform of v is equivalent to finite log capacity for some K-transform of v.The proof reduces the forward direction by replacing a geodesic ray associated with g ∈ G by an asymptotic ray associated with u ∈ K.Source: B Technical proofs · pp. 74–75
The value Q(ξ), defined from the differential of a Busemann function, is independent of the point used to represent the visual-boundary point ξ.Asymptotic geodesics identify the transported tangent data, yielding equality of Q at different base points.Source: B Technical proofs · pp. 73, 75