Alternating Projections and Douglas-Rachford for Sparse Affine Feasibility

Introduction

Numerical algorithms for nonconvex optimization models are often eschewed because the usual optimality criteria around which numerical algorithms are designed do not distinguish solutions from critical points. This issue comes into sharp relief with what has become known as the sparsity optimization problem [14, Eq.(1.3)]:

where $m,n\in I\!\!N$, the nonnegative integers, with $m<n$, $M\in{I\!\!R}^{m\times n}$ is a real $m-$by$-n$ matrix of full rank and $\|x\|_{0}:=\sum_{j=1}^{n}|\mbox{sign}(x_{j})|$ with $\mbox{sign}(0)=0$ is the number of nonzero entries of a real vector $x\in{I\!\!R}^{n}$ of dimension $n$. The first-order necessary optimality condition for this problem is (formally)

and $\iota_{B}(x)=0$ if $x\in B$ and $+\infty$ otherwise. The function $\|\cdot\|_{0}$ is subdifferentially regular , so all of the varieties of the subdifferential in (2) are equivalent. It can be shown that every point in $B$ satisfies (2) and so this is uninformative as a basis for numerical algorithms.

In this note we explore the following question: when do elementary numerical algorithms for solving some related nonconvex problem converge locally and/or globally?

The current trend for solving this problem, sparked by the now famous paper of Candès and Tao , is to use convex relaxations. Convex relaxations have the advantage that every point satisfying the necessary optimality criteria is also a solution to the relaxed optimization problem. This certainty comes at the cost of imposing difficult-to-verify restrictions on the affine constraints in order to guarantee the correspondence of solutions to the relaxed problem to solutions to the original problem. Moreover, convex relaxations can lead to a tremendous increase in the dimensionality of the problem (see for example ).

In this work we present a different nonconvex approach; one with the advantage that the available algorithms are simple to apply, (locally) linearly convergent, and the problem formulation stays close in spirit if not in fact to the original problem, thus avoiding the curse of dimensionality. We also provide conditions under which fundamental algorithms applied to the nonconvex model are globally convergent.

the set of $s$-sparse vectors for a fixed $s\leq n$. Notable in this model is that the sparsity “objective” is in the constraint, and one must specify a priori the sparsity of the solution. Also notable is that the problem (4) is still nonconvex, although one can still obtain global convergence results.

Inspired by (4), and the desire to stay as close to (1) as possible, we model the optimization problem as a feasibility problem

where $A_{s}$ and $B$ are given by (5) and (3), respectively. For a well-chosen sparsity parameter $s$, solutions to (6) exactly correspond to solutions to (1). Such an approach was also proposed in where the authors proved local convergence of a simple alternating projections algorithm for feasibility with a sparsity set. Alternating projections is but one of a huge variety of projection algorithms for solving feasibility problems. The goal of this paper is to show when and how fast fundamental projection algorithms applied to this nonconvex problem converge. Much of this depends on the abstract geometric structure of the sets $A_{s}$ and $B$; for affine sparse feasibility this is well-defined and surprisingly simple.

The set $B$ is an affine subspace and $A_{s}$ is a nonconvex set. However, the set $A_{s}$ is the union of finitely many subspaces, each spanned by $s$ vectors from the standard basis for ${I\!\!R}^{n}$ . We show in (20) that one can easily calculate a projection onto $A_{s}$.

For $\Omega\subset{I\!\!R}^{n}$ closed and nonempty, we call the mapping $P_{\Omega}:{I\!\!R}^{n}\rightrightarrows\Omega$ the projector onto $\Omega$ defined by

This is in general a set-valued mapping, indicated by the notation “$\rightrightarrows$” [35, Chapter 5]. We call a point $\bar{x}\in P_{\Omega}(x)$ a projection. It is well known that if the set $\Omega$ is closed, nonempty and convex then the projector is single-valued. In a reasonable abuse of terminology and notation, we will write $P_{\Omega}(x)$ for the (there is only one) projection onto a convex set $\Omega$. An operator closely related to the projector is the reflector. We call the (possibly set-valued) mapping $R_{\Omega}:{I\!\!R}^{n}\rightrightarrows{I\!\!R}^{n}$ the reflector across $\Omega$ defined by $R_{\Omega}(x):=2P_{\Omega}(x)-x$. We call a point in $R_{\Omega}(x)$ a reflection. As with projections, when $\Omega$ is convex, we will write $R_{\Omega}(x)$ for the (there is only one) reflection. The projection/reflection methods discussed in this work are easy to implement, computationally efficient and lie at the foundation of many first-order methods for optimization.

For two closed sets $\Omega_{1},\Omega_{2}\subset{I\!\!R}^{n}$ the mapping

is called the alternating projections operator. The corresponding alternating projections algorithm is given by the iteration $x^{k+1}\in T_{AP}x^{k},$ $k\in I\!\!N$ with $x^{0}$ given.

Other well known algorithms, such as steepest descents for minimizing the average of squared distances between sets, can be formulated as instances of the alternating projections algorithm . We show below (Corollary 3.13) that alternating projections corresponds to projected gradients for problems with special linear structure.

For two closed sets $\Omega_{1},\Omega_{2}\subset{I\!\!R}^{n}$ the mapping

is called the Douglas-Rachford operator. The corresponding Douglas-Rachford algorithm is the fixed point iteration $x^{k+1}\in T_{DR}x^{k},$ $k\in I\!\!N$ with $x^{0}$ given.

The Douglas-Rachford algorithm owes its prominence in large part to its relation via duality to the alternating directions method of multipliers (ADMM) for solving constrained optimization problems .

We present four main results, three of which are new. The first of these results, Theorem 3.8, concerns local linear convergence of alternating projections to a solution of (6). This has been shown, with optimal rates, in . Our proof uses fundamentally different tools developed in . It is exactly these newer tools that enable us to prove the second of our main results, Theorem 4.7, namely local linear convergence of the Douglas-Rachford algorithm. Convergence of Douglas-Rachford, with rates, for sparse affine feasibility is a new result. In the remaining two main new results, Corollary 3.13 and Theorem 3.15, we specify classes of affine subspaces $B$ for which alternating projections is globally linearly convergent. This shows that nonconvex models, in this case, can be a reasonable alternative to convex relaxations.

The outline of this paper is as follows. First we recall some definitions and results from variational analysis regarding alternating projections and Douglas-Rachford in Section 2. We also show in this section local linear convergence of alternating projections. In Section 3 we provide conditions on matrices $M$ that guarantee global linear convergence of alternating projections. In the same section we formulate different conditions on the matrices $M$ that guarantee global linear convergence of the same algorithm. In Section 4 we show that for most problems of interest in sparse optimization there exist fixed points of Douglas-Rachford that are not in the intersection $A_{s}\cap B$. On the other hand, we show that locally the iterates of Douglas-Rachford converge with linear rate to a fixed point whose shadow is a solution to (6). Finally in Section 5 we present numerical and analytical examples to illustrate the theoretical results.

Preliminary Definitions and Results

We use the following notation, most of which is standard. We denote the closed ball of radius $\delta$ centered on $\bar{x}$ by $I\!\!B_{\delta}(\bar{x})$. We assume throughout that the matrix $M$ is full rank in the definition of the affine subspace $B$ (3). The nullspace of $M$ is denoted $\ker M$ and $M^{\dagger}$ indicates the Moore-Penrose inverse, defined by

The inner product of two points $x,y\in{I\!\!R}^{n}$ is denoted $\langle x,~{}y\rangle$. The orthogonal complement to a nonempty affine set $\Omega$ is given by

For two arbitrary sets $\Omega_{1},\Omega_{2}\subset{I\!\!R}^{n}$ we denote the Minkowski sum by $\Omega_{1}+\Omega_{2}:=\{x_{1}+x_{2}~{}|~{}x_{1}\in\Omega_{1}\ \text{and}\ x_{2}\in\Omega_{2}\}$. The set of fixed points of a self-mapping $T$ is given by $\textup{Fix}~{}T$. The identity mapping is denoted by Id. For a set $\Omega\subset{I\!\!R}^{n}$ we define the distance of a point $x\in{I\!\!R}^{n}$ to $\Omega$ by $d_{\Omega}(x):=\inf_{y\in\Omega}\|x-y\|$. When $\Omega$ is closed the distance is attained at a projection onto $\Omega$, that is, $d_{\Omega}\left(x\right)=\|\bar{x}-x\|$ for $\bar{x}\in P_{\Omega}$.

Our proofs make use of some standard tools and notation from variational analysis which we briefly define here. We remind the reader of the definition of the projection onto a closed set (7). The following definition follows [7, Definition 2.1] and is based on [31, Definition 1.1 and Theorem 1.6].

The proximal normal cone $N^{P}_{\Omega}(\bar{x})$ to a closed nonemtpy set $\Omega\subset{I\!\!R}^{n}$ at a point $\bar{x}\in\Omega$ is defined by

The limiting normal cone, or simply the normal cone $N_{\Omega}(\bar{x})$ is defined as the set of all vectors that can be written as the limit of proximal normals; that is, $\overline{v}\in N_{\Omega}(\bar{x})$ if and only if there exist sequences $(x^{k})_{k\in\mathbf{N}}$ in $\Omega$ and $(v^{k})_{k\in\mathbf{N}}$ in $N^{P}_{\Omega}(x^{k})$ such that $x^{k}\to\bar{x}$ and $v^{k}\to\overline{v}$.

The normal cone describes the local geometry of a set. What is meant by regularity of sets is made precise below.

A nonempty set $\Omega\subset{I\!\!R}^{n}$ is ($\varepsilon,\delta$)-subregular at $\bar{x}$ with respect to $U\subset{I\!\!R}^{n}$, if there exist $\varepsilon\geq 0$ and $\delta>0$ such that

holds for all $y\in\Omega\cap I\!\!B_{\delta}(\bar{x}),$ $z\in U\cap I\!\!B_{\delta}(\bar{x}),$ $v\in N_{\Omega}(y)$. We simply say $\Omega$ is ($\varepsilon,\delta$)-subregular at $\bar{x}$ if $U=\{\bar{x}\}$.

The definition of ($\varepsilon,\delta$)-subregularity was introduced in and is a generalization of the notion of ($\varepsilon,\delta$)-regularity introduced in [7, Definition 8.1]. During the preparation of this article it was brought to our attention that a similar condition appears in the context of regularized inverse problems [22, Corollary 3.6].

We define next some notions of regularity of collections of sets that, together with ($\varepsilon,\delta$)-subregularity, provide sufficient conditions for linear convergence of both alternating projections and Douglas-Rachford. In the case of Douglas-Rachford, as we shall see, these conditions are also necessary. Linear regularity, defined next, can be found in [2, Definition 3.13]. Local versions of this have appeared under various names in [21, Proposition 4], [32, Section 3], and [23, Equation (15)].

A collection of closed, nonempty sets $\left(\Omega_{1},\Omega_{2},\dots,\Omega_{m}\right)\subset{I\!\!R}^{n}$ is called locally linearly regular at $\bar{x}\in\cap_{j=1}^{m}\Omega_{j}$ on $I\!\!B_{\delta}(\bar{x})$ if there exists a $\kappa>0$ and a $\delta>0$ such that

If (11) holds at $\bar{x}$ for every $\delta>0$ the collection of sets is said to be linearly regular there. The infimum over all $\kappa$ such that (11) holds is called modulus of regularity on $I\!\!B_{\delta}(\bar{x})$. If the collection is linearly regular one just speaks of the modulus of regularity (without mention of $I\!\!B_{\delta}(\bar{x})$).

There is yet a stronger notion of regularity of collections of sets that we make use of called the basic qualification condition for sets in [31, Definition 3.2]. For the purposes of this paper we refer to this as strong regularity.

The collection $(\Omega_{1},\Omega_{2})$ is strongly regular at $\bar{x}$ if

It can be shown that strong regularity implies local linear regularity (see, for instance ). Any collection of finite dimensional affine subspaces with nonempty intersection is linearly regular (see for instance [3, Proposition 5.9 and Remark 5.10]). Moreover, it is easy to see that, if $\Omega_{1}$ and $\Omega_{2}$ are affine subspaces,

In the case where $\Omega_{1}$ and $\Omega_{2}$ are affine subspaces we say that the collection is strongly regular without mention of any particular point in the intersection - as long as this is nonempty - since the collection is strongly regular at all points in the intersection.

2 General local linear convergence results

The algorithms that we consider here are fixed-point algorithms built upon projections onto sets. Using tools developed in and , alternating projections applied to (6) was shown in to be locally linearly convergent with optimal rates in terms of the Friedrichs angle between ${A_{s}}$ and $B$, and an estimate of the radius of convergence. Our approach, based on , is in line with but does not rely on local firm nonexpansiveness of the fixed point mapping. It has the advantage of being general enough to be applied to any fixed point mapping, but the price one pays for this generality is in the rate estimates, which may not be optimal or easy to compute. We do not present the results of in their full generality, but focus instead on the essential elements for affine feasibility with sparsity constraints.

(See [19, Corollary 3.13].) Let the collection $(\Omega_{1},\Omega_{2})$ be locally linearly regular at $\bar{x}\in\Omega:=\Omega_{1}\cap\Omega_{2}$ with modulus of regularity $\kappa$ on $I\!\!B_{\delta}(\bar{x})$ and let $\Omega_{1}$ and $\Omega_{2}$ be $(\varepsilon,\delta)-$subregular at $\bar{x}$. For any $x^{0}\in I\!\!B_{\delta/2}(\bar{x})$, generate the sequence $\left(x^{k}\right)_{k\in I\!\!N}\subset{I\!\!R}^{n}$ by alternating projections, that is, $x^{k+1}\in T_{AP}x^{k}$. Then

In the analogous statement for the Douglas-Rachford algorithm, we defer, for the sake of simplicity, characterization of the constant in the asserted linear convergence rate. A more refined analysis of such rate constants and their geometric interpretation is the subject of future research.

(See [19, Corollary 3.20].) Let $\Omega_{1},\Omega_{2}$ be two affine subspaces with $\Omega_{1}\cap\Omega_{2}\neq\emptyset$. The Douglas-Rachford algorithm converges to $\Omega_{1}\cap\Omega_{2}$ for all $x^{0}\in{I\!\!R}^{n}$ if and only if the collection $(\Omega_{1},\Omega_{2})$ is strongly regular, in which case, convergence is linear.

Sparse Feasibility with an Affine Constraint: local and global convergence of alternating projections

We are now ready to apply the above general results to affine sparse feasibility. We begin with characterization of the regularity of the sets involved.

We specialize to the case where $B$ is an affine subspace defined by (3) and $A_{s}$ defined by (5) is the set of vectors with at most $s$ nonzero elements. Following we decompose the set $A_{s}$ into a union of subspaces. For $a\in{I\!\!R}^{n}$ define the sparsity subspace associated with $a$ by

Define $\mathcal{J}:=2^{\left\{1,2,\dots,n\right\}}~{}\textup{and }~{}\mathcal{J}_{s}:=\left\{J\in\mathcal{J}\middle|~{}J\mbox{ has }s\mbox{ elements}\right\}$. The set $A_{s}$ can be written as the union of all subspaces indexed by $J\in\mathcal{J}_{s}$ [8, Equation (27d)],

where $A_{J}:=\textup{span}\left\{e_{i}\middle|~{}i\in J\right\}$ and $e_{i}$ is the $i-$th standard unit vector in ${I\!\!R}^{n}$. For $x\in{I\!\!R}^{n}$ we define the set of $s$ largest coordinates in absolute value

The next elementary result will be useful later.

(See [8, Lemma 3.4]) Let $a\in A_{s}$ and assume $s\leq n-1$. Then

Using the above notation, the normal cone to the sparsity set $A_{s}$ at $a\in A_{s}$ has the following closed-form representation (see [8, Theorem 3.9] and [29, Proposition 3.6] for the general matrix representation).

The normal cone to the affine set $B$ also has a simple closed form, namely $N_{B}(x)=B^{\perp}$ (see for example [31, Proposition 1.5]). Let $y\in{I\!\!R}^{n}$ be a point such that $My=p$. Note that $\ker M$ is the subspace parallel to $B$, i.e. $\ker M=B+\{-y\}$.

This notation yields the following explicit representations for the projectors onto ${A_{s}}$ [8, Proposition 3.6] and $B$:

We collect next some facts about the projectors and reflectors of $A_{s}$ and $B$. We remind the reader that, in a slight abuse of notation, since the set $B$ is convex, we make no distinction between the projector $P_{B}(x)$ and the projection $\bar{x}\in P_{B}(x)$.

Let ${A_{s}}$ and $B$ be defined by (5) and (3). Let $a\in A_{s}$ and $b\in B$. For any $\delta_{a}\in(0,\min\left\{|a_{j}|~{}\middle|~{}j\in I(a)\right\})$ and $\delta_{b}\in(0,\infty)$ the following hold:

$P_{B}(x)\in I\!\!B_{\delta_{b}}(b)$ for all $x\in I\!\!B_{\delta_{b}}(b)$;

$P_{A_{s}}(x)\subset I\!\!B_{\delta_{a}/2}(a)$ for all $x\in I\!\!B_{\delta_{a}/2}(a)$;

$R_{B}(x)\in I\!\!B_{\delta_{b}}(b)$ for all $x\in I\!\!B_{\delta_{b}}(b)$;

$R_{A_{s}}(x)\subset I\!\!B_{\delta_{a}/2}(a)$ for all $x\in I\!\!B_{\delta_{a}/2}(a)$.

Proof. (i). This follows from the fact that the projector is nonexpansive, since $B$ is convex and $\|P_{B}x-b\|=\|P_{B}x-P_{B}b\|\leq\|x-b\|$. (In fact, the projector is firmly nonexpansive as shown, for example, in [37, Lemma 1.2].)

(ii). Let $x\in I\!\!B_{\delta_{a}/2}(a)$. For any $i\in I^{\circ}(a):=\{i:a_{i}=0\}$, we have $|x_{i}-a_{i}|=|x_{i}|\leq\delta_{a}/2$. Moreover, for all $j\in I(a):=\{j:a_{j}\neq 0\}$, we have $|x_{j}-a_{j}|\leq\delta_{a}/2$ and so $|x_{j}|>\delta_{a}/2$ for all $j\in I(a)$. Altogether this means that $|x_{j}|>|x_{i}|$ for all $i\in I^{\circ}(a),j\in I(a)$. Therefore the indices of the nonzero elements of $a$ correspond exactly to the indices of the $|I(a)|$-largest elements of $x$, where $|I(a)|$ denotes the cardinality of the set $I(a)$. Since $|I(a)|\leq s$, the projector of $x$ need not be single-valued. (Consider the case $a=(1,0,\dots,0)$ and $x=(1,\delta/4,\delta/4,0,\dots,0)$ and $s=2$.) Nevertheless, for all $x^{+}\in P_{A_{s}}(x)$ we have $a\in\textup{supp}(x^{+})$ where $\textup{supp}(x^{+})$ is defined by (14). Since $\textup{supp}(x^{+})$ is a subspace, $x^{+}$ is the orthogonal projection of $x$ onto a subspace, hence by Pythagoras’ Theorem

Thus $P_{A_{s}}x\subset I\!\!B_{\delta_{a}/2}(a)$.

(iii). Since the reflector $R_{B}$ is with respect to an affine subspace containing $b$ a simple geometric argument shows that for all $x$ we have $\|R_{B}x-b\|=\|x-b\|$. The result follows immediately.

(iv). As in the proof of (ii), for all $x\in I\!\!B_{\delta_{a}/2}$ we have $a\in\textup{supp}(x^{+})$ for each $x^{+}\in P_{A_{s}}(x)$. In other words, the projector, and hence the corresponding reflector, is with respect to a subspace containing $a$. Thus, as in (iii), $\|R_{A_{s}}x-a\|=\|x-a\|$, though in this case only for $x\in I\!\!B_{\delta_{a}/2}$.

The next lemma shows that around any point $\bar{x}\in A_{s}$ the set $A_{s}$ is the union of subspaces in $A_{s}$ containing $\bar{x}$. Hence around any point $\bar{x}\in A_{s}\cap B$ the intersection $A_{s}\cap B$ can be described locally as the intersection of subspaces and the affine set $B$, each containing $\bar{x}$.

Let $\bar{x}\in A_{s}\cap B$ with $0<\|\bar{x}\|_{0}\leq s$. Then for all $\delta<\min\{|\bar{x}_{i}|:\bar{x}_{i}\neq 0\}$ we have

If in fact $\|\bar{x}\|_{0}=s$, then there is a unique $J\in\mathcal{J}_{s}$ such that for all $\delta<\min\{|\bar{x}_{i}|:\bar{x}_{i}\neq 0\}$ we have $A_{s}\cap I\!\!B_{\delta}(\bar{x})=A_{J}\cap I\!\!B_{\delta}(\bar{x})$ and hence $A_{s}\cap B\cap I\!\!B_{\delta}(\bar{x})=A_{J}\cap B\cap I\!\!B_{\delta}(\bar{x})$.

Proof. If $s=n$, then the set $A_{s}$ is all of ${I\!\!R}^{n}$ and both statements are trivial. For the case $s\leq n-1$, choose any $x\in I\!\!B_{\delta}(\bar{x})\cap A_{s}$. From the definition of $\delta$ and Lemma 3.1 we have that, for any $J\in\mathcal{J}_{s}$, if $\bar{x}\notin A_{J}$ then $x\notin A_{J}$. By contraposition, therefore, $x\in A_{J}$ implies that $\bar{x}\in A_{J}$, hence, for each $x\in I\!\!B_{\delta}(\bar{x})\cap A_{s}$, we have $x\in I\!\!B_{\delta}(\bar{x})\cap A_{I(x)}$ where $I(\bar{x})\subseteq I(x)\in\mathcal{J}_{s}$. The intersection $I\!\!B_{\delta}(\bar{x})\cap A_{s}$ is then the union over all such intersections as given by (25). Equation (26) is an immediate consequence of (25).

If, in addition $\|\bar{x}\|_{0}=s$, then the cardinality of $I(\bar{x})$ is $s$ and by [8, Lemma 3.5] $C_{s}(\bar{x})=\{I(\bar{x})\}$, where $C_{s}(\bar{x})$ is given by (17). This means that if $\bar{x}$ has sparsity $s$, then there is exactly one subspace $A_{J}$ with index set $J:=I(\bar{x})$ in $\mathcal{J}_{s}$ containing $\bar{x}$. By Lemma 3.1, $d_{A_{s}\setminus A_{J}}\left(\bar{x}\right)=\min\left\{|\bar{x}_{j}|~{}\middle|~{}j\in J\right\}>\delta$. From this we conclude the equality $A_{s}\cap I\!\!B_{\delta}(\bar{x})=A_{J}\cap I\!\!B_{\delta}(\bar{x})$ and hence $A_{s}\cap B\cap I\!\!B_{\delta}(\bar{x})=A_{J}\cap B\cap I\!\!B_{\delta}(\bar{x})$, as claimed.

We conclude this introductory section with a characterization of the sparsity set $A_{s}$.

At any point $\bar{x}\in A_{s}\backslash\{0\}$ the set $A_{s}$ is $(0,\delta)$-subregular at $\bar{x}$ for $\delta\in(0,\min\left\{|\bar{x}_{j}|~{}\middle|~{}j\in I(\bar{x})\right\}).$ On the other hand, the set $A_{s}$ is not $(0,\delta)$-subregular at $\bar{x}\in A_{s}\backslash\{0\}$ for any $\delta\geq\min\left\{|\bar{x}_{j}|~{}\middle|~{}j\in I(\bar{x})\right\})$. In contrast, at the set $A_{s}$ is $(0,\infty)$-subregular.

Proof. Choose any $x\in I\!\!B_{\delta}(\bar{x})\cap A_{s}$ and any $v\in N_{A_{s}}(x)$. By the characterization of the normal cone in (19) there is some $J\in\mathcal{J}_{s}$ with $I(x)\subseteq J$ and $v\in A^{\perp}_{J}\subset N_{A_{s}}(x)$. As in the proof of Lemma 3.3, for any $\delta\in(0,\min\left\{|\bar{x}_{j}|~{}\middle|~{}j\in I(\bar{x})\right\})$ we have $I(\bar{x})\subseteq I(x)$, hence $\bar{x}-x~{}{\in A_{J}}$ and thus $\langle{v},{\bar{x}-x\rangle}=0$. By the definition of $(\varepsilon,\delta)$-regularity (Definition 2.2) $A_{s}$ is $(0,\delta)$-subregular as claimed.

That $A_{s}$ is not $(0,\delta)$-subregular at $\bar{x}\in A_{s}\setminus\{0\}$ for any $\delta\geq\min\left\{|\bar{x}_{j}|~{}\middle|~{}j\in I(\bar{x})\right\})$ follows from the failure of Lemma 3.3 on balls larger than $\min\left\{|\bar{x}_{j}|~{}\middle|~{}j\in I(\bar{x})\right\}$. Indeed, suppose $\delta$ $\geq$ $\min\left\{|\bar{x}_{j}|~{}\middle|~{}j\in I(\bar{x})\right\}$, then by Lemma 3.1 there is a point $x\in I\!\!B_{\delta}(\bar{x})\cap A_{s}$ with $x\in A_{J}\subset A_{s}$ but $\bar{x}\notin A_{J}$. Now we choose $v\in A^{\perp}_{J}\subset N_{A_{s}}(x)$. Since $\bar{x}\notin A_{J}$, then $\bar{x}-x~{}{\notin A_{J}}$ and thus $|\langle{v},{\bar{x}-x\rangle}|>0$. Since $N_{A_{s}}(x)$ is a union of subspaces, the sign of $v$ can be chosen so that $\langle{v},{\bar{x}-x\rangle}>0$, in violation of $(0,\delta)$-subregularity.

For the case $\bar{x}=0$, by (19) for any $x\in A_{s}$ and $v\in N_{A_{s}}(x)$ we have $\langle{v},{x}\rangle=0$, since $\textup{supp}(x)^{\perp}\perp\textup{supp}(x)$, which completes the proof.

We show in this section that the collection $(A_{s},B)$ is locally linearly regular as long as the intersection is nonempty. We begin with a technical lemma.

Let $\left(\Omega_{1},\Omega_{2},\dots,\Omega_{m},\Omega_{m+1}\right)$ be a collection of nonempty subsets of ${I\!\!R}^{n}$ with nonempty intersection. Let $\bar{x}\in\left(\cap_{j=1}^{m}\Omega_{j}\right)\cap\Omega_{m+1}$. Suppose that, for some $\delta>0$, the pair $\left(\Omega_{j},\Omega_{m+1}\right)$ is locally linearly regular with modulus $\kappa_{j}$ on $I\!\!B_{\delta}(\bar{x})$ for each $j\in\{1,2,\dots,m\}$. Then the collection $\left(\bigcup_{j=1}^{m}\Omega_{j},\Omega_{m+1}\right)$ is locally linearly regular at $\bar{x}$ on $I\!\!B_{\delta}(\bar{x})$ with modulus $\overline{\kappa}=\max_{j}\{\kappa_{j}\}$.

Proof. Denote $\Gamma:=\bigcup_{j=1}^{m}\Omega_{j}$. First note that for all $x\in I\!\!B_{\delta}(\bar{x})$ we have

where the inequality on the right follows from the assumption that $\left(\Omega_{j},\Omega_{m+1}\right)$ is locally linearly regular with modulus $\kappa_{j}$ on $I\!\!B_{\delta}(x)$. Let $\overline{\kappa}\geq\max_{j}\{\kappa_{j}\}$. Then

Let ${A_{s}}$ and $B$ be defined by (5) and (3) with $A_{s}\cap B\neq\emptyset$. At any $\bar{x}\in{A_{s}}\cap B$ and for any $\delta\in(0,\min\left\{|\bar{x}_{j}|~{}\middle|~{}j\in I(\bar{x})\right\})$ the collection $(A_{s},B)$ is locally linearly regular on $I\!\!B_{\delta/2}(\bar{x})$ with modulus of regularity $\overline{\kappa}=\underset{J\in\mathcal{J}_{s},I(\bar{x})\subseteq J}{\max}\{\kappa_{J}\}$ where $\kappa_{J}$ is the modulus of regularity of the collection $(A_{J},B)$.

Proof. For any $\bar{x}\in A_{s}\cap B$ we have $\bar{x}\in A_{J}\cap B$ for all $J\in\mathcal{J}_{s}$ with $I(\bar{x})\subseteq J$ and thus $(A_{J},B)$ is linearly regular with modulus of regularity $\kappa_{J}$ [3, Proposition 5.9 and Remark 5.10]. Define

Then by Lemma 3.5 the collection $\left(\overline{A_{s}},B\right)$ is linearly regular at $\bar{x}$ with modulus of regularity $\overline{\kappa}:=\underset{J\in\mathcal{J}_{s},~{}I(\bar{x})\subseteq J}{\max}\{\kappa_{J}\}$. By Lemma 3.3 $A_{s}\cap I\!\!B_{\delta/2}(\bar{x})=\overline{A_{s}}\cap I\!\!B_{\delta/2}(\bar{x})$ for any $\delta\in(0,\min\left\{|\bar{x}_{j}|~{}\middle|~{}j\in I(\bar{x})\right\})$. Moreover, by Lemma 3.2(ii), for all $x\in I\!\!B_{\delta/2}(\bar{x})$, we have $P_{A_{s}}x\subset I\!\!B_{\delta/2}(\bar{x})$, and thus $P_{A_{s}}x=P_{\overline{A_{s}}}x$. In other words, $d_{A_{s}}\left(x\right)=d_{\overline{A_{s}}}\left(x\right)$ for all $x\in I\!\!B_{\delta/2}(\bar{x})$, hence the collection $(A_{s},B)$ is locally linearly regular on $I\!\!B_{\delta}(\bar{x})$ with modulus $\overline{\kappa}$. This completes the proof.

A simple example shows that the collection $(A_{s},B)$ need not be linearly regular. Consider the sparsity set $A_{1}$, the affine set $B=\{(1,\tau,0)~{}|~{}\tau\in{I\!\!R}\}$ and the sequence of points $(x^{k})_{k\in I\!\!N}$ defined by $x^{k}=(0,k,0)$. Then $A_{1}\cap B=\{(1,0,0)\}$ and $\max\{d_{A_{1}}\left(x^{k}\right),d_{B}\left(x^{k}\right)\}=1$ for all $k$ while $d_{A_{1}\cap B}\left(x^{k}\right)\to\infty$ as $k\to\infty$.

3 Local linear convergence of alternating projections

The next result shows the local linear convergence of alternating projections to a solution of (6). This was also shown in [8, Theorem 3.19] using very different techniques. The approach taken here based on the modulus of regularity $\kappa$ on $I\!\!B_{\delta}(x)$ is more general, that is, it can be applied to other nonconvex problems, but the relationship between the modulus of regularity and the angle of intersection which is used to characterize the optimal rate of convergence [8, Theorem 2.11] is not fully understood.

Let ${A_{s}}$ and $B$ be defined by (5) and (3) with nonempty intersection and let $\bar{x}\in{A_{s}}\cap B$. Choose $0<\delta<\min\left\{|\bar{x}_{j}|~{}\middle|~{}j\in I(\bar{x})\right\}$. For $x^{0}\in I\!\!B_{\delta/2}(\bar{x})$ the alternating projections iterates converge linearly to the intersection ${A_{s}}\cap B$ with rate $\left(1-\frac{1}{\kappa^{2}}\right)$ where $\kappa$ is the modulus of regularity of $(A_{s},B)$ on $I\!\!B_{\delta}(\bar{x})$ (Definition 2.3).

Proof. By Lemma 3.2(i) and (ii) the projections $P_{B}$ and $P_{A_{s}}$ each map $I\!\!B_{\delta/2}(\bar{x})$ to itself, hence their composition maps $I\!\!B_{\delta/2}(\bar{x})$ to itself.

Finally, we show that we may apply Lemma 2.5. The set $B$ is $(0,+\infty)$-subregular at every point in $B$ (i.e., convex) and by Theorem 3.4 the sparsity set ${A_{s}}$ is $(0,\delta)-$ subregular at $\bar{x}$. Lastly, by Theorem 3.6 the pair $(A_{s},B)$ is locally linearly regular at $\bar{x}$ on $I\!\!B_{\delta}(\bar{x})$ for any $\delta\in(0,\min\left\{|\bar{x}_{j}|~{}\middle|~{}j\in I(\bar{x})\right\})$. The assertion then follows from Lemma 2.5 with $\epsilon=0$.

The above result does not need an exact a priori assumption on the sparsity $s$. If there is a solution $\overline{x}\in{A_{s}}\cap B$, then $\|\overline{x}\|_{0}$ can be smaller than $s$ and, geometrically speaking, $\overline{x}$ is on a crossing of linear subspaces contained in ${A_{s}}$. It is also worth noting that the assumptions are also not tantamount to local convexity. In the case that $B$ is a subspace, the point is trivially a solution to (6) (and, for that matter (1)). The set ${A_{s}}$ is not convex on any neighborhood of , however the assumptions of Theorem 3.8 hold, and alternating projections indeed converges locally linearly to , regardless of the size of the parameter $s$.

4 Global convergence of alternating projections

Following where the authors consider problem (4), we present a sufficient condition for global linear convergence of the alternating projections algorithm for affine sparse feasibility. Though our presentation is modeled after this work is predated by the nearly identical approach developed in . We also note that the arguments presented here do not use any structure that is particular to ${I\!\!R}^{n}$, hence the results can be extended, as they were in , to the problem of finding the intersection of the set of matrices with rank at most $s$ and an affine subspace in the Euclidean space of matrices. Since this generalization complicates the local analysis, we have chosen to limit our scope to ${I\!\!R}^{n}$.

Key to the analysis of are the following well-known restrictions on the matrix $M$.

The mapping $M:{I\!\!R}^{n}\to{I\!\!R}^{m}$ satisfies the restricted isometry property of order $s$, if there exists $0\leq\delta\leq 1$ such that

The infimum $\delta_{s}$ of all such $\delta$ is the restricted isometry constant. The mapping $M:{I\!\!R}^{n}\to{I\!\!R}^{m}$ satisfies the scaled/asymmetric restricted isometry property of order $(s,\alpha)$ for $\alpha>1$, if there exist $\nu_{s},\mu_{s}>0$ with $1\leq\frac{\mu_{s}}{\nu_{s}}<\alpha$ such that

The restricted isometry property (29) was introduced in , while the asymmetric version (30) first appeared in [10, Theorem 4]. Clearly (29) implies (30), since if a matrix $M$ satisfies (29) of order $s$ with restricted isometry constant $\delta_{s}$, then it also satisfies (30) of order $\left(s,\beta\right)$ for $\beta>\frac{1+\delta_{s}}{1-\delta_{s}}$.

To motivate the projected gradient algorithm given below, note that any solution to (6) is also a solution to

Conversely, if ${A_{s}}\cap B\neq\emptyset$ and $\bar{x}$ is in $S$, then $\bar{x}$ solves (6).

Given a closed set $A\subset{I\!\!R}^{n}$, a continuously differentiable function $f:{I\!\!R}^{n}\to{I\!\!R}$ and a positive real number $\tau$, the mapping

is called the projected gradient operator. The projected gradients algorithm is the fixed point iteration

for $x^{0}$ given arbitrarily and a sequence of positive real numbers $(\tau_{k})_{k\in I\!\!N}$.

In the context of linear least squares with a sparsity constraint, the projected gradient algorithm is equivalent to what is also known as the iterative hard thresholding algorithm (see for instance ) where the constraint $A=A_{s}$ and the projector given by (20) amounts to a thresholding operation on the largest elements of the iterate.

With these definitions we cite a result on convergence of the projected gradient algorithm applied to (31) (see [11, Theorem 4] and [9, Theorem 3 and Corollary 1]).

Let $M$ satisfy (30) of order $(2s,2)$ and, for any given initial point $x^{0}$, let the sequence $(x^{k})_{k\in I\!\!N}$ be generated by the projected gradient algorithm with $A=A_{s}$, $f(x)=\frac{1}{2}\left\|Mx-p\right\|_{2}^{2}$ and the constant step size $\tau\in[\mu_{2s},2\nu_{2s})$. Then the iterates converge to the unique global solution to (31) and $f(x^{k})\to 0$ linearly as $k\to\infty$ with rate $\rho=\left(\frac{\tau}{\nu_{2s}}-1\right)<1$, that is,

We specialize this theorem to alternating projections next.

Let the matrix $M$ satisfy (30) of order $(2s,2)$ with $\mu_{2s}=1$ and $MM^{\top}=\mbox{Id}$. Then $A_{s}\cap B$ is a singleton and alternating projections applied to (6) converges linearly to $A_{s}\cap B$ with rate $\rho=\left(\frac{1}{\nu_{2s}}-1\right)<1$ for every initial point $x^{0}$.

Proof. For $f(x)=\tfrac{1}{2}\|Mx-p\|_{2}^{2}$ we have $\nabla f(x)=M^{\top}(Mx-p)$. The projected gradients iteration with constant step length $\tau=1$ then takes the form

The projection onto the subspace $B$ is given by (see (20))

Since $MM^{\top}=\mbox{Id}$ this simplifies to $x^{k}-M^{\top}(Mx^{k}-p)=P_{B}x^{k}$, hence

This shows that projected gradients 3.11 with unit step length applied to (31) with $A=A_{s}$ and $f(x)=\frac{1}{2}\left\|Mx-p\right\|_{2}^{2}$ is equivalent to the method of alternating projections 1.1 applied to (6).

To show convergence to a unique solution, we apply Theorem 3.12, for which we must show that the step length $\tau=1$ lies in the nonempty interval $[\mu_{2s},2\nu_{2s})$. By assumption $M$ satisfies (30) of order $(2s,2)$ with $\mu_{2s}=1$. Hence $\frac{1}{2}<\nu_{2s}\leq 1$ and $\tau=1$ lies in the nonempty interval $[1,2\nu_{2s})$. The assumptions of Theorem 3.12 are thus satisfied with $\tau=1$, whence global linear convergence to the unique solution of (31), and hence (6), immediately follows.

The restriction to matrices satisfying $MM^{\top}=\mbox{Id}$ is very strong indeed. We consider next a different condition that, in principle, can be more broadly applied to the alternating projections algorithm. The difference lies in our ansatz: while in the goal is to minimize $f(x):=\frac{1}{2}\left\|Mx-p\right\|_{2}^{2}$ over $x\in A_{s}$, we solve instead

These are different objective functions, yet the idea is similar: Both functions $f$ and $g$ take the value zero on $A_{s}$ if and only if $x\in A_{s}\cap B$. The distance of the point $x$ to $B$, however, is the space of signals, while $f$ measures the distance of the image of $x$ under $M$ to the measurement. The former is more robust to bad conditioning of the matrix $M\in{I\!\!R}^{m\times n}$ with $m<n$, since a poorly-conditioned $M$ could still yield a small residual $\frac{1}{2}\left\|Mx-p\right\|_{2}^{2}$.

Note also that the matrix $M^{\dagger}M$ is the orthogonal projection onto the subspace $\ker(M)^{\perp}$. This means that the operator norm of $M^{\dagger}M$ is $1$ and so we have, for all $x\in{I\!\!R}^{n}$, that $\left\|M^{\dagger}Mx\right\|_{2}\leq\left\|x\right\|_{2}$. Our second global result for alternating projections given below, involves a scaled/asymmetric restricted isometry condition analogous to (30) with $M$ replaced by $M^{\dagger}M$. This only requires a lower bound on the operator norm of $M^{\dagger}M$ with respect to vectors of sparsity $2s$ since the upper bound analogous to (30) is automatic. Specifically, we assume that

The condition (34) can be reformulated in terms of the scaled/asymmetric restricted isometry property (30) and strong regularity of the range of $M^{\top}$ and the complement of each of the subspaces comprising $A_{2s}$. We remind the reader that $A_{J}:=\textup{span}\left\{e_{i}\middle|~{}i\in J\right\}$ for $J\in\mathcal{J}_{2s}:=\left\{J\in 2^{\left\{1,2,\dots,n\right\}}\middle|~{}J\mbox{ has }2s\mbox{ elements}\right\}$.

Let $M\in{I\!\!R}^{m\times n}$ with $m\leq n$ be full rank. Then $M$ satisfies (34) with $\delta_{2s}\in[0,\frac{\alpha-1}{\alpha})$ for some fixed $s>0$ and $\alpha>1$ if and only if $M^{\dagger}M$ satisfies the scaled/asymmetric restricted isometry property (30) of order $(2s,\alpha)$ with $\mu_{2s}=1$ and $\nu_{2s}=(1-\delta_{2s})$. Moreover, for $M$ satisfying (34) with $\delta_{2s}\in[0,\frac{\alpha-1}{\alpha})$ for some fixed $s>0$ and $\alpha>1$, for all $J\in\mathcal{J}_{2s}$ the collection $\left(A_{J}^{\perp},\mbox{range}(M^{\top})\right)$ is strongly regular (Definition 2.4), that is,

Proof. The first statement follows directly from the definition of the scaled/asymmetric restricted isometry property.

For the second statement, note that, if $M$ satisfies inequality (34) with $\delta_{2s}\in[0,\frac{\alpha-1}{\alpha})$ for some fixed $s>0$ and $\alpha>1$, then the only element in $A_{2s}$ satisfying $M^{\dagger}Mx=0$ is $x=0$. Recall that $M^{\dagger}M$ is the projector onto the space orthogonal to the nullspace of $M$, that is, the projector onto the range of $M^{\top}$. Thus

Here we have used the fact that the projection of a point $x$ onto a subspace $\Omega$ is zero if and only if $x\in\Omega^{\perp}$. Now using the representation for $A_{2s}$ given by (16) we have that (36) is equivalent to

But by (13) this is equivalent to the strong regularity of $\left(A_{J}^{\perp},\mbox{range}(M^{\top})\right)$ for all $J\in\mathcal{J}_{2s}.$

We are now ready to prove one of our main new results.

Proof. From the correspondence between (34) and (30) in Proposition 3.14, we can apply Theorem 3.12 to the feasibility problem $\mbox{Find }x\in A_{s}\cap B^{\dagger}$, where $B^{\dagger}:=\{x~{}|~{}M^{\dagger}Mx=p^{\dagger}\}$ for $p^{\dagger}:=M^{\dagger}p$. This establishes that the intersection is a singleton. But from (10) the set $B^{\dagger}$ is none other than $B$, hence (34) for $\alpha=2$ implies existence and uniqueness of the intersection $A_{s}\cap B$.

To establish convergence of alternating projections, for the iterate $x^{k}$ define the mapping

where $g$ is the objective function defined in (33). By definition of the projector, the iterate $x^{k+1}$ is a solution to the problem $\min\left\{q(x,x^{k})\ \middle|\ x\in A_{s}\right\}.$ To see this, recall that, by the definition of the projection, $g(x^{k})=\frac{1}{2}\|x^{k}-P_{B}(x^{k})\|^{2}$. Together with (20) this yields

Now, by definition of the alternating projections sequence,

That is, $x^{k+1}$ is a minimizer of $q(x,x^{k})$ in $A_{s}$. On the other hand,