{'fraction_non_alphanumeric': 0.04748279694483199, 'fraction_numerical': 0.013407741965995885, 'mean_word_length': 4.029135450112975, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 31, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 38, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Local convergence for alternating and averaged nonconvex projections

The idea of a finite collection of closed sets having"strongly regular intersection"at a given point is crucial in variational analysis. We show that this central theoretical tool also has striking algorithmic consequences. Specifically, we consider the case of two sets, one of which we assume to be suitably"regular"(special cases being convex sets, smooth manifolds, or feasible regions satisfying the Mangasarian-Fromovitz constraint qualification). We then prove that von Neumann's method of"alternating projections"converges locally to a point in the intersection, at a linear rate associated with a modulus of regularity. As a consequence, in the case of several arbitrary closed sets having strongly regular intersection at some point, the method of"averaged projections"converges locally at a linear rate to a point in the intersection. Inexact versions of both algorithms also converge linearly.


Introduction
An important theme in computational mathematics is the relationship between the "conditioning" of a problem instance and the speed of convergence of iterative solution algorithms on that instance. A classical example is the method of conjugate gradients for solving a positive definite system of linear equations: we can bound the linear convergence rate in terms of the relative condition number of the associated matrix. More generally, Renegar [32][33][34] showed that the rate of convergence of interior-point methods for conic convex programming can be bounded in terms of the "distance to ill-posedness" of the program.
In studying the convergence of iterative algorithms for nonconvex minimization problems or nonmonotone variational inequalities, we must content ourselves with a local theory. A suitable analogue of the distance to ill-posedness is then the notion of "metric regularity", fundamental in variational analysis. Loosely speaking, a generalized equation, such as a system of inequalities, for example, is metrically regular when, locally, we can bound the distance from a trial solution to an exact solution by a constant multiple of the error in the equation generated by the trial solution. The constant needed is called the "regularity modulus", and its reciprocal has a natural interpretation as a distance to ill-posedness for the equation [15].
This philosophy suggests understanding the speed of convergence of algorithms for solving generalized equations in terms of the regularity modulus at a solution. Recent literature focuses in particular on the proximal point algorithm (see for example [1,22,29]). A unified approach to the relationship between metric regularity and the linear convergence of a family of conceptual algorithms appears in [23].
We here study a very basic algorithm for a very basic problem. We consider the problem of finding a point in the intersection of several closed sets, using the method of averaged projections: at each step, we project the current iterate onto each set, and average the results to obtain the next iterate. Global convergence of this method in the case of two closed convex sets was proved in 1969 in [2]. In this work we show, in complete generality, that this method converges locally to a point in the intersection of the sets, at a linear rate governed by an associated regularity modulus. Our linear convergence proof is elementary: although we use the idea of the normal cone, we apply only the definition, and we discuss metric regularity only to illuminate the rate of convergence.
Our approach to the convergence of the method of averaged projections is standard [4,30]: we identify the method with von Neumann's alternating projection algorithm [40] on two closed sets (one of which is a linear subspace) in a suitable product space. A nice development of the classical method of alternating projections may be found in [11]. The linear convergence of the method for two closed convex sets with regular intersection was proved in [4], strengthening a classical result of [21]. Remarkably, we show that, assuming strong regularity, local linear convergence requires good geometric properties (such as convexity, smoothness, or more generally, "amenability " or "proxregularity") of only one of the two sets.
One consequence of our convergence proof is an algorithmic demonstration of the "exact extremal principle" described in [26,Theorem 2.8]. This result, a unifying theme in [26], asserts that if several sets have strongly regular intersection at a point, then that point is not "locally extremal" [26]: in other words, translating the sets by small vectors cannot render the intersection empty locally. To prove this result, we simply apply the method of averaged projections, starting from the point of regular intersection. In a further section, we show that inexact versions of the method of averaged projections, closer to practical implementations, also converge linearly.
The method of averaged projections is a conceptual algorithm that might appear hard to implement on concrete nonconvex problems. However, the projection problem for some nonconvex sets is relatively easy. A good example is the set of matrices of some fixed rank: given a singular value decomposition of a matrix, projecting it onto this set is immediate. Furthermore, nonconvex iterated projection algorithms and analogous heuristics are quite popular in practice, in areas such as inverse eigenvalue problems [7,8], pole placement [27,42], information theory [39], low-order control design [19,20,28] and image processing [5,41]). Previous convergence results on nonconvex alternating projection algorithms have been uncommon, and have either focussed on a very special case (see for example [7,25]), or have been much weaker than for the convex case [10,39]. For more discussion, see [25].
Our results primarily concern R-linear convergence: in other words, we show that our sequences of iterates converge, with error bounded by a geometric sequence. In a final section, we employ a completely different approach to show that the method of averaged projections, for prox-regular sets with regular intersection, has a Q-linear convergence property: each iteration guarantees a fixed rate of improvement. In a final section, we illustrate these theoretical results with an elementary numerical example coming from signal processing.

Notation and definitions
We begin by fixing some notation and definitions. Our underlying setting throughout this work is a Euclidean space E with corresponding closed unit ball B. For any point x ∈ E and radius ρ > 0 , we write B ρ (x) for the set x + ρB.
Consider first two sets F, G ⊂ R. A pointx ∈ F ∩G is locally extremal [26] for this pair of sets if restricting to a neighborhood ofx and then translating the sets by small distances can render their intersection empty: in other words, there exists a ρ > 0 and a sequence of vectors z r → 0 in E such that

Clearlyx is not locally extremal if and only if
For recognition purposes, it is easier to study a weaker property than local extremality. Following the terminology of [24], we say the two sets F, G ⊂ E have strongly regular intersection at the pointx ∈ F ∩ G if there exists a constant α > 0 such that for all points x ∈ F nearx and z ∈ G nearx. By considering the case x = z =x, we see that strong regularity implies thatx is not locally extremal. This "primal" definition of strong regularity is often not the most convenient way to handle strong regularity, either conceptually or theoretically. By contrast, a "dual" approach, using normal cones, is very helpful.
Given a set F ⊂ E, we define the distance function and (multivalued) projection for F by The central tool in variational analysis is the normal cone to a closed set F ⊂ E at a pointx ∈ F , which can be defined (see [9,26,35]) as Notice two properties in particular. First, Secondly, the normal cone is a "closed" multifunction: for any sequence of points x r →x in F , any limit of a sequence of normals y r ∈ N F (x r ) must lie in N F (x). Indeed, the definition of the normal cone is in some sense driven by these two properties: it is the smallest cone satisfying the two properties.
Notice also that we have the equivalence: Normal cones provide an elegant alternative approach to defining strong regularity. In general, a family of closed sets F 1 , F 2 , . . . F m ⊂ E has strongly regular intersection at a pointx ∈ ∩ i F i , if the only solution to the system is y i = 0 for i = 1, 2, . . . , m. In the case m = 2, this condition can be written and it is equivalent to our previous definition (see [24,Cor 2], for example). We also note that this condition appears throughout variational-analytic theory. For example, it guarantees the important inclusion (see [35,Theorem 6.42]) We will find it helpful to quantify the notion of strong regularity (cf. [24]). A straightforward compactness argument shows the following result.
Proposition 2.2 (quantifying strong regularity) A collection of closed sets F 1 , F 2 , . . . , F m ⊂ E have strongly regular intersection at a pointx ∈ ∩F i if and only if there exists a constant k > 0 such that the following condition holds: We define the condition modulus cond(F 1 , F 2 , . . . , F m |x) to be the infimum of all constants k > 0 such that property (2.3) holds. Using the triangle and Cauchy-Schwarz inequalities, we notice that vectors y 1 , y 2 , . . . , y m ∈ E always satisfy the inequality which yields . . . , m; in this case the condition modulus is zero. One goal of this paper is to show that, far from being of purely analytic significance, strong regularity has central algorithmic consequences, specifically for the method of averaged projections for finding a point in the intersection ∩ i F i . Given any initial point x 0 ∈ E, the algorithm proceeds iteratively as follows: Our main result shows, assuming only strong regularity, that providing the initial point x 0 is nearx, any sequence x 1 , x 2 , x 3 , . . . generated by the method of averaged projections converges linearly to a point in the intersection ∩ i F i , at a rate governed by the condition modulus.

Strong and metric regularity
The notion of strong regularity is well-known to be closely related to another central idea in variational analysis: "metric regularity". A concise summary of the relationships between a variety of regular intersection properties and metric regularity appears in [24]. We summarize the relevant ideas here. Consider a set-valued mapping Φ : For vectorsx ∈ E andȳ ∈ Φ(x), we say Φ is metrically regular atx forȳ if there exists a constant κ > 0 such that all vectors x ∈ E close tox and vectors y ∈ Y close toȳ satisfy Intuitively, this inequality gives a local linear bound for the distance to a solution of the generalized equation y ∈ Φ(x) (where the vector y is given and we seek the unknown vector x), in terms of the the distance from y to the set Φ(x). The infimum of all such constants κ is called the modulus of metric regularity of Φ atx forȳ, denoted reg Φ(x|ȳ). This modulus is a measure of the sensitivity or "conditioning" of the generalized equation y ∈ Φ(x). To take one simple example, if Φ is a single-valued linear map, the modulus of regularity is the reciprocal of its smallest singular value. In general, variational analysis provides a powerful calculus for computing the regularity modulus. In particular, we have the following formula [35,Thm 9.43]: where D * denotes the "coderivative". We now study these ideas for a particular mapping, highlighting the connections between metric and strong regularity. As in the previous section, consider closed sets F 1 , F 2 , . . . , F m ⊂ E and a pointx ∈ ∩ i F i . We endow the space E m with the inner product (x 1 , x 2 , . . . , x m ), (y 1 , y 2 , . . . , y m ) = i x i , y i , and define set-valued mapping Φ : Then the inverse mapping is given by and finding a point in the intersection ∩ i F i is equivalent to finding a solution of the generalized equation 0 ∈ Φ(x). By definition, the mapping Φ is metrically regular atx for 0 if and only if there is a constant κ > 0 such that the following strong metric inequality holds: Furthermore, the regularity modulus reg Φ(x|0) is just the infimum of those constants κ > 0 such that inequality (3.2) holds.
To compute the coderivative D * Φ(x|0), we decompose the mapping Φ as Ψ − A, where, for points x ∈ E, The calculus rule [35, 10.43 From the coderivative formula (3.1) we now obtain where, following the usual convention, we interpret the right-hand side as Thus the regularity modulus agrees exactly with the condition modulus that we defined in the previous section: Furthermore, as is well-known [24], strong regularity is equivalent to the strong metric inequality (3.2).

Clarke regularity and refinements
Even more central than strong regularity in variational analysis is the concept of "Clarke regularity". In this section we study a slight refinement, crucial for our development. In the interest of maintaining as elementary approach as possible, we use the following geometric definition of Clarke regularity.

Definition 4.1 (Clarke regularity)
A closed set C ⊂ R n is Clarke regular at a pointx ∈ C if, given any δ > 0, any two points u, z nearx with z ∈ C, and any point y ∈ P C (u), satisfy In other words, the angle between the vectors z −x and u − y, whenever it is defined, cannot be much less than π 2 when the points u and z are nearx.

Remark 4.2
This property is equivalent to the standard notion of Clarke regularity. To see this, suppose the property in the definition holds. Consider any unit vector v ∈ N C (x), and any unit "tangent direction" w to C atx. By definition, there exists a sequences u r →x, y r ∈ P C (u r ), and z r →x with z r ∈ C, such that By assumption, given any ǫ > 0, for all large r the angle between the two vectors on the left-hand side is at least π 2 − ǫ, and hence so is the angle between v and w. Thus v, w ≤ 0, so Clarke regularity follows, by [35,Cor 6.29]. Conversely, if the property described in the definition fails, then for some ǫ > 0 and some sequences u r →x, y r ∈ P C (u r ), and z r →x with z r ∈ C, the angle between the unit vectors is less than π 2 − ǫ. Then any cluster points v and w of the two sequences (4.3) are respectively an element of N C (x) and a tangent direction to C atx, and satisfy v, w > 0, contradicting Clarke regularity.
The property we need for our development is an apparently-slight modification of Clarke regularity.

Definition 4.4 (super-regularity)
A closed set C ⊂ R n is super-regular at a pointx ∈ C if, given any δ > 0, any two points u, z nearx with z ∈ C, and any point y ∈ P C (u), satisfy In other words, then angle between the vectors z − y and u − y, whenever it is defined, cannot be much less than π 2 when the points u and z are nearx. An equivalent statement involves the normal cone.

Proposition 4.5 (super-regularity and normal angles)
holds for all points y, z ∈ C nearx and all normal vectors v ∈ N C (y).
Proof Super-regularity follows immediately from the normal cone property describe in the proposition, by property (2.1). Conversely, suppose the normal cone property fails, so for some δ > 0 and sequences of distinct points y r , z r ∈ C approachingx and unit normal vectors v r ∈ N C (y r ), we have, for all r = 1, 2, . . ., v r , z r − y r z r − y r > δ.
Fix an index r. By definition of the normal cone, there exist sequences of distinct points u j r → y r and y j r ∈ P C (u j r ) such that Since lim j y j r = y r , we must have, for all large j, Choose j sufficiently large to ensure both the above inequality and the inequality u j r − y r < 1 r , and then define points u ′ r = u j r and y ′ r = y j r .
We now have sequences of points u ′ r , z r approachingx with z r ∈ C, and y ′ r ∈ P C (u ′ r ), and satisfying Hence C is not super-regular atx. Super-regularity is a strictly stronger property than Clarke regularity, as the following result and example make clear. Proof Suppose the point in question isx. Fix any δ > 0, and set y =x in Proposition 4.5. Then clearly any unit tangent direction d to C atx and any unit normal vector v ∈ N C (x) satisfy v, d ≤ δ. Since δ was arbitrary, in fact v, d ≤ 0, so Clarke regularity follows by [35,Cor 6.29].
2 Example 4.7 Consider the following function f : R → (−∞, +∞], taken from an example in [37]: The epigraph of this function is Clarke regular at (0, 0), but it is not hard to see that it is not super-regular there. Indeed, a minor refinement of this example (smoothing the set slightly close to the nonsmooth points (2 r , 0) and (2 r , 4 r−1 )) shows that a set can be everywhere Clarke regular, and yet not super-regular.
Super-regularity is a common property: indeed, it is implied by two wellknown properties, that we discuss next. Following [35], we say that a set C ⊂ R n is amenable at a pointx ∈ C when there exists a neighborhood U ofx, a C 1 mapping G : U → R ℓ , and a closed convex set D ⊂ R ℓ containing G(x), and satisfying the constraint qualification such that points x ∈ R n nearx lie in C exactly when G(x) ∈ D. In particular, if C is defined by C 1 equality and inequality constraints and the Mangasarian-Fromovitz constraint qualification holds atx, then C is amenable atx.
Proposition 4.9 (amenable implies super-regular) If a closed set C ⊂ R n is amenable at a point in C, then it is super-regular there.
Proof Suppose the result fails at some pointx ∈ C. Assume as in the definition of amenability that, in a neighborhood ofx, the set C is identical with the inverse image G −1 (D), where the C 1 map G and the closed convex set D satisfy the condition (4.8). Then by definition, for some δ > 0, there are sequences of points y r , z r ∈ C and unit normal vectors v r ∈ N C (y r ) satisfying v r , z r − y r > δ z r − y r , for all r = 1, 2, . . ..

It is easy to check the condition
for all large r, since otherwise we contradict assumption (4.8). Consequently, using the standard chain rule from [35], we deduce so there are normal vectors u r ∈ N D (G(y r )) such that ∇G(y r ) * u r = v r . The sequence (u r ) must be bounded, since otherwise, by taking a subsequence, we could suppose u r → ∞ and u r −1 u r approaches some unit vectorû, leading to the contradiction For all large r, we now have ∇G(y r ) * u r , z r − y r > δ z r − y r , and by convexity we know Adding these two inequalities gives But as r → ∞, the left-hand side is o( z r − y r ), since the sequence (u r ) is bounded and G is C 1 . This contradiction completes the proof. 2 A rather different refinement of Clarke regularity is the notion of "proxregularity". Following [31, Thm 1.3], we call a set C ⊂ E is prox-regular at a pointx ∈ C if the projection mapping P C is single-valued aroundx. (In this case, clearly C must be locally closed aroundx.) For example, if, in the definition of an amenable set that we gave earlier, we strengthen our assumption on the map G to be C 2 rather than just C 1 , the resulting set must be prox-regular. On the other hand, the set is amenable at the point (0, 0) (and hence super-regular there), but is not prox-regular there. Proof If the results fails atx ∈ C, then for some constant δ > 0, there exist sequences of points y r , z r ∈ C converging to the pointx, and a sequence of normal vectors v r ∈ N C (y r ) satisfying the inequality v r , z r − y r > δ v r · z r − y r .
By [31, Proposition 1.2], there exist constants ǫ, ρ > 0 such that for all large r. This gives a contradiction, since z r − y r ≤ δǫ ρ eventually. 2 Super-regularity is related to various other notions in the literature. We end this section with a brief digression to discuss these relationships. First note the following equivalent definition, which is an immediate consequence of Proposition 4.5, and which gives an alternate proof of Proposition 4.10 via "hypomonotonicity" of the truncated normal cone mapping x → N C (x) ∩ B for prox-regular sets C [31, Thm 1.3].

Corollary 4.11 (approximate monotonicity)
If we replace the normal cone N C in the property described in the result above by its convex hull, the "Clarke normal cone", we obtain a stronger property, called "subsmoothness" in [3]. Similar proofs to those above show that, like super-regularity, subsmoothness is a consequence of either amenability or prox-regularity. However, submoothness is strictly stronger than superregularity. To see this, consider the graph of the function f : R → R defined by the following properties: The graph of f is super-regular at (0, 0), but is not subsmooth there.
In a certain sense, however, the distinction between subsmoothness and super-regularity is slight. Suppose the set F is super-regular at every point in F ∩ U, for some open set U ⊂ R n . Since super-regularity implies Clarke regularity, the normal cone and Clarke normal cone coincide throughout F ∩ U, and hence F is also subsmooth throughout F ∩ U. In other words, "local" super regularity coincides with "local" subsmoothness, which in turn, by [3,Thm 3.16] coincides with the "first order Shapiro property" [36] (also called "near convexity" in [38]) holding locally.

Alternating projections with nonconvexity
Having reviewed or developed over the last few sections the key variationalanalytic properties that we need, we now turn to projection algorithms. In this section we develop our convergence analysis of the method of alternating projections. The following result is our basic tool, guaranteeing conditions under which the method of alternating projections converges linearly. For flexibility, we state it in a rather technical manner. For clarity, we point out afterward that the two main conditions, (5.2) and (5.3), are guaranteed in applications via assumptions of strong regularity and super-regularity (or in particular, amenability or prox-regularity) respectively.
We can now easily check that the sequence (x k ) is Cauchy and therefore converges. To see this, note for any integer n = 0, 1, 2, . . . and any integer k > 2n, we have and a similar argument shows Hence x k converges to some pointx ∈ E, and for all n = 0, 1, 2, . . . we have (5.14) x We deduce that the limitx lies in the intersection F ∩ C and satisfies the inequality x −x 0 ≤ α 1+c 1−c , and furthermore that the convergence is R-linear with rate √ c, which completes the proof. 2 To apply Theorem 5.1 to alternating projections between a closed and a super-regular set, we make use of the key geometric property of super-regular sets (Proposition 4.5): at any point near a point where a set is super-regular the angle between any normal vector and the direction to any nearby point in the set cannot be much less than π 2 . We can now prove our key result.

Theorem 5.15 (alternating projections with a super-regular set)
Consider closed sets F, C ⊂ E and a pointx ∈ F ∩ C. Suppose C is superregular atx (as holds, for example, if it is amenable or prox-regular there). Suppose furthermore that F and C have strongly regular intersection atx: that is, the condition holds, or equivalently, the constant is strictly less than one. Fix any constant c ∈ (c, 1). Then, for any initial point x 0 ∈ C close tox, any sequence of iterated projections x 2n+1 ∈ P F (x 2n ) and x 2n+2 ∈ P C (x 2n+1 ) (n = 0, 1, 2, . . .) must converge to a point in F ∩ C with R-linear rate √ c.
Proof Let us show first the equivalence betweenc < 1 and strong regularity. The compactness of the intersections between normal cones and the unit ball guarantees the existence of u and v achieving the maximum in (5.16).
Observe then that u, v ≤ u v ≤ 1.
The cases of equality in the Cauchy-Schwarz inequality permits to writē which corresponds to the desired equivalence. Fix now any constant c ′ ∈ (c, c) and define δ = c−c ′ 2 . To apply Theorem 5.1, we just need to check the existence of a constant ǫ > 0 such that conditions (5.2) and (5.3) hold. Condition (5.3) holds for all small ǫ > 0, by Proposition 4.5. On the other hand, if condition (5.2) fails for all small ǫ > 0, then there exist sequences of points x r →x in the set F and y r →x in the set C, and sequences of vectors u r ∈ −N F (x r ) ∩ B and v r ∈ N C (y r ) ∩ B, satisfying u r , v r > c ′ . After taking a subsequences, we can suppose u r approaches some vector u ∈ −N F (x) ∩ B and v r approaches some vector v ∈ N C (x) ∩ B, and then u, v ≥ c ′ >c, contradicting the definition of the constantc. Proof Inequality (5.6), and its analog when the roles of F and C are interchanged, together show for all large k, and the result then follows easily, using an argument analogous to that at the end of the proof of Theorem 5.1. 2 In the light of our discussion in the previous section, the strong regularity assumption of Theorem 5.15 is equivalent to the metric regularity atx for 0 of the set-valued mapping Ψ : E → → E 2 defined by Using equation (3.3), the regularity modulus is determined by and a short calculation then shows The closer the constantc is to one, the larger the regularity modulus. We have shown thatc also controls the speed of linear convergence for the method of alternating projections applied to the sets F and C.
Inevitably, Theorem 5.15 concerns local convergence: it relies on finding an initial point x 0 sufficiently close to a point of strongly regular intersection. How might we find such a point?
One natural context in which to pose this question is that of sensitivity analysis. Suppose we already know a point of strongly regular intersection of a closed set and a subspace, but now want to find a point in the intersection of two slight perturbations of these sets. The following result shows that, starting from the original point of intersection, the method of alternating projections will converge linearly to the new intersection.
we deduce from condition (5.2) the implication Furthermore, using condition (5.3) we deduce the implication We can now apply Theorem 5.1 with the set C replaced by C − d and the constant ǫ replaced by ǫ 2 . We deduce that the method of alternating projections on the sets F and C − d, starting at the point The theorem statement then follows by translation. 2 Lack of convexity notwithstanding, more structure sometimes implies that the method of alternating projections converges Q-linearly, rather than just R-linearly, on a neighborhood of point of strongly regular intersection of two closed sets. One example is the case of two manifolds [25].

Inexact alternating projections
Our basic tool, the method of alternating projections for a super-regular set C and an arbitrary closed set F , is a conceptual algorithm that may be challenging to realize in practice. We might reasonably consider the case of exact projections on the super-regular set C: for example, in the next section, for the method of averaged projections, C is a subspace and computing projections is trivial. However, projecting onto the set F may be much harder, so a more realistic analysis allows relaxed projections.
We sketch one approach. Given two iterates x 2n−1 ∈ F and x 2n ∈ C, a necessary condition for the new iterate x 2n+1 to be an exact projection on F , that is x 2n+1 ∈ P F (x 2n ), is In the following result we assume only that we choose the iterate x 2n+1 to satisfy a relaxed version of this condition, where we replace the second part by the assumption that the distance from the normal cone at the iterate to the normalized direction of the last step is small.
Theorem 6.1 (inexact alternating projections) With the assumptions of Theorem 5.15, fix any constant ǫ < √ 1 − c 2 , and consider the following inexact alternating projection iteration. Given any initial points x 0 ∈ C and x 1 ∈ F , for n = 1, 2, 3, . . . suppose Then, providing x 0 and x 1 are close tox, the iterates converge to a point in Sketch proof. Once again as in the proof of Theorem 5.15, we fix any constant c ′ ∈ (c, c) and define δ = c−c ′ 2 , so there exists a constant ǫ > 0 such that conditions (5.2) and (5.3) hold. Define a vector By assumption, there exists a vector w ∈ N F (x 2n+1 ) satisfying w − z ≤ ǫ. Some elementary manipulation then shows that the unit vectorŵ = w −1 w satisfies ŵ, z ≥ √ 1 − ǫ 2 .
As in the proof of Theorem 5.1, assuming inductively that x 2n+1 is close to bothx and x 2n , sinceŵ ∈ N F (x 2n+1 ), and We now see that, on the unit sphere, the arc distance between the unit vectorsŵ and z is no more than arccos( √ 1 − ǫ 2 ), whereas the arc distance betweenŵ and the unit vector u is at least arccos c ′ . Hence by the triangle inequality, the arc distance between z and u is at least Some elementary calculus shows that the quantity on the right-hand side is strictly less than one. Again as in the proof of Theorem 5.1, this inequality shows, providing x 0 is close tox, the inequality and in conjunction with the inequality this suffices to complete the proof by induction. 2

Local convergence for averaged projections
We now return to the problem of finding a point in the intersection of several closed sets using the method of averaged projections. The results of the previous section are applied to the method of averaged projections via the well-known reformulation of the algorithm as alternating projections on a product space. This leads to the main result of this section, Theorem 7.3, which shows linear convergence in a neighborhood of any point of strongly regular intersection, at a rate governed by the associated regularity modulus. We begin with a characterization of strongly regular intersection, relating the condition modulus with a generalized notion of angle for several sets. Such notions, for collections of convex sets, have also been studied recently in the context of projection algorithms in [12,13].
is strictly less than one. Indeed, we have Proof Whenx ∈ ∩ i int F i , the result follows by definition. Henceforth, we therefore rule out that case. For any vectors u i , v i ∈ E (i = 1, 2, . . . , m), by Lagrangian duality and differentiation we obtain Consequently,c 2 is the optimal value of the optimization problem By homogeneity, the optimal solution must occur when the inequality constraint is active, so we obtain an equivalent problem by replacing that constraint by the corresponding equation. By 3.3 an the definition of the condition modulus it follows that the optimal value of this new problem is as required. x ∈ ∩ i F i . Define a constantc ∈ [0, 1) by equation (7.2), and fix any constant c ∈ (c, 1). Then for any initial point x 0 ∈ E close tox, the method of averaged projections converges to a point in the intersection ∩ i F i , with R-linear rate c (and if each set F i is super-regular atx, or in particular, prox-regular or amenable there, then the convergence rate is c 2 ). Furthermore, for any small perturbations d i ∈ E for i = 1, 2, . . . , m, the method of averaged projections applied to the sets d i + F i , with the initial pointx, converges linearly to a nearby point in the intersection, with R-linear rate c.
Proof In the product space E m with the inner product where the linear map A : E → E m is defined by Ax = (x, x, . . . , x). Notice Ax ∈ F ∩ L, and it is easy to check and L ⊥ = (u 1 , u 2 , . . . , u m ) : Hence F 1 , F 2 , . . . , F m have strongly regular intersection atx if and only if F and L have strongly regular intersection at the point Ax. This latter property is equivalent to the constantc defined in Theorem 5.15 (with C = L) being strictly less than one. But that constant agrees exactly with that defined by equation (7.2), so we show next that we can apply Theorem 5.15 and Theorem 5.19. To see this note that, for any point x ∈ E, we have the equivalence 1, 2, . . . , m).
Hence in fact the method of averaged projections for the sets F 1 , F 2 , . . . , F m , starting at an initial point x 0 , is essentially identical with the method of alternating projections for the sets F and L, starting at the initial point Ax 0 . If x 0 , x 1 , x 2 , . . . is a possible sequence of iterates for the former method, then a possible sequence of even iterates for the latter method is Ax 0 , Ax 1 , Ax 2 , . . .. For x 0 close tox, this latter sequence must converge to a point Ax ∈ F ∩ L with R-linear rate c, by Theorem 5.15 and its corollary. Thus the sequence x 0 , x 1 , x 2 , . . . converges tox ∈ ∩ i F i at the same linear rate. When each of the sets F i is super-regular atx, it is easy to check that the Cartesian product F is super-regular at Ax, so the rate is c 2 . The last part of the theorem follows from Theorem 5.19. 2 Applying Theorem 6.1 to the product-space formulation of averaged projections shows in a similar fashion that an inexact variant of the method of averaged projections will also converge linearly.
Remark 7.4 (strong regularity and local extremality) We notice, in the language of [26], that we have proved algorithmically that if closed sets have strongly regular intersection at a point, then that point is not "locally extremal".

Remark 7.5 (alternating versus averaged projections)
Consider a feasibility problem involving two super-regular sets F 1 and F 2 . Assume that strong regularity holds atx ∈ F 1 ∩ F 2 and set κ = cond(F 1 , F 2 |x). Theorem 7.3 gives a bound on the rate of convergence of the method of averaged projections as r av ≤ 1 − 1 2κ 2 . Notice that each iteration involves two projections: one onto each of the sets F 1 and F 2 . On the other hand, Corollary 5.17 and (5.18) give a bound on the rate of convergence of the method of alternating projections as and each iteration involves just one projection. Thus we note that our bound on the rate of alternating projections r alt is always better than the bound on the rate of averaged projection r av . At least from the perspective of this analysis, averaged projections seems to have no advantage over alternating projections, although our proof of linear convergence for alternating projections needs a super-regularity assumption not necessary in the case of averaged projections.

Prox-regularity and averaged projections
If we assume that the sets F 1 , F 2 , . . . , F m are prox-regular, then we can refine our understanding of local convergence for the method of averaged projections using a completely different approach, explored in this section. Proof This result corresponds essentially to [31,Prop 3.1], which yields the smoothness of d 2 F together with the gradient formula. This proof of this proposition also shows that for any small δ > 0, all points x 1 , x 2 ∈ E nearx satisfy the inequality [31, p. 5239]). Consequently we have As before, consider sets F 1 , F 2 , . . . , F m ⊂ E and a pointx ∈ ∩ i F i , but now let us suppose moreover that each set F i is prox-regular atx. Define a function f : E → R by This function is half the mean-squared-distance from the point x to the set system {F i }. According to the preceding result, f is continuously differentiable aroundx, and its gradient is Lipschitz continuous with constant 1 on a neighborhood ofx. The method of averaged projections constructs the new iterate x + ∈ E from the old iterate x ∈ E via the update so we can interpret it as the method of steepest descent with a step size of one when the sets F i are all prox-regular. To understand its convergence, we return to our strong regularity assumption. The condition modulus controls the behavior of normal vectors not just at the pointx but also at nearby points. For each i = 1, 2, . . . , the sequence u 1 i , u 2 i , . . . is bounded, so after taking subsequences we can suppose it converges to some vector u i ∈ E, and since the normal cone N F i is closed as a set-valued mapping from F i to E, we deduce u i ∈ N F i (x). But then we have contradicting the definition of the condition modulus cond(F 1 , F 2 , . . . , F m |x).
The result follows. 2 The size of the gradient of the mean-squared-distance function f , defined by equation (8.2), is closely related to the value of the function near a point of strongly regular intersection. To be precise, we have the following result. Proposition 8.6 (gradient of mean-squared-distance) Consider proxregular sets F 1 , F 2 , . . . , F m ⊂ E having strongly regular intersection at a point x ∈ ∩F i , and any constant k > cond(F 1 , F 2 , . . . , F m |x).
Then on a neighborhood ofx, the mean-squared-distance function Proof Consider any point x ∈ E nearx. By equation (8.3), we know for each i = 1, 2, . . . , m. By definition, we have Using inequality (2.4), we obtain On the other hand, since x is nearx, so are the projections P F i (x), so using Proposition 8.6. 2 A simple induction argument now gives an independent proof in the proxregular case that the method of averaged projections converges linearly to a point in the intersection of the given sets. Specifically, the result above shows that mean-squared-distance f (x k ) decreases by at least a constant factor at each iteration, and Proposition 8.6 shows that the size of the step ∇f (x k ) also decreases by a constant factor. Hence the sequence (x k ) must converge R-linearly to a point in the intersection.
Comparing this result to Theorem 7.3 (linear convergence of averaged projections), we see that the predicted rates of linear convergence are the same. Theorem 7.3 guarantees that the squared distance to the intersection converges to zero with R-linear rate c 2 (for any constant c ∈ (c, 1)). The argument gives no guarantee about improvements in a particular iteration: it only describes the asymptotic behavior of the iterates. By contrast, the argument of Theorem 8.8, with the added assumption of prox-regularity, guarantees the same behavior but with the stronger information that the mean-squared-distance decreases monotonically to zero with Q-linear rate c 2 . In particular, each iteration must decrease the mean-squared-distance.

A Numerical Example
In this final section, we give a numerical illustration showing the linear convergence of alternating and averaged projections algorithms. Some major problems in signal or image processing come down to reconstructing an object from as few linear measurements as possible. Several recovery procedures from randomly sampled signals have been proved to be effective when combined with sparsity constraints (see for instance the recent developments of compressed sensing [16], [14]). These optimization problems can be cast as linear programs. However for extremely large and/or nonlinear problems, projection methods become attractive alternatives. In the spirit of compressive sampling we use projection algorithms to optimize the compression matrix. This speculative example is meant simply to illustrate the theory rather than make any claim on real applications.
We consider the decomposition of images x ∈ R n as x = W z where W ∈ R n×m (n < m) is a "dictionary" (that is, a redundant collection of basis vectors). Compressed sensing consists in linearly reducing x to y = P x = P W z with the help of a compression matrix P ∈ R d×n (with d ≪ n); the inverse operation is to recover x (or z) from y. Compressed sensing theory gives sparsity conditions on z to ensure exact recovery [16], [14]. Reference [16] in fact proposes a recovery algorithm based on alternating projections (on two convex sets). In general, we might want to design a specific sensing matrix P adapted to W , to ease this recovery process. An initial investigation on this question is [17]; we suggest here another direction, inspired by [6] and [18], where averaged projections naturally appear.
Candes and Romberg [6] showed that, under orthogonality conditions, sparse recovery is more efficient when the entries |(P W ) ij | are small. One could thus use the componentwise ℓ ∞ norm of P W as a measure of quality of P . This leads to the following feasibility problem: to find U = P W such that UU ⊤ = I and with the infinity norm constraint U ∞ ≤ α (for a fixed tolerance α). The sets corresponding to these constraints are given by L = {U ∈ R d×m : U = P W }, M = {U ∈ R d×m : UU ⊤ = I}, C = {U ∈ R d×m : U ∞ ≤ α}.
The first set L is a subspace, the second set M is a smooth manifold while the third C is convex; hence the three are prox-regular. Moreover we can easily compute the projections. The projection onto the linear subspace L can be computed with a pseudo-inverse. The manifold M corresponds to the set of matrices U whose singular values are all ones; it turns out that naturally the projection onto M is obtained by computing the singular value decomposition of U, and setting singular values to 1 (apply for example Theorem 27 of [25]). Finally the projection onto C comes by shrinking entries of U (specifically, we operate min{max{u ij , −α}, α} for each entry u ij ). This feasibility problem can thus be treated by projection algorithms, and hopefully a matrix U ∈ L ∩ M ∩ C will correspond to a good compression matrix P .
To illustrate this problem, we generate random entries (normally distributed) of the dictionary W (size 128 × 512, redundancy factor 4) and of an initial iterate U 0 ∈ L. We fix α = 0.1, and we run the averaged projection algorithm which computes a sequence of U k . Figure 9 shows for each iteration k. We also observe that the ratio for all iterations k, showing the expected Q-linear convergence. We note that working on random test cases is of interest for our simple testing of averaged projections: though we cannot guarantee in fact that the intersection of the three sets is strongly regular, randomness seems to prevent irregular solutions, providing α is not too small. So in this situation, it is likely that the algorithm will converge linearly; this is indeed what we observe in Figure 9. We note furthermore that we tested alternating projections on this problem (involving three sets, so not explicitly covered by Theorem 5.15). We observed that the method is still converging linearly in practice, and again, the rate is better than for averaged projections. This example illustrates how the projection algorithm behaves on random feasibility problems of this type. However the potential benefits of using optimized compression matrix versus random compression matrix in practice are still unclear. Further study and more complete testing have to be done for these questions; this is beyond the scope of this paper.