REVIEW 6 minor 22 references
A geodesic convexity-like structure for the polar decomposition of a square matrix
T0 review · 0 major / 6 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read This paper shows the orthogonal Procrustes problem—equivalently, computing the polar factor of a square matrix—satisfies a weak-quasi-strong-convexity inequality along geodesics, yielding linear convergence of Riemannian gradient descent…
desk verdict A solid theory paper: proves a convexity-like inequality for the Procrustes problem with linear convergence of Riemannian GD, caveated by a local initialization bound. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the weak-quasi-strong-convexity (WQSC) inequality on the orthogonal group, assembled from Proposition 3 (geodesic weak-quasi-convexity) and Proposition 4 (quadratic growth). The proof machinery is the canonical form of the relative rotation X^T X* = P D P^T, which diagonalizes the Riemannian logarithm as P skew(D) (phi/sin phi) P^T and reduces the key trace inequality to verifying that the diagonal matrix phi/sin phi - D^T (phi/sin phi) D + c(D^T - I) is positive semidefinite block-wise, with c = 1 + cos(|r|max). This block structure is what turns a global non-convex landscape into a locally convex-on-geodesics one.
What would settle it
Run Riemannian gradient descent on f(X) = -Tr(C^T X) for C = diag(1, 2) on O(2), starting from X0 a rotation by angle $\theta$ with dist(X0, I) < pi (e.g., $\theta$ = 0.5), using step size eta exactly at the theorem's bound, and measure the squared-distance contraction over many iterations; if the observed contraction factor ever exceeds the predicted (1 - (1/$pi^{2}$)(1+cos(dist0))*sigma_min(C)*eta), the central rate claim is refuted.
Extended reading notes
Core claim
The central discovery is that the orthogonally constrained objective f(X) = -Tr(C^T X) obeys a weak-quasi-strong-convexity (WQSC) inequality: for every X with |r|max < pi, f(X) - f* <= (1/a(X))<grad f(X), -log_X(X*)> - (mu/2) $dist^{2}$(X, X*), where a(X) = (1+cos|r|max)/4 and mu = 4*sigma_min(C)/$pi^{2}$. This inequality combines a geodesic weak-quasi-convexity lower bound on the inner product between the gradient and the logarithm map with a quadratic-growth lower bound on the objective gap. The paper derives both from the canonical form of the orthogonal matrix X^T X*, reducing the argument to trace inequalities on 2x2 rotation blocks. With this structure in hand, the authors prove an explicit linear convergence theorem for Riemannian gradient descent: starting at any X0 with dist(X0, X*) < pi and using step size eta <= (1+cos(dist(X0,X*)))/(4*sigma_max(C)), the squared distance to the polar factor contracts by the factor (1 - (1/$pi^{2}$)(1+cos(dist(X0,X*)))*sigma_min(C)*eta) at each iteration when C is invertible.
Load-bearing premise
The initialization must lie within a geodesic distance strictly less than pi of the optimal polar factor; if the starting orthogonal matrix is further away, or in the other connected component of O(n), the key positive parameter a(X) can degenerate and the convergence proof no longer applies.
Editorial extensions
If this is right
- For invertible C and an initialization closer than pi to the polar factor, fixed-step Riemannian gradient descent on O(n) contracts the squared distance to the optimum at a linear rate with an explicitly computable contraction factor.
- For singular C the same algorithm retains an O(1/t) bound on the objective gap, so the approach covers the full range of square matrices.
- The convexity-like constants are expressed directly in the singular values of C, making the convergence theory applicable as an a priori complexity certificate for first-order methods on the polar factor problem.
- The analysis extends the WQSC framework previously used for the symmetric eigenvalue problem to a second fundamental matrix factorization, suggesting a common structural explanation for the tractability of these problems.
Reading between the lines
- A direct implication is that any first-order method respecting the same step-size and initialization restrictions—not just gradient descent—should inherit the same linear or algebraic rates, since WQSC plus smoothness is the whole mechanism.
- The authors suggest robust polar decomposition as a min-max problem that classical linear algebra cannot handle; the WQSC structure may provide the missing curvature control for gradient-descent-ascent algorithms on that nonconvex-nonconcave landscape.
- The square-matrix restriction is a clear next test: if a similar WQSC inequality holds on Stiefel manifolds for the rectangular Procrustes problem, the same convergence theory would carry over, though the paper predicts the geometry makes this harder.
- One can test the sharpness of the constants by running the algorithm with eta exactly at the bound on a sequence of matrices with growing condition number; the observed contraction should approach the formula's prediction if the constants are tight.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper analyzes the orthogonal Procrustes problem, equivalent to computing the polar factor of a square matrix, as an optimization problem on the orthogonal group O(n). It establishes a weak-quasi-strong-convexity (WQSC) inequality by combining a geodesic weak-quasi-convexity bound (Prop. 3) with a quadratic growth bound (Prop. 4), and proves geodesic smoothness with constant sigma_max(C) (Prop. 7). These ingredients are used to analyze Riemannian gradient descent: for invertible C, Theorem 10 gives linear convergence of the squared distance to the unique polar factor under a fixed step size, provided the initialization satisfies dist(X0, X*) < pi; Theorem 11 gives an O(1/t) rate on function values for general nonzero C under the same initialization condition. The paper also discusses the geometry of O(n), including the injectivity domain of the exponential map and distance formulas.
Significance. The paper provides a clean structural explanation for the tractability of the Procrustes problem, in the same spirit as the authors' earlier work on the symmetric eigenvalue problem. The main inequalities are derived from scratch in a self-contained manner, with explicit constants, and the convergence results are stated with precise step-size and initialization conditions. A particular strength is that the proofs are largely algebraic and checkable, and the delicate trace identity in Proposition 3 is valid once the implicit replacement of P_X(X*) by X* is justified. The main limitation, the initialization condition dist(X0, X*) < pi, is restrictive but correctly stated in the theorems; the abstract, however, omits this qualification. Overall, this is a solid theoretical contribution, though the presented algorithm is not intended to compete with state-of-the-art SVD-based methods.
minor comments (6)
- [Abstract and Theorems 10–11] The abstract claims linear and algebraic convergence for gradient descent without mentioning the initialization condition dist(X0, X*) < pi. Since this condition is load-bearing in both theorems, the abstract should be qualified accordingly to avoid overclaiming.
- [Theorem 11 proof] The proof of Theorem 11 states that 'we still satisfy all the hypotheses of Theorem 10', but Theorem 10 explicitly assumes sigma_min(C) > 0, which fails when C is singular. The required bound dist(Xt, X*) <= dist(X0, X*) follows instead by induction from Proposition 9, which does not use invertibility; the proof should be rephrased to invoke Proposition 9 directly.
- [Proposition 3 proof] The equality <PX(CT), PX(X*)P phi/sin(phi) P^T> = <Xskew(X^T C^T), X* P phi/sin(phi) P^T> is not immediate. It holds because the difference between PX(X*) and X* contributes a term X P cos(phi)(phi/sin(phi)) P^T, whose trace against the skew-symmetric matrix P^T skew(X^T C^T) P vanishes. Please add a sentence making this justification explicit.
- [Throughout] There are several typographical issues: 'slew-symmetric' in Section 3; in the proof of Theorem 11, 'Lemma 9' should be 'Proposition 9', and the phrase '−ηtXt+1 is in the injectivity domain' should read '−ηt gradf(Xt) is in the injectivity domain'.
- [Proposition 4 proof] In the proof of Proposition 4, the reduction from Tr((I−D^T)A) to Tr((I−cos phi)A) is correct, but the cancellation of the off-diagonal sin r terms relies on the trace structure of each 2x2 block; a brief explanatory sentence would improve readability.
- [Equation (5)] The distance formula dist(X,Y) = ||phi||_2 uses a vector phi that lists each rotation angle r together with its negative for two-dimensional blocks but lists r=0 only once; a short note on this convention would help the reader.
Circularity Check
No circularity: WQSC and the convergence rates are derived from first principles inside the paper; the self-citations are motivational and not load-bearing.
full rationale
I walked the derivation chain of the central results, Propositions 3--5 and Theorems 10--11. The weak-quasi-strong-convexity inequality is not imported from the authors' earlier work; it is assembled in this paper from Proposition 3 (geodesic weak-quasi-convexity) and Proposition 4 (quadratic growth), both of which are proven from scratch using the canonical-form decomposition of X^T X*, the SVD of C, and elementary trace inequalities. Proposition 5 merely packages these two proven inequalities with the explicit choices a(X) = (1+cos|r|max)/4 and mu = 4 sigma_min(C)/pi^2. The smoothness constant L = sigma_max(C) is computed directly from the Riemannian Hessian in Proposition 7. Lemma 8 is proven in the text. The convergence analysis in Proposition 9 and Theorem 10 is a standard induction that uses only these propositions, the nonnegative curvature bound from Proposition 2, and the stated step-size and initialization assumptions. No parameter is fitted to data, no quantity is renamed as a prediction, and no convergence claim is assumed through a citation. The only self-citations are to [3] and [4]: [3] is cited for the general statement that WQSC-like inequalities are necessary for linear convergence, which is not used in the proofs; [4] is cited only to note that a similar structure was established for the symmetric eigenvalue problem. Neither citation supplies a fact on which the present proofs depend. The initialization condition dist(X0, X*) < pi is restrictive and is explicitly stated and used in the induction to keep the WQSC coefficient positive, but this is a legitimate assumption, not circularity. The proof chain is self-contained.
Assumptions & free parameters
assumptions (5)
- standard math Sectional curvatures of O(n) are nonnegative (folklore; O(n) is a Stiefel manifold).
- standard math Toponogov comparison theorem in nonnegative curvature.
- standard math The SVD decomposition C = U Σ V^T and the closed form of the Procrustes solution X* = V U^T.
- standard math The inequality 1 - cos r ≥ (2/π^2) r^2 for |r| ≤ π.
- standard math Von Neumann's trace inequality to bound the Riemannian Hessian quadratic form.
Cite this review
Pith. "Pith review of A geodesic convexity-like structure for the polar decomposition of a square matrix." pith.science (2026). https://pith.science/paper/MGRC3JPG
@misc{pith2026241213990,
author = {Pith},
title = {Pith review of: A geodesic convexity-like structure for the polar decomposition of a square matrix},
year = {2026},
howpublished = {\url{https://pith.science/paper/MGRC3JPG}},
note = {Machine review of arXiv:2412.13990}
}
read the original abstract
We make a full landscape analysis of the (generally non-convex) orthogonal Procrustes problem. This problem is equivalent to computing the polar factor of a square matrix. We reveal a convexity-like structure, which explains the already established tractability of the problem and show that gradient descent in the orthogonal group computes the polar factor of a square matrix with linear convergence rate if the matrix is invertible and with an algebraic one if the matrix is singular. These results are similar to the ones of Alimisis and Vandereycken (2024) for the symmetric eigenvalue problem.
Reference graph
Works this paper leans on
-
[1]
Optimization algo- rithms on matrix manifolds
P-A Absil, Robert Mahony, and Rodolphe Sepulchre. Optimization algo- rithms on matrix manifolds . Princeton University Press, 2009. 19
work page 2009
-
[2]
Generalized procrustes analysis and its ap plications in pho- togrammetry
Devrim Akca. Generalized procrustes analysis and its ap plications in pho- togrammetry. Technical report, ETH Zurich, 2003
work page 2003
-
[3]
Characterization of optimization pro blems that are solv- able iteratively with linear convergence
Foivos Alimisis. Characterization of optimization pro blems that are solv- able iteratively with linear convergence. MTNS 2024 , 2024
work page 2024
-
[4]
Geodesic convex ity of the sym- metric eigenvalue problem and convergence of steepest desc ent
Foivos Alimisis and Bart Vandereycken. Geodesic convex ity of the sym- metric eigenvalue problem and convergence of steepest desc ent. Journal of Optimization Theory and Applications , pages 1–40, 2024
work page 2024
-
[5]
Optimality conditions on the orthogona l group
Nicolas Boumal. Optimality conditions on the orthogona l group. https://www.racetothebottom.xyz/posts/optimality-orthogonal/, 2023
work page 2023
-
[6]
A Note on Nesterov's Accelerated Method in Nonconvex Optimization: a Weak Estimate Sequence Approach
Jingjing Bu and Mehran Mesbahi. A note on nesterov’s acce lerated method in nonconvex optimization: a weak estimate sequence approa ch. arXiv preprint arXiv:2006.08548, 2020
work page Pith review arXiv 2006
-
[7]
A new scaling for newton’s ite ration for the polar decomposition and its backward stability
Ralph Byers and Hongguo Xu. A new scaling for newton’s ite ration for the polar decomposition and its backward stability. SIAM Journal on Matrix Analysis and Applications , 30(2):822–843, 2008
work page 2008
-
[8]
Error bounds, q uadratic growth, and linear convergence of proximal methods
Dmitriy Drusvyatskiy and Adrian S Lewis. Error bounds, q uadratic growth, and linear convergence of proximal methods. Mathematics of Operations Research, 43(3):919–948, 2018
work page 2018
Show all 22 references
-
[9]
Study ing morphological variation: Exploring the shape space in evolutionary anthr opology
Shira Faigenbaum-Golovin and Ingrid Daubechies. Study ing morphological variation: Exploring the shape space in evolutionary anthr opology. arXiv preprint arXiv:2410.20040, 2024
2024 arXiv
-
[10]
On halley’s iteration method
Walter Gander. On halley’s iteration method. The American Mathematical Monthly, 92(2):131–134, 1985
1985
-
[11]
Accelerated meth- ods for α -weakly-quasi-convex problems
Sergey Guminov, Alexander Gasnikov, and Ilya Kuruzov. Accelerated meth- ods for α -weakly-quasi-convex problems. arXiv preprint arXiv:1710.00797, 2017
2017 arXiv
-
[12]
Gradient d escent learns linear dynamical systems
Moritz Hardt, Tengyu Ma, and Benjamin Recht. Gradient d escent learns linear dynamical systems. The Journal of Machine Learning Research , 19(1):1025–1068, 2018
2018
-
[13]
Computing the polar decomposition—w ith applica- tions
Nicholas J Higham. Computing the polar decomposition—w ith applica- tions. SIAM Journal on Scientific and Statistical Computing , 7(4):1160– 1174, 1986
1986
-
[14]
Functions of matrices: Theory and co mputation, 2008
Nicholas J Higham. Functions of matrices: Theory and co mputation, 2008
2008
-
[15]
A solution for the best rotation to rel ate two sets of vectors
Wolfgang Kabsch. A solution for the best rotation to rel ate two sets of vectors. Acta Crystallographica Section A: Crystal Physics, Diffracti on, Theoretical and General Crystallography , 32(5):922–923, 1976. 20
1976
-
[16]
Linear co nvergence of gradient and proximal-gradient methods under the polyak-ł ojasiewicz con- dition
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear co nvergence of gradient and proximal-gradient methods under the polyak-ł ojasiewicz con- dition. In Machine Learning and Knowledge Discovery in Databases: Eu- ropean Conference, ECML PKDD 2016, Riva del Garda, Italy, Sep te...
2016
-
[17]
Charles Kenney and Alan J. Laub. On scaling newton’s met hod for polar decomposition and the matrix sign function. In 1990 American Control Conference, pages 2560–2564, 1990
1990
-
[18]
Opti mizing halley’s iteration for computing the matrix polar decomposition
Yuji Nakatsukasa, Zhaojun Bai, and François Gygi. Opti mizing halley’s iteration for computing the matrix polar decomposition. SIAM Journal on Matrix Analysis and Applications , 31(5):2700–2720, 2010
2010
-
[19]
Backward stabi lity of iterations for computing the polar decomposition
Yuji Nakatsukasa and Nicholas J Higham. Backward stabi lity of iterations for computing the polar decomposition. SIAM Journal on Matrix Analysis and Applications, 33(2):460–479, 2012
2012
-
[20]
Lin ear convergence of first order methods for non-strongly convex optimization
Ion Necoara, Yurii Nesterov, and Francois Glineur. Lin ear convergence of first order methods for non-strongly convex optimization. Mathematical Programming, 175:69–107, 2019
2019
-
[21]
Introduction to Differential Geometry
Joel Robbin and Dietmar Salamon. Introduction to Differential Geometry . ETH lecture notes, 2022
2022
-
[22]
A generalized solution of the ortho gonal procrustes problem
Peter H Schönemann. A generalized solution of the ortho gonal procrustes problem. Psychometrika, 31(1):1–10, 1966. 21
1966
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.