A Composed Alternating Relaxed Projection Algorithm for Feasibility Problem

Yuting Shen, Jingwei Liang · 2025

Read A Composed Alternating Relaxed Projection Algorithm for Feasibility Problem by Yuting Shen, Jingwei Liang (2025) 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-2504-11313.txt.

Introduction

Yuting Shen and Jingwei Liang offer a new math method in a 2025 paper. The basic task is to find a point that lies in two or more closed sets at once. Such tasks show up in imaging, planning, and signal work. Classic methods bounce a guess between the sets until it settles.

One classic method can spiral slowly when the sets are flat subspaces. The same method can be very fast on curved sets, though. The authors build on it by adding a mix of projection and reflection steps. They also give a version whose settings change as it runs. Proofs in the paper back the claims, and number tests support them. The goal is faster, more reliable solving across both flat and curved cases.

Catalog record

CREATORYuting Shen, Jingwei Liang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-11313

Browse the full library · About the Tower of Babel

Full text

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

A Composed Alternating Relaxed Projection Algorithm for Feasibility Problem Yuting Shen, Jingwei Liang Abstract Feasibility problem aims to find a common point of two or more closed (convex) sets whose intersection is nonempty. In the literature, projection based algorithms are widely adopted to solve the problem, such as the method of alternating projection (MAP), and Douglas–Rachford splitting method (DR). The performance of the methods are governed by the geometric properties of the underlying sets. For example, the fixed-point sequence of the Douglas–Rachford splitting method exhibits a spiraling behavior when solving the feasibility problem of two subspaces, leading to a slow convergence speed and slower than MAP. However, when the problem at hand is non-polyhedral, DR can demonstrate significant faster performance. Motivated by the behaviors of the DR method, in this paper we propose a new algorithm for solving convex feasibility problems. The method is designed based on DR method by further incorporating a composition of projection and reflection. A non-stationary version of the method is also designed, aiming to achieve faster practical performance. Theoretical guarantees of the proposed schemes are provided and supported by numerical experiments. Key words. Feasibility problem, Projection, Relaxation, Friedrichs angle, Linear convergence 1 Introduction In this paper, we are interested in the following feasibility problem of two sets (1.1) \mathrm{find}\hskip 5.0pt{x\in\mathcal{H}}\hskip 5.0pt\textrm{such\,that}\hskip 5.0ptx\in X\cap Y, where \mathcal{H} is a real Hilbert space, and X,Y\subset\mathcal{H} are closed convex such that X\cap Y\neq\emptyset. Feasibility problems exist in various fields including signal/image processing [ 14 ] , compressed sensing [ 32 , 34 ] , seismic data processing [ 20 ] , etc. In the literature, projection (see Definition 2.2 ) based algorithms are widely adopted to solve feasibility problems. Over the years, significant advances have been made in both numerical methods and theoretical understanding. The very basic algorithm to solve the feasibility problem is the method of alternating projection (MAP) [ 21 , 4 ] . With an initial point which does not necessarily belong to either of the two sets, MAP applied the projection of the two alternatively. The convergence of the method can be obtained when the two sets are closed and convex, even when the intersection is empty [ 4 ] . Based on MAP, various modifications of the method can be found in the literature, such as relaxed alternating projection (RAP) and partial relaxed alternating projection (PRAP) [ 6 ] , averaged alternating modified reflections (AAMR) [ 1 ] , relaxed averaged alternating reflections (RAAR) [ 28 ] , simultaneous projection (SP) [ 31 ] , and generalized relaxed alternating projection (GRAP) [ 19 , 16 ] . Recently, by further utilizing the geometric properties of the problem, a so-called circumcentered-reflection method (CRM) is designed [ 2 , 12 , 11 ] . Operator splitting methods can also be applied to solve the feasibility problem, since the projection operator is a special case of the proximity operator [ 3 ] . Actually, MAP is an instance of the Backward-Backward splitting method [ 8 ] . For both AAMR and GRAP methods, with proper parameter choices, they can recover the Peaceman–Rachford splitting method [ 29 ] , and the Douglas–Rachford splitting method [ 18 ] ; see Table 1 for details. Theoretical understandings of projection based methods under different settings are also studied. As most projection based methods can be written fixed-point iteration of nonexpansive operators, their global convergence and convergence rate can be found in [ 25 ] . When the underling two sets are so-called “partly smooth” [ 22 ] , locally linear convergence can be obtained, see for instance [ 23 , 26 ] . In [ 24 ] , convergence properties of DR for nonconvex feasibility problem is studied. When the two sets are moreover subspaces, in [ 5 , 9 , 1 ] the authors studied the (optimal) linear convergence rate of several projection based methods, including DR and MAP. We also refer to [ 17 ] for linear convergence of projection methods, and [ 7 , 10 ] for recent development of projection algorithms. 1.1 Motivation and contribution Consider the problem where X,Y are two subspaces, then MAP and DR converge linearly where the rate of convergence is characterized by the Friedrichs angle between X and Y (see Definition 2.5 ) [ 5 , 6 ] . Moreover, from the convergence analysis of [ 5 ] , it can be derived that the trajectory of the fixed-point sequence of DR forms a spiral, see also [ 30 ] . In Figure 1 we provide an illustration of this behavior, X,Y are two intersecting subspaces, the black spiral denotes the trajectory of the fixed-point sequence of DR. Such spiral behavior is the main reason why DR performs poorly on subspace feasibility problems, see Table 1 and Figure 2 for details. Figure 1: Spiraling behavior of the fixed-point sequence of Douglas–Rachford splitting method. In [ 6 ] , it is shown that for this problem the standard DR achieves the optimal convergence rate, and relaxation does not provide acceleration. Moreover, as pointed out in [ 30 ] , inertial acceleration also fails to provide speedup. Motivated by this behavior of DR method, in this paper we propose a composed alternating relaxed projection algorithm (CARPA, see Algorithm 1 ) to improve the performance of the DR method. The green trajectory in Figure 1 displays the trajectory of the fixed-point sequence of CARPA. The key idea of the method a convex combination of the DR and projection-reflection, doing so the method managed to provide significant acceleration over DR method, see Table 1 and Figure 2 . More precisely, this work contains the following contributions • A novel projection based algorithm (Algorithm 1 ) for solving convex feasibility problems, with theoretical guarantees. We also design a non-stationary version of the method, and prove its convergence property. • For the feasibility problem of two subspaces, we analyze the linear rate of convergence of the method and identify parameter choices under which optimal convergence rate is obtained. Furthermore, numerical experiments on feasibility of two subspaces, a ball tangent to a subspace and a compressed sensing problem are provided to demonstrate the advantages of the proposed schemes. 1.2 Paper organization The remainder of this paper is organized as follows. In Section 2 , we introduce the notations and basic results used throughout the paper. Section 3 describes the proposed method and its non-stationary version, with theoretical analysis. In Section 4 , we provide numerical comparisons against several existing methods in the literature. 2 Mathematical background Denote \mathcal{H} the Hilbert space equipped with scalar inner product \langle\cdot,\,\cdot\rangle and the associated norm {|\kern-1.125pt|}\cdot{|\kern-1.125pt|} . Denote \mathbb{R}^{n} the n -dimensional real Euclidean space. \mathrm{Id} denotes the identity operator. Given A\in\mathbb{R}^{m\times n} , denote by \mathrm{ker}(A) , \mathrm{ran}(A) , \mathrm{rank}(A) the kernel, range, rank of A , respectively. Operators In this part, we provide the definitions of nonexpansive and projection related operator, we refer to [ 3 , Chapter 4] for more details regarding this topic. Definition 2.1 (Nonexpansive operator). An operator \mathcal{F}:\mathcal{H}\rightarrow\mathcal{H} is called nonexpansive if it is 1 -Lipschitz continuous, i.e. {|\kern-1.125pt|}\mathcal{F}(x)-\mathcal{F}(x^{\prime}){|\kern-1.125pt|}\leq{|\kern-1.125pt|}x-x^{\prime}{|\kern-1.125pt|},\,\,\,\forall x,x^{\prime}\in\mathcal{H}. For any \alpha\in]0,1[ , \mathcal{F} is \alpha -averaged if there exists a nonexpansive operator \mathcal{F}^{\prime} such

Read the complete text