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 (Gamma,Lambda) denote a set pair. Starting from an element X_1 in Gamma , we find the closest element to X_1 (e.g. using the |.|_F norm) in Lambda denoted by Y_1 which we call the optimal projection of X_1 on Lambda . Next, we find the optimal projection of Y_1 on Gamma denoted by X_2 . 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 Gamma and Lambda usually represent a partitioning of the desirable properties of the signal. Therefore, a signal design via alternating projections onto Gamma and Lambda 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 T_1 . Red circle: the initial point on T_2 .

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 f(t,s): mathcal{C} times (mathcal{N} cup {0}) rightarrow mathcal{C} ; as an extension, for every matrix mathbf{X} let f(mathbf{X},s) be a matrix such that $[f(mathbf{X},s)]_{k,l}=f(mathbf{X}(k,l),s)$ . We say that: (i) is element-wisely monotonic iff for any t in mathcal{C} , both |f(t,s)| and arg(f(t,s)) are monotonic in . (ii) A set is textbf{converging} to a set T^dagger under a function iff for every t in T ,

$left{ begin{array}{l} f(t,0)=t~, lim_{s rightarrow infty} f(t,s) in T^dagger end{array} right.$

and for every t^dagger in T^dagger , there exists an element t in T such that

$lim_{s rightarrow infty} f(t,s) = t^dagger.$

(iii) The function is identity iff for any t in T and t^dagger in T^dagger satisfying the above, is the closest element of to , and (iv) the sequence of sets ${ T^{(s)} }_{s=0}^{infty}$ where $T^{(s)}={ f(t,s)~|~t in T }$ 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, T^dagger 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 $T^{(s)}$ , and entries of a (constrained) finite set T^dagger respectively for $0<s_+<s_{++}<infty$ .

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

(a) $T=mathcal{R}-{0},~ T^dagger={-1,1}:$

$f(t,s)=mbox{sgn}(t)cdot |t|^{e^{-nu s}}$

(b) $T=mathcal{R}, ~T^dagger=mathcal{Z}:$

$f(t,s)=[ t ] + { t} cdot e^{-nu s}$

$f(t,s)=|t|^{e^{-nu s}} cdot e^{j arg (t)}$

(d) $T=mathcal{C}-{0}, ~ T^dagger={zeta in mathcal{C} ~ | ~ zeta^m=1}:$

$f(t,s)=|t|^{e^{-nu s}} cdot e^{j frac{2 pi}{m} left( left[ frac{m arg(t)}{2 pi} right] + left{ frac{m arg(t)}{2 pi} right} cdot e^{-nu s} right)}$

where is a positive real number. In all cases, the monotonic function $e^{-nu s}$ 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 (T_1,T_2) . A pair of sets (C_1,C_2) where C_1 subseteq T_1 and C_2 subseteq T_2 is called an attraction landscape of iff starting from any point in C_1 or C_2 , the alternating projections on T_1 and T_2 end up in the same element pair ( c_1 in C_1 , c_2 in C_2 ). Furthermore, for a pair of sets (T_1,T_2) , an attraction landscape (C_1,C_2) is said to be complete iff for any attraction landscape (C'_1,C'_2) such that C_1 subseteq C'_1 and C_2 subseteq C'_2 , we have C_1= C'_1 and C_2 = C'_2 .

Now consider the alternating projections on two compact sets T_1 and T_2 . Suppose T_1 is converging to a constrained set T_1^dagger subseteq T_1 under some element-wisely monotonic identity function . As discussed before, the aim of the alternating projections on T_1 and T_2 is to find the closest two points in an attraction landscape of (T_1,T_2) ; 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 $lim_{s rightarrow infty} f(t_1,s)=t_1^dagger in T_1^dagger$ . 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 t_1 in T_1 and thus a) is satisfied. To satisfy b) as well, we consider the following modification: at the $s^{th}$ step of the alternating projections, let $t_1^{(s)} in T_1$ be the orthogonal projection of $t_2^{(s)} in T_2$ on T_1 and let ${t'}_1^{(s)} = f(t_1^{(s)},s) in T_1^{(s)}$ . Now, instead of projecting $t_1^{(s)}$ on T_2 , we project ${t'}_1^{(s)}$ on T_2 to obtain $t_2^{(s+1)}$ .

The above video has illustrated the alternating projections with the proposed modification. Supposing that $lim_{s' rightarrow infty} f(t_1^{(s)},s') ={t^dagger}_1^{(s)}$ , we comment on two cases for the goodness of solutions in the constrained set T_1^dagger in connection with the modified projections:

${t^dagger}_1^{(s)}$ is close to $t_1^{(s)}$ : As is element-wisely monotonic, $t_1^{(s)}$ is element-wisely closer to ${t'}_1^{(s)}$ than to ${t^dagger}_1^{(s)}$ which implies that $| t_1^{(s)} - {t'}_1^{(s)} | < | t_1^{(s)} -{t^dagger}_1^{(s)} |$ . Therefore, if ${t^dagger}_1^{(s)}$ is close to $t_1^{(s)}$ we can assume that ${t'}_1^{(s)}$ is also close to $t_1^{(s)}$ . In this case, the modified projections approximate well the typical alternating projections which tend to improve the goodness of $t_1^{(s)} in T_1$ .

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

In sum, knowing the sets T_1 and T_1^dagger we design a convenient function as described in Definition 3. The function , and as a result, the sets ${ T_1^{(s)} }_{s=0}^{infty}$ provide information about the goodness (or closeness) of elements of at the boundary of the compact set T_1 . 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.