Generalized Composed Alternating Relaxed Projection Algorithm for Two-Set Feasibility Problem

Xinxin Li, Yudong Wei, Hao Zhang · 2026

Read Generalized Composed Alternating Relaxed Projection Algorithm for Two-Set Feasibility Problem by Xinxin Li, Yudong Wei, Hao Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-17276.txt.

Introduction

Li, Wei, and Zhang propose gCARPA, a flexible projection algorithm for finding a point shared by two closed convex sets in Hilbert space. It blends Douglas-Rachford and projection-reflection dynamics through outer averaging and internal relaxation, covering several classic methods as special cases, with a version whose parameters shift across iterations. For subspace problems they derive an explicit spectral recipe for choosing parameters, and experiments show the tuning can match or beat baselines.

Catalog record

CREATORXinxin Li, Yudong Wei, Hao Zhang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE87827
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.17276

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Generalized Composed Alternating Relaxed Projection Algorithm for Two-Set Feasibility Problem Xinxin Li, Yudong Wei, Hao Zhang Abstract We study the two-set feasibility problem of finding a point in the intersection X ∩ Y X\cap Y of closed convex sets in a Hilbert space. We propose a generalized composed alternating relaxed projection algorithm (gCARPA) that blends Douglas–Rachford-type and projection–reflection-type dynamics via an outer averaging step μ \mu and an internal relaxation ( γ , θ , η ) (\gamma,\theta,\eta) . The algorithm contains several classical projection methods as special cases. We also introduce its non-stationary variant, in which ( γ k , θ k , η k ) (\gamma_{k},\theta_{k},\eta_{k}) vary over iterations, and establish its convergence. For the subspace feasibility model, we derive an explicit spectral characterization via principal-angle block decompositions, yielding computable subdominant-eigenvalue factors and a minimax parameter-selection recipe in a symmetric regime that targets critical damping on principal-angle planes. Numerical experiments illustrate that the generalized relaxation and its non-stationary tuning can improve or match baseline methods in problem-dependent regimes. Key words. Feasibility problem, Projection, Relaxation, Nonstationary scheme, Friedrichs angle, Linear convergence 1 Introduction In this paper, we are interested in the following feasibility problem of two sets: (1.1) \mathrm{find}\;\bm{x}\in\mathcal{H}\ \ \textrm{such that}\ \ \bm{x}\in X\cap Y, where \mathcal{H} is a real Hilbert space, and X,Y\subset\mathcal{H} are nonempty closed convex sets satisfying X\cap Y\neq\emptyset. Feasibility problems of the form ( 1.1 ) arise in a wide range of applications, including signal and image processing [ 15 , 13 ] , compressed sensing [ 38 , 39 ] , seismic data processing [ 22 , 37 ] , and many others. Projection-based methods are among the most popular approaches for such problems, due to their simplicity and their strong convergence theory in Hilbert spaces. A fundamental method for ( 1.1 ) is the method of alternating projections (MAP) [ 23 , 3 ] . Over the years, numerous variants have been proposed to improve practical performance or to obtain sharper convergence properties, such as relaxed alternating projection (RAP) and partial relaxed alternating projection (PRAP) [ 5 ] , averaged alternating modified reflections (AAMR) [ 1 ] , relaxed averaged alternating reflections (RAAR) [ 30 ] , simultaneous projection (SP) [ 35 ] , and generalized relaxed alternating projection (GRAP) [ 21 , 17 ] . More recently, geometric acceleration ideas have also been explored, for instance via circumcentered-reflection type schemes [ 2 , 12 , 11 ] . Projection algorithms can also be viewed through the lens of operator splitting, since the projection is a special case of the proximity operator [ 6 ] . Indeed, MAP can be interpreted as an instance of the backward–backward splitting method [ 8 ] . Moreover, several projection/reflection methods recover classical splittings such as Peaceman–Rachford [ 31 ] and Douglas–Rachford [ 19 ] under suitable parameter choices; see, e.g., [ 4 , 5 , 1 ] and references therein. The convergence theory of projection-based fixed-point iterations has also been extensively developed. Many algorithms can be written as Krasnosel’skiĭ–Mann iterations of (firmly) nonexpansive or averaged operators, enabling global convergence guarantees and rate estimates; see, e.g., [ 27 ] . Under additional regularity such as partial smoothness, one can obtain local linear convergence [ 24 , 25 , 28 ] . For nonconvex feasibility, convergence properties of Douglas–Rachford type schemes have been studied as well; see, e.g., [ 26 ] . In the special case where X and Y are subspaces, sharp linear rates can be characterized in terms of the Friedrichs angle [ 4 , 9 , 1 ] ; see also [ 18 , 7 , 10 ] for further developments. 1.1 Motivation and contribution When X and Y are two subspaces, both MAP and Douglas–Rachford (DR) converge linearly, and the rate is governed by the Friedrichs angle between X and Y [ 4 , 5 ] . However, despite its appealing theory, the DR fixed-point sequence may exhibit a pronounced spiraling trajectory [ 33 ] , which can lead to slow practical progress on subspace feasibility problems. This geometric phenomenon motivates algorithmic designs that retain the favorable nonexpansive structure of DR while mitigating its spiral behavior. Recently, Shen et al. [ 36 ] proposed the composed alternating relaxed projection algorithm (CARPA), which blends DR-type composition with a projection-reflection correction, and demonstrated significant speedup over DR on several feasibility models. In this work, we further generalize CARPA by introducing relaxed reflections with parameters \theta,\eta\in(0,1] , leading to a generalized composed alternating relaxed projection algorithm (gCARPA), given in Algorithm 1 . Concretely, we use \mathcal{R}_{X}^{\theta}:=(1-\theta)\mathcal{I}+\theta(2\mathcal{P}_{X}-\mathcal{I}),\qquad\mathcal{R}_{Y}^{\eta}:=(1-\eta)\mathcal{I}+\eta(2\mathcal{P}_{Y}-\mathcal{I}), where \mathcal{P}_{X} and \mathcal{P}_{Y} denote the orthogonal projections onto X and Y , and \mathcal{I} is the identity operator. When \theta=\eta=1 , the operators \mathcal{R}_{X}^{\theta} and \mathcal{R}_{Y}^{\eta} reduce to the standard reflections, in which case gCARPA coincides with CARPA in [ 36 ] . The additional parameters \theta and \eta provide a flexible interpolation between projection steps and reflection steps, and allow us to unify several classical schemes within a single template. For instance, the gCARPA update can be written as a relaxed fixed-point iteration \bm{z}^{k+1}=(1-\mu)\bm{z}^{k}+\mu\,\mathcal{F}^{\theta,\eta}_{\gamma}(\bm{z}^{k}), where the operator \mathcal{F}^{\theta,\eta}_{\gamma} is a convex combination of a DR-type averaging term and a projection term built from \mathcal{P}_{Y}\circ\mathcal{R}_{X}^{\theta} . As special cases, one may recover relaxed DR (e.g., \gamma=0 ), and relaxed alternating projections (e.g., \gamma=1 and \mu=1 ), highlighting gCARPA as a unifying algorithm. The main contributions of this paper are summarized as follows. ❖ We propose the generalized composed alternating relaxed projection algorithm for the convex feasibility problem ( 1.1 ). Compared with CARPA, the additional relaxation parameters (\theta,\eta) in gCARPA provide extra degrees of freedom to control the balance between spiraling and damping in the fixed-point dynamics. We establish its fixed-point characterization and global convergence under suitable parameter choices. We also introduce and analyze a non-stationary variant. ❖ For the feasibility problem of two subspaces, we derive explicit linear convergence rates of gCARPA and identify parameter regimes that yield provably optimal rates. In particular, when \theta=\eta=1 , our results specialize to the CARPA setting of [ 36 ] . ❖ We provide numerical experiments on representative feasibility models, including subspace feasibility and additional structured examples, to illustrate how the extra relaxation parameters \theta,\eta can improve robustness and performance compared with existing projection/reflection methods. 1.2 Paper organization The remainder of this paper is organized as follows. Section 2 collects notation and preliminary results. In Section 3 , we present gCARPA and its non-stationary extension, together with the convergence analysis. Section 4 reports numerical experiments and comparisons with several related methods. 2 Mathematical background Throughout, let \mathcal{H} be a real Hilbert space endowed with inner product \langle\cdot,\,\cdot\rangle and the induced norm {|\kern-1.125pt|}\cdot{|\kern-1.125pt|} . We write \mathcal{I} for the identity operator on \mathcal{H} . When we specialize to the Euclidean setting, \mathbb{R}^{n} denotes the n -dimensional real vector space equipped with the standard inner product. We use bold uppercase (lowercase) letters to denote matrices (column vectors) and calligraphic letters to represent operators. Given a matrix \bm{A}\in\mathbb{R}^{m\times n} , we denote by \mathrm{ker}(\bm{A}) , \mathrm{ran}(\bm{A}) , and \mathrm{rank}(\bm{A}) the null space, range, and rank of \bm{A} , respectively. We use \mathrm{span}(\cdot) to denote the linear span of a set of vectors. We denote

Read the complete text