{'fraction_non_alphanumeric': 0.05781833264205724, 'fraction_numerical': 0.01493156366652841, 'mean_word_length': 3.810853950518755, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Note on the Finite Convergence of Alternating Projections

We establish sufficient conditions for finite convergence of the alternating projection method for finding the closest points in two non-intersecting sets. To the best of our knowledge, these are the first known results on finite convergence for alternating projections. In the special case of a polyhedron and closed half space, our sufficient conditions allow us to quantify how large the distance between these sets needs to be for alternating projects to converge in a single iteration.

(a) Linear convergence (b) Finite convergence (c) 1 step convergence Fig. 1 Convergence of the alternating projection method A key step in our approach is to extend the concept of intrinsic transversality, first defined for consistent cases in [11], to the more general setting when the intersection can be empty or nonempty (Conditions 1, 2, 3 in Section 3). We show that under these conditions, finite convergence of alternating projections is guaranteed. Additionally, the number of iterations depends on the distance between the two sets, the starting point and a constant, which is the maximum angle between vectors of type (a − b), where a ∈ A and b ∈ B, and the proximal normal cones N prox A (a) and N prox B (b). Using these conditions, we then prove the finite convergence of alternating projections and calculate the number of steps for a case when the two sets are a polyhedron and a closed half space.
Projection methods are often used as robust methods for solving large-scale linear programming problems and systems of linear equations (see [2,3,7,12,13,19,20]). A linear programming problems can indeed be solved by finding the closest points of the following sets (1) the problem feasible's region; and (2) the closed half space containing all vectors whose objective function value does not exceed a specified lower bound for the cost function.
These two sets are polyhedrons and hence our results for finite convergence of the alternating projection method are applicable. We can also determine the minimum distance (or lower bound), relative to the starting point, needed to ensure the convergence after one iteration. This idea is valid not just for linear programming problems, but also some other optimization problems.
The paper is organized as follows. In Section 2, we recall some essential results that will be used in subsequent sections, and we provide a new proof for one of these results. Section 3 contains our main result on the finite convergence of the alternating projection method. Section 4 explores its finite convergence for some special cases and then discusses the application of this technique to linear programming.

Preliminaries and auxiliary results
Let B denote the open unit ball and furthermore let B δ (x) and B δ (x) denote, respectively, the open and closed balls with center x and radius δ > 0. We use R and R + to denote the real line (with the usual norm) and the set of all non-negative real numbers. The boundary and interior of a set A are denoted as bd A and int A, respectively. The distance from a point x to a set A is defined by d(x, A) := inf u∈A u − x , and we use the convention d(x, ∅) = +∞. The set of all projections of x onto A is If A is a closed subset of a finite dimensional space, then P A (x) = ∅. Additionally, if A is a closed convex set of an Euclidean space, then P A (x) is a singleton. As defined in [17], the proximal normal cone to A at a ∈ A is defined as follows: For convenience, we will use the notation N A (a) instead of N prox A (a) throughout. Observe that if a ∈ P A (x), then x − a ∈ N A (a). A functional counterpart of the proximal normal cone is the proximal subdifferential of a proper lower semicontinuous function, denote ∂ P f , or ∂f for simplicity. Note that the fuzzy sum rule holds for ∂f . Note also that ∂1 A (a) = N A (a) for any a ∈ A, here 1 A is the indicator function of the set A. If we replace proximal normal cones by Fréchet normal cones, the analysis throughout the paper still holds.
The following definition was introduced in [11]. Our convergence results rely on modifications of this definition.
Definition 1 (Intrinsic transversality) [11, Definition 3.1] Given two closed sets A, B of a Hilbert space The following result has been proved in [11] and here we give an alternative proof.
Theorem 1 (Distance decrease) [11, Theorem 5.2] Consider a Hilbert space X, a closed set A, and points Proof Consider the continuous function f (x) = x − b and suppose to the contrary that . By (4), we have x 0 is the global minimizer of the sum x − a < δ, the previous inequality contradicts (2).
The next proposition provides complementary results for the convergence of the alternating projections. Proof If a − b = d > 0 with a ∈ A, b ∈ B, then a ∈ P A (b) and b ∈ P B (a). By the definition of the proximal normal cones, b − a ∈ N A (a) and a − b ∈ N B (b).
Consider the distance function restricted to the sets A and B, f : The product space X × X is equipped with the usual sum norm. When two sets A, B are convex, the function f is convex. We have (a, b) is the global minimizer of f , or equivalently a pair of shortest distance between A and B if and only if The next theorem establishes the linear convergence of the alternating projection method under intrinsic transversality assumption.

Convergence results
We extend the definition of the intrinsic transversality in Definition 1 to more general frameworks without the assumption A ∩ B = ∅, relaxingx and its local neighborhood Bρ(x). Condition 1 is applied for the whole sets A, B. In Condition 2, we consider local neighbourhoods around the given points. Condition 1 Given two closed sets A, B of a Hilbert space X and a constant α ∈ (0, 1), for all Remark 1 If A ∩ B = ∅, then d(A, B) = 0 and Condition 2 reduces to Definition 1 and Condition 1 reduces to the following condition. Condition 1' Given two closed sets A, B of a Hilbert space X, A ∩ B = ∅, and a constant α ∈ (0, 1), for all x ∈ A \ B, y ∈ B \ A, the inequality (1) holds. This assumption is an extension of Definition 1 to the global framework. Observe that for anyx ∈ A ∩ B, the pair {A, B} is intrinsically transversal atx with ρ = +∞.
We will show later in this section that under Conditions 1 or 2, when A ∩ B = ∅, the method of alternating projection converges after finite number of steps. First, we establish the key result for the convergence theorems.
Consequently, if Condition 1 holds, inequality holds for any This implies z ∈ A \ B. Hence, inequality (1) holds with z in place of x. On the other hand, The estimations above together with inequality (1) yield d Then, applying Theorem 1, we obtain d(y, Lemma 1 studies the main building block of the method, which envolves two successive projections: Under Condition 1, thanks to Lemma 1 we have This idea plays the core role in the following theorem. Theorem 3 Suppose A, B are closed subsets of a Hilbert space X and Condition (1) holds for some α ∈ (0, 1). Consider a sequence of alternating projections x 2n ∈ A and x 2n+1 ∈ B (n ≥ 0).
(i) If d(A, B) > 0, then the alternating projections (xn) converge finitely to a pair of points of nearest distance. Furthermore, the number of steps is 2N with Proof Assume that Condition 1 holds with α ∈ (0, 1).
The following examples demonstrate the application of Condition 1 in Theorem 3. respectively. Hence, it is sufficient to consider x ∈ bd A and y ∈ bd B. Take x = (x 1 , |x 1 |) and y = (x 2 , 0) with x 1 , x 2 ∈ R, x 1 = 0. Observe that We have The two equalities above imply The method of alternating projections, initiated at x 0 , converges linearly tox with the rate 7/8. . Take x ∈ bd A and y ∈ bd B with x = (x 1 , |x 1 | + k), y = (x 2 , 0), x 1 , x 2 ∈ R, x 1 = 0. We apply the analysis in (i) for the pair x = (x 1 + k, |x 1 | + k) and y = ( Hence, the alternating projections converge after log 7/8 k d(x 0 , B)

steps.
Remark 2 Theorem 3 explains the finite convergence in Example 1 (ii). Additionally, the estimation on the number of steps (8) shows that the larger the distance between the two sets relative to the starting point, the fewer steps of the method. By increasing k (in b = (0, k)), the distance between two sets A and B + b increases accordingly. With the same starting point (x 0 , A), the algorithm will reach one of the nearest points after one projection, i.e. b ∈ P B+b (x 0 ).
The next example shows that if the setting does not satisfy Condition 1, the linear convergence and finite convergence as in previous example does not hold. Proof Suppose that Condition 2 holds with α ∈ (0, 1)and ρ > 0.
Remark 3 (i) Since Condition 2 is weaker than intrinsic transversality property, Theorem 4 is rich enough to cover Theorem 2. (ii) When two sets A ∩ B = ∅ and a ∈ A, b ∈ B with a − b = d(A, B), it is hard to localize the setting A, B at a and b in the sense that all the projections of any points sufficiently near a or b will remain stay near a, b. In the global version (Condition 1), we do not encounter this obstacle. This explains why we cannot estimate an upper bound for the number of steps for the method in Theorem 4.

Condition 3
Given two closed subsets A, B of a Hilbert space X and constants α ∈ (0, 1), β ∈ [0, 1], then for all x ∈ A \ B and y ∈ P B (x) such that d(y, A) > d (A, B), then with δ = α( x − y − βd(A, B)) > 0 and ρ = x − y . In Condition 3, instead of considering all vectors y ∈ B \ A, we only consider the projections of the vector x onto A. This condition also gives us flexibility in choosing the neighborhoods of x in B. The next theorem presents the convergence results of the method under this condition.
(i) If β < 1, then (xn) converges finitely to a pair of points of nearest distance and the number of step is 2N (ii) If β = 1, then the sequence ( x 2n − x 2n+1 − d) converges linearly to 0 with the rate (1 − α 2 ).
(i) If β < 1, from the above inequalities, we have and the sequence (xn) converges after N steps.
(ii) If β = 1, we have The sequence ( x 2n − x 2n−1 − d) converges linearly to 0 with a linear rate (1 − α 2 ). Remark 4 Theorem 5 states that if the neighborhood associated with the vector x in Condition 3 is small, the method will not converge finitely. Observe that in (i), the radius δ is always bigger than the constant α(1 − β)d (A, B). On the other hand, in (ii), the radius δ tends to 0 when x − y → d(A, B). When d(A, B) = 0, Theorem 5 can be formulated as in Theorem 3.

Alternating projections for two polyhedrons
In this section, we apply the results in Section 3 for some special cases in Euclidean spaces. First, we consider the case when the two sets are a polyhedron and a closed half space.
with the convention that the minimum over an empty set is 1.
Proof Take x ∈ A and y ∈ P B (x) such that d(y, A) > d(A, B). Due to Proposition 1 (i), y−x / ∈ N A (x) = R + (c) and c / ∈ N B (y), hence y − x, c < y − x c . On the other hand, c, x ≤ M < c, y , therefore, c, x − y < 0 and due to (14) together with c / ∈ N B (y) and x − y ∈ N B (y), we have Observe that either z ∈ int A and N A (z) = {0} or z ∈ bd A and N A (z) = R + (c). For both cases, we have the following estimations Hence, inequality (11) holds. The pair {A, B} satisfies Condition 3 with β = 0 and α defined as in (14).
Theorem 6 Let X be an Euclidean space, A a closed subspace and B a polyhedron defined as in Proposition 2 with A ∩ B = ∅. Then, the method of alternating projections, initiated at x 0 ∈ A, converges after 2N steps with where the constant α is given in (14). If B is a polyhedron, we can replace A by the closed half space Note also that if two sets in R n are convex and one of the set is bounded (i.e. compact), the method of alternating projections always converge to a pair of points of shortest distance.  The alternating projections for two polyhedrons, in general, are not necessary to converge finitely. The following example presents a simple counterexample.  We propose a projection method for solving linear programming (LP). min c, x

We have
x ∈ A,