Optimal Diagonal Preconditioning Beyond Worst-Case Conditioning: Theory and Practice of Omega Scaling

Saeed Ghadimi; Woosuk L. Jung; Arnesh Sujanani; David Torregrosa-Belén; Henry Wolkowicz

math.OCSep 27, 2025

Optimal Diagonal Preconditioning Beyond Worst-Case Conditioning: Theory and Practice of Omega Scaling

Authors: Saeed Ghadimi, Woosuk L. Jung, Arnesh Sujanani, David Torregrosa-Belén, Henry Wolkowicz

Organizations: Department of Management Science and Engineering, University of Waterloo, ON, Canada · Department of Combinatorics and Optimization, University of Waterloo, ON, Canada · Department of Mathematics, University of Alicante, Alicante, Spain

Abstract

We study optimal diagonal preconditioning using the classical worst-case $κ$ -condition number and the averaging-based $ω$ -condition number. For the $κ$ -optimal preconditioning problem, we derive an affine-based pseudoconvex reformulation with three key advantages: all stationary points are global minima, subgradients are inexpensive to compute, and the optimization variable is an $n$ -dimensional vector rather than an $n\times n$ matrix as in semidefinite programming (SDP) approaches. We develop a simple and highly efficient subgradient method, with convergence guarantees, for solving this pseudoconvex formulation that is substantially more scalable and accurate than existing SDP-based methods. For the $ω$ -condition number, we provide explicit characterizations of optimal diagonal and block diagonal preconditioners. In particular, we show that several classical preconditioners, including Jacobi and row/column normalization, are $ω$ -optimal, and that matrix balancing schemes monotonically reduce $ω$ and converge to stationary points of the two-sided problem. To the best of our knowledge, this is the first unified and explicit characterization of optimality conditions for both $κ$ and $ω$ -based preconditioning. Our numerical experiments further reveal a striking phenomenon: although $κ$ -optimal preconditioners achieve stronger reductions in the worst-case condition number, $ω$ -optimal preconditioners are substantially cheaper to compute and yield better performance for iterative methods such as preconditioned conjugate gradient (PCG) and least squares method (LSQR). Moreover, applying $ω$ -optimal scaling to linear systems that are already $κ$ -optimally preconditioned leads to further improvements in PCG iterations.

Figures & tables

s_{k}=\frac{\lambda_{1}^{k}}{\lambda_{n}^{k}}\left(\frac{1}{\langle x_{1}^{k},d_{k}\bullet x_{1}^{k}\rangle}\left(x_{1}^{k}\bullet x_{1}^{k}\right)-\frac{1}{\langle x_{n}^{k},d_{k}\bullet x_{n}^{k}\rangle}\left(x_{n}^{k}\bullet x_{n}^{k}\right)\right);

(2.9)

Algorithm 2.1 A Subgradient Method for Minimizing

\kappa(d)

over

\Omega

g_{k}=\frac{\lambda_{1}^{k}}{\lambda_{n}^{k}}V^{T}\left(\frac{1}{\langle x_{1}^{k},w_{k}\bullet x_{1}^{k}\rangle}\left(x_{1}^{k}\bullet x_{1}^{k}\right)-\frac{1}{\langle x_{n}^{k},w_{k}\bullet x_{n}^{k}\rangle}\left(x_{n}^{k}\bullet x_{n}^{k}\right)\right)

(2.22)

Algorithm 2.2 A Subgradient Method for Minimizing

\kappa(v):=\kappa(\cVo(v))

over

\hat{\Omega}

Special Structure	Preconditioner	Location	Literature
Right Diagonal	Column Normalization	Proposition 3.1	[ 7 , 8 ]
Diagonal for Symmetric $M\succ 0$	Jacobi Preconditioner	Corollary 3.2	[ 17 ]
Left Diagonal	Row Normalization	Theorem 3.3
Two-Sided Diagonal	Sinkhorn-Knopp/Matrix Balancing	Theorem 3.6	[ 29 , 22 , 28 ]
Right Block-Diagonal	Block QR	Corollary 3.10	[ 18 , 8 ]
Left Block-Diagonal	Characterization	Theorem 3.11

Table 3.1: Relation of

\omega

-Optimal Preconditioners to the Literature

\hat{C}^{1/2}:=\Diag\left(\prod_{j=1}^{k}\sqrt{c_{j}}\right)\text{ and }\hat{D}^{1/2}:=\Diag\left(\prod_{j=1}^{k}\sqrt{d_{j}}\right).

Algorithm 3.1 Square-Root Sinkhorn-Knopp Algorithm for Two Sided

\omega

-Optimal Preconditioner

Dim & Density, & $\kappa(M)$			% Reduction in $\kappa$				CPU Time (seconds)				CPU Ratios
$n$	density	$\kappa(M)$	[ 25 ]	[ 11 ]	Algorithm 2.2	Algorithm B.1	[ 25 ]	[ 11 ]	Algorithm 2.2	Algorithm B.1	[ 25 ] / Algorithm 2.2	[ 25 ] / Algorithm B.1
1074	1.1e-02	2.6e+07	0.0e+00	0.0e+00	9.9e+01	9.9e+01	48.203	51.700	8.469	5.644	5.7	8.5
2003	2.1e-02	1.1e+10	0.0e+00	0.0e+00	9.8e+01	6.8e+01	330.887	324.334	12.968	0.120	25.5	2752.3
3600	2.1e-03	1.8e+07	0.0e+00	0.0e+00	6.0e+01	6.0e+01	510.244	1102.270	24.644	9.538	20.7	53.5
3134	4.6e-03	2.6e+12	-9.7e-04	0.0e+00	7.5e+01	7.0e+01	178.360	1347.551	2.542	0.410	70.2	435.3
3562	1.3e-02	1.9e+11	0.0e+00	0.0e+00	8.6e+01	7.8e+01	1621.648	948.059	36.940	1.694	43.9	957.4

Table 4.1: Comparison of Algorithms for Min

\kappa

on SuiteSparse

Dim & Density, & $\kappa(A)$			% Reduction in $\kappa$				CPU Time (seconds)				CPU Ratios
$n$	density	$\kappa(M)$	[ 25 ]	[ 11 ]	Algorithm 2.2	Algorithm B.1	[ 25 ]	[ 11 ]	Algorithm 2.2	Algorithm B.1	[ 25 ] / Algorithm 2.2	[ 25 ] / Algorithm B.1
2000	1.0e-03	2.0e+06	-4.8e+01	4.8e+01	5.3e+01	6.6e+01	14.498	76.446	4.470	1.154	3.2	12.6
2500	8.1e-04	2.5e+06	-5.0e+01	2.9e+01	5.2e+01	5.2e+01	21.500	229.744	9.068	1.233	2.4	17.4
3000	6.7e-04	3.0e+06	-1.8e+01	0.0e+00	1.9e+01	1.3e+01	32.757	358.866	5.011	0.476	6.5	68.8
3500	5.8e-04	3.5e+06	-1.9e+01	2.5e+01	4.3e+01	4.9e+01	43.032	565.527	8.757	1.961	4.9	21.9
4000	5.0e-04	4.0e+06	-4.4e+01	0.0e+00	2.8e+01	6.3e+00	56.246	631.303	11.281	0.519	5.0	108.4

Table 4.2: Comparison of Algorithms for Min

\kappa

on Random

Dim & Density, & $\kappa(M)$			% Reduction in $\kappa$		CPU Time
$n$	density	$\kappa(M)$	Algorithm 2.2	Algorithm B.1	Algorithm 2.2	Algorithm B.1
14822	3.3e-03	2.0e+06	3.9e+01	3.0e+01	7.850	283.641
15439	1.1e-03	4.4e+12	8.0e+01	7.2e+01	8.734	2.185
15439	6.5e-05	6.1e+09	4.2e+01	5.4e+01	2.283	2.725
17361	1.1e-03	2.5e+06	1.3e+01	1.2e+01	1.097	9.086
17361	3.4e-03	1.1e+09	5.6e+01	3.0e+01	19.675	9.306

Table 4.3: Comparison of Algorithms for Min

\kappa

on Large SuiteSparse

Dim & Density, & $\kappa(M)$			% Reduction in $\kappa$		CPU Time
$n$	density	$\kappa(M)$	Algorithm 2.2	Algorithm B.1	Algorithm 2.2	Algorithm B.1
50000	3.8e-05	1.0e+11	1.7e+01	7.7e+00	244.577	74.798
60000	3.2e-05	1.2e+11	1.5e+01	6.5e+00	400.467	103.404
70000	2.7e-05	1.4e+11	1.4e+01	5.6e+00	492.698	123.284
80000	2.4e-05	1.6e+11	1.1e+01	5.0e+00	436.111	198.894
90000	2.1e-05	1.8e+11	1.0e+01	4.3e+00	550.245	223.299

Table 4.4: Comparison of Algorithms for Min

\kappa

on Large Random

Dim, Density, & $\kappa(A)$			% Reduction in $\kappa$		PCG Iterations		PCG CPU Time		Total CPU Time
$n$	density	$\kappa(M)$	[ 25 ]	Algorithm B.1	[ 25 ]	Algorithm B.1	[ 25 ]	Algorithm B.1	[ 25 ]	Algorithm B.1
1000	3.3e-03	1.0e+09	-2.6e+01	3.6e+01	115264	99023	1.14	0.99	5.33	1.29
1300	2.5e-03	1.3e+09	-2.6e+01	6.0e+01	153760	101197	1.89	1.23	8.41	1.49
1600	2.0e-03	1.6e+09	-4.3e+01	-1.0e-13	180929	179469	2.67	2.67	12.17	2.71
1900	1.7e-03	1.9e+09	-3.5e+01	6.9e+01	202276	121629	3.43	2.07	16.17	2.87
2200	1.4e-03	2.2e+09	-4.9e+01	7.1e+01	245521	126567	4.82	2.50	21.54	3.39

Table 4.5: PCG Comparison Using Preconditioners Found by Algorithm in [ 25 ] and Algorithm B.1

Dim & Density, & $\kappa(A)$			Ratio of Condition Numbers		CPU Time for Prec		LSQR Iterations		Total CPU Time
$n$	density	$\kappa(A)$	$\kappa(S)/\kappa(T)$	$\omega(S)/\omega(T)$	Algorithm 3.1	[ 25 ]	Algorithm 3.1	[ 25 ]	Algorithm 3.1	[ 25 ]
300	6.6e-03	5.2e+03	1.3e+00	1.0e+00	0.006	23.358	5	4	0.015	23.36
130	6.1e-02	6.1e+10	1.1e-01	8.2e-01	0.002	27.943	9	35	0.005	27.95
200	2.0e-02	2.4e+03	1.0e+00	1.0e+00	0.000	19.308	750	756	0.022	19.32
104	9.2e-02	5.5e+03	1.6e+00	9.7e-01	0.001	10.056	301	288	0.004	10.06
216	9.3e-02	3.3e+04	8.9e-01	4.6e-01	0.002	309.028	56	175	0.004	309.03

Table 4.6: LSQR Comparison on Small Suitesparse Matrices: Algorithm 3.1 vs [ 25 ]

Dim & Density, & $\kappa(A)$			Ratio of Condition Numbers		CPU Time for Prec		LSQR Iterations		Total CPU Time
$n$	density	$\kappa(A)$	$\kappa(S)/\kappa(T)$	$\omega(S)/\omega(T)$	Algorithm 3.1	[ 25 ]	Algorithm 3.1	[ 25 ]	Algorithm 3.1	[ 25 ]
50	2.5e-01	1.0e+03	1.2e+00	9.4e-01	0.007	16.583	18	18	0.02	16.59
60	2.4e-01	1.0e+03	5.2e+00	5.1e-01	0.001	11.914	46	67	0.01	11.92
70	2.3e-01	1.1e+03	1.4e+00	8.3e-01	0.001	17.909	22	27	0.00	17.91
80	2.2e-01	1.1e+03	2.0e+00	2.6e-01	0.002	13.848	51	191	0.00	13.85
90	2.2e-01	1.2e+03	2.2e+00	5.0e-01	0.002	18.674	43	90	0.00	18.68

Table 4.7: LSQR Comparison on Small Random Matrices: Algorithm 3.1 vs [ 25 ]

Dim & Density, & $\omega(A)$			Ratio of Omega & Prec CPU Time		LSQR Iter		Total CPU Time
$n$	density	$\omega(A)$	$\omega(S)/\omega(A)$	Algorithm 3.1 CPU	No Prec	Algorithm 3.1	No Prec	Algorithm 3.1
14214	1.3e-03	5.1e+01	3.2e-02	1.0e-01	100000	8963	3.63e+01	3.43e+00
4119	2.1e-03	4.1e+05	3.6e-06	1.7e-02	5461	946	4.98e-01	1.04e-01
7479	1.2e-03	2.8e+04	4.8e-05	3.0e-02	9393	1758	1.85e+00	3.81e-01
9271	1.4e-03	8.2e+06	1.7e-07	4.1e-02	1798	377	4.44e-01	1.37e-01
4562	6.3e-03	2.3e+02	7.4e-03	1.3e-02	6497	1070	1.11e+00	2.00e-01

Table 4.8: LSQR Comparison on Large Suitesparse Matrices: Algorithm 3.1 vs No Preconditioning

Dim & Density		Ratios in conds $(J,M)$		$J$ : $\omega$ -opt of $M$		Ratios M/J
$n$	density	$\kappa(J)/\kappa(M)$	$\omega(J)/\omega(M)$	iters	cpu	iters	cpu
5000	9.40e-03	2.98e+00	7.368e-01	19.4	3.927e-03	25.2	13.9
10000	7.44e-03	3.31e+00	7.362e-01	18.8	6.698e-03	36.6	30.5
15000	6.02e-03	2.64e+00	7.365e-01	17.0	1.418e-02	41.6	39.0
20000	4.57e-03	3.56e+00	7.363e-01	20.6	2.861e-02	41.6	41.1
25000	3.47e-03	3.71e+00	7.370e-01	20.6	8.006e-02	30.9	29.1

Table 4.9: PCG tol.

1e\!-\!7

; Medium;

\kappa

-opt VS

J,\omega

-opt of

M

Dim & Density		Ratios in conds $(J,M)$		$J$ : $\omega$ -opt of $M$		Ratios M/J
$n$	density	$\kappa(J)/\kappa(M)$	$\omega(J)/\omega(M)$	iters	cpu	iters	cpu
50000	9.05e-03	3.26e+00	7.366e-01	15.6	3.332e-01	48.7	42.5
52000	8.17e-03	4.34e+00	7.362e-01	20.8	4.245e-01	51.7	46.9
54000	7.49e-03	3.55e+00	7.365e-01	17.0	3.578e-01	47.5	42.4
56000	6.71e-03	3.73e+00	7.363e-01	18.0	3.672e-01	57.1	51.0
58000	5.98e-03	3.33e+00	7.369e-01	16.8	3.367e-01	38.5	34.1

Table 4.10: PCG tol.

1e\!-\!7

; Large;

\kappa

-opt VS

J,\omega

-opt of

M

Matrix Optimization

Matrix optimization develops methods for optimizing matrix-valued variables with structure such as low rank, sparsity, positivity, or orthogonality.

See all 58 papers

Restricted Dynamic Geometric Complexity: Path-Space Reduction and Möbius--Jacobi Response
Jul 8, 2026Zavier LiRiemannian Optimization Constrained Optimization
Xidian University, Xi’an, China
Dual Space Preconditioning for Gradient Descent in the Overparameterized Regime
Mar 11, 2026Reza Ghane, Danil Akhtiamov, Babak HassibiGradient Descent Implicit Bias
Electrical Engineering Department, California Institute of Technology, Pasadena, CA 91125 USA · Computing + Mathematical Sciences Department, California Institute of Technology, Pasadena, CA 91125 USA
Optimal Projection-Free Adaptive SGD for Matrix Optimization
Apr 2, 2026Dmitry KovalevAdaptive Gradient Methods Matrix Optimization
Yandex Research

Jul 8, 2026J/K move · Enter open · S save

Restricted Dynamic Geometric Complexity: Path-Space Reduction and Möbius--Jacobi Response

Zavier Li

Xidian University, Xi’an, China

Riemannian Optimization Constrained Optimization

Open paper AskPDF arXiv

Structured preconditioners restrict optimization to a small family of positive metrics, but endpoint condition-number reachability does not measure the geometric effort required to reach a useful metric. We formulate this effort as a path-space value problem. Restricted dynamic geometric complexity is the least affine-invariant length of an admissible metric path whose endpoint reaches a Hessian-relative generalized-eigenvalue condition target. Path elimination gives an exact min-plus semigroup and Bellman principle, while fixed-horizon kinetic energy is exactly squared complexity divided by twice the horizon. The main response result is global on a Hadamard state space: geodesic convexity produces a smooth intervention-cube path branch and a uniformly coercive Jacobi form, while one Green inverse generates the value Hessian, two-sided force-to-curvature bounds, exact Möbius effects, and arbitrary prescribed finite-order responses. For the hard condition target, a bordered Jacobi--KKT theorem differentiates the moving projection endpoint and multiplier on every regular active spectral stratum; its indefinite inverse also explains why hard-target interactions need not share the unconstrained sign. The theory specializes to affine-invariant positive-definite geometry. A determinant-one two-dimensional diagonal model has an exact target interval, a closed-form forced path, and a strictly negative-definite interaction matrix. A moving diagonal Hessian gives a closed-form hard-target projection, multiplier, and pair effects of either sign, while a coordinate-sequential three-dimensional protocol yields an exact path metric strictly larger than the ambient projection distance. Thus the global Green and bordered hard-target responses are explicit laws of restricted metric-path elimination built on Bellman composition.

Abstract

Matrix Optimization

Explore similar work

Restricted Dynamic Geometric Complexity: Path-Space Reduction and Möbius--Jacobi Response

Dual Space Preconditioning for Gradient Descent in the Overparameterized Regime

Optimal Projection-Free Adaptive SGD for Matrix Optimization