pith. sign in

arxiv: 2604.17276 · v1 · submitted 2026-04-19 · 🧮 math.OC · cs.NA· math.NA

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

Xinxin Li , Yudong Wei , Hao Zhang This is my paper

Pith reviewed 2026-05-10 06:20 UTC · model grok-4.3

classification 🧮 math.OC cs.NAmath.NA
keywords two-set feasibilityrelaxed projectionDouglas-Rachfordalternating projectionsconvergence analysissubspace feasibilityprincipal anglesparameter selection
0
0 comments X

The pith

A generalized algorithm blending relaxed projections and averaging converges to solutions of the two-set convex feasibility problem.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces gCARPA, a generalized composed alternating relaxed projection method for locating a point in the intersection of two closed convex sets in Hilbert space. It combines Douglas-Rachford-type and projection-reflection dynamics through an outer averaging parameter and internal relaxation parameters, recovering several classical projection algorithms as special cases. A non-stationary version with iteration-varying parameters is also defined and shown to converge. For the subspace case an explicit spectral decomposition in terms of principal angles supplies computable factors that guide minimax parameter choice aimed at critical damping.

Core claim

We propose the gCARPA iteration that blends Douglas-Rachford-type and projection-reflection-type dynamics via an outer averaging step μ and an internal relaxation (γ, θ, η). The algorithm contains several classical projection methods as special cases. We establish convergence of both the stationary and non-stationary variants. For the subspace feasibility model we derive an explicit spectral characterization via principal-angle block decompositions that yields computable subdominant-eigenvalue factors and a minimax parameter-selection recipe in a symmetric regime that targets critical damping on principal-angle planes.

What carries the argument

The composed gCARPA operator formed by relaxed projections, reflections, and outer averaging, which remains averaged or firmly nonexpansive for suitable parameter ranges and thereby guarantees convergence.

If this is right

  • Classical methods such as alternating projections, relaxed alternating projections, and Douglas-Rachford splitting arise as direct special cases.
  • Convergence holds for both fixed parameters and iteration-dependent parameters provided the averagedness condition is met.
  • In the subspace setting the principal-angle spectral factors allow explicit computation of the linear convergence rate and optimal parameter choice.
  • Numerical behavior can be tuned per problem class by adjusting the outer averaging and internal relaxation values.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same spectral tuning recipe may apply to other feasibility problems whose linearization admits a principal-angle decomposition.
  • Non-stationary parameter schedules could be adapted on the fly using local estimates of principal angles when the sets change slowly.
  • The unification suggests that performance gains observed in one classical method can be ported to others by appropriate choice of the outer averaging weight.
  • The framework may extend to inconsistent feasibility problems by replacing the intersection condition with a distance-minimization objective.

Load-bearing premise

The relaxation parameters must be chosen so that the overall iteration operator stays averaged or firmly nonexpansive.

What would settle it

A concrete pair of closed convex sets together with a parameter triple outside the averaged range for which the iterates fail to converge to the intersection would falsify the convergence claim.

Figures

Figures reproduced from arXiv: 2604.17276 by Hao Zhang, Xinxin Li, Yudong Wei.

Figure 1
Figure 1. Figure 1: Predicted linear convergence fac￾tors on subspace feasibility problems with n = 100, p = q = 50, φp = π/2, and angles {φi} defined by (4.4). -1.5 -1 -0.5 0 0.5 1 1.5 -1 -0.5 0 0.5 1 [PITH_FULL_IMAGE:figures/full_fig_p019_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: Subspace feasibility with n = 100, p = q = 50, φp = π/2, and angles given by (4.4). Log-scale plots of FPRk = kz k+1 − z kk/ max{1, kz kk} for DR, CARPA-opt(γ) with θ = η = 1, gCARPA-opt(γ) with θ = η = 0.7, and gCARPA-grid best (γ, θ, η). 4.2.3 Trajectory illustration Finally, we visualize the trajectory behavior on a single principal-angle plane. For subspace feasibility, the DR fixed-point iteration typ… view at source ↗
Figure 4
Figure 4. Figure 4: Toy sparse linear inverse instance with ( [PITH_FULL_IMAGE:figures/full_fig_p025_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Realistic sparse linear inverse instances: log-s [PITH_FULL_IMAGE:figures/full_fig_p026_5.png] view at source ↗
read the original abstract

We study the two-set feasibility problem of finding a point in the intersection $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 $(\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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript proposes the generalized composed alternating relaxed projection algorithm (gCARPA) for the two-set feasibility problem of finding a point in X ∩ Y where X and Y are closed convex sets in a Hilbert space. The method combines Douglas-Rachford-type and projection-reflection-type dynamics through an outer averaging parameter μ and an internal relaxation triple (γ, θ, η). It recovers several classical projection methods as special cases under suitable parameter choices. Convergence is proved for both the stationary algorithm and its non-stationary variant with iteration-dependent parameters. For the subspace feasibility model, an explicit spectral characterization is derived via principal-angle block decompositions, yielding computable subdominant-eigenvalue factors and a minimax parameter-selection recipe. Numerical experiments illustrate performance relative to baseline methods.

Significance. If the convergence claims hold, the paper supplies a unifying parametric framework for projection algorithms that extends standard results on averaged and firmly nonexpansive operators while adding a non-stationary extension and an explicit rate formula for the subspace case. The spectral analysis and minimax tuning recipe are particularly useful for applications where subspace models appear, and the recovery of classical methods as special cases provides a clear unification. The numerical illustrations suggest practical benefits in problem-dependent regimes.

minor comments (3)
  1. The statement that the algorithm contains classical methods as special cases would benefit from an explicit table or enumerated list (with the precise parameter settings for each recovered method) to allow immediate verification by readers.
  2. In the subspace spectral analysis, the transition from the principal-angle block decomposition to the explicit subdominant-eigenvalue expression should include a short derivation sketch or reference to the relevant matrix blocks to improve readability.
  3. The numerical experiments section would be strengthened by reporting the specific dimensions, generation procedure for the test sets, and stopping criteria used, so that the observed improvements can be reproduced and compared quantitatively.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive and accurate summary of the manuscript, including the unification of projection methods via gCARPA, the convergence results for both stationary and non-stationary variants, the explicit spectral analysis for subspace feasibility, and the numerical illustrations. We are pleased that the significance of the parametric framework, the minimax tuning recipe, and the recovery of classical methods as special cases was recognized. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The manuscript defines gCARPA explicitly via the outer averaging parameter μ and internal relaxations (γ,θ,η), recovers classical methods by direct substitution into those parameters, proves convergence by verifying that the composed operator remains averaged or firmly nonexpansive under the stated ranges (standard facts from convex analysis), and obtains the subspace spectral characterization by block-diagonalizing the iteration operator with respect to principal-angle subspaces. None of these steps reduce to a fitted quantity defined from the target result, a self-citation chain, or an ansatz smuggled in; the central claims follow directly from the operator definitions and the listed hypotheses on X and Y.

Axiom & Free-Parameter Ledger

2 free parameters · 1 axioms · 0 invented entities

The central claim rests on the standard domain assumption that the sets are closed and convex in a Hilbert space together with the free choice of relaxation parameters that must satisfy averaging conditions for the convergence theorems.

free parameters (2)
  • outer averaging weight μ
    Tunable scalar that blends the two dynamics; its admissible range is part of the algorithm definition.
  • internal relaxation triple (γ, θ, η)
    Three scalars controlling the relaxed projections; chosen once or per iteration in the non-stationary case.
axioms (1)
  • domain assumption X and Y are closed convex subsets of a Hilbert space
    Invoked to guarantee that the projection operators are well-defined, single-valued, and firmly nonexpansive.

pith-pipeline@v0.9.0 · 5467 in / 1328 out tokens · 57465 ms · 2026-05-10T06:20:14.965544+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages

  1. [1]

    Arag´ on Artacho and Rub´ en Campoy

    Francisco J. Arag´ on Artacho and Rub´ en Campoy. Optimal rates of linear convergence of the averaged alternating modified reflections method for t wo subspaces. Numerical Algorithms, 82:397–421, 2019

    work page 2019

  2. [2]

    Iusem, and Luiz-Rafael Santos

    Reza Arefidamghani, Roger Behling, Alfredo N. Iusem, and Luiz-Rafael Santos. A circumcentered-reflection method for finding common fixed po ints of firmly nonexpansive operators. arXiv preprint arXiv:2203.02410 , 2022

    work page arXiv 2022

  3. [3]

    H. H. Bauschke and J. M. Borwein. On the convergence of von neumann’s alternating projection algorithm for two sets. Set-Valued Analysis, 1(2):185–212, 1993

    work page 1993

  4. [4]

    H. H. Bauschke, J. Y. B. Cruz, T. T. A. Nghia, H. M. Phan, and X. Wang. The rate of linear convergence of the douglas–rachford algorithm for s ubspaces is the cosine of the friedrichs angle. Journal of Approximation Theory , 185:63–79, 2014. 27

    work page 2014

  5. [5]

    H. H. Bauschke, J. Y. Bello Cruz, T. T. Nghia, H. M. Pha, and X. Wang. Optimal rates of linear convergence of relaxed alternating projections a nd generalized douglas-rachford methods for two subspaces. Numerical Algorithms, 73(1):33–76, 2016

    work page 2016

  6. [6]

    Bauschke, Tom Bendit, and Walaa M

    Heinz H. Bauschke, Tom Bendit, and Walaa M. Moursi. How av eraged is the composition of two linear projections? Numerical Functional Analysis and Optimization , 44(15- 16):1652–1668, 2023

    work page 2023

  7. [7]

    Correction to: convex analysis and mono- tone operator theory in hilbert spaces

    Heinz H Bauschke and Patrick L Combettes. Correction to: convex analysis and mono- tone operator theory in hilbert spaces. pages C1–C4, 2020

    work page 2020

  8. [8]

    Bauschke, Patrick L

    Heinz H. Bauschke, Patrick L. Combettes, and Simeon Reic h. The asymptotic behavior of the composition of two resolvents. Nonlinear Analysis: Theory, Methods & Applications , 60(2):283–301, 2005

    work page 2005

  9. [9]

    Bauschke, J

    Heinz H. Bauschke, J. Y. Bello Cruz, Tran T. A. Nghia, Hung M. Pha, and Xianfu Wang. Optimal rates of linear convergence of relaxed alternating projections and generalized douglas-rachford methods for two subspaces. Numerical Algorithms, 73:33–76, 2016

    work page 2016

  10. [10]

    Bauschke, Dayou Mao, and Walaa M

    Heinz H. Bauschke, Dayou Mao, and Walaa M. Moursi. How to project onto the intersec- tion of a closed affine subspace and a hyperplane. Mathematical Methods of Operations Research, 100(2):411–435, 2024

    work page 2024

  11. [11]

    A suc- cessive centralized circumcentered-reflection method for the convex feasibility problem

    Roger Behling, Yunier Bello-Cruz, Alfredo Iusem, Di Li u, and Luiz-Rafael Santos. A suc- cessive centralized circumcentered-reflection method for the convex feasibility problem. Computational Optimization and Applications , 87(1):83–116, 2024

    work page 2024

  12. [12]

    On the circumcentered- reflection method for the convex feasibility problem

    Roger Behling, Yunier Bello-Cruz, and Luiz-Rafael San tos. On the circumcentered- reflection method for the convex feasibility problem. Numerical Algorithms , 86:1475– 1494, 2021

    work page 2021

  13. [13]

    Robust signal recovery under uncertain-but-bounded perturbations in observation matr ix

    Yannis Bekri, Anatoli Juditsky, and Arkadi Nemirovski . Robust signal recovery under uncertain-but-bounded perturbations in observation matr ix. Journal of Optimization Theory and Applications , 205(3):55, 2025

    work page 2025

  14. [14]

    P. L. Combettes. The convex feasibility problem in imag e recovery. 95:155–270, 1996

    work page 1996

  15. [15]

    P. L. Combettes and I. Yamada. Compositions and convex c ombinations of averaged nonexpansive operators. Journal of Mathematical Analysis and Applications , 425(1):55– 70, 2015

    work page 2015

  16. [16]

    Fast projection onto the simplex and th e l1 ball

    Laurent Condat. Fast projection onto the simplex and th e l1 ball. Mathematical Pro- gramming, 158(1):575–585, 2016

    work page 2016

  17. [17]

    Linear convergence of the gene ralized douglas–rachford algorithm for feasibility problems

    Minh N Dao and Hung M Phan. Linear convergence of the gene ralized douglas–rachford algorithm for feasibility problems. Journal of Global Optimization , 72:443–474, 2018

    work page 2018

  18. [18]

    Dao and Hung M

    Minh N. Dao and Hung M. Phan. Linear convergence of proje ction algorithms. Mathe- matics of Operations Research , 44(2):715–738, 2019

    work page 2019

  19. [19]

    Douglas and H

    J. Douglas and H. H. Rachford. On the numerical solution of heat conduction problems in two and three space variables. Transactions of the American Mathematical Society , 82(2):421–439, 1956. 28

    work page 1956

  20. [20]

    Efficient pro- jections onto the ℓ1-ball for learning in high dimensions

    John Duchi, Shai Shalev-Shwartz, Yoram Singer, and Tus har Chandra. Efficient pro- jections onto the ℓ1-ball for learning in high dimensions. In Proceedings of the 25th International Conference on Machine Learning (ICML) , pages 272–279, 2008

    work page 2008

  21. [21]

    F¨ alt and P

    M. F¨ alt and P. Giselsson. Optimal convergence rates fo r generalized alternating projec- tions. In 2017 IEEE 56th Annual Conference on Decision and Control (CDC) , pages 2268–2274. IEEE, 2017

    work page 2017

  22. [22]

    Convergence improvement and noise attenuation consi derations for beyond alias projection onto convex sets reconstruction

    Jianjun Gao, Aaron Stanton, Mostafa Naghizadeh, Mauri cio D Sacchi, and Xiaohong Chen. Convergence improvement and noise attenuation consi derations for beyond alias projection onto convex sets reconstruction. Geophysical prospecting, 61:138–151, 2013

    work page 2013

  23. [23]

    L. G. Gubin, B. T. Polyak, and E. V. Raik. The method of pro jections for finding the common point of convex sets. USSR Computational Mathematics and Mathematical Physics, 7(6):1–24, 1967

    work page 1967

  24. [24]

    W. L. Hare and A. S. Lewis. Identifying active manifolds . Algorithmic Operations Re- search, 2(2):75–82, 2007

    work page 2007

  25. [25]

    Lewis, D

    Adrian S. Lewis, D. Russell Luke, and J´ erˆ ome Malick. Local linear convergence for alter- nating and averaged nonconvex projections. Foundations of Computational Mathematics , 9(4):485–513, 2009

    work page 2009

  26. [26]

    Douglas–rachford splittin g for nonconvex optimization with application to nonconvex feasibility problems

    Guoyin Li and Ting Kei Pong. Douglas–rachford splittin g for nonconvex optimization with application to nonconvex feasibility problems. Mathematical Programming, 159:371– 401, 2016

    work page 2016

  27. [27]

    Liang, J

    J. Liang, J. Fadili, and G. Peyr´ e. Convergence rates with inexact non-expansive operators. Mathematical Programming, 159(1-2):403–434, 2016

    work page 2016

  28. [28]

    Liang, J

    J. Liang, J. Fadili, and G. Peyr´ e. Local convergence pr operties of douglas–rachford and alternating direction method of multipliers. Journal of Optimization Theory and Applications, 172(3):874–913, 2017

    work page 2017

  29. [29]

    Lorenz and Quoc Tran-Dinh

    Dirk A. Lorenz and Quoc Tran-Dinh. Non-stationary doug las–rachford and alternating direction method of multipliers: adaptive step-sizes and c onvergence. Computational Optimization and Applications , 74:67–92, 2019

    work page 2019

  30. [30]

    Russell Luke

    D. Russell Luke. Relaxed averaged alternating reflecti ons for diffraction imaging. Inverse Problems, 21(1):37, 2004

    work page 2004

  31. [31]

    D. W. Peaceman and H. H. Rachford, Jr. The numerical solu tion of parabolic and elliptic differential equations. Journal of the Society for Industrial and Applied Mathematic s, 3(1):28–41, 1955

    work page 1955

  32. [32]

    Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem

    Ting Kei Pong, Hao Sun, Ningchuan Wang, and Henry Wolkow icz. Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem. Computational optimization and applications , 63(2):333–364, 2016

    work page 2016

  33. [33]

    Trajectory of alternat ing direction method of multipliers and adaptive acceleration

    Clarice Poon and Jingwei Liang. Trajectory of alternat ing direction method of multipliers and adaptive acceleration. Advances in neural information processing systems , 32, 2019

    work page 2019

  34. [34]

    Geometry of first-order methods and adaptive acceleration

    Clarice Poon and Jingwei Liang. Geometry of first-order methods and adaptive acceler- ation. arXiv preprint arXiv:2003.03910 , 2020. 29

    work page arXiv 2003

  35. [35]

    The optimal error bound for the method of simultaneous projections

    Simeon Reich and Rafa/suppress l Zalas. The optimal error bound for the method of simultaneous projections. Journal of Approximation Theory , 223:96–107, 2017

    work page 2017

  36. [36]

    A composed alternating r elaxed projection algorithm for feasibility problem, 2025

    Yuting Shen and Jingwei Liang. A composed alternating r elaxed projection algorithm for feasibility problem, 2025. arXiv:2504.11313

    work page arXiv 2025

  37. [37]

    Learning models for seismic-i nduced vibrations optimal control in structures via random forests

    Francesco Smarra, Giovanni Domenico Di Girolamo, Vinc enzo Gattulli, Fabio Graziosi, and Alessandro D’Innocenzo. Learning models for seismic-i nduced vibrations optimal control in structures via random forests. Journal of Optimization Theory and Applica- tions, 187(3):855–874, 2020

    work page 2020

  38. [38]

    A new hybrid cq algorithm for the split feasibility problem in hilbert spaces and its a pplications to compressed sensing

    Suthep Suantai, Suparat Kesornprom, and Prasit Cholam jiak. A new hybrid cq algorithm for the split feasibility problem in hilbert spaces and its a pplications to compressed sensing. Mathematics, 7(9):789, 2019

    work page 2019

  39. [39]

    Friedlander, Gilles Henn enfent, Felix J

    Ewout Van Den Berg, Michael P. Friedlander, Gilles Henn enfent, Felix J. Herrmann, Rayan Saab, and ¨Ozg¨ ur Yilmaz. Algorithm 890: Sparco: A testing framework f or sparse reconstruction. ACM Transactions on Mathematical Software (TOMS) , 35(4):1–16, 2009. 30

    work page 2009