Retraction-Based Gradient Projection Algorithms on Manifolds

Conglong Xu; Hao Wu

math.OCSep 25, 2026

Retraction-Based Gradient Projection Algorithms on Manifolds

Authors: Conglong Xu, Hao Wu

Organizations: Department of Mathematics, The George Washington University, Phillips Hall, Room 739, 801 22nd Street, N.W., Washington, DC 20052, USA.

Abstract

We introduce a framework for retraction-based convex optimization on Riemannian manifolds, which includes a notion of retraction-specific convex sets and retraction-based gradient projection algorithms. The standard theory of gradient projection algorithms generalizes easily to this framework. Within this framework, we establish convergence results for retraction-based gradient projection algorithms with various stepsize rules. As an application, we use our framework to study the weighted low-rank approximation. We also provide numerical validation of our convergence results on the image completion task.

Figures & tables

Sampled MNIST
QR retraction
rank	$\lambda$	Regularized Armijo (Benchmark)				Feasible Direction (Main Routine)				Projection Arc (Main Routine)
		best	mean	evals	fail.	best	mean	evals	fail.	best	mean	evals	fail.
32	$10^{-2}$	0.2138 $(0.9,0.75,0.5)$	0.2153	50.3	0	0.2134 $(0.9,0.75,0.5)$	0.2152	50.3	0	0.2133 $(0.9,0.75,0.3)$	0.2152	50.3	0
32	$10^{-4}$	0.2137 $(0.9,0.75,0.3)$	0.2153	50.3	0	0.2134 $(0.9,0.75,0.5)$	0.2152	50.3	0	0.2133 $(0.9,0.75,0.3)$	0.2152	50.3	0
32	$10^{-6}$	0.2140 $(0.9,0.75,0.5)$	0.2153	50.2	0	0.2134 $(0.9,0.75,0.5)$	0.2152	50.3	0	0.2133 $(0.9,0.75,0.3)$	0.2152	50.3	0

Table 1: For each retraction-rank-regularization configuration, the table reports each routine’s best and mean final RMSE, mean Armijo inequality checks per iteration (“mean Armijo Evaluations”), and failure count. Evaluation counts are averaged over each successful run’s

200

iterations, then across successful grid runs. Failures count grid runs that reached the

200

-backtrack limit. Failed records are excluded from evaluating the other three metrics. Parentheses give the Armijo parameters

(\beta,\sigma,s)

for the best RMSE entry. Boldface marks the lowest best RMSE among the three routines in each row. The masking rate is set to

0.5

Figure 1: RMSE convergence over $1000$ iterations using the optimal Armijo-rule parameters selected from the grid search summarized in Table 1 . The left panels use the QR decomposition-based retraction and the right panels use the polar decomposition-based retraction. The $x$ -axis is logarithmic. The thicker curve with a star at its final point marks the lowest final RMSE in that subplot. The masking rate is set to $0.5$ . On the sampled MNIST dataset (the upper panel), (1) the “Feasible Direction” routine appears to consistently outperform the benchmark routine when using the polar-decomposition-based retraction and the low-rank $p=128$ , (2 )the “Projection Arc” routine appears to consistently outperform the benchmark routine when using the QR-decomposition-based retraction and the low-rank $p=64$ . On the sampled CIFAR-10 dataset (the lower pannel), (1) the “Feasible Direction” routine appears to consistently outperform the benchmark routine when using the polar-decomposition-based retraction and the low-rank $p=32$ , (2) the “Projection Arc” routine appears to consistently outperform the Regularized Armijo (benchmark) routine when using the QR-decomposition-based retraction and the low-rank $p=128$ .

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Category	Parameter	Values or setting
Armijo rule	Contraction factor $\beta$	$\{0.5,0.75,0.9\}$
	Sufficient-decrease factor $\sigma$	$\{0.25,0.5,0.75\}$
	Initial trial step $s$	$\{0.3,0.5,1.0\}$
Configuration	Retraction	QR, polar
	Low-rank $p$	$\{32,64,128\}$
	Regularization parameter $\lambda$	$\{10^{-2},10^{-4},10^{-6}\}$

Appendix

Table 2: Parameters used in the Armijo grid searches. Each combination of the Armijo rule parameters

\beta

\sigma

and

s

defines one Armijo grid point, giving

27

points for each routine within a retraction-rank-regularization configuration. There are 18 retraction-rank-regularization configurations per dataset. With the three routines, each dataset therefore has

27\times 18\times 3=1458

runs in each grid search. The Armijo tolerance is a numerical slack in the Armijo stepsize rules computations.

Sampled MNIST
QR retraction
rank	$\lambda$	Regularized Armijo (Benchmark)				Feasible Direction (Main Routine)				Projection Arc (Main Routine)
		best	mean	evals	fail.	best	mean	evals	fail.	best	mean	evals	fail.
32	$10^{-2}$	0.2734 $(0.9,0.75,0.5)$	0.2786	43.6	0	0.2735 $(0.9,0.75,0.3)$	0.2786	43.5	0	0.2735 $(0.9,0.75,0.5)$	0.2785	43.6	0
32	$10^{-4}$	0.2745 $(0.9,0.75,0.3)$	0.2786	43.6	0	0.2735 $(0.9,0.75,0.3)$	0.2786	43.5	0	0.2735 $(0.9,0.75,0.5)$	0.2785	43.6	0
32	$10^{-6}$	0.2729 $(0.9,0.75,0.3)$	0.2786	43.6	0	0.2735 $(0.9,0.75,0.3)$	0.2786	43.5	0	0.2735 $(0.9,0.75,0.5)$	0.2785	43.6	0

Appendix

Table 3: For each retraction-rank-regularization configuration, the table reports each routine’s best and mean final RMSE, mean Armijo inequality checks per iteration (“mean Armijo Evaluations”), and failure count. Evaluation counts are averaged over each successful run’s

200

iterations, then across successful grid runs. Failures count grid runs without a successful final metric. Failed records are excluded from evaluating the other three metrics. Parentheses give the Armijo parameters

(\beta,\sigma,s)

for the best RMSE entry. Boldface marks the lowest best RMSE among the three routines in each row. The upper table reports results for the sampled MNIST dataset, and the lower table reports results for the sampled CIFAR-10 dataset. The masking rate is set to 0.75.

Figure 2: RMSE convergence over $1000$ iterations using the optimal Armijo-rule parameters selected from the grid search summarized in Table 3 . The left panels use the QR-decomposition-based retraction and the right panels use the polar-decomposition-based retraction. The $x$ -axis is logarithmic. The thicker curve with a star at its final point marks the lowest final RMSE in that subplot. The masking rate is set to 0.75. On the sampled MNIST dataset (the upper panel), the “Feasible Direction” routine appears to consistently outperform the Regularized Armijo (benchmark) routine when using the QR-decomposition-based retraction and the low-rank $p=64$ or $p=128$ . On the sampled CIFAR-10 dataset (the lower panel), (1) the “Feasible Direction” routine appears to consistently outperform the Regularized Armijo (benchmark) routine when using the QR-decomposition-based retraction and the low-rank $p=64$ , or when using the polar-decomposition-based retraction and the low-rank $p=128$ ; (2) the “Projection Arc” routine appears to consistently outperform the Regularized Armijo (benchmark) routine when using the polar-decomposition-based retraction and the low-rank $p=64$ .

Sampled MNIST
QR retraction
rank	$\lambda$	Regularized Armijo (Benchmark)				Feasible Direction (Main Routine)				Projection Arc (Main Routine)
		best	mean	evals	fail.	best	mean	evals	fail.	best	mean	evals	fail.
32	$10^{-2}$	0.1649 $(0.9,0.75,1)$	0.1654	54.2	0	0.1651 $(0.9,0.75,0.3)$	0.1654	54.3	0	0.1650 $(0.9,0.75,0.3)$	0.1654	54.3	0
32	$10^{-4}$	0.1651 $(0.9,0.75,0.5)$	0.1654	54.2	0	0.1651 $(0.9,0.75,0.3)$	0.1654	54.3	0	0.1650 $(0.9,0.75,0.3)$	0.1654	54.3	0
32	$10^{-6}$	0.1651 $(0.9,0.75,0.3)$	0.1654	54.2	0	0.1651 $(0.9,0.75,0.3)$	0.1654	54.3	0	0.1650 $(0.9,0.75,0.3)$	0.1654	54.3	0

Appendix

Table 4: For each retraction-rank-regularization configuration, the table reports each routine’s best and mean final RMSE, mean Armijo inequality checks per iteration (“mean Armijo Evaluations”), and failure count. Evaluation counts are averaged over each successful run’s

200

(\beta,\sigma,s)

Figure 3: RMSE convergence over $1000$ iterations using the optimal Armijo-rule parameters selected from the grid search summarized in Table 4 . The left panels use the QR-decomposition-based retraction and the right panels use the polar-decomposition-based retraction. The $x$ -axis is logarithmic. The thicker curve with a star at its final point marks the lowest final RMSE in that subplot. The masking rate is set to 0.25. On the sampled MNIST dataset (the upper panel), the “Projection Arc” routine appears to consistently outperform the Regularized Armijo (benchmark) routine when using the QR-decomposition-based retraction and the low-rank $p=32$ , or using the polar-decomposition-based retraction and the low-rank $p=32$ or $p=128$ . On the sampled CIFAR-10 dataset (the lower panel), the “Feasible Direction” routine appears to consistently outperform the Regularized Armijo (benchmark) routine when we using the QR-decomposition-based retraction and the low-rank $p=64$ .

Full-train MNIST
QR retraction
rank	$\lambda$	Regularized Armijo (Benchmark)			Feasible Direction (Main Routine)			Projection Arc (Main Routine)
		best	mean	fail.	best	mean	fail.	best	mean	fail.
32	$10^{-2}$	0.2140 $(0.9,0.75,0.3)$	0.2143	0	0.2139 $(0.9,0.75,0.5)$	0.2143	0	0.2140 $(0.9,0.75,0.3)$	0.2143	0
32	$10^{-4}$	0.2139 $(0.9,0.75,0.5)$	0.2143	0	0.2139 $(0.9,0.75,0.5)$	0.2143	0	0.2140 $(0.9,0.75,0.3)$	0.2143	0
32	$10^{-6}$	0.2139 $(0.9,0.75,0.5)$	0.2143	0	0.2139 $(0.9,0.75,0.5)$	0.2143	0	0.2140 $(0.9,0.75,0.3)$	0.2143	0

Appendix

Table 5: For each retraction-rank-regularization configuration, the table reports each routine’s best final RMSE (“best RMSE”), mean final RMSE (“mean RMSE”), and number of failures (“failures”). The number of failures is the count of grid points whose runs failed by reaching the maximum number of backtracking steps (set to

200

) before producing a successful final metric. Failed records are excluded from evaluating the other two metrics. Parentheses give the Armijo parameters

(\beta,\sigma,s)

for the best RMSE entry. Boldface marks the lowest best RMSE among the three routines in each row. The masking rate is set to 0.5.

Full-train CIFAR-10
QR retraction
rank	$\lambda$	Regularized Armijo (Benchmark)			Feasible Direction (Main Routine)			Projection Arc (Main Routine)
		best	mean	fail.	best	mean	fail.	best	mean	fail.
32	$10^{-2}$	0.2876 $(0.75,0.5,0.5)$	0.2891	4	0.2873 $(0.9,0.5,1)$	0.2889	1	0.2874 $(0.9,0.5,1)$	0.2890	2
32	$10^{-4}$	0.2874 $(0.9,0.5,1)$	0.2891	4	0.2873 $(0.9,0.5,1)$	0.2889	1	0.2874 $(0.9,0.5,1)$	0.2890	2
32	$10^{-6}$	0.2873 $(0.9,0.5,1)$	0.2890	2	0.2873 $(0.9,0.5,1)$	0.2889	1	0.2874 $(0.9,0.5,1)$	0.2890	2

Appendix

Table 6: Stage 1 grid search on all

50000

grayscale CIFAR-10 training images, forming a

1024\times 50000

matrix with masking rate

0.5

. For each retraction-rank-regularization configuration, the table reports each routine’s best final RMSE, mean final RMSE over successful grid points, and number of failures. Each routine has

27

grid points per configuration and runs for

200

iterations. Failures reached the maximum of

200

backtracking steps and are excluded from both RMSE metrics. Parentheses give the selected Armijo parameters

(\beta,\sigma,s)

. Boldface marks the lowest best RMSE among the three routines using unrounded values; selection ties are broken by final unregularized WLRA loss, with exact remaining ties marked jointly.

Comparison	Metric	mean difference	$t_{143}$	one-sided $p$	Outperforms?
Feasible Direction (Main Routine) vs Regularized Armijo (Benchmark)	best RMSE	$-2.617\times 10^{-4}$	-2.5414	$6.05\times 10^{-3}$	Yes
	mean RMSE	$-4.821\times 10^{-5}$	-2.4839	$7.07\times 10^{-3}$	Yes
Projection Arc (Main Routine) vs Regularized Armijo (Benchmark)	best RMSE	$-2.472\times 10^{-4}$	-2.3232	0.011	Yes
	mean RMSE	$-4.902\times 10^{-5}$	-2.0029	0.024	Yes

Appendix

Table 7: Paired, one-sided

t

-tests comparing Feasible Direction (main routine) and Projection Arc (main routine) with Regularized Armijo (benchmark) across the 144 matched configurations in Tables 1 , 3 , 4 , 5 , and 6 . The mean difference is the named main routine minus Regularized Armijo (benchmark), so a negative value favors the main routine because lower RMSE values are preferred. The alternative hypothesis is that the mean paired difference is negative. “Outperforms” is reported as Yes when the unadjusted one-sided

p

-value is below

0.05

; no multiple-testing correction is applied.

Comparison	Metric	mean difference	$t_{107}$	one-sided $p$	Outperforms?
Feasible Direction (Main Routine) vs Regularized Armijo (Benchmark)	final RMSE	$-2.463\times 10^{-4}$	-0.9209	0.180	No
Projection Arc (Main Routine) vs Regularized Armijo (Benchmark)	final RMSE	$-2.206\times 10^{-4}$	-0.8556	0.197	No

Appendix

Table 8: Paired, one-sided

t

-tests comparing Feasible Direction (main routine) and Projection Arc (main routine) with Regularized Armijo (benchmark) across the 108 matched configurations in Figures 1 , 2 , and 3 . The mean difference is the final RMSE for the named main routine minus that for Regularized Armijo (benchmark), so a negative value favors the main routine because lower RMSE values are preferred. The alternative hypothesis is that the mean paired difference is negative. “Outperforms” is reported as Yes when the unadjusted one-sided

p

-value is below

0.05

; no multiple-testing correction is applied.

Gradient Projection

Gradient projection constrains optimization steps to feasible directions or subspaces, reducing interference while preserving desired properties.

See all 21 papers

Projected Riemannian Gradient Descent for the Bures-Wasserstein Barycenter: Dimension-Independent Linear Convergence at Unit Step Size
Sep 3, 2026A. AfhamRiemannian Optimization Optimization Convergence Analysis
Centre for Quantum Technologies, National University of Singapore, Singapore
Optimization over the intersection of manifolds
May 21, 2026Yan Yang, Bin Gao, Ya-xiang YuanRiemannian Optimization
State Key Laboratory of Mathematical Sciences, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, and University of Chinese Academy of Sciences, China · State Key Laboratory of Mathematical Sciences, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, China
Regularized Optimization on Grassmann Manifold: Theory, Algorithm and Applications
Jul 23, 2026Zhuan Liang, Zheng ZhaiSpectral Regularization Riemannian Optimization
Department of Statistics, Faculty of Arts and Sciences at Beijing Normal University, Zhuhai

Sep 3, 2026J/K move · Enter open · S save

Projected Riemannian Gradient Descent for the Bures-Wasserstein Barycenter: Dimension-Independent Linear Convergence at Unit Step Size

A. Afham

Centre for Quantum Technologies, National University of Singapore, Singapore

Riemannian Optimization Optimization Convergence Analysis Wasserstein Barycenters Optimal Transport

Open paper AskPDF arXiv

The computation of the Bures-Wasserstein (BW) barycenter of an ensemble of positive definite matrices arises throughout machine learning, optimal transport, and quantum information. Riemannian gradient descent (RGD) at unit step size -- the fixed-point iteration used in practice -- converges rapidly, yet existing analyses present a dichotomy: unit-step guarantees carry worst-case exponential dependence on the dimension, while dimension-independent guarantees require small step sizes that forfeit the empirical speed. We resolve this dichotomy, not by improving the guarantees for unit-step RGD, but by proposing a Projected RGD algorithm that achieves dimension-independent linear convergence at unit step size. The achieved rate,

(1 - κ^{-3/2})

, where

κ

is the condition number of the ensemble, also polynomially improves on the best small-step guarantee (

κ^{3/2}

versus

κ^{5/2}

iteration complexity). The crux is a novel Projection Lemma: clipping the eigenvalues of a positive matrix to an interval

[α, β]

is the closed-form, non-expansive (1-Lipschitz) BW-metric projection onto the set

\{S : αI \leq S \leq βI\}

-- a statement which, unlike its known one-sided counterpart, does not follow from convexity. The projection is moreover free: it reuses an eigendecomposition the next iteration must perform in any case, so the projected and unprojected iterations cost the same per step. The same analysis covers the invariant matrix projection problem of Brahmachari et al. (2025), whose fixed-point algorithm we identify as unit-step RGD on a totally geodesic submanifold, thereby extending the dimension-independent guarantee to that setting verbatim.

Abstract

Gradient Projection

Explore similar work

Projected Riemannian Gradient Descent for the Bures-Wasserstein Barycenter: Dimension-Independent Linear Convergence at Unit Step Size

Optimization over the intersection of manifolds

Regularized Optimization on Grassmann Manifold: Theory, Algorithm and Applications