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) f is element-wisely monotonic iff for any t in mathcal{C}, both |f(t,s)| and arg(f(t,s)) are monotonic in s. (ii) A set T is textbf{converging} to a set T^dagger under a function f 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 f is identity iff for any t in T and t^dagger in T^dagger satisfying the above, t^dagger is the closest element of T^dagger to t, 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 T is a compact set, T^dagger is a finite subset of T with 3 elements. Generally, we need to know both T and T^dagger to propose a suitable identity function f.

alt text 

Fig. 1 An example of a converging set. (a-c) show a (non-constrained) compact set T, the sets T^{(s)}, and entries of a (constrained) finite set T^dagger respectively for 0<s_+<s_{++}<infty.

We present examples of f 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}
  • (c) T=mathcal{C}-{0},~ T^dagger={zeta in mathcal{C}~|~|zeta|=1}:

 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 nu 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 nu 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 (T_1,T_2) 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,c_2) (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 f. 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 (T_1,T_2)) end up at (t_1,t_2) and that lim_{s rightarrow infty} f(t_1,s)=t_1^dagger in  T_1^dagger. The key idea is that t_1^dagger in T_1^dagger is a good solution if it has the properties below:

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

  • b) t_1^dagger is close to t_1.

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 f 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 s 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 T_1^dagger, 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 f as described in Definition 3. The function f, and as a result, the sets { T_1^{(s)} }_{s=0}^{infty} provide information about the goodness (or closeness) of elements of T_1^dagger 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.