# Alternating Projections on Converging Sets

• The aim of alternating projections is to find elements in the intersection of the two sets, or if not possible, pairs of elements in the two sets that are as close as possible.

• The idea of Alternating Projections on Converging Sets leads to a modified version of alternating projections that can be particularly useful when at least one of the sets is not “well-behaved”.

# Motivation, and the Central Idea

Let denote a set pair. Starting from an element in , we find the closest element to (e.g. using the norm) in denoted by which we call the optimal projection of on . Next, we find the optimal projection of on denoted by . Repeating these projections leads to a method known as alternating projections. Note that the distance between the obtained elements from the two sets is decreasing. The aim of alternating projections is to find elements in the intersection of the two sets, or if not possible, pairs of elements in the two sets that are as close as possible.

In signal processing, the two sets and usually represent a partitioning of the desirable properties of the signal. Therefore, a signal design via alternating projections onto and seeks to find signals that (at least nearly) possess both type of properties.

Alternating projections exhibit a good performance when the two sets are “well-behaved”. For example, if the two sets are convex, alternating projections are guaranteed to converge to the closest points (or a point in the intersection) of the two sets. However, when the sets are less well-behaved, e.g. finite, or non-convex in general, alternating projections suffer from the possibility of getting stuck in a local “solution”.

Green circles: elements of . Red circle: the initial point on .

Alternating Projections on Converging Sets is a modified type of alternating projections that can be particularly useful when at least one of the sets is not well-behaved, i.e. tricky. The key idea is to replace the tricky set with a well-behaved (perhaps compact/convex) set that in limit converges to the tricky set of interest. Then we employ the typical alternating projections, while the replaced set, at each iteration, gets closer to the tricky set. See an illustrative example below!

## Mathematical Formalism

Definition 1. Consider a function ; as an extension, for every matrix let be a matrix such that . We say that: (i) is element-wisely monotonic iff for any , both and are monotonic in . (ii) A set is textbf{converging} to a set under a function iff for every ,

and for every , there exists an element such that

(iii) The function is identity iff for any and satisfying the above, is the closest element of to , and (iv) the sequence of sets where is a sequence of converging sets.

An example of a converging set is depicted in Fig. 1. Note that in this example, while is a compact set, is a finite subset of with elements. Generally, we need to know both and to propose a suitable identity function .

 Fig. 1 An example of a converging set. (a-c) show a (non-constrained) compact set , the sets , and entries of a (constrained) finite set respectively for .

We present examples of for some constrained alphabets commonly used in sequence design:

• (a)

• (b)

• (c)

• (d)

where is a positive real number. In all cases, the monotonic function is used to construct the desirable functions which are both element-wisely monotonic and identity. Note that tunes the speed of convergence (as well as the accuracy of the method described in the following).

Definition 2. Consider a pair of sets . A pair of sets where and is called an attraction landscape of iff starting from any point in or , the alternating projections on and end up in the same element pair (, ). Furthermore, for a pair of sets , an attraction landscape is said to be complete iff for any attraction landscape such that and , we have and .

Now consider the alternating projections on two compact sets and . Suppose is converging to a constrained set under some element-wisely monotonic identity function . As discussed before, the aim of the alternating projections on and is to find the closest two points in an attraction landscape of ; the closer the obtained points, the better the solution. We assume that the alternating projections (in an attraction landscape of ) end up at and that . The key idea is that is a good solution if it has the properties below:

• a) Its corresponding projection is a good solution in .

• b) is close to .

Typical alternating projections can provide good solutions and thus a) is satisfied. To satisfy b) as well, we consider the following modification: at the step of the alternating projections, let be the orthogonal projection of on and let . Now, instead of projecting on , we project on to obtain .

The above video has illustrated the alternating projections with the proposed modification. Supposing that , we comment on two cases for the goodness of solutions in the constrained set in connection with the modified projections:

• is close to : As is element-wisely monotonic, is element-wisely closer to than to which implies that . Therefore, if is close to we can assume that is also close to . In this case, the modified projections approximate well the typical alternating projections which tend to improve the goodness of .

• is far from : One could then expect that is also far from ; particularly so as increases. Note that considering instead of can change the complete attraction landscape. More important, when the algorithm is converging to a poor solution in , where is far from , it tries to replace complete attraction landscapes more often than in the case of good solutions (when is close to ).

In sum, knowing the sets and we design a convenient function as described in Definition 3. The function , and as a result, the sets provide information about the goodness (or closeness) of elements of at the boundary of the compact set . This information can be used to keep the good solutions and continue looking for other solutions when the obtained solution is not desirable. In Applications, we show the benefits of the proposed modification for alternating projections on some particular sets.