Restricted Dynamic Geometric Complexity:
Certificates for Structured Preconditioning
July 08, 2026
Optimization geometrodynamics views optimizer state as evolving geometry. Its full positive-definite quadratic benchmark gives the least affine-invariant deformation needed to reduce condition number when arbitrary metrics are allowed. This paper records that benchmark in the present notation and develops restricted dynamic geometric complexity: an intrinsic certificate distance for reaching a target condition-number class when the metric is restricted to a specified family. The main proved results are monotonicity and submanifold-distance principles, diagonal and block reachability as linear matrix inequality feasibility problems, an exact two-dimensional diagonal complexity formula, and affine-invariant Kronecker projection theorems with normal equations, computable mismatch certificates, Armijo solver convergence, auxiliary self-conditioned \(K\)-target bounds, and Hessian-relative candidate certificates through an exact Kronecker Loewner-sandwich reachability condition, including a Kronecker expression threshold and a fixed-basis exact subproblem. Low-rank spectral models, curvature-proxy inflation, stochastic restricted complexity, discrete geometric length, and expression–estimation–flow–discretization accounting are presented as diagnostic interfaces rather than full optimizer characterizations. The resulting language turns structural preconditioner questions into geometric distance, reachability, and certificate problems. The repository includes deterministic toy and synthetic workflows that check diagonal expression gaps, block primal/dual certificates, Kronecker spectral width, and Hessian-relative Kronecker candidate certificates on small quadratic instances, together with low-rank spectral monotonicity.
Adaptive preconditioners can be viewed as a controlled evolution of geometry. In the finite-dimensional quadratic model, the unconstrained reference problem is clean: if the metric may move through all of \(\mathbb{S}_{++}^d\), the minimum affine-invariant length required to reduce relative condition number is the distance from the relative log-spectrum to a low-width set. For completeness, 1 states and proves this full positive-definite benchmark inside the present paper. This manuscript is the restricted-family counterpart to optimization geometrodynamics [1]. That framework introduces dynamic geometric optimization and the full positive-definite quadratic benchmark; the present paper asks what remains reachable, and at what affine-invariant path cost, when the metric is constrained to structured families such as diagonal, block, Kronecker, and low-rank models.
Real adaptive optimizers almost never move inside the full positive-definite cone. AdaGrad and Adam use diagonal geometries [2], [3]; Adafactor and SM3 use factored or memory-efficient second-moment statistics [4], [5]; K-FAC uses Kronecker approximations to Fisher geometry [6]; Shampoo uses tensor factor preconditioners [7]; full-matrix adaptive regularization and GGT occupy a more expressive but more expensive regime [8]; quasi-Newton and memory-limited methods often use low-rank corrections [9], [10]. These methods motivate structural metric families at different levels of abstraction. We study the geometric cost of a specified family once that family has been formalized; claims about a concrete optimizer require an explicit mapping from its state variables, damping, and update rules to such a family.
Given a strongly convex quadratic objective with Hessian \(H\succ0\), a metric \(G\succ0\), and a restricted metric family \(\mathfrak F\subset\mathbb{S}_{++}^d\), define the relative metric \[S=H^{-1/2}GH^{-1/2}.\] The full cone can always move \(S\) optimally toward the set \[\mathcal{C}_K=\{S\in\mathbb{S}_{++}^d:\kappa(S)\le K\}.\] The restricted family can only use relative metrics in \[\mathcal{S}_\mathfrak F(H)=\{H^{-1/2}GH^{-1/2}:G\in\mathfrak F\}.\] The central object of this paper is the intrinsic path distance from \(S_0\) to \(\mathcal{S}_\mathfrak F(H)\cap\mathcal{C}_K\). This is the restricted dynamic geometric complexity. It measures the extra geometric deformation required by a structured preconditioning family.
The paper separates exact finite-dimensional results from diagnostic extension layers.
Position relative to closest condition-number work. Condition-number optimization under scaling and convex constraints has a long history, including optimal scaling conditions, block scaling, and convex programming formulations [11]–[16]. The novelty claimed here is the combination of this reachability question with an affine-invariant path-distance benchmark, explicit restricted-family distance \(D_{K,\mathfrak F}\), structured primal/dual certificates, and a layer-by-layer accounting language for expression, estimation, flow, and discretization gaps. The diagonal and block LMI results should therefore be read as certificate-ready specializations inside this geometric benchmark, with closest-work comparisons made in [sec:related] [sec:diag-block]. The following table makes the intended novelty boundary explicit.
| Claim family | Closest prior line | Increment claimed here |
|---|---|---|
| Diagonal and block reachability | Optimal scaling, equilibration, and convex condition-number minimization | Certificate-ready LMI specialization inside an affine-invariant restricted path-distance benchmark |
| Kronecker structure | K-FAC/Shampoo-style factor metrics, Kronecker approximation, separable covariance estimation | Affine-invariant projection diagnostics, log-Kronecker mismatch, and self-conditioned target bounds, plus Hessian-relative Loewner-sandwich reachability, threshold, fixed-basis exactness, and candidate certificates |
| Proxy, stochastic, flow, and discrete layers | Estimator concentration, continuous flows, and algorithmic discretization analyses | An accounting interface that locates which assumption supplies each ratio |
Core results.
We record the full positive-definite quadratic benchmark used as the reference distance, using the standard affine-invariant spectral lower bound.
We define certificate-ready realizable metric families and restricted dynamic geometric complexity \(D_{K,\mathfrak F}(S_0;H)\), together with expression ratios relative to the full benchmark.
We prove monotonicity and submanifold-distance principles for restricted complexity; these are organizing principles that follow from path-set inclusion and intrinsic distance, not deep new lower bounds.
We show that diagonal and block reachability are exactly linear matrix inequality feasibility problems of the form \[E\preceq H\preceq K E\] with \(E\) constrained to the same structural family.
We give a structured SDP dual certificate for infeasible diagonal or block targets, including a rank-one sign-flip witness for cross-block coupling obstructions.
We derive an exact two-dimensional formula for diagonal restricted complexity in a determinant-one gauge.
We derive the Kronecker quotient line element, separate it from a spectral additive surrogate, and identify the fixed shared Kronecker eigenbasis regime in which the surrogate is exact. We also prove that the full affine-invariant Kronecker family is closed and totally geodesic, that projection onto it is unique and characterized by partial-trace normal equations, and that the corresponding normal residual gives a stopping certificate and Armijo convergence rate for projected Riemannian solvers. The \(K\)-target bounds in this Kronecker projection subsection concern self-conditioned Kronecker metrics unless a Hessian-relative target is explicitly stated. For the Hessian-relative target, we give an exact Kronecker Loewner-sandwich reachability theorem and a direct candidate certificate that turns any passing Kronecker metric into a finite \(D_{K,\mathcal{K}}\) upper bound. We also define the endpoint threshold \(K^\star_{\mathcal{K}}(H)\) and solve the fixed Kronecker eigenbasis subproblem as a linear feasibility problem in log-eigenvalue variables.
Extension and accounting layers.
We separate additive, log-low-rank, and inverse Woodbury low-rank families, then state a shared-eigenbasis spectral low-rank monotonicity result.
We state checkable proxy-curvature, high-probability stochastic, and discrete-length interfaces for using the benchmark as a certificate problem.
We give diagnostic certificate ingredients for K-FAC-style metric states, separating family mismatch, within-family optimizer error, auxiliary \(K\)-target cost, and metric path length. Turning these ingredients into a full optimizer certificate still requires an optimizer-to-family mapping and a Hessian-relative target.
We give an exact chain factorization of expression, estimation, flow, and discretization ratios, and spell out the extra hypotheses under which those ratios can all be interpreted as cost inflations. This factorization is an accounting identity for locating assumptions, not a standalone algorithmic lower bound.
We include deterministic synthetic quadratic benchmarks that visualize diagonal expression gaps, block primal/dual feasibility phases, Kronecker spectral width, Hessian-relative Kronecker candidate certificates, and low-rank spectral monotonicity.
This is a theory paper about finite-dimensional metric control. Exact Hessians and the semidefinite programs below are benchmarks and certificates, with the purpose of making expressive limits of structured preconditioners mathematically comparable. Claims about practical optimizer families are structural interpretations of their metric restrictions unless a formal family equivalence is stated. Tensor, factored second-moment, stochastic, and low-rank optimizer examples are used as motivations for specified certificate problems; the paper does not claim a complete characterization of those algorithms. The repository also contains deterministic toy and synthetic scripts for checking the diagonal formula, block primal/dual certificate construction, Kronecker spectral width, Hessian-relative Kronecker candidate certificates, and low-rank spectral monotonicity on small fixed configurations. They are reproducibility checks for the certificate workflow, not empirical optimizer benchmarks, and they do not validate the noncommuting Kronecker projection solver; large-scale empirical optimizer comparison remains future work.
2 positions the framework relative to adaptive methods, SPD geometry, matrix scaling, and stochastic curvature estimation. 3 recalls the full SPD benchmark. 4 defines restricted complexity. 5 gives diagonal and block exact results. 6 studies Kronecker and low-rank structure. 7 introduces proxy, stochastic, flow, and discrete layers. 8 gives the exact total gap decomposition, and 9 closes with limitations and open problems.
Continuous-time analyses of optimization often encode algorithmic behavior as geometry or dynamics, including accelerated-gradient ODEs, Bregman dynamics, mirror descent, and natural gradient flow [17]–[21]. The present paper uses a narrower finite-dimensional quadratic benchmark: the metric itself is the controlled object, and the target is a bound on relative condition number. Optimization geometrodynamics [1] provides the broader dynamic geometric optimization framework and the full positive-definite quadratic benchmark. The present paper is the restricted-family counterpart: it fixes a structured metric family, studies Hessian-relative reachability, and turns the resulting expression limits into path-distance and certificate problems.
Diagonal adaptive methods such as AdaGrad and Adam maintain coordinatewise statistics and therefore operate inside a diagonal metric family [2], [3]. Adafactor replaces a full matrix-shaped second-moment accumulator by row and column factors [4]; SM3 gives a memory-efficient adaptive method based on shared accumulators across tensor coordinate sets [5]. Natural-gradient methods change the metric using information geometry [21]; K-FAC approximates this geometry with Kronecker-factored curvature [6]; KFC extends this factorization idea to convolution layers [22], and EKFAC uses a Kronecker-factored eigenbasis [23], which is especially close to the fixed-basis spectral surrogate below. Shampoo uses tensor-structured preconditioners for high-dimensional parameter arrays [7], with scalable full-matrix and tensor-preconditioner implementations developed in later work [24]. Full-matrix adaptive regularization, including GGT, uses richer matrix information at higher computational cost [8]. Quasi-Newton and limited-memory methods motivate low-rank correction families [9], [10]. The benchmark below gives certificate problems for structural metric families motivated by these choices. It compares an optimizer itself only when the optimizer-to-family correspondence has been specified.
The correspondence between an optimizer and a family \(\mathfrak F\) can be exact or only structural. Coordinatewise AdaGrad and Adam correspond directly to diagonal metric families once damping and bias-correction conventions are fixed. Adafactor and SM3 motivate factored diagonal or tensor-coordinate families; they are best represented by the spectral and certificate interfaces in this paper unless the precise accumulator parameterization is specified. K-FAC and Shampoo motivate Kronecker and tensor-factor families at the metric level. This paper formalizes Kronecker factor metrics through both a general affine-invariant projection problem and a fixed-basis spectral surrogate; a general tensor-preconditioner theorem would require a separate realization of the relevant tensor factors and gauges. Full-matrix adaptive regularization provides a high-expressivity reference between diagonal restrictions and the full \(\mathbb{S}_{++}^d\) benchmark. Low-rank quasi-Newton models motivate the low-rank extension layer, but additive, log-low-rank, and inverse Woodbury forms have different geometries.
Kronecker approximation has a substantial literature outside adaptive optimization. Frobenius-norm approximation by Kronecker products is developed by [25], while separable covariance and matrix-normal models lead to flip-flop and maximum-likelihood estimators [26], [27]. These works are closest to the projection side of our Kronecker section. The present paper uses a different objective: affine-invariant distance inside the SPD cone, target condition-number classes, and certificate language for structured metric families. Thus the Kronecker results below should be read as geometric projection and diagnostic statements, not as replacements for statistical estimation theory or Frobenius Kronecker approximation algorithms.
The affine-invariant geometry of positive-definite matrices gives a natural distance, length, logarithm map, and quotient language for metric evolution [28], [29]. Matrix logarithms and exponentials also underlie the discrete update models used later [30]. For smooth restricted families, our complexity is an intrinsic path distance in an embedded or quotient submanifold, placing the problem close to standard tools from optimization on matrix manifolds [31], [32].
Diagonal and block reachability are closely related to matrix scaling and equilibration. Classical work on condition-number equilibration studies how diagonal scaling changes numerical conditioning [33], with earlier optimal scaling conditions and later block-diagonal scaling results giving necessary conditions and algorithms for related scaling objectives [11]–[13]. Recent diagonal-preconditioning work gives a detailed theory and algorithms for optimal diagonal preconditioners [16]. More general condition-number minimization has also been studied through variational and convex-programming formulations [14], [15]. These works are the closest precedents for the reachability side of the present paper. Our use of LMIs integrates that reachability question with affine-invariant restricted path length and explicit infeasibility certificates. Balancing algorithms such as Sinkhorn–Knopp and Knight–Ruiz provide a broader computational tradition [34], [35]. Our diagonal and block conditions are expressed as linear matrix inequalities, so semidefinite programming supplies both feasibility algorithms and dual certificates [36], [37].
Classical diagonal or block scaling asks for a scaling that improves a matrix criterion, often with algorithmic or variational optimality guarantees. The present benchmark adds three geometric layers. First, the target is a condition-number class viewed in the relative SPD geometry of a quadratic objective. Second, after reachability is decided, the cost is the intrinsic affine-invariant path length from an initial metric to the reachable target inside the chosen family. Third, the same target language is used to separate expression restrictions from proxy-estimation, continuous-flow, and finite-step effects. This is why the paper keeps classical scaling references close to the diagonal and block results while treating stochastic and optimizer-specific sections as certificate interfaces.
Practical adaptive methods rarely access the exact Hessian. They use Fisher, Gauss–Newton, gradient-moment, or mini-batch curvature proxies. We isolate this issue as an estimation gap. Matrix concentration inequalities give one route for converting sample size and noise assumptions into high-probability proxy bounds [38].
We work first with the quadratic model \[f(\theta)=\frac{1}{2}\theta^\top H\theta,\qquad H\in\mathbb{S}_{++}^d.\] For a constant metric \(G\in\mathbb{S}_{++}^d\), the gradient flow is \[\dot{\theta}=-G^{-1}H\theta.\] The relevant linear operator is the generalized Hessian \(G^{-1}H\), equivalently the generalized eigenproblem \[Hv=\lambda Gv.\] We define the relative metric \[S=H^{-1/2}GH^{-1/2}.\] Then \(\kappa(G^{-1}H)=\kappa(S)\).
The affine-invariant length of a path \(S_t\in\mathbb{S}_{++}^d\) is \[\operatorname{Len}_{\mathrm{AI}}(S_{[0,T]}) = \int_0^T \left\lVert S_t^{-1/2}\dot{S}_tS_t^{-1/2}\right\rVert_F\,\mathrm dt.\] The corresponding geodesic distance is \[d_{\mathrm{AI}}(S_0,S_1) = \left\lVert \log(S_0^{-1/2}S_1S_0^{-1/2})\right\rVert_F.\] This is the standard affine-invariant Riemannian distance on the positive definite cone [28], [29]. Matrix logarithms and exponentials are understood through the usual functional calculus for positive-definite matrices [30].
For \(K\ge1\), let \[\mathcal{C}_K=\{S\in\mathbb{S}_{++}^d:\kappa(S)\le K\}.\]
Theorem 1 (Full SPD spectral benchmark). Let \(S_0\in\mathbb{S}_{++}^d\), and let \(y_1\le\cdots\le y_d\) be the ordered log-eigenvalues of \(S_0\). Then the affine-invariant distance from \(S_0\) to the target \(\mathcal{C}_K\) is \[D_K(S_0) = d_{\mathrm{AI}}(S_0,\mathcal{C}_K) = \min_{c\in\mathbb{R}} \left( \sum_{i=1}^d \operatorname{dist}(y_i,[c,c+\log K])^2 \right)^{1/2}.\]
Thus the full SPD benchmark is the Euclidean distance from the relative log-spectrum to the set of spectra whose width is at most \(\log K\). The present paper studies what happens when the path is restricted to a structural subfamily of \(\mathbb{S}_{++}^d\).
Remark 1 (Scale invariance). The condition number is invariant under \(S\mapsto cS\). Consequently, many restricted families carry a pure scale direction that does not change the target condition. The theory either quotients this direction or fixes a gauge, for example \(\det S=1\) or \(\operatorname{tr}\log S=0\).
Let \(\mathfrak F\subset\mathbb{S}_{++}^d\) be a family of admissible metrics. Examples include \[\mathfrak F_{\operatorname{diag}} = \{\operatorname{diag}(g_1,\ldots,g_d):g_i>0\},\] fixed block-diagonal families, \[\mathfrak F_{\mathrm{block}} = \{\operatorname{blockdiag}(G_1,\ldots,G_m):G_j\succ0\},\] Kronecker families, \[\mathfrak F_{\mathrm{kron}} = \{B\otimes A:A\succ0,\;B\succ0\},\] and low-rank correction families. Tensor-coordinate methods are treated only after a concrete matrix, Kronecker, spectral, or quotient realization has been specified; the notation below does not assume a generic tensor family.
A family \(\mathfrak F\) is realizable for the present theory if its geometry is specified well enough for path length, target reachability, and comparison with the full SPD benchmark to be meaningful. We use the following working requirements.
Positive definiteness and component. \(\mathfrak F\subset\mathbb{S}_{++}^d\), and the path-connected component of the initial metric \(G_0\) is specified.
Scale treatment. Scale freedom is either closed under \(G\mapsto cG\) or fixed by a gauge, such as \(\det G=\det H\) or \(\operatorname{tr}\log(H^{-1/2}GH^{-1/2})=0\).
Length interpretation. The family has a smooth embedded submanifold, stratified length-space, or quotient-space interpretation. Smooth and quotient cases can be handled with standard matrix-manifold tools [31], [32].
Path-space convention. The admissible path space from \(G_0\) is fixed as part of the realization. It consists of absolutely continuous curves in the specified component or quotient chart, with length interpreted as an extended nonnegative number. The definition below uses the infimum over this path space; it does not require a minimizing path or a globally complete geodesic theory.
Target convention. The target set \[\mathcal{C}_{K,\mathfrak F}(H)=\mathcal{S}_\mathfrak F(H)\cap\mathcal{C}_K\] is interpreted as empty when no admissible metric can reach the target.
Computable representation. The family is represented by a linear cone, a group/quotient action, or a smooth parameterization when one wants certificates or algorithms.
Here \[\mathcal{S}_\mathfrak F(H)=\{H^{-1/2}GH^{-1/2}:G\in\mathfrak F\}.\]
These cases have different mathematical content. Diagonal and fixed-block families are geodesically simple embedded submanifolds. Kronecker factorizations have a scale gauge and should be treated as quotient spaces. Additive low-rank families are stratified and generally nonconvex. The same symbol \(D_{K,\mathfrak F}\) is used for all of them, with the underlying path space stated each time. Results proved for one realization should therefore not be transferred to another realization without checking the path space, gauge, and target convention.
For the certificate statements below, a realization should provide explicit data: a parameter space \(\Theta\), a map \(\psi:\Theta\to\mathbb{S}_{++}^d\), any gauge equivalence on \(\Theta\), a membership test for \(\psi(\Theta)\), and the induced line element or quotient line element. In the diagonal and block cases this data is a linear positive cone, and a reachability certificate is either a primal matrix \(E\in\mathfrak F\) satisfying \(E\preceq H\preceq KE\) or a dual separating certificate from the corresponding semidefinite feasibility problem. For Kronecker and low-rank models, the paper states the realization explicitly before using a spectral surrogate or quotient metric.
Definition 1 (Restricted dynamic geometric complexity). Let \(K\ge1\), \(G_0\in\mathfrak F\), and \[S_0=H^{-1/2}G_0H^{-1/2}.\] The restricted length complexity is \[\begin{align} D_{K,\mathfrak F}(S_0;H) = \inf \left\{ \operatorname{Len}_{\mathrm{AI}}(S_{[0,T]}): \begin{array}{l} S(0)=S_0,\quad S_T\in\mathcal{C}_{K,\mathfrak F}(H),\\ S_t\in\mathcal{S}_\mathfrak F(H),\quad S_t \text{ absolutely continuous} \end{array} \right\}. \end{align}\] If \(\mathcal{C}_{K,\mathfrak F}(H)=\emptyset\), set \(D_{K,\mathfrak F}(S_0;H)=+\infty\).
The expression gap relative to the full SPD benchmark is \[\operatorname{Gap}_{\mathrm{expr}}(K,\mathfrak F;S_0,H) = \frac{D_{K,\mathfrak F}(S_0;H)}{D_K(S_0)}\] when \(D_K(S_0)>0\); if \(D_K(S_0)=0\), we use the convention that the gap is one when the restricted target is already reached.
Proposition 1 (Monotonicity and full SPD lower bound). Assume \(\mathfrak F_1\subset\mathfrak F_2\), the same initial relative metric \(S_0\) is admissible for both realizations, and every admissible \(\mathfrak F_1\)-path is also an admissible \(\mathfrak F_2\)-path with the same length. Then \[D_{K,\mathfrak F_1}(S_0;H)\ge D_{K,\mathfrak F_2}(S_0;H).\] In particular, for every admissible family \(\mathfrak F\) whose paths are also ambient SPD paths, \[D_{K,\mathfrak F}(S_0;H)\ge D_K(S_0).\] If \(K_1\le K_2\), then \[D_{K_1,\mathfrak F}(S_0;H)\ge D_{K_2,\mathfrak F}(S_0;H).\]
Proposition 2 (Submanifold distance). Assume that \(\mathcal{S}_\mathfrak F(H)\) is a smooth embedded submanifold of \(\mathbb{S}_{++}^d\), equipped with the path length induced by the ambient affine-invariant metric. Then \[D_{K,\mathfrak F}(S_0;H) = d_{\mathcal{S}_\mathfrak F(H)}(S_0,\mathcal{C}_{K,\mathfrak F}(H)),\] the intrinsic submanifold distance from \(S_0\) to the target set. If the target does not lie in the same path-connected component, the distance is \(+\infty\).
The proof of both propositions is immediate from path-set inclusion and the definition of intrinsic path distance; it is recorded in 10.
Diagonal and block families are the closest finite-dimensional models of coordinatewise and grouped adaptive preconditioning. Their reachability admits a clean semidefinite characterization. This connects restricted geometric complexity to the classical literature on scaling and equilibration [11]–[13], [16], [33]–[35], to condition-number optimization through convex programming [14], [15], and to semidefinite feasibility [36], [37]. The role of this section is to place those reachability questions inside the restricted affine-invariant path-distance benchmark and to record primal and dual certificates in the notation used by \(D_{K,\mathfrak F}\).
| Topic | Closest classical object | Role here |
|---|---|---|
| Diagonal/block scaling | Optimal scaling and equilibration criteria | Endpoint reachability for a restricted metric family |
| Condition-number minimization | Variational and convex-programming formulations | The same target embedded in an affine-invariant path-distance benchmark |
| Semidefinite feasibility | Primal feasibility and dual separation | Certificate language for finite \(D_{K,\mathfrak F}\) or unreachable targets |
Let \[\mathfrak F_{\operatorname{diag}}=\{D=\operatorname{diag}(e^{x_1},\ldots,e^{x_d}):x\in\mathbb{R}^d\}.\] Inside this family the affine-invariant line element is Euclidean in log coordinates: \[\operatorname{Len}_{\operatorname{diag}}(x_{[0,T]})=\int_0^T\left\lVert \dot{x}_t\right\rVert_2\,\mathrm dt.\] The diagonal target set is \[\mathcal{X}_K(H)= \{x\in\mathbb{R}^d:\kappa(\operatorname{diag}(e^{-x})H)\le K\}.\] When \(\mathcal{X}_K(H)\) is closed, \[D_{K,\operatorname{diag}}(x_0;H)=\operatorname{dist}_{\ell^2}(x_0,\mathcal{X}_K(H)).\]
Theorem 2 (Diagonal LMI reachability). For \(K\ge1\), the following are equivalent:
there exists a positive diagonal \(D\) with \(\kappa(D^{-1}H)\le K\);
there exists a positive diagonal \(E\) with \[E\preceq H\preceq K E.\]
Consequently, \[K_{\operatorname{diag}}^\ast(H) = \inf\{K\ge1:\exists E\succ0\;\mathrm{diagonal},\;E\preceq H\preceq KE\}.\] For fixed \(K\), diagonal reachability is an LMI feasibility problem.
Remark 2 (Certificate interpretation). 2 separates reachability from path length. If the LMI is infeasible, then \(D_{K,\operatorname{diag}}(x_0;H)=+\infty\) for every initial diagonal metric. If it is feasible, the remaining problem is the intrinsic distance from the initial log-scale \(x_0\) to the feasible set \(\mathcal{X}_K(H)\). Semidefinite duality can therefore provide certificates that no diagonal preconditioner can reach a desired condition-number threshold.
Corollary 1 (Aligned diagonal optimum). If \(H=\operatorname{diag}(h_1,\ldots,h_d)\) and \(G_0\) is diagonal, then \[D_{K,\operatorname{diag}}(S_0;H)=D_K(S_0).\]
Thus diagonal geometry can be optimal when the target curvature is already aligned with the coordinate axes. Its loss comes from directional mismatch.
The two-dimensional case exposes this mismatch explicitly. A general diagonal metric can be written as \[\operatorname{diag}(e^{x_1},e^{x_2})=e^c D(u), \qquad c=\frac{x_1+x_2}{2},\quad u=x_1-x_2,\] where the scalar \(e^c\) does not change \(\kappa(D^{-1}H)\). After quotienting out this scale direction, impose the determinant-one gauge \[D(u)=\operatorname{diag}(e^{u/2},e^{-u/2}).\] The diagonal length is \[\operatorname{Len}_{\operatorname{diag}}(u_{[0,T]}) = \frac{1}{\sqrt2}\int_0^T |\dot{u}_t|\,\mathrm dt.\]
Theorem 3 (Two-dimensional diagonal exact complexity). Let \(H\in\mathbb{S}_{++}^2\), \(K\ge1\), and \[R_K=\frac{K+1}{\sqrt K}\sqrt{\det H}.\] If \(K<K_{\operatorname{diag}}^\ast(H)\), then \[D_{K,\operatorname{diag}}^{2D}(u_0;H)=+\infty.\] If \(K\ge K_{\operatorname{diag}}^\ast(H)\), define \[x_\pm(K) = \frac{ R_K\pm\sqrt{R_K^2-4H_{11}H_{22}} }{2H_{22}}, \qquad u_\pm(K)=2\log x_\pm(K).\] Then the feasible set is the interval \[\mathcal{I}_K(H)=[u_-(K),u_+(K)]\] and \[D_{K,\operatorname{diag}}^{2D}(u_0;H) = \frac{1}{\sqrt2}\operatorname{dist}(u_0,\mathcal{I}_K(H)).\]
In this gauge, the diagonal family has one expressive direction. The interval \(\mathcal{I}_K(H)\) describes precisely which log-scale ratios make the preconditioned Hessian have condition number at most \(K\). The off-diagonal entry of \(H\) appears through \(\det H\), so stronger coordinate correlation shrinks the feasible interval and raises the smallest reachable condition number. The formula is gauge-specific: the determinant-one normalization removes the global scaling direction, so \(D_{K,\operatorname{diag}}^{2D}\) measures distance only along the remaining log-scale ratio.
Let the coordinates be split as \[\mathbb{R}^d=V_1\oplus\cdots\oplus V_m, \qquad \dim V_j=d_j,\] and let \(\mathfrak F_{\mathrm{block}}\) be the corresponding block-diagonal positive definite family.
Theorem 4 (Block LMI reachability). For \(K\ge1\), the following are equivalent:
there exists \(G\in\mathfrak F_{\mathrm{block}}\) with \(\kappa(G^{-1}H)\le K\);
there exists \(E\in\mathfrak F_{\mathrm{block}}\) with \[E\preceq H\preceq K E.\]
Therefore block reachability is also an LMI feasibility problem.
The LMI formulation also gives a checkable certificate when a target condition number is impossible. Let \(\mathcal{L}\) be either the diagonal symmetric subspace or a fixed block-diagonal symmetric subspace, and let \(\Pi_{\mathcal{L}}\) be the Frobenius-orthogonal projection onto \(\mathcal{L}\). For fixed \(K\), the primal reachability problem asks for \(E\in\mathcal{L}\) such that \[H-E\succeq0,\qquad KE-H\succeq0.\]
Proposition 3 (Structured SDP dual certificate). If there exist \(P,Q\in\mathbb{S}_{+}^d\) such that \[\Pi_{\mathcal{L}}(P-KQ)=0, \qquad \left\langle P-Q,H\right\rangle<0,\] then no \(E\in\mathcal{L}\) satisfies \(E\preceq H\preceq KE\). Hence the diagonal or block restricted target is empty at threshold \(K\).
Corollary 2 (Sign-flip rank-one certificate). Let \(T=\operatorname{blockdiag}(s_1 I_{d_1},\ldots,s_m I_{d_m})\), where \(s_j\in\{-1,1\}\), and let \(\mathcal{L}\) be the corresponding block-diagonal subspace. If \[\lambda_{\min}(K THT-H)<0,\] then the block family cannot reach condition number \(K\). The diagonal case is the special case \(d_j=1\).
The sign-flip certificate is not meant to solve every infeasible SDP. It gives a cheap, inspectable dual witness for synthetic examples where the obstruction is cross-block or cross-coordinate coupling.
Proposition 4 (Block Jacobi upper bound). Let \[G_{\mathrm{BJ}}=\operatorname{blockdiag}(H_{11},\ldots,H_{mm})\] with every \(H_{jj}\succ0\), and set \[\widetilde{H}=G_{\mathrm{BJ}}^{-1/2}HG_{\mathrm{BJ}}^{-1/2}.\] Then \[K_{\mathrm{block}}^\ast(H)\le \kappa(\widetilde{H}).\] If \(\left\lVert \widetilde{H}-I\right\rVert_{\operatorname{op}}\le\delta<1\), then \[K_{\mathrm{block}}^\ast(H)\le\frac{1+\delta}{1-\delta}.\]
The block family can absorb all within-block curvature. The residual difficulty is the normalized off-block interaction.
Matrix and tensor parameters motivate Kronecker and low-rank restrictions. These families require more care than diagonal or block families because their parameterizations include gauge redundancies and nonconvex structure. They model the structural assumptions behind Kronecker-factored natural gradient and tensor preconditioning methods [6], [7]. They are also related to classical Kronecker approximation and separable covariance estimation [25]–[27]; the objective here is affine-invariant metric geometry rather than Frobenius approximation or statistical likelihood. This section proves a local quotient line element, a fixed-basis spectral equivalence, and a general affine-invariant projection theorem for Kronecker metrics. The projection theorem does not give an elementary closed form in the fully noncommuting case, but it gives a unique target, partial-trace normal equations, certified residuals, and auxiliary self-conditioned \(K\)-target bounds. The Hessian-relative target has an exact endpoint reachability formulation as a nonconvex Kronecker Loewner sandwich, an associated expression threshold, and a fixed-basis log-spectrum subproblem; a separate candidate certificate then gives a direct upper bound on \(D_{K,\mathcal{K}}\) whenever a proposed Kronecker metric passes the generalized condition-number test against \(H\). The intended output is a set of checkable subproblems: a factor-path line element, a spectral mismatch signal, a fixed-basis regime where the surrogate becomes intrinsic, and a general projection problem that can be solved by Riemannian optimization.
Let \(W\in\mathbb{R}^{m\times n}\), so that \(\operatorname{vec}(W)\in\mathbb{R}^{mn}\). A Kronecker metric has the form \[G=B\otimes A,\qquad A\in\mathbb{S}_{++}^m,\quad B\in\mathbb{S}_{++}^n.\] If \[A=U\operatorname{diag}(a_i)U^\top,\qquad B=V\operatorname{diag}(b_j)V^\top,\] then \(B\otimes A\) has eigenvectors \(v_j\otimes u_i\) and eigenvalues \(b_j a_i\). Its log-spectrum has the additive form \[\log a_i+\log b_j.\] This motivates the additive subspace \[\mathcal{A}_{\mathrm{kron}} = \{Z\in\mathbb{R}^{m\times n}:Z_{ij}=\alpha_i+\beta_j\}.\]
Remark 3 (Status of the spectral surrogate). The additive log-spectrum model below is a diagnostic subproblem. It becomes an intrinsic Kronecker complexity only in the shared fixed-eigenbasis regime of 8. Outside that regime, Kronecker structure also constrains eigenvectors; the quotient geometry in 6 and the projection theorem below are the geometric objects.
In a fixed shared Kronecker eigenbasis, let \(Y\in\mathbb{R}^{m\times n}\) denote the current relative log-spectrum. A Kronecker spectral update can move inside the affine set \(Y+\mathcal{A}_{\mathrm{kron}}\). Define \[\mathcal{Y}_K=\{Z:\max_{i,j}Z_{ij}-\min_{i,j}Z_{ij}\le\log K\}.\]
Definition 2 (Kronecker spectral complexity). The Kronecker spectral surrogate is \[D_{K,\mathrm{kron}}^{\mathrm{spec}}(Y) = \operatorname{dist}_F\bigl( Y,\;(Y+\mathcal{A}_{\mathrm{kron}})\cap\mathcal{Y}_K \bigr),\] with value \(+\infty\) if the intersection is empty.
Proposition 5 (Spectral lower bound). Let \(D_K(Y)=\operatorname{dist}_F(Y,\mathcal{Y}_K)\). Then \[D_{K,\mathrm{kron}}^{\mathrm{spec}}(Y)\ge D_K(Y).\] If the full projection \(\Pi_{\mathcal{Y}_K}(Y)\) lies in \((Y+\mathcal{A}_{\mathrm{kron}})\), then equality holds.
This surrogate is useful but incomplete: the true Kronecker family also restricts eigenvectors to Kronecker product form. Consequently, a small value of \(D_{K,\mathrm{kron}}^{\mathrm{spec}}\) is a certificate only for the shared-eigenbasis subproblem unless accompanied by an eigenvector-compatibility argument. For a general Hessian, this missing compatibility can dominate the spectral width calculation: the additive log-spectrum may be favorable while no nearby Kronecker eigenbasis aligns with the curvature directions.
For \(Y\in\mathbb{R}^{m\times n}\), write \[\bar Y=\frac{1}{mn}\sum_{i,j}Y_{ij},\qquad r_i=\frac{1}{n}\sum_jY_{ij}-\bar Y,\qquad c_j=\frac{1}{m}\sum_iY_{ij}-\bar Y,\] and define the residual \[E_{ij}=Y_{ij}-\bar Y-r_i-c_j.\] Then \(E\) is orthogonal to \(\mathcal{A}_{\mathrm{kron}}\) in Frobenius inner product. The quantity \[\Delta_{\mathrm{kron}}(Y)=\left\lVert E\right\rVert_F\] is invariant under Kronecker spectral updates \(Y\mapsto Y+Z\) with \(Z\in\mathcal{A}_{\mathrm{kron}}\). It is therefore a structural mismatch signal. Turning it into a condition-number lower bound requires additional width or projection assumptions; the residual alone records nonadditivity.
The factorization has a gauge: \[B\otimes A=(c^{-1}B)\otimes(cA),\qquad c>0.\] Thus the intrinsic factor space is a quotient of \(\mathbb{S}_{++}^n\times\mathbb{S}_{++}^m\). For an absolutely continuous factor path define \[X_t=A_t^{-1/2}\dot{A}_tA_t^{-1/2},\qquad Y_t=B_t^{-1/2}\dot{B}_tB_t^{-1/2}.\]
Proposition 6 (Restricted affine-invariant line element). For \(G_t=B_t\otimes A_t\), \[\left\lVert \dot{G}_t\right\rVert_{G_t,\mathrm{AI}}^2 = n\left\lVert X_t\right\rVert_F^2 + m\left\lVert Y_t\right\rVert_F^2 + 2\operatorname{tr}(X_t)\operatorname{tr}(Y_t).\] The direction \(X_t=\alpha I_m,\;Y_t=-\alpha I_n\) has zero length and is exactly the factor-scale gauge direction.
Proposition 7 (Distance between Kronecker metrics). For \(G_0=B_0\otimes A_0\) and \(G_1=B_1\otimes A_1\), set \[L_A=\log(A_0^{-1/2}A_1A_0^{-1/2}),\qquad L_B=\log(B_0^{-1/2}B_1B_0^{-1/2}).\] Then the ambient affine-invariant distance is \[d_{\mathrm{AI}}(G_0,G_1)^2 = n\left\lVert L_A\right\rVert_F^2+m\left\lVert L_B\right\rVert_F^2 +2\operatorname{tr}(L_A)\operatorname{tr}(L_B).\]
The line element identifies the degenerate gauge direction and the length assigned to a specified factor path. The product-distance formula gives exact distances between two Kronecker metrics. Projecting an arbitrary target Hessian onto the Kronecker family is a separate problem handled after the fixed-basis surrogate below.
Proposition 8 (Fixed-basis exactness of the spectral surrogate). Assume \(H\), \(G_0\), and all feasible \(G_t=B_t\otimes A_t\) share a fixed Kronecker eigenbasis. Let \(\alpha_i(t)=\log\lambda_i(A_t)\) and \(\beta_j(t)=\log\lambda_j(B_t)\), and set \(Z_{ij}(t)=\alpha_i(t)+\beta_j(t)\). Then \[\left\lVert \dot{G}_t\right\rVert_{G_t,\mathrm{AI}}^2=\left\lVert \dot{Z}_t\right\rVert_F^2.\] Consequently, in the fixed-basis log-spectrum subproblem, \(D_{K,\mathrm{kron}}^{\mathrm{spec}}\) is the intrinsic Kronecker complexity.
The fixed-basis surrogate can be strengthened without assuming shared eigenvectors. Define \[\mathcal{K}_{m,n} = \{B\otimes A:A\in\mathbb{S}_{++}^m,\;B\in\mathbb{S}_{++}^n\} \subset\mathbb{S}_{++}^{mn},\] and the log-Kronecker subspace \[\mathcal{L}_{m,n} = \{I_n\otimes X+Y\otimes I_m: X\in\mathbb{S}^m,\;Y\in\mathbb{S}^n\}.\] For \(L\in\mathbb{S}^{mn}\), write \(L=[L_{pq}]_{p,q=1}^n\) in \(m\times m\) blocks and define partial traces \[\operatorname{Tr}_B(L)=\sum_{p=1}^n L_{pp}, \qquad \operatorname{Tr}_A(L)=[\operatorname{tr}(L_{pq})]_{p,q=1}^n.\]
Theorem 5 (Log-Kronecker mismatch and closed-form projection). For \(M\in\mathbb{S}_{++}^{mn}\), \[M\in\mathcal{K}_{m,n} \quad\Longleftrightarrow\quad \log M\in\mathcal{L}_{m,n}.\] Moreover, the Frobenius projection of \(L\in\mathbb{S}^{mn}\) onto \(\mathcal{L}_{m,n}\) is \[\Pi_{\mathcal{L}}L = \tau I_{mn}+I_n\otimes X_0+Y_0\otimes I_m,\] where \[\tau=\frac{\operatorname{tr}L}{mn},\qquad X_0=\frac{1}{n}\operatorname{Tr}_B(L)-\tau I_m,\qquad Y_0=\frac{1}{m}\operatorname{Tr}_A(L)-\tau I_n.\] Thus \[\delta_{\mathrm{kron}}^{\log}(M) = \left\lVert \log M-\Pi_{\mathcal{L}}\log M\right\rVert_F\] is a closed-form, eigenvector-aware Kronecker mismatch certificate. It vanishes exactly on \(\mathcal{K}_{m,n}\).
The double-centering residual above is the special case of 5 in a fixed Kronecker eigenbasis. Outside that regime, \(\delta_{\mathrm{kron}}^{\log}\) also detects eigenvector incompatibility.
Theorem 6 (Affine-invariant Kronecker projection). The family \(\mathcal{K}_{m,n}\) is a closed totally geodesic submanifold of the SPD cone under \(d_{\mathrm{AI}}\). Hence every \(M\in\mathbb{S}_{++}^{mn}\) has a unique projection \[G_\star=P_{\mathcal{K}}(M) = \operatorname*{arg\,min}_{G\in\mathcal{K}_{m,n}}d_{\mathrm{AI}}(M,G).\] If \[R_\star=\log(G_\star^{-1/2}MG_\star^{-1/2}),\] then \[\operatorname{Tr}_B(R_\star)=0,\qquad \operatorname{Tr}_A(R_\star)=0.\] Conversely, any \(G\in\mathcal{K}_{m,n}\) satisfying these two equations equals \(G_\star\). Therefore \[d_{\mathrm{AI}}(M,\mathcal{K}_{m,n})=\left\lVert R_\star\right\rVert_F.\]
Theorem 6 is the intrinsic replacement for the fixed-basis surrogate. It gives an implicit but global distance computation. The log-Euclidean certificate remains useful because the exponential-metric-increasing inequality gives \[d_{\mathrm{AI}}(M,\mathcal{K}_{m,n})\ge \delta_{\mathrm{kron}}^{\log}(M).\]
Corollary 3 (Residual certificate for the Kronecker projection solver). For \(G\in\mathcal{K}_{m,n}\), define \[R_G(M)=\log(G^{-1/2}MG^{-1/2}), \qquad V(G)=\Pi_{\mathcal{L}}R_G(M).\] Then \[V(G)=0\quad\Longleftrightarrow\quad G=P_{\mathcal{K}}(M),\] and \[d_{\mathrm{AI}}(G,P_{\mathcal{K}}(M))\le\left\lVert V(G)\right\rVert_F,\qquad 0\le f(G)-f(P_{\mathcal{K}}(M))\le\frac{1}{2}\left\lVert V(G)\right\rVert_F^2,\] where \(f(G)=\frac{1}{2}d_{\mathrm{AI}}(G,M)^2\). Consequently \(\left\lVert V(G)\right\rVert_F\) is a certified stopping residual for a projected Riemannian solver.
Corollary 4 (Armijo solver for the Kronecker projection). Fix \(G_0\in\mathcal{K}_{m,n}\), \(\bar\eta>0\), and \(\gamma,c\in(0,1)\). At iteration \(r\), set \[V_r=\Pi_{\mathcal{L}}R_{G_r}(M).\] If \(V_r=0\), stop. Otherwise choose the largest \(\eta_r\in\{\bar\eta,\bar\eta\gamma,\bar\eta\gamma^2,\ldots\}\) satisfying \[f\!\left(G_r^{1/2}\exp(\eta_rV_r)G_r^{1/2}\right) \le f(G_r)-c\eta_r\left\lVert V_r\right\rVert_F^2.\] Then \[G_{r+1}=G_r^{1/2}\exp(\eta_rV_r)G_r^{1/2}\] is well defined, remains in \(\mathcal{K}_{m,n}\), and either terminates at \(P_{\mathcal{K}}(M)\) or converges to \(P_{\mathcal{K}}(M)\). Moreover, there exists \(\underline\eta\in(0,(2c)^{-1}]\), depending only on the initial sublevel set and the Armijo parameters, such that \[f(G_r)-f(P_{\mathcal{K}}(M)) \le (1-2c\underline\eta)^r \bigl[f(G_0)-f(P_{\mathcal{K}}(M))\bigr].\]
Theorem 7 (Self-conditioned Kronecker \(K\)-target bounds). Let \[\mathcal{K}_{m,n,K}=\mathcal{K}_{m,n}\cap\mathcal{C}_K.\] Here \(\mathcal{C}_K\subset\mathbb{S}_{++}^{mn}\), so this target constrains the condition number of the Kronecker metric itself. It is an auxiliary self-conditioning target. For a fixed Hessian \(H\), the RDGC preconditioning target is instead \(\{G\in\mathcal{K}_{m,n}:\kappa(G^{-1}H)\le K\}\), equivalently \(\mathcal{S}_{\mathcal{K}}(H)\cap\mathcal{C}_K\) in relative coordinates. The two targets coincide only under additional compatibility assumptions.
The self-conditioned set \(\mathcal{K}_{m,n,K}\) is closed and geodesically convex. If \(G_\star=P_{\mathcal{K}}(M)\), then \[d_{\mathrm{AI}}(M,\mathcal{K}_{m,n,K})^2 \ge d_{\mathrm{AI}}(M,\mathcal{K}_{m,n})^2 + d_{\mathrm{AI}}(G_\star,\mathcal{K}_{m,n,K})^2,\] and \[d_{\mathrm{AI}}(M,\mathcal{K}_{m,n,K}) \le d_{\mathrm{AI}}(M,\mathcal{K}_{m,n}) + d_{\mathrm{AI}}(G_\star,\mathcal{K}_{m,n,K}).\] Moreover, if \(G_0=B_0\otimes A_0\in\mathcal{K}_{m,n}\) and \[A_0=U\operatorname{diag}(e^{a_1},\ldots,e^{a_m})U^\top,\qquad B_0=V\operatorname{diag}(e^{b_1},\ldots,e^{b_n})V^\top\] with sorted \(a_i\) and \(b_j\), then \[d_{\mathrm{AI}}(G_0,\mathcal{K}_{m,n,K})^2 = \min_{x,y} \sum_{i=1}^m\sum_{j=1}^n(x_i+y_j-a_i-b_j)^2\] subject to \[x_1\le\cdots\le x_m,\qquad y_1\le\cdots\le y_n,\qquad (x_m-x_1)+(y_n-y_1)\le\log K.\]
Theorem 8 (Hessian-relative Kronecker reachability). For a fixed \(H\in\mathbb{S}_{++}^{mn}\), define \[\mathcal{R}_{K,\mathcal{K}}(H) = \{G\in\mathcal{K}_{m,n}:\kappa(G^{-1}H)\le K\}.\] Then the following are equivalent:
\(\mathcal{R}_{K,\mathcal{K}}(H)\ne\emptyset\);
\(\mathcal{C}_{K,\mathcal{K}}(H)=\mathcal{S}_{\mathcal{K}}(H)\cap\mathcal{C}_K\ne\emptyset\);
there exist \(A\succ0\), \(B\succ0\), and \(\lambda>0\) such that \[\lambda(B\otimes A)\preceq H\preceq K\lambda(B\otimes A).\]
Equivalently, because the scale \(\lambda\) can be absorbed into one factor, reachability is the feasibility of \[B\otimes A\preceq H\preceq K(B\otimes A), \qquad A\succ0,\quad B\succ0.\] If these equivalent conditions hold, then for every \(G_0\in\mathcal{K}_{m,n}\), with \(S_0=H^{-1/2}G_0H^{-1/2}\), \[D_{K,\mathcal{K}}(S_0;H) = d_{\mathrm{AI}}\bigl(G_0,\mathcal{R}_{K,\mathcal{K}}(H)\bigr).\] Moreover, \(\mathcal{R}_{K,\mathcal{K}}(H)\) is a closed geodesically convex subset of the Kronecker manifold, and the displayed distance is attained at a unique projection point. Thus the endpoint reachability problem is exact, but the Kronecker Loewner sandwich is generally a nonconvex feasibility problem in the ambient matrix variable.
Corollary 5 (Kronecker expression threshold). Define \[K_{\mathcal{K}}^\star(H) = \min_{G\in\mathcal{K}_{m,n}}\kappa(G^{-1}H).\] The minimum is attained. Moreover, for every \(K\ge1\), \[\mathcal{R}_{K,\mathcal{K}}(H)\ne\emptyset \quad\Longleftrightarrow\quad K\ge K_{\mathcal{K}}^\star(H).\] Thus \(K_{\mathcal{K}}^\star(H)\) is the intrinsic endpoint threshold for whether a Kronecker metric can reach the Hessian-relative condition-number target.
Proposition 9 (Fixed-basis Hessian-relative Kronecker exactness). Fix orthogonal matrices \(U\in\mathbb{R}^{m\times m}\) and \(V\in\mathbb{R}^{n\times n}\), and consider the fixed-basis subfamily \[\mathcal{K}_{U,V} = \{(V\operatorname{diag}(e^{b_1},\ldots,e^{b_n})V^\top) \otimes (U\operatorname{diag}(e^{a_1},\ldots,e^{a_m})U^\top):a\in\mathbb{R}^m,\;b\in\mathbb{R}^n\}.\] Assume \[H=(V\otimes U)\operatorname{diag}(h_{ij})(V\otimes U)^\top, \qquad h_{ij}>0,\] and set \(\ell_{ij}=\log h_{ij}\). Then reachability in \(\mathcal{K}_{U,V}\) at target \(K\) is equivalent to the linear feasibility problem \[\exists a\in\mathbb{R}^m,\;b\in\mathbb{R}^n,\;c\in\mathbb{R} \quad\text{such that}\quad c\le \ell_{ij}-a_i-b_j\le c+\log K \quad\forall i,j.\] Equivalently, the fixed-basis threshold is \[\log K^\star_{U,V}(H) = \min_{a,b} \left[ \max_{i,j}(\ell_{ij}-a_i-b_j) - \min_{i,j}(\ell_{ij}-a_i-b_j) \right].\] Feasibility for this fixed-basis subfamily is a primal certificate for the full Kronecker family. Infeasibility for the fixed-basis subfamily does not rule out a noncommuting Kronecker metric with different factor eigenvectors.
Proposition 10 (Hessian-relative Kronecker candidate certificate). Let \(H\in\mathbb{S}_{++}^{mn}\), \(G_0=B_0\otimes A_0\in\mathcal{K}_{m,n}\), and \(G_c=B_c\otimes A_c\in\mathcal{K}_{m,n}\). Define \[S_0=H^{-1/2}G_0H^{-1/2}, \qquad S_c=H^{-1/2}G_cH^{-1/2}.\] If \[\kappa(S_c)\le K,\] equivalently \(\kappa(G_c^{-1}H)\le K\), then \(G_c\) is a primal Hessian-relative Kronecker certificate and \[D_{K,\mathcal{K}}(S_0;H)\le d_{\mathrm{AI}}(G_0,G_c).\] With \[L_A=\log(A_0^{-1/2}A_cA_0^{-1/2}),\qquad L_B=\log(B_0^{-1/2}B_cB_0^{-1/2}),\] this upper bound has the closed form \[d_{\mathrm{AI}}(G_0,G_c)^2 = n\left\lVert L_A\right\rVert_F^2+m\left\lVert L_B\right\rVert_F^2 +2\operatorname{tr}(L_A)\operatorname{tr}(L_B).\] Thus any candidate Kronecker metric passing the generalized condition-number test supplies a finite restricted-complexity upper bound. If a proposed candidate fails the test, no infeasibility conclusion follows.
Taking \(G_c=P_{\mathcal{K}}(H)\) gives a projection-based sufficient certificate: one checks the Hessian-relative condition number of the projected Kronecker metric and, if it is at most \(K\), obtains the path-length upper bound above. Failure of this projected candidate only means that this particular candidate does not reach the RDGC target; another Kronecker metric may still do so.
Proposition 11 (Nonsmooth active \(K\)-target condition). Assume \(K>1\). Let \(Q_\star=P_{\mathcal{K}_{m,n,K}}(M)\), and set \[R_\star=\log(Q_\star^{-1/2}MQ_\star^{-1/2}),\qquad \omega(Q)=\log\kappa(Q).\] If \(\omega(Q_\star)<\log K\), then \[\Pi_{\mathcal{L}}R_\star=0.\] If \(\omega(Q_\star)=\log K\), then there exist \(\mu\ge0\) and \(W_\star\in\partial\omega(Q_\star)\) such that \[\Pi_{\mathcal{L}}R_\star=\mu\Pi_{\mathcal{L}}W_\star.\] Here \(\partial\omega(Q_\star)\) is the convex hull of \[uu^\top-vv^\top,\qquad u\in E_{\max},\;\left\lVert u\right\rVert=1,\quad v\in E_{\min},\;\left\lVert v\right\rVert=1,\] with \(E_{\max}\) and \(E_{\min}\) the extremal eigenspaces of \(Q_\star\). For simple extremal eigenvalues this reduces to the usual multiplier equation with \(W_\star=u_{\max}u_{\max}^\top-u_{\min}u_{\min}^\top\).
Proposition 12 (Projection diagnostics for K-FAC-style metrics). Suppose an optimizer uses damped Kronecker metric states \[G_t=(B_t+\lambda_BI_n)\otimes(A_t+\lambda_AI_m).\] Let \(H_t\succ0\) be a reference curvature and \(P_t=P_{\mathcal{K}}(H_t)\). Then the quantities \[M_t=d_{\mathrm{AI}}(H_t,P_t),\quad A_t=d_{\mathrm{AI}}(P_t,G_t),\quad E_t=d_{\mathrm{AI}}(H_t,G_t),\quad C_{K,t}=d_{\mathrm{AI}}(P_t,\mathcal{K}_{m,n,K})\] satisfy \[E_t^2\ge M_t^2+A_t^2,\] and \[(M_t^2+C_{K,t}^2)^{1/2} \le d_{\mathrm{AI}}(H_t,\mathcal{K}_{m,n,K}) \le M_t+C_{K,t}.\] Here \(A_t\) and the discrete increment \(d_{\mathrm{AI}}(G_t,G_{t+1})\) have the closed form of 7, \(M_t\) is computed by 6, and \(C_{K,t}\) is the convex QP in 7. These quantities diagnose distance to the Kronecker family, optimizer-state lag inside that family, and distance to the auxiliary self-conditioned target. They do not by themselves certify \(\kappa(G_t^{-1}H_t)\le K\). A full preconditioning certificate must use the Hessian-relative target \(\{G\in\mathcal{K}_{m,n}:\kappa(G^{-1}H_t)\le K\}\) and must specify how the optimizer state, damping, bias correction, and discrete path realize an admissible family trajectory.
Low-rank structures split into three different models:
additive metric families, \(G=D+UU^\top\), which are close to practical low-rank preconditioners;
log-low-rank families, \(G=\exp(cI+L)\) with \(\operatorname{rank}(L)\le r\), which are cleaner for spectral theory;
inverse Woodbury forms, useful for implementation cost.
This paper uses low-rank as an extension layer. The result below is a spectral surrogate for practical additive forms \(D+UU^\top\); their intrinsic geometry requires a separate stratified analysis. The clean spectral model assumes a shared eigenbasis and lets at most \(r\) log-eigenvalue coordinates move away from an overall shift: \[\mathcal{Y}_{K,r}(y) = \{z\in\mathcal{Y}_K:\exists c\in\mathbb{R},\;|\{i:z_i\ne y_i+c\}|\le r\}.\] The corresponding spectral low-rank complexity is \[D_{K,r}^{\mathrm{spec}}(y)=\operatorname{dist}_{\ell^2}(y,\mathcal{Y}_{K,r}(y)).\]
Proposition 13 (Low-rank spectral monotonicity). If \(r_1\le r_2\), then \[D_{K,r_1}^{\mathrm{spec}}(y) \ge D_{K,r_2}^{\mathrm{spec}}(y) \ge D_K(y).\] When \(r\ge d\), the low-rank spectral complexity equals the full spectral benchmark \(D_K(y)\).
Remark 4 (Role of low rank). The proposition captures the intended hierarchy: more spectral correction directions cannot hurt, and full rank recovers the unconstrained benchmark. For practical additive forms \(D+UU^\top\), the same monotonicity should be studied in a stratified metric space rather than in this shared-eigenbasis spectral surrogate. The proposition therefore supports the hierarchy of spectral correction families under the stated shared-eigenbasis surrogate. Claims about a concrete low-rank preconditioner additionally require its update parameterization, damping convention, and admissible interpolation to be mapped into one of these geometric realizations.
The restricted complexity \(D_{K,\mathfrak F}\) is an ideal geometric benchmark: it assumes exact curvature, optimal continuous motion inside \(\mathfrak F\), and no discretization loss. A practical optimizer usually violates all three conditions. This section records the corresponding mathematical layers.
Suppose the optimizer uses a positive-definite proxy \(\widehat H\) for \(H\). Examples include Fisher, Gauss–Newton, empirical gradient-moment, Kronecker factor, or mini-batch curvature estimates. The following elementary comparison turns a verified Loewner proxy error into a stricter target threshold. The section does not supply the statistical proof of that proxy event; such a proof must come from the chosen estimator and data model.
Proposition 14 (Proxy inflation of condition number). Assume \[(1-\varepsilon)H\preceq \widehat H\preceq (1+\varepsilon)H, \qquad 0\le\varepsilon<1.\] Then for every \(G\succ0\), \[\kappa(G^{-1}H) \le \frac{1+\varepsilon}{1-\varepsilon}\, \kappa(G^{-1}\widehat H).\] Consequently, to certify \(\kappa(G^{-1}H)\le K\), it suffices to reach \[\kappa(G^{-1}\widehat H)\le \widehat K := K\frac{1-\varepsilon}{1+\varepsilon}.\] If \(\widehat K<1\), this proxy accuracy cannot certify the target \(K\).
This proposition separates geometric expressivity from curvature estimation. Even a family with small \(D_{K,\mathfrak F}(S_0;H)\) may need to solve a harder proxy problem when \(\widehat H\) is noisy.
Let \(\widehat H_t\) be a stochastic adapted curvature proxy and let \(\mathcal{G}_t\) denote the history available up to time \(t\). A stochastic controller \(\pi\) is admissible if its metric velocity or next metric choice is \(\mathcal{G}_t\)-measurable and remains in the admissible family \(\mathfrak F\). All random variables are taken on a fixed filtered probability space, and the terminal time \(T\) is fixed in advance or is a \(\mathcal{G}_t\)-stopping time for which the path length is well defined. Given a concrete proxy model, the event in 15 is the checkable certificate condition. Given a failure probability \(\delta\), define the high-probability stochastic restricted complexity by \[D_{K,\mathfrak F}^{\mathrm{stoch}}(S_0;H,\delta) = \inf_{\pi} \inf \left\{ B: \mathbb{P}_\pi \left( \operatorname{Len}_{\mathrm{AI}}(S_{[0,T]})\le B, S_T\in\mathcal{C}_{K,\mathfrak F}(H) \right) \ge 1-\delta \right\}.\]
Proposition 15 (High-probability proxy upper bound). Suppose that, with probability at least \(1-\delta\), \[(1-\varepsilon)H\preceq \widehat H_t\preceq(1+\varepsilon)H \quad\text{for all }t\in[0,T],\] and an adapted controller reaches a terminal metric \(G_T\in\mathfrak F\) satisfying \[\kappa(G_T^{-1}\widehat H_T)\le \widehat K\] with path length at most \(B\) on that event, where \[\widehat K=K\frac{1-\varepsilon}{1+\varepsilon}\ge1.\] Then \[D_{K,\mathfrak F}^{\mathrm{stoch}}(S_0;H,\delta)\le B.\]
The proposition creates an interface for concentration arguments: matrix concentration can be used to choose batch sizes or damping rules that make the proxy event hold with the desired probability [38]. Without such a concentration or deterministic approximation result, the stochastic quantity above is only a certificate template.
Let \(M_\mathfrak F=\mathcal{S}_\mathfrak F(H)\) be a smooth realization of the restricted family. For a smooth energy \(\Phi:M_\mathfrak F\to\mathbb{R}\), the intrinsic gradient flow \[\dot{S}_t=-\operatorname{grad}_{M_\mathfrak F}\Phi(S_t)\] satisfies \[\frac{\mathrm d}{\mathrm dt}\Phi(S_t) = -\left\lVert \operatorname{grad}_{M_\mathfrak F}\Phi(S_t)\right\rVert_{S_t,\mathrm{AI}}^2.\] A natural choice is the squared distance to a target or proxy metric. This gives an implementable continuous path, but the flow length need not equal the restricted distance \(D_{K,\mathfrak F}\); the ratio is the flow gap introduced in 8.
For exponential SPD updates with symmetric directions \(B_k=B_k^\top\), \[G_{k+1}=G_k^{1/2}\exp(\tau_kB_k)G_k^{1/2},\] the affine-invariant step length is \[\ell_k=\left\lVert \tau_kB_k\right\rVert_F.\] The total discrete geometric length is \[\operatorname{Len}_{\mathrm{alg}}=\sum_{k=0}^{N-1}\ell_k.\]
Proposition 16 (Discrete length lower bound). If a discrete path reaches \(G_N\) with \(\kappa(G_N^{-1}H)\le K\), then \[\operatorname{Len}_{\mathrm{alg}}\ge D_K(S_0).\] If, moreover, each discrete segment is realized by an admissible interpolation inside \(\mathfrak F\) with the same total length and the endpoint lies in \(\mathcal{C}_{K,\mathfrak F}(H)\), then \[\operatorname{Len}_{\mathrm{alg}}\ge D_{K,\mathfrak F}(S_0;H).\]
The interpolation condition matters: discrete nodes may lie in a nonlinear restricted family while the ambient SPD geodesic between them leaves that family. Restricted lower bounds therefore concern the actual admissible interpolation and the symmetry-compatible update directions, not just the endpoint sequence.
The restricted complexity \(D_{K,\mathfrak F}\) measures the best possible path inside a metric family. 7 separated three additional layers: curvature proxies, nonoptimal flows, and discrete updates. The useful point is that these layers can be written as an exact product of ratios. Some ratios are automatically at least one, while others require extra hypotheses before they deserve the name “loss” or “cost inflation.” Thus the theorem below is an accounting identity. Its role is to localize which assumption is responsible for an observed length increase, not to prove a new algorithmic lower bound by itself.
Assume the nondegenerate regime \[\widehat K\ge1,\qquad 0<D_K(S_0)<\infty,\qquad 0<D_{K,\mathfrak F}(S_0;H)<\infty,\] \[0<D_{\widehat K,\mathfrak F}(\widehat S_0;\widehat H)<\infty,\qquad 0<\operatorname{Len}_{\mathrm{cont}}<\infty,\] where \[\widehat S_0=\widehat H^{-1/2}G_0\widehat H^{-1/2}.\]
Theorem 9 (Exact chain factorization). In the above regime, \[\frac{\operatorname{Len}_{\mathrm{alg}}}{D_K(S_0)} = \frac{D_{K,\mathfrak F}(S_0;H)}{D_K(S_0)} \cdot \frac{D_{\widehat K,\mathfrak F}(\widehat S_0;\widehat H)}{D_{K,\mathfrak F}(S_0;H)} \cdot \frac{\operatorname{Len}_{\mathrm{cont}}}{D_{\widehat K,\mathfrak F}(\widehat S_0;\widehat H)} \cdot \frac{\operatorname{Len}_{\mathrm{alg}}}{\operatorname{Len}_{\mathrm{cont}}}.\]
The four factors are respectively the expression, estimation, flow, and discretization ratios: \[R_{\mathrm{expr}},\qquad R_{\mathrm{est}},\qquad R_{\mathrm{flow}},\qquad R_{\mathrm{disc}}.\] They answer four different questions: what the family can express, how much the proxy problem changes the target, how efficient the chosen flow is within the family, and how much finite-step implementation deviates from the continuous path.
Proposition 17 (When the ratios are cost inflations). In the nondegenerate regime of 9, the following conditions imply that the corresponding ratios are at least one.
\(R_{\mathrm{expr}}\ge1\) always, by the full SPD lower bound in 1.
\(R_{\mathrm{est}}\ge1\) whenever the proxy certificate problem is no easier than the true restricted problem, i.e. \[D_{\widehat K,\mathfrak F}(\widehat S_0;\widehat H) \ge D_{K,\mathfrak F}(S_0;H).\] A checkable special case is \(\widehat H=H\), \(\widehat S_0=S_0\), and \(\widehat K\le K\).
\(R_{\mathrm{flow}}\ge1\) whenever \(\operatorname{Len}_{\mathrm{cont}}\) is the length of an admissible continuous path in the proxy restricted family that reaches \(\mathcal{C}_{\widehat K,\mathfrak F}(\widehat H)\).
\(R_{\mathrm{disc}}\ge1\) whenever the implemented discrete path has total geometric length at least the continuous reference path being discretized.
Without these hypotheses, 9 remains an exact chain factorization, but the affected ratios should be reported as diagnostic ratios rather than losses.
Remark 5 (Degenerate regimes). If one of the denominators in 9 is zero or infinite, the multiplicative ratio should be replaced by the corresponding extended-real inequality statement. For example, if \(D_{K,\mathfrak F}(S_0;H)=+\infty\), the expression gap already proves structural impossibility at threshold \(K\).
The paper establishes a restricted counterpart to the full SPD benchmark from optimization geometrodynamics. The central object is the intrinsic distance \[D_{K,\mathfrak F}(S_0;H)\] from an initial relative metric to a target condition-number class, with paths constrained to a realizable family \(\mathfrak F\). This gives exact certificate language for diagonal and fixed-block metric families, and diagnostic realizations for Kronecker spectral, proxy, stochastic, flow, discrete, and low-rank extension layers.
Four features make the framework operational. First, diagonal and block reachability reduce to LMI feasibility, hence admit semidefinite certificates. Second, the two-dimensional diagonal formula gives an exact model of coordinate-curvature mismatch. Third, the Kronecker analysis separates a computable additive spectral surrogate from the intrinsic quotient geometry of Kronecker factors, then upgrades the general case to an affine-invariant projection problem with normal equations, residual certificates, and an Armijo solver convergence guarantee. The \(K\)-target bounds attached to this projection problem are auxiliary self-conditioning diagnostics unless they are replaced by a Hessian-relative preconditioning target. Fourth, the Hessian-relative Kronecker target has an exact endpoint reachability theorem: reachability is equivalent to a Kronecker Loewner sandwich, and any feasible candidate supplies a finite restricted-complexity upper bound. The associated threshold \(K^\star_{\mathcal{K}}(H)\) records the best condition number achievable by the Kronecker family, and the fixed Kronecker eigenbasis regime reduces to a linear log-spectrum feasibility problem.
The strongest exact results are finite-dimensional and quadratic. This is intentional: the quadratic model isolates the geometry of preconditioning from the separate problem of changing curvature along a nonlinear objective. For nonquadratic objectives, \(H\) should be interpreted locally or along a trajectory, and the theory becomes a time-dependent control problem.
The extension layers are weaker than the diagonal and block results. Proxy, stochastic, flow, discrete, and low-rank sections provide certificate interfaces and diagnostic ratios. They should not be read as fully solved geometric characterizations of every optimizer that motivates them. For a concrete optimizer, an additional mapping is needed: the optimizer state variables must define a metric family \(\mathfrak F\), damping and bias-correction conventions must be fixed, the continuous or discrete update path must be specified, and any stochastic curvature proxy must be tied to a deterministic or high-probability Loewner event. The present paper supplies the benchmark that such a mapping can use.
Low-rank families are treated as structured extensions rather than fully solved geometric spaces. Additive families \(D+UU^\top\), log-low-rank families, and Woodbury inverse implementations have different geometry. The paper separates them to avoid conflating spectral expressivity with implementation cost.
The Hessian-relative Kronecker reachability theorem gives exact endpoint equivalences and a solved fixed-basis subproblem, but the resulting full Loewner sandwich is nonconvex in the ambient matrix variable. The paper therefore supplies a precise certificate problem, not a scalable global solver or a finite SDP dual certificate for the general noncommuting case.
The stochastic layer is also deliberately modular. 15 shows how a high-probability proxy event implies a high-probability restricted complexity bound, but concrete sample-complexity rates require assumptions on the curvature estimator and the data distribution. Similarly, the Kronecker projection solver is proved as a geometric subproblem; the current reproducibility workflows do not implement or benchmark a noncommuting affine-invariant Kronecker projection algorithm.
The repository contains two deterministic workflows in the toy experiment directory. The first is a fixed-configuration sanity check. It verifies the two-dimensional diagonal exact formula against a brute-force grid, constructs a block-Jacobi primal certificate \(E\preceq H\preceq KE\), and checks invariance of the Kronecker double-centering residual under additive spectral updates. On the included configuration, the expected summary has seed \(7\), four finite diagonal target points, maximum diagonal grid discrepancy \(3.28\times10^{-4}\), block certificate \(K_{\mathrm{cert}}\approx1.2634\), and Kronecker residual invariance error below \(10^{-15}\).
The second workflow is a small synthetic benchmark over families of quadratic instances. It writes CSV files and plots for: (i) a two-dimensional diagonal expression-gap heatmap over coordinate coupling and target \(K\); (ii) a two-block phase diagram in which every grid point is certified either by a block-Jacobi primal witness or by the sign-flip dual witness in 2; (iii) a Kronecker spectral minimum-width linear program as the double-centering residual grows; (iv) a constructed Hessian-relative Kronecker candidate certificate with an identity baseline that fails the same target; and (v) the monotone decrease of the shared-eigenbasis low-rank spectral reachable width as the rank budget increases. On the reference run, the diagonal grid contains 86 finite expression-gap entries and 49 unreachable entries, the largest finite diagonal gap is about \(2.15\), the block dual projection residual is numerically zero, the largest block primal violation is below \(3\times10^{-16}\), the constructed Kronecker candidate has condition number \(1.6000\) for target \(K=1.75\), and the identity baseline has condition number about \(3.45\).
These workflows make the certificate behavior inspectable on small instances. They do not compare optimizers, tune hyperparameters, or estimate statistical variability, and they do not test the noncommuting Kronecker projection solver. Moving the synthetic sweep parameters into machine-readable configuration files, logging fuller environment metadata, and adding multi-seed random SPD instance suites are natural reproducibility improvements. Large empirical optimizer comparison remains future work.
Several directions are mathematically immediate.
Develop general algorithms for finding diagonal and block infeasibility dual certificates beyond the explicit sign-flip witness in 2.
Give a worked optimizer-to-family mapping for one small adaptive method, including state variables, damping, bias correction, admissible interpolation, and the resulting expression, estimation, flow, and discretization ratios.
Design scalable algorithms or dual certificates for the nonconvex Hessian-relative Kronecker Loewner sandwich, and compare the resulting certificates against K-FAC-style optimizer states.
Extend the generic simple-spectrum Kronecker eigenprojector mismatch criterion to repeated spectra without imposing an arbitrary grouping rule.
Build a stratified-length theory for additive low-rank families such as \(D+UU^\top\).
Combine matrix concentration with restricted complexity to obtain finite-sample estimation gaps for stochastic curvature proxies.
Restricted dynamic geometric complexity turns structural preconditioner design into a geometry problem. A metric family has an expression cost, a curvature proxy introduces an estimation ratio, a chosen continuous dynamics has a flow ratio, and a finite-step algorithm has a discretization ratio. Under the conditions in 17, these ratios become interpretable cost inflations; otherwise they remain exact diagnostic factors. In this form, the theory provides a foundation for asking which adaptive geometries are expressive enough, which geometric restrictions are provably costly, and which algorithmic approximations are responsible for the remaining distance from the full SPD benchmark.
Proof of 1. Let \(S_1\in\mathcal{C}_K\), and let \(z_1\le\cdots\le z_d\) be the ordered log-eigenvalues of \(S_1\). The affine-invariant distance satisfies the spectral lower bound \[d_{\mathrm{AI}}(S_0,S_1)\ge \left\lVert y-z\right\rVert_2,\] where \(y\) is the ordered log-spectrum of \(S_0\). This is the standard eigenvalue majorization lower bound for the affine-invariant metric on positive-definite matrices [28]. Since \(S_1\in\mathcal{C}_K\), the vector \(z\) has width at most \(\log K\), so \(z_i\in[c,c+\log K]\) for some \(c\). Hence \[d_{\mathrm{AI}}(S_0,S_1)^2 \ge \sum_{i=1}^d \operatorname{dist}(y_i,[c,c+\log K])^2.\] Taking the infimum over \(S_1\in\mathcal{C}_K\) gives the lower bound.
For the reverse inequality, fix \(c\) and define \[z_i(c)=\Pi_{[c,c+\log K]}(y_i),\] the scalar projection of \(y_i\) onto the interval. The vector \(z(c)\) has width at most \(\log K\). Choose \(S_1\) with the same eigenvectors as \(S_0\) and log-eigenvalues \(z_i(c)\). Then \(S_1\in\mathcal{C}_K\) and the commuting affine-invariant distance is exactly \(\left\lVert y-z(c)\right\rVert_2\). Minimizing over \(c\in\mathbb{R}\) proves the formula. ◻
Proof of 1. Under the stated compatibility assumption, every admissible \(\mathfrak F_1\)-path from the common initial point \(S_0\) to the \(\mathfrak F_1\)-target is also an admissible \(\mathfrak F_2\)-path with the same length. Moreover \(\mathcal{C}_{K,\mathfrak F_1}(H)\subseteq\mathcal{C}_{K,\mathfrak F_2}(H)\). Thus the feasible path set for \(\mathfrak F_2\) contains the feasible path set for \(\mathfrak F_1\), and the infimum cannot increase. Enlarging the target threshold \(K\) similarly enlarges the feasible endpoint set. The ambient SPD cone contains every admissible restricted path considered in the lower-bound statement, giving \(D_{K,\mathfrak F}\ge D_K\). ◻
Proof of 2. Under the smooth embedded submanifold assumption, admissible paths are exactly absolutely continuous paths in \(\mathcal{S}_\mathfrak F(H)\) from \(S_0\) to \(\mathcal{C}_{K,\mathfrak F}(H)\). The induced length is the ambient affine-invariant length restricted to that submanifold. Hence the infimum is the intrinsic distance to the target. If no path connects the component of \(S_0\) to the target, the intrinsic distance is \(+\infty\). ◻
Proof of 2. Suppose \(\kappa(D^{-1}H)\le K\). Let \[\lambda_{\min}=\min_{v\ne0}\frac{v^\top Hv}{v^\top Dv}.\] Then all generalized Rayleigh quotients lie in \([\lambda_{\min},K\lambda_{\min}]\). With \(E=\lambda_{\min}D\), \[E\preceq H\preceq K E.\] Conversely, if \(E\preceq H\preceq KE\) for a positive diagonal \(E\), then every generalized Rayleigh quotient \(v^\top Hv/v^\top Ev\) lies in \([1,K]\), so \(\kappa(E^{-1}H)\le K\). ◻
Proof of 1. If \(H\) and \(G_0\) are diagonal, then \(S_0=H^{-1/2}G_0H^{-1/2}\) is diagonal. The full SPD projection onto \(\mathcal{C}_K\) keeps the eigenvectors of \(S_0\) and clips only its log-spectrum. Therefore the optimal endpoint and the affine-invariant geodesic from \(S_0\) to that endpoint remain diagonal. The diagonal family contains a full SPD shortest path, and 1 gives equality. ◻
Proof of 3. For \(D(u)=\operatorname{diag}(e^{u/2},e^{-u/2})\), \[\log D(u)=\operatorname{diag}(u/2,-u/2),\] so the diagonal line element is \(ds^2=\frac{1}{2}\,du^2\). Let \[A(u)=D(u)^{-1/2}HD(u)^{-1/2}.\] Since \(\det D(u)=1\), \(\det A(u)=\det H\). If the eigenvalues of \(A(u)\) are \(\mu\le\nu\), the condition \(\nu/\mu\le K\) with fixed product \(\mu\nu=\det H\) is equivalent to \[\mu+\nu\le\left(\sqrt K+\frac{1}{\sqrt K}\right)\sqrt{\det H}=R_K.\] Moreover \[\operatorname{tr}A(u)=H_{11}e^{-u/2}+H_{22}e^{u/2}.\] With \(x=e^{u/2}\), the target condition becomes \[H_{22}x^2-R_Kx+H_{11}\le0.\] When \(K<K_{\operatorname{diag}}^\ast(H)\), the feasible set is empty. Otherwise the roots are \(x_\pm(K)\), the feasible set in \(u\)-coordinates is \([2\log x_-(K),2\log x_+(K)]\), and the one-dimensional distance formula gives the result. ◻
Proof of 4. The proof is identical to 2, replacing the diagonal cone by the block-diagonal cone. If \(\kappa(G^{-1}H)\le K\), take \(E=\lambda_{\min}G\), which is block diagonal. The converse follows from the generalized Rayleigh quotient bound. ◻
Proof of 3. Assume, for contradiction, that there exists \(E\in\mathcal{L}\) with \[H-E\succeq0,\qquad KE-H\succeq0.\] For \(P,Q\succeq0\), \[0 \le \left\langle P,H-E\right\rangle+\left\langle Q,KE-H\right\rangle = \left\langle P-Q,H\right\rangle+\left\langle -P+KQ,E\right\rangle.\] Since \(E\in\mathcal{L}\) and \(\Pi_{\mathcal{L}}(P-KQ)=0\), the last term is zero. Thus any feasible \(E\) would imply \(\left\langle P-Q,H\right\rangle\ge0\), contradicting the strict inequality in the certificate. ◻
Proof of 2. Let \(q\) be a unit eigenvector with \[q^\top(KTHT-H)q<0.\] Set \[Q=qq^\top,\qquad P=K(Tq)(Tq)^\top=KTQT.\] Then \(P,Q\succeq0\). Because \(T\) is a constant sign on each block, \(\Pi_{\mathcal{L}}(TQT-Q)=0\), and hence \[\Pi_{\mathcal{L}}(P-KQ)=K\Pi_{\mathcal{L}}(TQT-Q)=0.\] Moreover, \[\left\langle P-Q,H\right\rangle = q^\top(KTHT-H)q <0.\] 3 proves infeasibility. ◻
Proof of 4. The block Jacobi matrix \(G_{\mathrm{BJ}}\) is feasible in the block family, so the best block condition number is at most the one it achieves. If \(\left\lVert \widetilde{H}-I\right\rVert_{\operatorname{op}}\le\delta<1\), then \[(1-\delta)I\preceq \widetilde{H}\preceq (1+\delta)I,\] which gives the stated condition-number bound. ◻
Proof of 5. The restricted target \[(Y+\mathcal{A}_{\mathrm{kron}})\cap\mathcal{Y}_K\] is a subset of \(\mathcal{Y}_K\). Distance to a subset is at least distance to the full set. If the full projection lies in the restricted target, it attains both distances. ◻
Proof of 6. For \(G=B\otimes A\), \[G^{-1/2}\dot{G}\,G^{-1/2} = Y\otimes I_m+I_n\otimes X.\] Its Frobenius norm squared is \[m\left\lVert Y\right\rVert_F^2+n\left\lVert X\right\rVert_F^2+2\operatorname{tr}(X)\operatorname{tr}(Y),\] which is the displayed formula. For \(X=\alpha I_m\) and \(Y=-\alpha I_n\), the three terms sum to zero. ◻
Proof of 7. Using Kronecker identities, \[G_0^{-1/2}G_1G_0^{-1/2} = (B_0^{-1/2}B_1B_0^{-1/2}) \otimes (A_0^{-1/2}A_1A_0^{-1/2}).\] Taking the logarithm gives \[\log(G_0^{-1/2}G_1G_0^{-1/2}) = L_B\otimes I_m+I_n\otimes L_A.\] The squared Frobenius norm of this matrix is \[m\left\lVert L_B\right\rVert_F^2+n\left\lVert L_A\right\rVert_F^2+2\operatorname{tr}(L_A)\operatorname{tr}(L_B),\] which is the claimed formula. ◻
Proof of 8. In the fixed Kronecker eigenbasis, the eigenvalues of \(X_t\) and \(Y_t\) are \(\dot{\alpha}_i\) and \(\dot{\beta}_j\). By 6, \[\left\lVert \dot{G}_t\right\rVert_{G_t,\mathrm{AI}}^2 = n\sum_i\dot{\alpha}_i^2+ m\sum_j\dot{\beta}_j^2+ 2\left(\sum_i\dot{\alpha}_i\right)\left(\sum_j\dot{\beta}_j\right).\] On the other hand, \[\left\lVert \dot{Z}_t\right\rVert_F^2 = \sum_{i,j}(\dot{\alpha}_i+\dot{\beta}_j)^2,\] which expands to the same expression. ◻
Proof of 5. If \(M=B\otimes A\), then the spectral calculus for Kronecker products gives \[\log M=(\log B)\otimes I_m+I_n\otimes(\log A)\in\mathcal{L}_{m,n}.\] Conversely, if \[\log M=Y\otimes I_m+I_n\otimes X,\] then the two summands commute, and therefore \[M=\exp(Y\otimes I_m)\exp(I_n\otimes X)=\exp(Y)\otimes\exp(X).\] This proves the log characterization.
For the projection formula, decompose \[\mathcal{L}_{m,n} = \operatorname{span}\{I_{mn}\} \oplus \{I_n\otimes X:\operatorname{tr}X=0\} \oplus \{Y\otimes I_m:\operatorname{tr}Y=0\},\] an orthogonal direct sum under the Frobenius inner product. With \[P=\tau I_{mn}+I_n\otimes X_0+Y_0\otimes I_m,\] the definitions of \(\tau,X_0,Y_0\) give \[\operatorname{tr}P=\operatorname{tr}L,\qquad \operatorname{Tr}_B(P)=\operatorname{Tr}_B(L),\qquad \operatorname{Tr}_A(P)=\operatorname{Tr}_A(L).\] Thus \(L-P\) is orthogonal to each component of \(\mathcal{L}_{m,n}\), so \(P=\Pi_{\mathcal{L}}L\). The residual statement follows by applying the log characterization to \(L=\log M\). ◻
Proof of 6. By 5, \(\mathcal{K}_{m,n}=\exp(\mathcal{L}_{m,n})\). The principal matrix logarithm is a global diffeomorphism from \(\mathbb{S}_{++}^{mn}\) to \(\mathbb{S}^{mn}\), and \(\mathcal{L}_{m,n}\) is a linear subspace. Hence \(\mathcal{K}_{m,n}\) is a smooth embedded submanifold. This formulation also removes the factor-scale gauge: different pairs \((X,Y)\) that differ by \((X+\alpha I_m,Y-\alpha I_n)\) represent the same element of \(\mathcal{L}_{m,n}\).
For \(G_i=B_i\otimes A_i\), the affine-invariant geodesic satisfies \[G_0^{-1/2}G_1G_0^{-1/2} = (B_0^{-1/2}B_1B_0^{-1/2}) \otimes (A_0^{-1/2}A_1A_0^{-1/2}).\] Since \(\exp(t\log(P\otimes Q))=P^t\otimes Q^t\) for \(P,Q\succ0\), the ambient geodesic between \(G_0\) and \(G_1\) remains in \(\mathcal{K}_{m,n}\). Hence \(\mathcal{K}_{m,n}\) is totally geodesic.
It is also closed. If \(B_k\otimes A_k\to G\succ0\), fix the gauge \(\det A_k=1\). Uniform lower and upper eigenvalue bounds on \(B_k\otimes A_k\) bound all eigenvalue ratios of \(A_k\); the determinant gauge then bounds the eigenvalues of \(A_k\) above and below, and the product eigenvalue bounds do the same for \(B_k\). Passing to a subsequence gives \(A_k\to A\succ0\) and \(B_k\to B\succ0\), hence \(G=B\otimes A\).
The SPD cone with \(d_{\mathrm{AI}}\) is a Hadamard manifold. Projection onto a closed geodesically convex subset is therefore unique, giving \(G_\star\). For \(G=B\otimes A\), tangent vectors in whitened coordinates are exactly \[Y\otimes I_m+I_n\otimes X\in\mathcal{L}_{m,n}.\] Indeed, every such \(Z\in\mathcal{L}_{m,n}\) generates the curve \(G^{1/2}\exp(tZ)G^{1/2}\in\mathcal{K}_{m,n}\), while differentiating any smooth factor curve \(B_t\otimes A_t\) and whitening by \(G^{-1/2}\) gives an element of this same subspace. Thus the normal space is the Frobenius orthogonal complement of \(\mathcal{L}_{m,n}\) in whitened coordinates. At the projection point, the logarithmic residual \[R_\star=\log(G_\star^{-1/2}MG_\star^{-1/2})\] is orthogonal to every tangent direction. Orthogonality to \(I_n\otimes X\) and \(Y\otimes I_m\) is exactly \[\operatorname{Tr}_B(R_\star)=0,\qquad \operatorname{Tr}_A(R_\star)=0.\] Conversely, these equations give the first-order projection condition on a closed geodesically convex set in a Hadamard manifold, hence the unique projection. The distance formula is the definition of \(d_{\mathrm{AI}}\). ◻
Proof of 3. The equivalence \(V(G)=0\Longleftrightarrow G=P_{\mathcal{K}}(M)\) is the normal equation in 6. The quantitative bounds use that \[f(G)=\frac{1}{2}d_{\mathrm{AI}}(G,M)^2\] is \(1\)-strongly geodesically convex on the totally geodesic Hadamard submanifold \(\mathcal{K}_{m,n}\). Let \(G_\star=P_{\mathcal{K}}(M)\), \(v=\operatorname{Log}_G(G_\star)\), and \(d=\left\lVert v\right\rVert=d_{\mathrm{AI}}(G,G_\star)\). Strong convexity along the geodesic from \(G\) to \(G_\star\) gives \[f(G)-f(G_\star)\le \left\lVert V(G)\right\rVert_Fd-\frac{1}{2}d^2.\] Strong convexity at the minimizer gives \[f(G)-f(G_\star)\ge\frac{1}{2}d^2.\] Combining the inequalities yields \(d\le\left\lVert V(G)\right\rVert_F\), and maximizing \(\left\lVert V(G)\right\rVert_Fd-d^2/2\) over \(0\le d\le\left\lVert V(G)\right\rVert_F\) gives the objective-gap bound. ◻
Proof of 4. If \(G_r=B_r\otimes A_r\), then \(V_r\in\mathcal{L}_{m,n}\) has the form \[V_r=Y_r\otimes I_m+I_n\otimes X_r.\] The two summands commute, so \(\exp(\eta V_r)=\exp(\eta Y_r)\otimes \exp(\eta X_r)\), and the trial point remains in \(\mathcal{K}_{m,n}\).
Let \(G_\star=P_{\mathcal{K}}(M)\). The objective \[f(G)=\frac{1}{2}d_{\mathrm{AI}}(G,M)^2\] is geodesically convex on the totally geodesic Hadamard submanifold \(\mathcal{K}_{m,n}\), and its restricted negative gradient is represented in whitened coordinates by \(V(G)=\Pi_{\mathcal{L}}R_G(M)\). The initial sublevel set \(\{G\in\mathcal{K}_{m,n}:f(G)\le f(G_0)\}\) is closed and bounded in the complete finite-dimensional Hadamard submanifold \(\mathcal{K}_{m,n}\), hence compact by Hopf–Rinow. On a compact enlargement of this sublevel set, smoothness of the squared-distance objective away from no singularities in the SPD cone gives a bounded Lipschitz restricted gradient; this is the standard setting for Armijo backtracking on matrix manifolds [31], [32]. The geodesic descent lemma therefore implies that sufficiently small positive step sizes satisfy the Armijo inequality, uniformly over the sublevel set. Hence backtracking terminates and the accepted step sizes have a positive lower bound \(\eta_{\min}>0\).
Armijo decrease gives \[f(G_{r+1})\le f(G_r)-c\eta_r\left\lVert V_r\right\rVert_F^2.\] Thus \(f(G_r)\) decreases and \(\sum_r\eta_r\left\lVert V_r\right\rVert_F^2<\infty\). Since \(\eta_r\ge\eta_{\min}\), we have \(\left\lVert V_r\right\rVert_F\to0\). Any cluster point \(\bar G\) in the compact sublevel set satisfies \(V(\bar G)=0\), hence \(\bar G=G_\star\) by 3. The cluster point is unique, so the full sequence converges to \(G_\star\).
For the rate, set \[\underline\eta=\min\{\eta_{\min},(2c)^{-1}\}.\] 3 gives \[\left\lVert V_r\right\rVert_F^2\ge2\bigl[f(G_r)-f(G_\star)\bigr].\] Combining this with Armijo decrease and \(\eta_r\ge\underline\eta\) yields \[f(G_{r+1})-f(G_\star) \le (1-2c\underline\eta)\bigl[f(G_r)-f(G_\star)\bigr],\] and iteration proves the displayed bound. ◻
Proof of 7. For the self-conditioned metric target, the condition-number set \(\mathcal{C}_K\) is closed and geodesically convex because the weighted matrix geometric mean satisfies \[\lambda_{\max}(S_0\#_tS_1) \le \lambda_{\max}(S_0)^{1-t}\lambda_{\max}(S_1)^t\] and the analogous lower bound for \(\lambda_{\min}\). Together with 6, this makes \(\mathcal{K}_{m,n,K}=\mathcal{K}_{m,n}\cap\mathcal{C}_K\) closed and geodesically convex.
The two displayed distance bounds are the Hadamard Pythagorean inequality for projection onto \(\mathcal{K}_{m,n}\), followed by the triangle inequality through \(G_\star=P_{\mathcal{K}}(M)\).
It remains to prove the QP formula. For \(B\otimes A\), \[\kappa(B\otimes A)=\kappa(B)\kappa(A),\] so the target condition is \[(x_m-x_1)+(y_n-y_1)\le\log K\] for sorted log-eigenvalues \(x_i\) of \(A\) and \(y_j\) of \(B\). By 7, the squared distance between Kronecker products is \[n\,d_{\mathrm{AI}}(A_0,A)^2+m\,d_{\mathrm{AI}}(B_0,B)^2 +2(\log\det A-\log\det A_0)(\log\det B-\log\det B_0).\] The eigenvalue lower bound for the affine-invariant metric and Hoffman–Wielandt give \[d_{\mathrm{AI}}(A_0,A)^2\ge\sum_i(x_i-a_i)^2,\qquad d_{\mathrm{AI}}(B_0,B)^2\ge\sum_j(y_j-b_j)^2.\] The determinant terms are the corresponding sums of log-eigenvalue differences. Expanding gives the lower bound \[\sum_{i,j}(x_i+y_j-a_i-b_j)^2.\] Equality is attained by choosing \(A\) and \(B\) with the same eigenvectors as \(A_0\) and \(B_0\), proving the convex QP. ◻
Proof of 8. For any \(G\succ0\), \[\kappa(G^{-1}H) = \kappa(H^{-1/2}GH^{-1/2}),\] because \(G^{-1}H\) is similar to \(H^{1/2}G^{-1}H^{1/2}=(H^{-1/2}GH^{-1/2})^{-1}\), and a positive-definite matrix and its inverse have the same spectral condition number. Thus \(G\in\mathcal{R}_{K,\mathcal{K}}(H)\) if and only if \(H^{-1/2}GH^{-1/2}\in\mathcal{C}_{K,\mathcal{K}}(H)\), proving the equivalence of the first two items.
For fixed \(G\succ0\), the condition \(\kappa(G^{-1}H)\le K\) is equivalent to the existence of \(\lambda>0\) such that \[\lambda G\preceq H\preceq K\lambda G.\] Indeed, take \[\lambda=\lambda_{\min}(G^{-1/2}HG^{-1/2})\] for the forward implication, and use generalized Rayleigh quotients for the reverse implication. Setting \(G=B\otimes A\) gives the Kronecker Loewner sandwich. The scalar \(\lambda\) can be absorbed into \(A\) or \(B\), giving the scale-free form.
It remains to identify the distance. The target can be written as \[\mathcal{R}_{K,\mathcal{K}}(H) = \mathcal{K}_{m,n}\cap H^{1/2}\mathcal{C}_KH^{1/2}.\] The set \(\mathcal{C}_K\) is closed and geodesically convex, and congruence by \(H^{1/2}\) is an affine-invariant isometry, so \(H^{1/2}\mathcal{C}_KH^{1/2}\) is also closed and geodesically convex. Intersecting with the closed totally geodesic submanifold \(\mathcal{K}_{m,n}\) gives a closed geodesically convex subset of the Kronecker manifold. The Kronecker manifold is a complete Hadamard submanifold under the induced affine-invariant metric, so projection onto this nonempty closed geodesically convex subset exists and is unique.
Finally, congruence by \(H^{-1/2}\) maps paths in \(\mathcal{K}_{m,n}\) isometrically to paths in \(\mathcal{S}_{\mathcal{K}}(H)\). Therefore the intrinsic distance from \(S_0\) to \(\mathcal{C}_{K,\mathcal{K}}(H)\) equals the affine-invariant distance from \(G_0\) to \(\mathcal{R}_{K,\mathcal{K}}(H)\). By 2, this is exactly \(D_{K,\mathcal{K}}(S_0;H)\). ◻
Proof of 5. The objective \(\kappa(G^{-1}H)\) is invariant under positive rescaling of \(G\). Hence a minimizing sequence in \(\mathcal{K}_{m,n}\) can be rescaled to satisfy \(\det G=\det H\). Let \[S=H^{-1/2}GH^{-1/2}.\] On this determinant gauge, \(\det S=1\). Since the sequence has bounded condition number, the eigenvalues of \(S\) are uniformly bounded above and below. Thus the corresponding sequence of \(S\)’s has a convergent subsequence, and so does the sequence \(G=H^{1/2}SH^{1/2}\). The family \(\mathcal{K}_{m,n}\) is closed by 6, so the limit remains Kronecker and attains the minimum.
The equivalence \[\mathcal{R}_{K,\mathcal{K}}(H)\ne\emptyset \quad\Longleftrightarrow\quad K\ge K_{\mathcal{K}}^\star(H)\] is then immediate from the definition of \(K_{\mathcal{K}}^\star(H)\). ◻
Proof of 9. For \[G=(V\operatorname{diag}(e^{b_j})V^\top)\otimes(U\operatorname{diag}(e^{a_i})U^\top),\] the matrices \(H\) and \(G\) commute in the basis \(V\otimes U\), and the eigenvalues of \(G^{-1}H\) are \[\exp(\ell_{ij}-a_i-b_j).\] Therefore \[\log\kappa(G^{-1}H) = \max_{i,j}(\ell_{ij}-a_i-b_j) - \min_{i,j}(\ell_{ij}-a_i-b_j).\] The condition \(\kappa(G^{-1}H)\le K\) is thus equivalent to the existence of a scalar \(c\) such that all residual log-eigenvalues lie in \([c,c+\log K]\), which is exactly the displayed linear feasibility problem. Minimizing the residual width over \(a,b\) gives the fixed-basis threshold formula. Since \(\mathcal{K}_{U,V}\subset\mathcal{K}_{m,n}\), feasibility in the subfamily is a full-family primal certificate; subfamily infeasibility gives no full-family obstruction. ◻
Proof of 10. The matrix \[S_c^{-1}=H^{1/2}G_c^{-1}H^{1/2}\] has the same eigenvalues as \(G_c^{-1}H\), so \(\kappa(S_c)=\kappa(G_c^{-1}H)\). Hence the displayed condition is exactly membership of \(S_c\) in \(\mathcal{C}_K\), and \(S_c\in\mathcal{C}_{K,\mathcal{K}}(H)\).
By 6, \(\mathcal{K}_{m,n}\) is totally geodesic in the ambient affine-invariant SPD cone. Therefore the affine-invariant geodesic from \(G_0\) to \(G_c\) remains in \(\mathcal{K}_{m,n}\) and has length \(d_{\mathrm{AI}}(G_0,G_c)\). Congruence by \(H^{-1/2}\) is an isometry for the affine-invariant metric, so the relative path \[S_t=H^{-1/2}G_tH^{-1/2}\] is an admissible path in \(\mathcal{S}_{\mathcal{K}}(H)\) from \(S_0\) to the target point \(S_c\) with the same length. Taking the infimum over all admissible paths gives \[D_{K,\mathcal{K}}(S_0;H)\le d_{\mathrm{AI}}(G_0,G_c).\] The closed-form expression for the right-hand side is 7. The last statement is only the logical one-way nature of a sufficient certificate. ◻
Proof of 11. The objective gradient at \(Q\), in whitened coordinates and restricted to \(\mathcal{L}_{m,n}\), is \(-\Pi_{\mathcal{L}}R_Q(M)\). For the path \[Q(t)=Q^{1/2}\exp(tZ)Q^{1/2},\] the directional derivative of \(\log\lambda_{\max}\) is \[\max_{\substack{u\in E_{\max}\\ \left\lVert u\right\rVert=1}}u^\top Zu,\] and the directional derivative of \(\log\lambda_{\min}\) is \[\min_{\substack{v\in E_{\min}\\ \left\lVert v\right\rVert=1}}v^\top Zv.\] Thus the directional derivative of \(\omega=\log\lambda_{\max}-\log\lambda_{\min}\) is the support function of the stated subdifferential. Since \(K>1\) has the strict feasible point \(I_{mn}\), the convex KKT condition on the tangent Hadamard submanifold gives \[0\in-\Pi_{\mathcal{L}}R_\star+\mu\Pi_{\mathcal{L}}\partial\omega(Q_\star), \qquad \mu\ge0,\] with complementarity. This is the displayed equation; inactive constraints have \(\mu=0\). ◻
Proof of 12. Projection onto the closed geodesically convex family \(\mathcal{K}_{m,n}\) satisfies the Hadamard Pythagorean inequality. Applying it to \[H_t,\qquad P_t=P_{\mathcal{K}}(H_t),\qquad G_t\in\mathcal{K}_{m,n}\] gives \(E_t^2\ge M_t^2+A_t^2\). Applying 7 with \(M=H_t\) and \(G_\star=P_t\) gives the two-sided self-conditioned \(K\)-target bound. The computability statements are exactly 6 7 7. ◻
Proof of 14. From \[(1-\varepsilon)H\preceq \widehat H\preceq (1+\varepsilon)H\] we obtain \[\frac{1}{1+\varepsilon} \frac{v^\top\widehat H v}{v^\top Gv} \le \frac{v^\top H v}{v^\top Gv} \le \frac{1}{1-\varepsilon} \frac{v^\top\widehat H v}{v^\top Gv}.\] Taking minima and maxima over nonzero \(v\) gives the bound on generalized condition numbers. ◻
Proof of 15. On the proxy event, 14 implies that reaching \(\kappa(G_T^{-1}\widehat H_T)\le \widehat K\) certifies \(\kappa(G_T^{-1}H)\le K\). By assumption, the adapted controller has length at most \(B\) on the same event. This event has probability at least \(1-\delta\), so \(B\) is feasible in the definition of \(D_{K,\mathfrak F}^{\mathrm{stoch}}(S_0;H,\delta)\). ◻
Proof of 16. Each exponential update is the affine-invariant geodesic segment from \(G_k\) to \(G_{k+1}\) with length \(\ell_k\). Congruence by \(H^{-1/2}\) is an isometry for the affine-invariant metric, so the relative path \(S_t=H^{-1/2}G_tH^{-1/2}\) has the same length. Concatenating the relative segments gives an ambient SPD path from \(S_0\) to \(S_N=H^{-1/2}G_NH^{-1/2}\). If \(\kappa(G_N^{-1}H)\le K\), then \(S_N\in\mathcal{C}_K\), so the total length is at least the full SPD distance \(D_K(S_0)\). If the concatenated or substituted interpolation remains inside \(\mathfrak F\) and ends in \(\mathcal{C}_{K,\mathfrak F}(H)\), the corresponding relative path is an admissible restricted path, so its length is at least \(D_{K,\mathfrak F}(S_0;H)\). ◻
Proof of 9. The identity is obtained by multiplying and dividing \(\operatorname{Len}_{\mathrm{alg}}/D_K(S_0)\) by the three intermediate positive quantities \[D_{K,\mathfrak F}(S_0;H),\qquad D_{\widehat K,\mathfrak F}(\widehat S_0;\widehat H),\qquad \operatorname{Len}_{\mathrm{cont}}.\] ◻
Proof of 17. The expression ratio is at least one by 1. The estimation statement is exactly the displayed hypothesis; in the special case \(\widehat H=H\), \(\widehat S_0=S_0\), and \(\widehat K\le K\), it follows from monotonicity in the condition-number threshold. The flow statement follows from the definition of \(D_{\widehat K,\mathfrak F}(\widehat S_0;\widehat H)\) as the infimum over all admissible continuous paths to the proxy target. The discretization statement is the assumed length comparison between the implemented path and the chosen continuous reference path. ◻
Let \[\mathcal{Y}_{K,r}(y) = \{z\in\mathcal{Y}_K:\exists c\in\mathbb{R},\;|\{i:z_i\ne y_i+c\}|\le r\}.\] Then \[D_{K,r}^{\mathrm{spec}}(y) = \operatorname{dist}_{\ell^2}(y,\mathcal{Y}_{K,r}(y)).\]
Proof of 13. If \(r_1\le r_2\), then \[\mathcal{Y}_{K,r_1}(y)\subseteq \mathcal{Y}_{K,r_2}(y)\subseteq \mathcal{Y}_K,\] and therefore \[D_{K,r_1}^{\mathrm{spec}}(y) \ge D_{K,r_2}^{\mathrm{spec}}(y) \ge D_K(y).\] When \(r\ge d\), the low-rank restriction disappears and equality with \(D_K(y)\) holds. ◻