Global and Unconditional R-Linear Convergence of Rank-Compressed Weighted LMSD Sweeps for Strictly Convex Quadratics
Abstract
We study limited memory steepest descent (LMSD) with exact algebraic rank compression for strictly convex quadratic optimization. At each cycle, the method restricts the gradient history to its column space and applies the reciprocals of all Ritz values of the compressed projection in the next sweep. If the block-start gradient has at most p active distinct eigenvalues, the delayed sweep terminates finitely. For nonterminating trajectories, a determinant and Cauchy--Binet formula for the complete-sweep polynomial yields global convergence without a full-rank history or a run-wise normalized-conditioning bound. Consecutive sweep endpoints define a continuous positively homogeneous map on a closed cone of compatible states. Compactness then gives an R-linear endpoint estimate, uniform over compatible initial states, with constants depending only on H and p; the estimate extends to inner gradients, iterate errors, and objective gaps. Every fixed positive spectral weight W=ω(H) is linearly conjugate to the standard method. The weighted methods therefore share its decay factor, while the Euclidean-norm prefactor is increased by at most √(κ2(W)). This includes harmonic-Ritz LMSD, fixed power weights, and the delayed BB1 and BB2 recurrences.
Related
- R-Linear Convergence of Barzilai-Borwein Methods on Strictly Convex Quadratics via Closed-Cone Homogeneous Dynamics
- Doubly exponential convergence of the cyclic steepest descent method for strictly convex quadratics in arbitrary dimensions
- Convergence of cyclic steepest descent for quadratics with two distinct eigenvalues
- Unconditional optimal convergence of a relaxation Crank-Nicolson difference scheme for 2D space-fractional NLS
- Global existence and convergence of a density heat flow for strictly subcritical Liouville systems
BibTeX
@misc{yang2026global,
title = {{Global and Unconditional $R$-Linear Convergence of Rank-Compressed Weighted LMSD Sweeps for Strictly Convex Quadratics}},
author = {Shutai Yang and Ya-xiang Yuan},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.12114},
eprint = {2609.12114},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.12114},
}
RIS
TY - UNPB
TI - Global and Unconditional R-Linear Convergence of Rank-Compressed Weighted LMSD Sweeps for Strictly Convex Quadratics
AU - Shutai Yang
AU - Ya-xiang Yuan
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.12114
UR - https://arxiv.org/abs/2609.12114
AB - We study limited memory steepest descent (LMSD) with exact algebraic rank compression for strictly convex quadratic optimization. At each cycle, the method restricts the gradient history to its column space and applies the reciprocals of all Ritz values of the compressed projection in the next sweep. If the block-start gradient has at most p active distinct eigenvalues, the delayed sweep terminates finitely. For nonterminating trajectories, a determinant and Cauchy--Binet formula for the complete-sweep polynomial yields global convergence without a full-rank history or a run-wise normalized-conditioning bound. Consecutive sweep endpoints define a continuous positively homogeneous map on a closed cone of compatible states. Compactness then gives an R-linear endpoint estimate, uniform over compatible initial states, with constants depending only on H and p; the estimate extends to inner gradients, iterate errors, and objective gaps. Every fixed positive spectral weight W=ω(H) is linearly conjugate to the standard method. The weighted methods therefore share its decay factor, while the Euclidean-norm prefactor is increased by at most √(κ_2(W)). This includes harmonic-Ritz LMSD, fixed power weights, and the delayed BB1 and BB2 recurrences.
ER -