You Need to Calm Down: Calmness Regularity for a Class of Seminorm Optimization Problems^††thanks: This work was supported by NSF award DMS-18-30418.

We consider the following solution map

$$S(\boldsymbol{A})=\operatorname*{arg\,min}_{\boldsymbol{A}\boldsymbol{x}={\boldsymbol{b}}}\Omega(\boldsymbol{x})=\operatorname*{arg\,min}_{\boldsymbol{x}\in M(\boldsymbol{A})}\Omega(\boldsymbol{x}),$$

(3)

where $M(\boldsymbol{A})$ denotes the constraint set

$$M(\boldsymbol{A})=\{\boldsymbol{z}\in\mathbb{R}^{n}\mid\boldsymbol{A}\boldsymbol{z}={\boldsymbol{b}}\}.$$

We note that generally $S(\boldsymbol{A})$ is a set-valued function. We arbitrarily fix $\boldsymbol{A}_{0}\in\mathbb{R}^{m\times n}$ with full rank and quantitatively study the effect of perturbing $\boldsymbol{A}_{0}$ on the set-valued solution map $S(\boldsymbol{A})$.

In order to quantify the effect of perturbing $\boldsymbol{A}_{0}$ on the set-valued solution map $S(\boldsymbol{A})$, we use some well-known notions of regularity of set-valued functions. We first motivate them for our setting by considering the special case where $\Omega(\boldsymbol{x})=\left\lVert\boldsymbol{x}\right\rVert_{1}$ and $S(\boldsymbol{A}_{0})$ is an entire face of the $\ell^{1}$ ball. Then a small perturbation in $\boldsymbol{A}_{0}$ results in a jump from that face to a single vertex as we demonstrate in Figure 1. A model set-valued function with such a jump, which needs to be handled by the developed theory, is

$$G(t)=\begin{cases}[0,1]&\textrm{ if }t\in(1/2,1]\cr 0&\textrm{ if }t\in[0,1/2).\end{cases}$$

This function has several properties, which we will formulate below.

We will state their definitions in terms of Banach spaces $X$ and $Y$, where we denote by $2^{X}$ all subsets of $X$, $\|\cdot\|$ the norm of $Y$ and $d(\cdot,\cdot)$, the induced distance by $\|\cdot\|$ between points or sets in $X$. Throughout the paper we go back and forth between the general setting and our special setting of $X=\mathbb{R}^{n}$ with the Euclidean norm, $\|\cdot\|$, and $Y=\mathbb{R}^{m\times n}$ with the distance induced by the spectral norm. We also denote the spectral norm by $\|\cdot\|$. The induced distance by either norm is denoted by either $\|\cdot-\cdot\|$, when involving only matrices, or $d(\cdot,\cdot)$, when involving sets of matrices. Even though we use the same notation, e.g., $\|\cdot\|$ and $d(\cdot,\cdot)$ for different setting, they are easily distinguishable. When assuming norms and distances in the Euclidean case, we use vectors, which we denote by boldfaced small letters; when assuming matrices, we denote them by boldfaced capital letters; and when assuming abstract Banach spaces, we denote their elements by regular small letters.

It is somewhat intuitive that the above function $G(t)$ is “upper semicontinuous”. We clarify this notion as follows.

It has been known since the 1970s that if $\Omega$ is convex, then the solution map $S(\boldsymbol{A})$ is upper semicontinuous [17, Theorem 1.15]. Our result upgrades the upper semicontinuity of $S(\boldsymbol{A})$ to a kind of set-valued Lipschitz regularity, which we define next.

We note that if $S(\boldsymbol{A})$ is calm at $(\boldsymbol{A}_{0},\boldsymbol{x}_{0})$ then for all $\boldsymbol{A}_{1}$ sufficiently close, there exists $\boldsymbol{x}_{1}\in S(\boldsymbol{A}_{1})$ such that

$$\left\lVert\boldsymbol{x}_{0}-\boldsymbol{x}_{1}\right\rVert\leq C(\boldsymbol{A}_{0})\left\lVert\boldsymbol{A}_{0}-\boldsymbol{A}_{1}\right\rVert.$$

This means that small perturbations to the measurement matrix $\boldsymbol{A}$ leave at least two solutions $\boldsymbol{x}_{0}\in S(\boldsymbol{A}_{0})$ and $\boldsymbol{x}_{1}\in S(\boldsymbol{A}_{1})$ close.

We demonstrate that calmness is stronger than upper semicontinuity with the following example

$$H(t)=[-\sqrt{t},\sqrt{t}]\ \text{ for }t\in[0,1].$$

The upper semicontinuity of $H$ is obvious. It is not calm since for $t_{0}$ and $t_{1}$ with sufficiently small absolute values the distance between $H(t_{0})$ and $H(t_{1})$ grows as $|\sqrt{t_{0}}-\sqrt{t_{1}}|$ and in general cannot be controlled by $|t_{0}-t_{1}|$. Indeed, if, for example, $t_{0}=0$ and $t>0$ is arbitrary small, then $H(0)=\{0\}$ (or one may write $H(0)=0$ to emphasize the single value) and $d(H(0),H(t))=\sqrt{t}\gg t$.

At last, we define a stronger notion of regularity, which will be useful later. Unlike lower Lipschitz semicontinuity, both $y$ and $y^{\prime}$ are allowed to vary. Here and throughout the paper, $B_{\delta}(y)$ denotes an open ball in $Y$ with center $y$ and radius $\delta$, and similarly $B_{\epsilon}(x)$ denotes a corresponding open ball in $X$.

Note that we will use the Aubin property on the “inverse” of $F$ defined as

$$F^{-1}(y)=\{x\mid x\in F(y)\}$$

Note that the Aubin property of $F^{-1}$ implies a local bi-Lipschitz property of $F$.

In the general setting of Banach spaces $X$, $Y$ (with the above notation) and $Z$, and functions $M:Y\to 2^{X}$ and $f:Z\times Y\to\mathbb{R}$, Klatte and Kummer [16] provide sufficient conditions for calmness at $(y_{0},x_{0})\in Y\times 2^{X}$ of

$$S(y)=\operatorname*{arg\,min}_{z\in M(y)}f(z,y).$$

(4)

These sufficient conditions are requirements on the regularity of the constraint set $M(y)$ and the regularity of the mapping

$$L(y,\mu)=\{x\in M(y)\mid f(x,y_{0})\leq\mu\}$$

(5)

for a certain choice of $\mu$. The regularity of these quantities is quantified by calmness and the following notion of lower Lipschitz semicontinuity. It is almost identical to calmness except that $y$ varies instead of $x$.

We formulate Theorem 3.1 of Klatte and Kummer [16] on sufficient conditions for calmness of $S(y)$. We use the quantity $\mu_{0}=f(S(y_{0}),y_{0})$ for $y_{0}\in Y$ and $x_{0}\in X$. It follows from the definition of $f$ that this quantity is well-defined as $f$ is constant on all values of $S(y_{0})$.

We assume that the unit ball of $\Omega$, $\{\boldsymbol{x}\mid\Omega(\boldsymbol{x})\leq 1\}$, is a polyhedron. For brevity, we refer by polyhedron to a convex polyhedron, which is the intersection of finitely many half spaces.

We relate the above property to the following well-known general notions of a polyhedral map and polyhedral level sets, which we use in this work. We define the former notion for a general function and the latter one only for $\Omega$. For Banach spaces $X$ and $Y$, a map $F:X\to Y$ is a polyhedral map if there exists polyhedra $P_{i},i=1,\ldots,N$, such that

$$\textrm{Graph}F=\{(x,F(x))\mid x\in X\}=\bigcup_{i=1}^{N}P_{i}.$$

We say that $\Omega$ has polyhedral level sets if the level-set map

$$F(\mu)=\{\boldsymbol{x}\in\mathbb{R}^{n}\mid\Omega(\boldsymbol{x})\leq\mu\}$$

(6)

is polyhedral. Since $\Omega$ is a seminorm, it is equivalent to the assumed property that $F(1)$ consists of a single polyhedron $P_{1}$ (this claim will be clearer from the geometric argument presented later in Section 3.2.2).

We use a classic result from the theory of polyhedral mappings [18]:

We exploit the geometric interplay between the affine subspace solution of $\boldsymbol{A}\boldsymbol{x}={\boldsymbol{b}}$ and the affine subspaces of the polyhedral level sets using principal angles between shifted linear subspaces [19]. The principal angles $0\leq\theta_{1}\leq\cdots\leq\theta_{r}\leq\pi/2$ between two linear subspaces $\mathcal{U}$ and $\mathcal{V}$ of $\mathbb{R}^{n}$ with dimensions $r$ and $k$, respectively, where $r<k$, are defined recursively along with principal vectors $\boldsymbol{u}_{1}$, $\ldots$, $\boldsymbol{u}_{r}$ and $\boldsymbol{v}_{1}$, $\ldots$, $\boldsymbol{v}_{r}$. The smallest principal angle $\theta_{1}$ is given by

$$\theta_{1}=\min_{\begin{subarray}{c}\boldsymbol{u}\in\mathcal{U},\boldsymbol{v}\in\mathcal{U}\\ \|\boldsymbol{u}\|=\|\boldsymbol{v}\|=1\end{subarray}}\arccos(|\boldsymbol{u}^{T}\boldsymbol{v}|).$$

(7)

The principal vectors $\boldsymbol{u}_{1}$ and $\boldsymbol{v}_{1}$ achieve the minimum in (7). For $2\leq k\leq r$, the $k$th principal angle, $\theta_{k}$, and principal vectors, $\boldsymbol{u}_{k}$ and $\boldsymbol{v}_{k}$, are defined by

$$\theta_{k}=\min_{\begin{subarray}{c}\boldsymbol{u}\in\mathcal{U},\|\boldsymbol{u}\|=1,\boldsymbol{v}\perp\boldsymbol{u}_{1},\dots,\boldsymbol{u}_{k-1}\\ \boldsymbol{v}\in\mathcal{V},\|\boldsymbol{v}\|=1,\boldsymbol{v}\perp\boldsymbol{v}_{1},\dots,\boldsymbol{v}{k-1}\end{subarray}}\arccos(|\boldsymbol{u}^{T}\boldsymbol{v}|),$$

(8)

where $\boldsymbol{u}_{k}$ and $\boldsymbol{v}_{k}$ achieve the minimum in (8)

Our proof gives rise to a system of inequalities $f(\boldsymbol{x})\leq 0$, where $f$ is a convex function, and requires bounding the distance between the solution set of this system and a point that lies near the boundary of this set. The sharp constant of the required bound uses the subdifferential of $f$.

We first recall that the subdifferential of a convex function $f:\mathbb{R}^{n}\to\mathbb{R}$ is defined as the following set of subgradients of $f$:

$$\partial f(\boldsymbol{x}):=\{\boldsymbol{v}\in\mathbb{R}^{n}\mid f(\boldsymbol{z})-f(\boldsymbol{x})\geq\langle\boldsymbol{v},\,\boldsymbol{z}-\boldsymbol{x}\rangle\textrm{ for all }\boldsymbol{z}\in\mathbb{R}^{n}\}.$$

The use of the subdifferential to bound distances to constraint sets began with Hoffman’s original work [20] on error bounds for systems of inequalities $\boldsymbol{A}\boldsymbol{x}\leq b$. Define $\mathcal{S}_{\boldsymbol{A},{\boldsymbol{b}}}$ to be the solution set of all $\boldsymbol{x}\in\mathbb{R}^{n}$ that satisfy $\boldsymbol{A}\boldsymbol{x}\leq{\boldsymbol{b}}$. Assuming this set is nonempty, Hoffman shows that there exists a constant $C$ so that for all $\boldsymbol{x}\in\mathbb{R}^{n}$

$$d(\boldsymbol{x},\mathcal{S}_{\boldsymbol{A},{\boldsymbol{b}}})\leq C\|[\boldsymbol{A}\boldsymbol{x}-{\boldsymbol{b}}]_{+}\|,$$

(9)

where $([\boldsymbol{x}]_{+})_{i}=\max(x_{i},0)$ for $i=1$, $\ldots$, $n$. In his original paper, he proved the bound using results from conic geometry and then computed the constants ad hoc for a few different norms. Later results, see e.g., [21], generalize this to convex inequalities $f(\boldsymbol{x})\leq 0$ and compute sharp constants using the subdifferential $\partial f(\boldsymbol{x})$ . We will use the following theorem of [21], where (10) below is analogous to (9).

The following classical property of the Moore-Penrose inverse will be useful. We offer a short proof here.

We derive the calmness of $M(\boldsymbol{A})$ at $(\boldsymbol{A}_{0},\boldsymbol{x}_{0})\in\mathbb{R}^{m\times n}\times\mathbb{R}^{n}$ from the above lemma. We set the neighborhoods of Definition 2.2 as $U=\mathbb{R}^{m\times n}$ and $V$ any bounded neighborhood of $\boldsymbol{x}_{0}$ in $\mathbb{R}^{n}$ of diameter $D>0$, where any choice of $D>0$ is fine, but it impacts the calmness constant (see below). We arbitrarily fix $\boldsymbol{A}_{1}\in U$ and $\boldsymbol{x}_{1}\in M(\boldsymbol{A}_{1})\cap V$. To verify calmness, we directly apply Lemma 3.2

$$d(\boldsymbol{x}_{1},M(\boldsymbol{A}_{0}))\leq\left\lVert\boldsymbol{A}_{0}^{\dagger}\right\rVert\left\lVert\boldsymbol{A}_{0}\boldsymbol{x}_{1}-{\boldsymbol{b}}\right\rVert$$

and further note that

$$\boldsymbol{A}_{0}\boldsymbol{x}_{1}-{\boldsymbol{b}}=\boldsymbol{A}_{0}\boldsymbol{x}_{1}-{\boldsymbol{b}}-\boldsymbol{A}_{1}\boldsymbol{x}_{1}+{\boldsymbol{b}}=(\boldsymbol{A}_{0}-\boldsymbol{A}_{1})\boldsymbol{x}_{1}.$$

Combining the above two equations and using the triangle inequality yields the desired calmness of $M(\boldsymbol{A})$:

$$d(\boldsymbol{x}_{1},M(\boldsymbol{A}_{0}))\leq\left\lVert\boldsymbol{A}_{0}^{\dagger}\right\rVert\left\lVert\boldsymbol{x}_{1}\right\rVert\left\lVert\boldsymbol{A}_{0}-\boldsymbol{A}_{1}\right\rVert\leq\left\lVert\boldsymbol{A}_{0}^{\dagger}\right\rVert(\left\lVert\boldsymbol{x}_{0}\right\rVert+D)\left\lVert\boldsymbol{A}_{0}-\boldsymbol{A}_{1}\right\rVert.$$

(13)

The calmness constant $\left\lVert\boldsymbol{A}_{0}^{\dagger}\right\rVert(\left\lVert\boldsymbol{x}_{0}\right\rVert+D)$ is bounded since the diameter $D$ is bounded and $\boldsymbol{A}_{0}$ is full-rank, so its lowest singular value, $\sigma_{\textrm{min}}(\boldsymbol{A}_{0})$ is positive and thus $\left\lVert\boldsymbol{A}^{\dagger}_{0}\right\rVert=1/{\sigma_{\textrm{min}}(\boldsymbol{A}_{0})}$ is bounded. We remark that the bound in the first inequality of (13) is analogous to that in (9), though the latter one applies to a system of inequalities and not just equalities.

To see that $M(\boldsymbol{A})$ is lower Lipschitz semicontinuous, we use again the formula $\left\lVert\boldsymbol{A}^{\dagger}\right\rVert=1/{\sigma_{\textrm{min}}(\boldsymbol{A})}$. Since the complex roots of a polynomial vary continuously with respect to the coefficients, the eigenvalues of a real symmetric matrix vary continuously with respect to that matrix. Thus $\sigma_{\textrm{min}}(\boldsymbol{A})$, which is the minimal eigenvalue of $\boldsymbol{A}\boldsymbol{A}^{T}$, depends continuously on $\boldsymbol{A}$. Therefore, for every $\epsilon>0$ there exists a $\delta>0$ such that for $\boldsymbol{A}_{1}\in B_{\delta}(\boldsymbol{A}_{0})$, $\sigma_{\textrm{min}}(\boldsymbol{A}_{1})>0$, so that $\boldsymbol{A}_{1}$ is also full-rank, and

$$\left\lVert\boldsymbol{A}_{1}^{\dagger}\right\rVert\leq(1+\epsilon)\left\lVert\boldsymbol{A}_{0}^{\dagger}\right\rVert.$$

(14)

Swapping $\boldsymbol{A}_{1}$ and $\boldsymbol{A}_{0}$ in the first inequality of (13) and combining it with (14) gives

$$d(\boldsymbol{x}_{0},M(\boldsymbol{A}_{1}))\leq(1+\epsilon)\left\lVert\boldsymbol{A}_{0}^{\dagger}\right\rVert\left\lVert\boldsymbol{x}_{0}\right\rVert\left\lVert\boldsymbol{A}_{0}-\boldsymbol{A}_{1}\right\rVert.$$

This bound shows that $M(\boldsymbol{A})$ is lower Lipschitz semicontinuous at $(\boldsymbol{A}_{0},\boldsymbol{x}_{0})$.

Recall the map $F(\mu)$ defined in (6) and note that we can write

$$L(\boldsymbol{A},\mu)=M(\boldsymbol{A})\cap F(\mu).$$

(15)

Define also the system of inequalities

$$W(\mu)=M(\boldsymbol{A}_{0})\cap F(\mu).$$

The following theorem from [16] gives conditions on $M$ and $F$ that ensure $L$ is calm.

We will apply the theorem with $X=\mathbb{R}^{n}$, $Y=\mathbb{R}^{m\times n}$, and $Z=\mathbb{R}$. We set $F_{1}=M$, $F_{2}=F$, $F_{3}=W$, and $F_{4}=L$. Let $((\boldsymbol{A}_{0},\mu_{0}),\boldsymbol{x}_{0})\in\textrm{Graph }L$. To see that $L$ is calm at this point, we thus verify that

1. 1.

   $F^{-1}(\boldsymbol{x})$ has the Aubin property at $(\boldsymbol{x}_{0},\mu_{0})$.

2. 2.

   $F(\mu)$ is calm at $(\mu_{0},\boldsymbol{x}_{0})$.

3. 3.

   $W(\mu)$ is calm at $(\mu_{0},\boldsymbol{x}_{0})$.

We verify property 1 in Section 3.2.1, property 2 in Section 3.2.3, and property 3 in Section 3.2.3.

The main trick is that we have reduced the problem from perturbations in $\boldsymbol{A}$ to better understood cases of perturbations. For example, in verifying properties 2 and 3 we need to study tolerance to perturbations in the right hand side of an inequality system, represented by either $F(\mu)$ or $W(\mu)$. We prove the calmness of $W(\mu)$ and $F(\mu)$ by both geometric or algebraic approaches. The geometric ones are quite simple, while the algebraic ones enable us to compute explicit constants.