## Alternating Projections on Converging SetsThe 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 IdeaLet 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 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 .
## Mathematical Formalism
and for every , there exists an element such that ( 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 .
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).
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. |