# Sharp, strong and unique minimizers for low complexity robust recovery

Jalal Fadili111Normandie Université, ENSICAEN, UNICAEN, CNRS, GREYC, France;
<EMAIL_ADDRESS>Tran T. A. Nghia222Department of
Mathematics and Statistics, Oakland University, Rochester, MI 48309, USA;
email<EMAIL_ADDRESS>Research of this author was supported by the US
National Science Foundation under grant DMS-1816386. Trinh T. T.
Tran333Department of Mathematics and Statistics, Oakland University,
Rochester, MI 48309, USA; email<EMAIL_ADDRESS>
###### Abstract

In this paper, we show the important roles of sharp minima and strong minima
for robust recovery. We also obtain several characterizations of sharp minima
for convex regularized optimization problems. Our characterizations are
quantitative and verifiable especially for the case of decomposable norm
regularized problems including sparsity, group-sparsity, and low-rank convex
problems. For group-sparsity optimization problems, we show that a unique
solution is a strong solution and obtain quantitative characterizations for
solution uniqueness.

###### Contents

  1. 1 Introduction
    1. 1.1 Problem statement
    2. 1.2 Contributions and relation to prior work
  2. 2 Preliminaries
    1. 2.1 Some linear algebra
    2. 2.2 Some convex analysis
    3. 2.3 Sharp and strong minima
  3. 3 Unique, sharp, and strong solutions for robust recovery
    1. 3.1 Uniqueness and robust recovery
    2. 3.2 Sharp minima and robust recovery
    3. 3.3 Strong minima and robust recovery
  4. 4 Nondegeneracy, restricted injectivity and sharp minima
    1. 4.1 Subdifferential decomposability
    2. 4.2 Quantitative characterization of sharp minima
    3. 4.3 Robust recovery with analysis decomposable priors
    4. 4.4 Connections between unique/sharp/strong solutions in the noiseless case
  5. 5 Characterizations of unique/strong solutions for group-sparsity
    1. 5.1 Descent cone of group sparsity
    2. 5.2 Unique vs strong solutions
    3. 5.3 Connections between unique/strong solutions in the noiseless case
  6. 6 Numerical verification of solution uniqueness for group-sparsity
  7. 7 Conclusion

##  1 Introduction

###  1.1 Problem statement

Inverse problems and regularization theory is a central theme in various areas
of engineering and science. A typical case is where one observes a vector
$y_{0}\in\mathbb{R}^{m}$ of linear measurements according to

$y_{0}=\Phi x_{0}$ (1.1)

where $\Phi\in\mathbb{R}^{m\times n}$ is known, and is typically an
idealization of the sensing mechanism in signal/imaging science applications,
or the design matrix in a parametric statistical regression problem. The
vector $x_{0}\in\mathbb{R}^{n}$ is the unknown quantity of interest.

Solving the inverse problem associated to the linear forward model (1.1)
amounts to recovering $x_{0}$, either exactly or to a good approximation,
knowing $y_{0}$ and $\Phi$. This is however a quite challenging task
especially when the linear system (1.1) is underdetermined with $m\ll n$. In
fact, even when $m=n$, $\Phi$ is in general ill-conditioned or even singular.
This entails that the linear inverse problem is in general ill-posed.

In order to bring back the problem to the land of well-posedness, it is
necessary to restrict the inversion process to a well-chosen subset of
$\mathbb{R}^{n}$ containing the plausible solutions including $x_{0}$. This
can be achieved by adopting a variational framework and solving the following
optimization problem

$\min_{x\in\mathbb{R}^{n}}\quad J(x)\quad\text{subject to}\quad\Phi x=y_{0},$
(1.2)

where $J$ is function which is bounded from below (wlog non-negative). The
function $J$, known as a regularizer, is designed in such way that it is the
smallest on the sought-after solutions. Popular example in signal/image
processing and machine learning is the $\ell_{1}$ norm to promote sparsity,
the $\ell_{1}/\ell_{2}$ norm to promote group sparsity, analysis sparsity
seminorm (i.e., $J=J_{0}\circ D^{*}$, $D^{*}:\mathbb{R}^{n}\to\mathbb{R}^{p}$
is linear and $J_{0}$ is the $\ell_{1}$ or $\ell_{1}/\ell_{2}$ norm); see [6,
9, 12, 21, 29, 33, 35, 41, 43] to cite a few. Another popular example is the
nuclear norm, i.e., the $\ell_{1}$ norm of the singular values of a matrix, to
recover low-rank matrices [10, 8]. These prototypical cases are included in
the class of decomposable norms [26, 7, 14] that covers a wide range of
optimization-based recovery problems in different areas of data science.

When the observation is subject to errors, the system (1.1) is modified to

$y=\Phi x_{0}+\omega$ (1.3)

where $\omega$ accounts either for noise and/or modeling errors. The errors
can be either deterministic (in this case, one typically assumes to know some
bound on $\|\omega\|$) or random (in which case its distribution is assumed to
be known). Throughout, $\omega$ will be assumed deterministic with
$\|\omega\|\leq\delta$, with $\delta>0$ known.

To recover $x_{0}$ from (1.3), one solves the noise-aware form (aka Mozorov
regularization in the inverse problems literature)

$\min_{x\in\mathbb{R}^{n}}J(x)\quad\mbox{subject to}\quad\|y-\Phi
x\|\leq\delta$ (1.4)

or its penalized/Lagrangian form (aka Tikhonov regularization in the inverse
problems literature)

$\min_{x\in\mathbb{R}^{n}}\frac{1}{2}\|\Phi x-y\|^{2}+\mu J(x).$ (1.5)

with regularization parameter $\mu>0$. It is well-known that (1.4) and (1.5)
are formally equivalent in the sense that there exists a bijection between
$\delta$ and $\mu$ such that the both problems share the same set of
solutions.

We say that robust recovery occurs when solutions to (1.4) or (1.5) are close
enough to the original signal $x_{0}$ as long as $\mu$ is appropriately chosen
(as a function of the noise level $\delta$). For $\ell_{1}$-regularized
optimization problem, a significant result was achieved in [19, Theorem 4.7],
which shows that when $\mu$ is proportional to $\delta$, the error between any
solution of problem (1.5) to $x_{0}$ is $\mathcal{O}(\delta)$444This justifies
the conventional terminology ”linear convergence rate”. if and only if $x_{0}$
is the unique solution to (1.2). The structure of the $\ell_{1}$ norm plays a
crucial role in their result. Sufficient (but not necessary in general)
conditions for robust recovery with a linear convergence rate have been
proposed for general class of regularizers by solving either (1.4) or (1.5);
see [10, 14, 39, 42, 36] and references therein. For instance [10] and [36]
provide a sufficient condition via the geometric notion of descent cone for
robust recovery with linear rate by solving (1.4) (but not (1.5)). Injectivity
of $\Phi$ on the descent cone turns out to be a sufficient and necessary
condition for solution uniqueness of (1.2). However, solution uniqueness is
not enough to guarantee robust recovery with linear rate for general
regularizers.

In fact, we observe that [10] needs $x_{0}$ to be a sharp solution to problem
(1.2). A sharp minimum, introduced by Crome and Polyak [11, 27, 28], is a
point around which the objective value has a first-order growth (see Section 2
for a rigorous definition and discussion). It is certainly sufficient for
solution uniqueness and indeed is called strong uniqueness in [11]. In the
case of polyhedral problems, e.g., problem (1.2) with $\ell_{1}$ or
$\ell_{\infty}$ norms, solution uniqueness is equivalent to sharp minima. This
is the key reason why [19] only needs solution uniqueness for robust recovery
with linear rate. In the optimization community, sharp minima is well-known
for its essence to finite convergence of the proximal point algorithms; see,
e.g., [28, 31].

Sharp minima is actually hidden in both exact recovery (by solving (1.2)) and
robust recovery. As we will show later, sharpness is closely related to many
other results on exact and robust recovery, for instance those involving
conditions based on non-degenerate dual certificates (aka Nondegenerate Source
Condition) and restricted injectivity of $\Phi$, or the Null Space Property
and its variants; see [12, 9, 37, 16, 38, 8, 6, 19, 15, 41, 14, 7, 41, 39, 42,
44]. When $\Phi$ is drawn from an appropriate random ensemble, existing sample
complexiy bounds (i.e., a lower-bound on $m$ depending on the ”intrinsic”
dimension of the model subspace containing $x_{0}$ and logarithmically on $n$)
rely on verifying the afore-mentioned conditions with high probability on
$\Phi$; see [15, 42, 36] for comprehensive reviews. For Gaussian measurements,
sample complexity bounds for exact recovery are provided in terms of the
Gaussian width in [10] and the statistical dimension in [1], and the latter
has been shown to precise predictions about the quantitative aspects of the
phase transition for exact recovery from Gaussian measurements.

Another popular notion in optimization [5, 32] is that of strong minima, which
is a sufficient condition for solution uniqueness. It is also used implicitly
in many results on robust recovery. A strong minimum is a point around which
the objective value has a quadratic (or second-order) growth. Strong minima
are certainly weaker than sharp minima. In the $\ell_{1}$ case, we observe
that the cost function in (1.5) belongs to the bigger class of convex
piecewise linear-quadratic functions [32]. A unique solution to this function
is also a strong solution. This simple observation was used recently in [4] to
obtain some characterizations for solution uniqueness to (1.5) for the case of
the Lasso problem. Necessary and sufficient conditions for solution uniqueness
to (1.5) where $J$ is piecewise linear are also studied in [17, 24, 44].

###  1.2 Contributions and relation to prior work

The chief goal of this paper is to show the intricate and important roles of
sharp minima and strong minima in robust recovery. Our main contributions are
as follows.

  1. $\bullet$

As discussed above, solution uniqueness and sharp minima play a pivotal role
for robust recovery with linear rate. However, except the case where the
regularizer $J$ is merely polyhedral, a unique solution may not be sharp. For
example, as we will show in our Section 5, a unique solution to the group-
sparsity problem (1.2) is always a strong minimum but not a sharp one. The
natural question is therefore whether strong minima could also lead to some
meaningful results for robust recovery. Section 3 answers this question
positively without even needing convexity of $J$, unlike the previous work of
[39, 42] which showed that a sharp minimizer implicitly guarantees robust
recovery with linear rate, but convexity was essential there. We show that if
$x_{0}$ is a strong solution to (1.2), then we have robust recovery by solving
(1.4) or (1.5) with a convergence rate $\mathcal{O}(\sqrt{\delta})$ (Theorem
3.12). This rate can be improved to the linear rate $\mathcal{O}(\delta)$ when
$J=\|\cdot\|$. Whether this linear rate for robust recovery can be achieved
for other regularizers under the sole strong minimality assumption is an open
question. Besides that main result, we also revisit in Theorem 3.10 robust
recovery results when $x_{0}$ is assumed to be a sharp minimizer by proving
linear convergence and providing more explicit bounds in comparison to the
results in [10, 14, 19, 44].

  2. $\bullet$

Our second main contribution, at the heart of Section 4, is to study necessary
and sufficient conditions for the properties of sharp and strong minima. As
mentioned above, solution uniqueness is characterized via the descent cone
[10]. But it is hard to compute the descent cone for general functions $J$. On
the other hand, sharp and strong minima can be characterized explicitly via
first and second-order analysis [5, 28, 32]. We leverage these tools (see
Theorem 4.6 and Proposition 4.12) to get equivalent charaterizations of
unique/sharp/strong solutions, and to obtain a quantitative condition for
convex regularized problems that allows us to check numerically that a
solution is sharp. This condition bears similarities with the Nondegenerate
Source Condition of [19, 39, 42]. Our approach does not rely on any polyhedral
structure. This distinguishes our results from several ones in the literature
as in [17, 24, 44], and allows us to work on more general optimization
problems. We also believe that non-smooth second-order analysis of the type we
develop here, which is a powerful tool in variational analysis and nonsmooth
optimization, is not well-known in the robust recovery literature, and are
thus of particular importance in this context.

  3. $\bullet$

Finally, Section 5 is devoted to a comprehensive treatment of unique/strong
solutions for group-sparsity minimization problems [29, 33, 43], an important
class of (1.2) where $J$ is the $\ell_{1}/\ell_{2}$ norm. Sufficient
conditions for solution uniqueness for group-sparsity minimization problems
were achieved in [7, 18, 21, 29, 33, 39, 42], but none of them are necessary.
To find a characterization for solution uniqueness, we first obtain a closed
form for the descent cone (Theorem 5.1). To the best of our knowledge, this
was an open question in the literature, though the statistical dimension of
this cone is more computable [1]. By relying again on second-order analysis
[5, 32], we show that a unique solution to group-sparsity minimization
problems (1.2) and (1.5) is indeed a strong solution (Theorem 5.3). This
result is interesting in two ways: first, the function in (1.2) is not
piecewise linear-quadratic, which rules out the approach developed in [4] to
unify solution uniqueness and strong minima; second, strong solutions are
possibly more natural than sharp solutions for non-polyhedral minimization
problems whenever solution uniqueness occurs. Moreover, we establish a
quantitative condition for checking unique/strong solutions to group-sparsity
problems that is equivalent to solving a smooth convex optimization problem.
This convex problem can be solved via available packages such as cvxopt as we
will illustrate in the numerical results of Section 6. Consequently, we show
that solution uniqueness to group-sparsity problem is equivalent to the robust
recovery with rate $\mathcal{O}(\sqrt{\delta})$ for both problems (1.4) and
(1.5).

######  Remark 1.1.

Although we do not have a rigorous study for the case where $J$ is the nuclear
norm in this paper, we provide several examples showing that a unique solution
to (1.2) with the nuclear norm is neither sharp nor strong. This raises the
challenge of understanding the interplay between unique, sharp, and strong
solutions in this case. Some open questions will be discussed in Section 7 for
further research in this direction.

##  2 Preliminaries

Throughout the paper, $\mathbb{R}^{n}$ is the Euclidean space with dimension
$n$. In $\mathbb{R}^{n}$ we denote the inner product by
$\left\langle\cdot,\,\cdot\right\rangle$, the Euclidean norm by $\|\cdot\|$,
and the closed ball of radius $r>0$ centered at $x\in\mathbb{R}^{n}$ by
$\mathbb{B}_{r}(x)$, and $\mathbb{I}$ the identity operator.

###  2.1 Some linear algebra

Given an $m\times n$ matrix $A$, $\mbox{\rm Ker}\,A$ (resp. $\mbox{\rm
Im}\,A$) is the kernel/null (resp. image) space of $A$. The Moore-Penrose
generalized inverse [22, Page 423] of $A$ is denoted by $A^{\dagger}$, which
satisfies the property

$AA^{\dagger}A=A.$ (2.1)

Moreover, we have

$\begin{gathered}Ax=b\text{ is consistent if and only if
}AA^{\dagger}b=b,\enskip\text{and}\enskip\\\ \text{the set of solutions to
$Ax=b$ is }A^{\dagger}b+\mbox{\rm Ker}\,A.\end{gathered}$ (2.2)

If $A$ is injective then $A^{\dagger}=(A^{\top}A)^{-1}A^{\top}$, where
$A^{\top}$ is the transpose of $A$. If $A$ is surjective then
$A^{\dagger}=A^{\top}(AA\top)^{-1}$. $A^{*}$ will also denote the adjoint of
$A$ as a linear operator.

Suppose that $\bar{x}$ is a solution to the consistent system $Ax=b$. The
projection of $x\in\mathbb{R}^{n}$ onto the affine set
$C\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}A^{-1}b$ is

$\mbox{\rm
P}_{C}(x)=(\mathbb{I}-A^{\dagger}A)(x-\bar{x})+\bar{x}=x-A^{\dagger}A(x-\bar{x});$
(2.3)

see, e.g., [22, page 435–437]. Let $\|\cdot\|_{\mathcal{A}}$ and
$\|\cdot\|_{\mathcal{B}}$ be two arbitrary norms in $\mathbb{R}^{m}$ and
$\mathbb{R}^{n}$, respectively. The matrix operator norm
$\|\cdot\|_{\mathcal{A},\mathcal{B}}:\mathbb{R}^{m\times n}\to\mathbb{R}_{+}$
is defined by

$\|A\|_{\mathcal{A},\mathcal{B}}\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\max_{x\in\mathbb{R}^{n}\setminus\\{0\\}}\dfrac{\|Ax\|_{\mathcal{A}}}{\|x\|_{\mathcal{B}}}.$

We write $\|A\|_{2,2}$ for $\|A\|$. The Frobenius norm of $A$ is known as

$\|A\|_{F}=\sqrt{\mbox{\rm Trace}\,(A^{*}A)}.$

Recall that the nuclear norm of $A$ is

$\|A\|_{*}=\sum_{k=1}^{\min(m,n)}\sigma_{k},$

where $\sigma_{k}$, $1\leq k\leq\min(m,n)$ are all the singular values of $A$.

###  2.2 Some convex analysis

Let
$\varphi:\mathbb{R}^{n}\to\overline{\mathbb{R}}\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\mathbb{R}\cup\\{+\infty\\}$ be a proper lower semi-continuous
(lsc) convex function with domain $\mbox{\rm
dom}\,\varphi\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\left\\{x\in\mathbb{R}^{n}|\;\varphi(x)<\infty\right\\}$. The
subdifferential of $\varphi$ at $x\in\mbox{\rm dom}\,\varphi$ is defined by

$\partial\varphi(x)\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\left\\{v\in\mathbb{R}^{n}|\;\varphi(u)\geq\varphi(x)+\left\langle
v,\,u-x\right\rangle,\quad\forall u\in\mathbb{R}^{n}\right\\}.$

When $\varphi(\cdot)=\iota_{C}(\cdot)$, the indicator function of a nonempty
closed convex set $C$, i.e., $\iota_{C}(x)=0$ if $x\in C$ and $+\infty$
otherwise, the subdifferential of $\iota_{C}$ at $x\in C$ is the normal cone
to $C$ at $x$:

$N_{C}(x)\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\left\\{v\in\mathbb{R}^{n}|\;\left\langle v,\,u-x\right\rangle\leq
0,\quad\forall u\in C\right\\}.$ (2.4)

For a set $\Omega\subset\mathbb{R}^{n}$, $\mbox{\rm cone}\,\Omega$ is its
conical hull, $\mbox{\rm int}\,\Omega$ is the interior of $\Omega$, and
$\mbox{\rm ri}\,\Omega$ is the relative interior of the convex set $\Omega$.
Given a convex cone $K\subset\mathbb{R}^{n}$, the polar of $K$ is defined to
be the cone

$K^{\circ}\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\left\\{v\in\mathbb{R}^{n}|\;\left\langle v,\,u\right\rangle\leq
0,\quad\forall u\in\Omega\right\\}.$ (2.5)

It is well known, see [32, Corollary 6.21] that $K^{\circ}$ is closed and
convex, and that

$K^{\circ}=\mbox{\rm cl}\,(K)^{\circ}\enskip\text{and}\enskip
K^{\circ\circ}=(K^{\circ})^{\circ}=\mbox{\rm cl}\,(K),$ (2.6)

where cl denotes the topological closure. We will also use cl for the closure
of a function, i.e., the topological closure of its epigraph.

The gauge function of $\Omega$ is defined by

$\gamma_{\Omega}(u)\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\inf\left\\{r>0|\;u\in rC\right\\},\quad\text{for}\quad
u\in\mathbb{R}^{n}.$ (2.7)

The support function to $\Omega$ is denoted by

$\sigma_{\Omega}(v)\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\sup_{x\in\Omega}\left\langle
v,\,x\right\rangle,\quad\text{for}\quad v\in\mathbb{R}^{n}.$ (2.8)

It is a proper lsc convex function as soon as $\Omega$ is non-empty. The polar
set of $\Omega$ is given by

$\Omega^{\circ}\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\left\\{v\in\mathbb{R}^{n}|\;\sigma_{C}(v)\leq 1\right\\}.$ (2.9)

When $\Omega$ is a non-empty convex set, $\Omega^{\circ}$ is a non-empty
closed convex set containing the origin. When $\Omega$ is also closed and
contains the origin, it is well-known that

$\gamma_{\Omega}=\sigma_{\Omega^{\circ}},$ (2.10)

see, e.g., [30, Corollary 15.1.2]. In this case, $\gamma_{C}$ is a non-
negative lsc convex and positively homogenous function.

###  2.3 Sharp and strong minima

Let us first recall the definition of sharp and strong solutions in [5, 11,
28, 32] that are playing central roles throughout the paper.

######  Definition 2.1 (Sharp and strong minima).

We say $\bar{x}$ to be a sharp solution/minimizer to the (non necessarily
convex) function $\varphi$ with a constant $c>0$ if there exists
$\varepsilon>0$ such that

$\varphi(x)\geq\varphi(\bar{x})+c\|x-\bar{x}\|,\quad\forall
x\in\mathbb{B}_{\varepsilon}(\bar{x}).$ (2.11)

Moreover, $\bar{x}$ is said to be a strong solution/minimizer with a constant
$\kappa>0$ if there exists $\delta>0$ such that

$\varphi(x)\geq\varphi(\bar{x})+\frac{\kappa}{2}\|x-\bar{x}\|^{2},\quad\forall
x\in\mathbb{B}_{\delta}(\bar{x}).$ (2.12)

Properties (2.11) and (2.12) are also known as respectively, first order and
second order (or quadratic) growth properties.

Strong minima is certainly weaker than sharp minima. Moreover, if $\bar{x}$ is
a sharp or strong solution to $\varphi$, it is a unique local minimizer to
$\varphi$ (and the unique minimizer if $\varphi$ is convex). When the function
$\varphi$ is a convex piecewise linear convex, i.e., its epigraph is a
polyhedral, $\bar{x}$ is a unique solution to $\varphi$ if and only if it is a
sharp solution. Furthermore, if $\varphi$ is a convex piecewise linear-
quadratic function in the sense that its domain is a union of finitely many
polyhedral sets, relative to each of which $\varphi$ is a quadratic function,
$\bar{x}$ is a strong solution if and only if it is a unique solution, see,
e.g., [4].

To characterize sharp and strong solutions, it is typical to use directional
derivative and second subderivative; see, e.g., [5, 32].

######  Definition 2.2 (directional derivative and second subderivative).

Let $\varphi:\mathbb{R}^{n}\to\overline{\mathbb{R}}$ be a proper lsc convex
function. The directional derivative of $\varphi$ at $\bar{x}\in\mbox{\rm
dom}\,\varphi$ is the function
$d\varphi(\bar{x}):\mathbb{R}^{n}\to\overline{\mathbb{R}}$ defined by

$d\varphi(\bar{x})(w)\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\lim_{t\downarrow
0}\dfrac{\varphi(\bar{x}+tw)-\varphi(\bar{x})}{t}\quad\text{for}\quad
w\in\mathbb{R}^{n}.$ (2.13)

The second subderivative of $\varphi$ at $\bar{x}\in\mbox{\rm dom}\,\varphi$
for $\bar{v}\in\partial\varphi(\bar{x})$ is the function
$d^{2}\varphi(\bar{x}|\bar{v}):\mathbb{R}^{n}\to\overline{\mathbb{R}}_{+}$
defined by

$d^{2}\varphi(\bar{x}|\bar{v})(w)\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\liminf_{t\downarrow 0,w^{\prime}\to
w}\dfrac{\varphi(\bar{x}+tw^{\prime})-\varphi(\bar{x})-t\left\langle\bar{v},\,w^{\prime}\right\rangle}{\frac{1}{2}t^{2}}\quad\text{for}\quad
w\in\mathbb{R}^{n}.$ (2.14)

It is well-known that $d\varphi(\bar{x})(w)=\max\left\\{\left\langle
v,\,w\right\rangle|\;v\in\partial\varphi(\bar{x})\right\\}$ if $\varphi$ is
continuous at $\bar{x}$. The calculation of $d^{2}\varphi(\bar{x}|\bar{v})(w)$
is quite involved in general; see, e.g., [5, 32, 23]. Note that from [32,
Proposition 13.5 and Proposition 13.20], the function
$d^{2}\varphi(\bar{x}|\bar{v})$ is non-negative, lsc, positively homogeneous
of degree 2, and

$\mbox{\rm
dom}\,d^{2}\varphi(\bar{x}|\bar{v})\subset\mathcal{T}(\bar{x}|\bar{v})\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\left\\{w\in\mathbb{R}^{n}|\;d\varphi(\bar{x})(w)=\left\langle\bar{v},\,w\right\rangle\right\\}.$
(2.15)

If, moreover, $\varphi$ is twice-differentiable at $\bar{x}$, we have (see
[32, Example 13.8])

$d^{2}\varphi(\bar{x}|\nabla\varphi(\bar{x}))(w)=\left\langle
w,\,\nabla^{2}\varphi(\bar{x})w\right\rangle.$ (2.16)

The following sum rule for second subderivatives will be useful.

######  Lemma 2.3.

Let $\varphi,\phi:\mathbb{R}^{n}\to\overline{\mathbb{R}}$ be proper lsc convex
functions with $\bar{x}\in\mbox{\rm dom}\,\varphi\cap\mbox{\rm dom}\,\phi$.
Suppose that $\varphi$ is twice-differentiable at $\bar{x}\in{\rm
int}\,(\mbox{\rm dom}\,\varphi)$ and
$\bar{v}\in\partial(\varphi+\phi)(\bar{x})=\nabla\varphi(\bar{x})+\partial\phi(\bar{x})$.
Then we have

$d^{2}(\varphi+\phi)(\bar{x}|\bar{v})(w)=\langle
w,\nabla^{2}\varphi(\bar{x})w\rangle+d^{2}\phi(\bar{x}|\bar{v}-\nabla\varphi(\bar{x}))(w)\quad\text{for
all}\quad w\in\mathbb{R}^{n}.$ (2.17)

###### Proof.

Use convexity of $\varphi,\phi$ and twice-differentiability of $\varphi$ at
$\bar{x}$ into [32, Proposition 13.19]. ∎

The next result taken from [28, Lemma 3, Chapter 5] and [32, Theorem 13.24]
characterize sharp and strong minima.

######  Lemma 2.4 (Characterization of sharp and strong minima).

Let $\varphi:\mathbb{R}^{n}\to\overline{\mathbb{R}}$ be a proper lsc convex
function with $\bar{x}\in\mbox{\rm dom}\,\varphi$. We have:

  1. (i)

$\bar{x}$ is a sharp minimizer to $\varphi$ if and only if there exists $c>0$
such that $d\varphi(\bar{x})(w)\geq c\|w\|$ for all $w\in\mathbb{R}^{n}$,
i.e., $d\varphi(\bar{x})(w)>0$ for all $w\in\mathbb{R}^{n}\setminus\\{0\\}$.

  2. (ii)

$\bar{x}$ is a strong minimizer to $\varphi$ if and only if
$0\in\partial\varphi(\bar{x})$ and there exists $\kappa>0$ such that
$d^{2}\varphi(\bar{x}|0)(w)\geq\kappa\|w\|^{2}$ for all $w\in\mathbb{R}^{n}$,
which means

$\mbox{\rm Ker}\,d^{2}\varphi(\bar{x}|0)\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\left\\{w\in\mathbb{R}^{n}|\;d^{2}\varphi(\bar{x}|0)(w)=0\right\\}=\\{0\\}.$

It is important to observe that although the sharpness of a minimizer as
defined in (2.11) is a local property, it is actually a global one for convex
problems.

######  Lemma 2.5 (Global sharp minima).

Suppose that $\bar{x}$ is a sharp solution to the proper lsc convex function
$\varphi$. Then there exists $c>0$ such that

$\varphi(x)-\varphi(\bar{x})\geq c\|x-\bar{x}\|\quad\quad\text{for all}\quad
x\in\mathbb{R}^{n}.$

###### Proof.

Since $\bar{x}$ is a sharp solution to $\varphi$, we have from Lemma 2.4(i)
that $\exists c>0$ such that $d\varphi(\bar{x})(w)\geq c\|w\|$, $\forall
w\in\mathbb{R}^{n}$. Thus, by the characterization of the directional
derivative for convex functions, we have for any $x\in\mathbb{R}^{n}$

$\varphi(x)-\varphi(\bar{x})=\varphi(\bar{x}+(x-\bar{x}))-\varphi(\bar{x})\geq\inf_{t>0}\dfrac{\varphi(\bar{x}+t(x-\bar{x}))-\varphi(\bar{x})}{t}=d\varphi(\bar{x})(x-\bar{x})\geq
c\|x-\bar{x}\|.$

The proof is complete. ∎

##  3 Unique, sharp, and strong solutions for robust recovery

###  3.1 Uniqueness and robust recovery

Let us consider the optimization problem in (1.2) where we suppose that
$J:\mathbb{R}^{n}\to\overline{\mathbb{R}}$ is a non-negative lsc function but
not necessarily convex. We denote by
$J_{\infty}:\mathbb{R}^{n}\to\overline{\mathbb{R}}$ the asymptotic (or
horizon) function [2] associated with $J$, which is defined by

$J_{\infty}(w)\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\liminf_{w^{\prime}\to w,t\to\infty}\dfrac{J(tw^{\prime})}{t}.$
(3.1)

Throughout this section, we assume that $J$ satisfies

$\mbox{\rm Ker}\,J_{\infty}\cap\mbox{\rm Ker}\,\Phi=\\{0\\},$ (3.2)

where $\mbox{\rm Ker}\,J_{\infty}\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\left\\{w\in\mathbb{R}^{n}|\;J_{\infty}(w)=0\right\\}$, and the
range of $J_{\infty}$ is on $\mathbb{R}_{+}$ since $J$ is non-negative. It
then follows from [2, Corollary 3.1.2] that (3.2) ensures that problem (1.2)
has a non-empty compact set of minimizers.

Define $\Psi:\mathbb{R}^{n}\to\overline{\mathbb{R}}$ as

$\Psi(x)\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}J(x)+\iota_{\Phi^{-1}(\Phi x_{0})}(x)\quad\mbox{for all}\quad
x\in\mathbb{R}^{n}.$ (3.3)

We say that $x_{0}$ is a unique, sharp, or strong solution to (1.2) if it is a
unique, sharp, or strong solution to the function $\Psi$, respectively.

Our first result shows that solution uniqueness is sufficient for robust
recovery. If $J$ is also convex, then uniqueness is also necessary. The
sufficiency part of our result generalizes the corresponding part of [20,
Theorem 3.5] to nonconvex problems.

######  Proposition 3.1 (Solution uniqueness for robust recovery).

Suppose that $J$ is a non-negative lsc function which satisfies (3.2).

  1. (i)

If $x_{0}$ is the unique solution to problem (1.2) then:

    1. (a)

any solution $x_{\delta}$ to problem (1.4) with $\|y-y_{0}\|\leq\delta$
converges to $x_{0}$ as $\delta\to 0$,

    2. (b)

for any constant $c_{1}>0$, any solution $x_{\mu}$ to problem (1.5) with
$\mu=c_{1}\delta$ and $\|y-y_{0}\|\leq\delta$ converges to $x_{0}$ as
$\delta\to 0$.

  2. (ii)

Conversely, if $J$ is convex and $\mbox{\rm dom}\,J=\mathbb{R}^{n}$, then:

    1. (a)

(i)-(i)(a) implies $x_{0}$ is the unique solution to (1.2).

    2. (b)

(i)-(i)(b) implies $x_{0}$ is the unique solution to (1.2).

###### Proof.

  1. (i)

Suppose that $x_{0}$ is the unique solution to problem (1.2). To justify
(i)-(i)(a), define the function $g\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\iota_{\mathbb{B}_{\delta}(y)}\circ\Phi$. We have, using [2,
Propositions 2.6.1, 2.6.3 and 2.1.2], that

$\displaystyle(J+g)_{\infty}(w)\geq
J_{\infty}(w)+g_{\infty}(w)=J_{\infty}(w)+(\iota_{\mathbb{B}_{\delta}(y)})_{\infty}(\Phi
w)$ $\displaystyle=$ $\displaystyle J_{\infty}(w)+\iota_{\\{0\\}}(\Phi w)$
$\displaystyle=$ $\displaystyle J_{\infty}(w)+\iota_{\mbox{\rm
Ker}\,\Phi}(w)\geq 0.$

Thus, under (3.2), the set of solutions to (1.4) is nonempty and compact
thanks to [2, Corollary 3.1.2]. If $\\{x_{\delta}\\}_{\delta>0}$ is unbounded,
without passing to subsequences suppose that $\|x_{\delta}\|\to\infty$ and
$\dfrac{x_{\delta}}{\|x_{\delta}\|}\to w$ as $\delta\downarrow 0$ with
$\|w\|=1$. We have

$0\leq\left\|\Phi\left(\frac{x_{\delta}}{\|x_{\delta}\|}\right)-\frac{y}{\|x_{\delta}\|}\right\|\leq\frac{\delta}{\|x_{\delta}\|},$

and after passing to the limit, we get that $w\in\mbox{\rm Ker}\,\Phi$.
Moreover, since $x_{0}$ is a feasible point of (1.4), we have
$J(x_{\delta})\leq J(x_{0})$, and thus

$0=\liminf_{\delta\downarrow
0}\dfrac{J(x_{0})}{\|x_{\delta}\|}\geq\liminf_{\delta\downarrow
0}\dfrac{J(x_{\delta})}{\|x_{\delta}\|}\geq J_{\infty}(w)\geq 0,$

which means that $w\in\mbox{\rm Ker}\,J_{\infty}$. This entails that $0\neq
w\in\mbox{\rm Ker}\,J_{\infty}\cap\mbox{\rm Ker}\,\Phi$, which contradicts
(3.2). Thus $\\{x_{\delta}\\}_{\delta>0}$ is bounded. Pick any subsequence
$\\{x_{\delta_{k}}\\}_{k\in\mathbb{N}}$ of $\\{x_{\delta}\\}_{\delta>0}$
converging to some $\bar{x}$ as $\delta_{k}\downarrow 0$. From lower
semicontinuity of $J$ and of the norm, we get

$J(\bar{x})\leq\liminf_{k}J(x_{\delta_{k}})\leq
J(x_{0})\enskip\text{and}\enskip
0\leq\|y_{0}-\Phi\bar{x}\|\leq\liminf_{k}\|y_{0}-\Phi x_{\delta_{k}}\|\leq
2\lim_{k}\delta_{k}=0.$

This means that $\bar{x}$ is a solution of (1.2), and by uniqueness of the
minimizer, $\bar{x}=x_{0}$. Since the subsequence
$\\{x_{\delta_{k}}\\}_{k\in\mathbb{N}}$ was arbitrary, we have $x_{\delta}\to
x_{0}$ as $\delta\downarrow 0$, whence claim (i)-(i)(a) follows.

The proof of (i)-(i)(b) uses a similar reasoning. Let
$g=\frac{1}{2}\|y-\cdot\|^{2}\circ\Phi$. One has, using [2, Propositions
2.6.1, 2.6.3 and 2.6.7], that

$\displaystyle(\mu J+g)_{\infty}(w)\geq\mu J_{\infty}(w)+g_{\infty}(w)=\mu
J_{\infty}(w)+\frac{1}{2}\left(\|\cdot\|^{2}\right)_{\infty}(\Phi w)$
$\displaystyle=$ $\displaystyle\mu J_{\infty}(w)+\iota_{\\{0\\}}(\Phi w)$
$\displaystyle=$ $\displaystyle\mu J_{\infty}(w)+\iota_{\mbox{\rm
Ker}\,\Phi}(w)\geq 0.$

Hence the set of optimal solutions to problem (1.5) is nonempty and compact
according to [2, Corollary 3.1.2]. Similarly to part (i)-(i)(a), we claim that
$\\{x_{\mu}\\}_{\mu>0}$ is bounded. By contradiction, suppose again that
$\|x_{\mu}\|\to\infty$ and $\dfrac{x_{\mu}}{\|x_{\mu}\|}\to z$ with $\|z\|=1$.
Note that by optimality of $x_{\mu}$

$\mu J(x_{\mu})\leq\frac{1}{2}\|\Phi x_{\mu}-y\|^{2}+\mu
J(x_{\mu})\leq\frac{1}{2}\|\Phi x_{0}-y\|^{2}+\mu
J(x_{0})\leq\frac{\delta^{2}}{2}+\mu J(x_{0}).$ (3.4)

As $\mu=c_{1}\delta$, we obtain from (3.4) that

$0=\liminf_{\delta\downarrow
0}\dfrac{J(x_{0})+\frac{\delta}{2c_{1}}}{\|x_{\mu}\|}\geq\liminf_{\delta\downarrow
0}\dfrac{J(x_{\mu})}{\|x_{\mu}\|}\geq J_{\infty}(z)\geq 0,$

which means $z\in\mbox{\rm Ker}\,J_{\infty}$. Furthermore, (3.4) also entails

$0\leq\frac{1}{2}\left\|\Phi\left(\frac{x_{\mu}}{\|x_{\mu}\|}\right)-\frac{y}{\|x_{\mu}\|}\right\|^{2}\leq\frac{1}{\|x_{\mu}\|^{2}}\left(\frac{\delta^{2}}{2}+\mu
J(x_{0})\right),$

which tells us, after passing to the limit, that $0\neq z\in\mbox{\rm
Ker}\,J_{\infty}\cap\mbox{\rm Ker}\,\Phi$, hence contradicting (3.2). Thus
$\\{x_{\mu}\\}_{\mu>0}$ is bounded. Arguing as in (i)-(i)(a), we use lower
semicontinuity of $J$ and of the norm to show that any cluster point of
$\\{x_{\mu}\\}_{\mu>0}$ is a solution of (1.2), and deduce claim (i)-(i)(b)
thanks to uniqueness of the minimizer $x_{0}$.

  2. (ii)

Suppose now that $J$ is also convex and $\mbox{\rm dom}\,J=\mathbb{R}^{n}$
(hence continuous). If (i)-(i)(a) holds, we have

$J(x_{\delta})\leq J(x)\quad\text{for any}\quad x\quad\text{such
that}\quad\|y-\Phi
x\|\leq\delta\enskip\text{and}\enskip\|y-y_{0}\|\leq\delta.$ (3.5)

It follows that

$J(x_{\delta})\leq J(x)\quad\text{for any}\quad x\quad\text{such
that}\quad\Phi x=y_{0}.$

By letting $\delta\downarrow 0$, and using continuity of $J$, we obtain that
$x_{0}$ is a minimizer to (1.2). Let $\bar{x}$ be an arbitrary minimizer to
problem (1.2). As $\mbox{\rm dom}\,J=\mathbb{R}^{n}$, Fermat’s rule for (1.2)
and subdifferential calculus gives

$0\in\partial\Psi(\bar{x})=\partial
J(\bar{x})+N_{\Phi^{-1}y_{0}}(\bar{x})=\partial J(\bar{x})+\mbox{\rm
Im}\,\Phi^{*}.$ (3.6)

Or, equivalently, there exists a dual multiplier $\eta\in\mathbb{R}^{m}$ such
that $\Phi^{*}\eta\in\partial J(\bar{x})$555This is known as the Source
Condition [34].. If $\eta=0$, we have $0\in\partial J(\bar{x})$, which means
that $\bar{x}$ is a minimizer to $J$. Thus, $\bar{x}$ is also a minimizer to
problem (1.4) for any $\delta>0$. By (i)-(i)(a), $\bar{x}-x_{0}\to 0$ as
$\delta\downarrow 0$, i.e., $\bar{x}=x_{0}$.

If $\eta\neq 0$, take any $\delta>0$ and define
$\mu\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}\dfrac{\delta}{\|\eta\|}$
and $y\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}y_{0}+\mu\eta=\Phi\bar{x}+\mu\eta$. It follows that
$\|y-\Phi\bar{x}\|=\|y-y_{0}\|=\delta$ and that

$\frac{1}{\mu}\Phi^{*}(y-\Phi\bar{x})=\Phi^{*}\eta\in\partial J(\bar{x}).$
(3.7)

On the other hand, under our assumption, we have that $x^{\star}$ is a
solution to (1.4) if and only if

$0\in\partial J(x^{\star})+\Phi^{*}N_{\mathbb{B}_{\delta}(y)}(\Phi
x^{\star}),$

where $N_{\mathbb{B}_{\delta}(y)}(\Phi x^{\star})=\mathbb{R}_{+}(\Phi
x^{\star}-y)$ whenever $\|y-\Phi x^{\star}\|=\delta$. This is precisely the
optimality condition verified by $\bar{x}$ in (3.7), which shows that
$\bar{x}$ is also a solution to (1.4). By (i)-(i)(a) again, we have
$\bar{x}=x_{0}$. Since the choice of $\bar{x}$ is arbitrary, $x_{0}$ is the
unique solution to (1.2).

Finally, suppose that (i)-(i)(b) is satisfied. We have for any
$x\in\Phi^{-1}y_{0}$ that

$\mu J(x_{\mu})\leq\frac{1}{2}\|\Phi x-y\|^{2}+\mu
J(x)\leq\frac{\delta^{2}}{2}+\mu J(x).$

Dividing both sides by $\mu=c_{1}\delta$ and letting $\delta\to 0$ entails
$J(x_{0})\leq J(x)$ for any $x\in\Phi^{-1}y_{0}$, which is equivalent to
saying that $x_{0}$ is a solution to problem (1.2). The proof of uniqueness
follows similar lines as for problem (1.4) with the choice
$y=\Phi\bar{x}+\mu\eta$ and $\mu=c_{1}\delta$. Note that under our assumption,
Fermat’s rule for problem (1.5) is (3.7) without further qualification
condition unlike what is required for (1.4).

∎

######  Remark 3.2.

In the convex case, the condition (3.2) is superfluous in Proposition 3.1(i).
Indeed, (3.2) is equivalent in this case to the fact the set of minimizers of
(1.2) is a non-empty compact set, which is obviously the case when $x_{0}$ is
the unique minimizer.

###  3.2 Sharp minima and robust recovery

A sufficient and necessary condition for uniqueness to problem (1.2), together
with its implication for robust recovery, is studied in [10] via the key
geometric notion of descent cone that we recall now.

######  Definition 3.3 (Descent cone).

The descent cone of the function $J$ at $x_{0}$ is defined by

$\mathcal{D}_{J}(x_{0})\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\mbox{\rm cone}\,\left\\{x-x_{0}|\;J(x)\leq J(x_{0})\right\\}.$
(3.8)

The following proposition provides a characterization for solution uniqueness
whose proof can be found in [10, Proposition 2.1].

######  Proposition 3.4 (Descent cone for solution uniqueness [1, 10]).

Then $x_{0}$ is the unique solution to (1.2) if and only if $\mbox{\rm
Ker}\,\Phi\cap\mathcal{D}_{J}(x_{0})=\\{0\\}$.

In [10, Proposition 2.2] (see also [36, Proposition 2.6]), the authors also
prove a robust recovery result for solutions of (1.4) via the descent cone.

######  Proposition 3.5 (Robust recovery via descent cone [10]).

Let Suppose that there exists some $\alpha>0$ such that $\|\Phi
w\|\geq\alpha\|w\|$ for all $w\in\mathcal{D}_{J}(x_{0})$. Then any solution
$x_{\delta}$ to problem (1.4) satisfies

$\|x_{\delta}-x_{0}\|\leq\frac{2\delta}{\alpha}.$ (3.9)

The parameter $\alpha$ is known as the minimum conic singular value of $\Phi$
with respect to the cone $\mathcal{D}_{J}(x_{0})$. One may observe that the
condition in Proposition 3.5 is not the same with the one for solution
uniqueness in Proposition 3.4. The reason is that the descent cone
$\mathcal{D}_{J}(x_{0})$ is not necessarily closed in general. To see this, we
first unveil the relation between the descent and critical cones. Denote

$L_{x_{0}}(J)\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\left\\{x\in\mathbb{R}^{n}|\;J(x)\leq J(x_{0})\right\\}$

the sublevel set of $J$ at $x_{0}$. The critical cone of a convex function $J$
at $x_{0}$ is

$\mathcal{C}_{J}(x_{0})\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\left\\{w\in\mathbb{R}^{n}|\;dJ(x_{0})(w)\leq 0\right\\}.$ (3.10)

######  Lemma 3.6 (Relationship between descent cone and critical cone).

Suppose that $J$ is a continuous convex function. Then,

$\mathcal{D}_{J}(x_{0})\subset\mbox{\rm
cl}\,(\mathcal{D}_{J}(x_{0}))\subset\mathcal{C}_{J}(x_{0}).$ (3.11)

If moreover $0\notin\partial J(x_{0})$, then

$\mbox{\rm cl}\,(\mathcal{D}_{J}(x_{0}))=\mathcal{C}_{J}(x_{0}).$ (3.12)

###### Proof.

We have from (2.6) that

$\mbox{\rm
cl}\,(\mathcal{D}_{J}(x_{0}))=(\mathcal{D}_{J}(x_{0}))^{\circ\circ}=\left((\mbox{\rm
cl}\,\mathcal{D}_{J}(x_{0}))^{\circ}\right)^{\circ}=(N_{L_{x_{0}}(J)}(x_{0}))^{\circ}\subset\mathcal{C}_{J}(x_{0}),$
(3.13)

where we used (2.6) in the first two equalities, polarity in the third, and
convexity and the first claim of [32, Proposition 10.3] in the last equality.
If in addition $0\notin\partial J(x_{0})$, then using [30, Corollary 23.7.1]
and the last claim of [32, Proposition 10.3], the inclusion in (3.13) becomes

$\mbox{\rm
cl}\,(\mathcal{D}_{J}(x_{0}))=(N_{L_{x_{0}}(J)}(x_{0}))^{\circ}=(\mbox{\rm
cone}\,\partial J(x_{0}))^{\circ}=\mathcal{C}_{J}(x_{0}).$ (3.14)

∎

When $J$ is also positively homogenous, the requirement $0\notin\partial
J(x_{0})$ in Lemma 3.6 can be dropped.

######  Proposition 3.7.

Suppose that $J=\sigma_{C}$, where $C\subset\mathbb{R}^{n}$ is a non-empty
compact convex set with $0\in\mbox{\rm ri}\,C$. Then, (3.12) holds at any
$x_{0}\in\mathbb{R}^{n}$.

###### Proof.

Thanks to the assumptions on $C$, we have from [30, Theorem 13.2 and Corollary
13.3.1] that $J$ convex, positively and homogenous and finite everywhere,
hence continuous. We now only consider the case where $0\in\partial J(x_{0})$
as, otherwise, the result claim follows from Lemma 3.6. By [40, Lemma 1], $J$
is also non-negative and $\mbox{\rm Ker}\,J$ is a linear subspace. This
entails that $0\in\partial J(x_{0})$ is equivalent to $x_{0}\in\mbox{\rm
Ker}\,J$, and thus from (3.8), that

$\mathcal{D}_{J}(x_{0})=\mbox{\rm cone}\,(\mbox{\rm Ker}\,J-x_{0})=\mbox{\rm
Ker}\,J.$

On the other hand, we have from (3.10) that

$\mathcal{C}_{J}(x_{0})=(\partial J(x_{0}))^{\circ}=(\mbox{\rm cone}\,\partial
J(x_{0}))^{\circ}=N_{\partial J(x_{0})}(0).$

Moreover, by [32, Corollary 8.25]

$\partial J(x_{0})=C\cap\\{x_{0}\\}^{\perp}.$

Combining this with [32, Theorem 6.42] (recall that $C$ is convex and
$0\in\mbox{\rm ri}\,C\cap\\{x_{0}\\}^{\perp}$), we get

$\mathcal{C}_{J}(x_{0})=N_{C\cap\\{x_{0}\\}^{\perp}}(0)=N_{C}(0)+\mathbb{R}x_{0}=\mbox{\rm
Ker}\,J+\mathbb{R}x_{0}=\mbox{\rm Ker}\,J,$

where the last equality comes from the fact that $\mbox{\rm Ker}\,J$ is a
linear subspace containing $x_{0}$. This completes the proof. ∎

We now turn to showing that the condition in Proposition 3.5 actually means
that $x_{0}$ is a sharp solution to (1.2).

######  Proposition 3.8 (Characterization of sharp minima via the descent and
critical cones).

Let $J$ be a continuous convex function.

  1. (i)

$x_{0}$ is a sharp solution to (1.2) if and only if $\mbox{\rm
Ker}\,\Phi\cap\mathcal{C}_{J}(x_{0})=\\{0\\}$.

  2. (ii)

If $J=\sigma_{C}$, where $C\subset\mathbb{R}^{n}$ is a non-empty compact
convex set with $0\in\mbox{\rm ri}\,C$, then $x_{0}$ is a sharp solution to
(1.2) if and only if there exists $\alpha>0$ such that $\|\Phi
w\|\geq\alpha\|w\|$ for all $w\in\mathcal{D}_{J}(x_{0})$.

###### Proof.

  1. (i)

Recall $\Psi$ from (3.3). We have

$d\Psi(x_{0})(w)=dJ(x_{0})(w)+\iota_{\mbox{\rm Ker}\,\Phi}(w).$ (3.15)

By Lemma 2.4, $x_{0}$ is a sharp solution to (1.2) if and only if
$d\Psi(x_{0})(w)>0$ for all $w\in\mathbb{R}^{n}\setminus\\{0\\}$. Combining
this with (3.10) and (3.15) leads the claimed equivalence.

  2. (ii)

Assume $x_{0}$ is a sharp solution to (1.2). Since $\mathcal{C}_{J}(x_{0})$ is
closed, we have from claim (i) that there exists $\alpha>0$ such that $\|\Phi
w\|\geq\alpha\|w\|$ for all $w\in\mathcal{C}_{J}(x_{0})$. We then get the
first implication from the inclusion (3.11). Conversely, if there is
$\alpha>0$ such that $\|\Phi w\|\geq\alpha\|w\|$ for all
$w\in\mathcal{D}_{J}(x_{0})$, we have $\|\Phi w\|\geq\alpha\|w\|$ for all
$w\in\mathcal{C}_{J}(x_{0})$ thanks to Proposition 3.7. It follows that
$\mbox{\rm Ker}\,\Phi\cap\mathcal{C}_{J}(x_{0})=\\{0\\}$. This implies, in
view of claim (i), that $x_{0}$ is a sharp solution to (1.2).

∎

The main lesson we learn from the above, in particular Proposition 3.4 and
Proposition 3.8, is that there is a gap between solution uniqueness and
solution sharpness (hence robust recovery via Proposition 3.5) for problem
(1.2). This difference lies in the closedness of the descent cone. Indeed,
when the descent cone $\mathcal{D}_{J}(x_{0})$ is closed, it coincides with
the critical cone $\mathcal{C}_{J}(x_{0})$. Unfortunately, in general,
$\mathcal{D}_{J}(x_{0})$ is not closed. A prominent example where
$\mathcal{D}_{J}(x_{0})$ may fail to be closed is that of the
$\ell_{1}/\ell_{2}$ norm very popular to promote group sparsity. The following
example is a prelude of our precise formula for the descent cone of the
$\ell_{1}/\ell_{2}$ norm in Theorem 5.1, in which the interior of the critical
cone $\mathcal{C}_{J}(x_{0})$ plays a significant role.

######  Example 3.9 (Gap between solution uniqueness and sharpness for group-
sparsity).

Consider the following $\ell_{1}/\ell_{2}$ norm minimization problem:

$\min_{x\in\mathbb{R}^{3}}J(x)=\sqrt{x_{1}^{2}+x_{2}^{2}}+|x_{3}|\quad\text{subject
to}\quad\Phi x=y_{0},$ (3.16)

with $\Phi=\begin{pmatrix}1&1&0\\\ 1&0&-1\end{pmatrix}$,
$x_{0}=(0,1,0)^{\top}$, and $y_{0}=\Phi x_{0}=(1,0)^{\top}$. We have
$\mbox{\rm Ker}\,\Phi=\mathbb{R}(1,-1,1)^{\top}$, and feasible points of
(3.16) then take the form $x=x_{0}+t(1,-1,1)^{\top}$ for any $t\in\mathbb{R}$.
For all such points, we have

$\displaystyle
J(x)-J(x_{0})=\sqrt{t^{2}+(1-t)^{2}}+|t|-1=\dfrac{t^{2}+2(|t|-t)}{\sqrt{t^{2}+(1-t)^{2}}+1-|t|},$

which tells us that $x_{0}$ is the unique solution to (3.9). In fact, simple
calculation shows that $x_{0}$ is a strong but not a sharp solution to (3.9).
For $J$ in (3.16), Figure 1 illustrates the difference between the descent
cone computed by Theorem 5.1 and the critical cone (3.10) whose computation is
straightforward in this case. It is obvious that $\mbox{\rm
Ker}\,\Phi\cap\mathcal{C}_{J}(x_{0})\neq\\{0\\}$, though $\mbox{\rm
Ker}\,\Phi\cap\mathcal{D}_{J}(x_{0})=\\{0\\}$ (which is indeed equivalent to
solution uniqueness).

Figure 1: The descent cone $\mathcal{D}_{J}(x_{0})$ and critical cone
$\mathcal{C}_{J}(x_{0})$ for $J$ in (3.16). Here,
$\mathcal{D}_{J}(x_{0})=(\mathcal{E}\cap\mbox{\rm
bd}\,\mathcal{C}_{J}(x_{0}))\cup\mbox{\rm int}\,\mathcal{C}_{J}(x_{0})$, where
$\mathcal{E}=\left\\{(0,x_{2},x_{3})|\;x_{2},x_{3}\in\mathbb{R}\right\\}$ (see
(5.8)) and
$\mathcal{C}_{J}(x_{0})=\left\\{(x_{1},x_{2},x_{3})|\;x_{2}+|x_{3}|\leq
0\right\\}$. The green shaded surface is $\mbox{\rm
bd}\,\mathcal{C}_{J}(x_{0})$ and the blue half-lines correspond to
$\mathcal{E}\cap\mbox{\rm bd}\,\mathcal{C}_{J}(x_{0})$.

∎

Inspired by Proposition 3.5, we show next that sharpness of the minimizer
guarantees robust recovery for both problems (1.4) and (1.5) with linear rate.
Unlike [10, Proposition 2.2] and many other results [14, 19, 39, 42, 44] in
this direction, we do not need convexity of $J$. In fact, the key is to assume
that $x_{0}$ is a unique and sharp solution to problem (1.2).

######  Theorem 3.10 (Sharp minima for robust recovery).

Suppose that $J$ is a non-negative lsc function which satisfies (3.2), and is
Lipschitz continuous around $x_{0}$ with modulus $L$. If $x_{0}$ is the unique
and sharp solution to (1.2) with constant $c>0$, then for all $\delta>0$
sufficiently small, the following statements hold:

  1. (i)

Any solution $x_{\delta}$ to problem (1.4) satisfies

$\|x_{\delta}-x_{0}\|\leq\frac{2(L+c)\|\Phi^{\dagger}\|}{c}\delta.$ (3.17)

  2. (ii)

For any $c_{1}>0$ and $\mu=c_{1}\delta$, any minimizer $x_{\mu}$ to (1.5)
satisfies

$\|x_{\mu}-x_{0}\|\leq\frac{c_{1}}{2c}\left(\frac{1}{c_{1}}+(c+L)\|\Phi^{\dagger}\|\right)^{2}\delta.$
(3.18)

###### Proof.

  1. (i)

$L$-Lipschitz continuity of $J$ around $x_{0}$ entails that
$\exists\varepsilon>0$ such that

$|J(x)-J(z)|\leq L\|x-z\|\quad\text{for all}\quad
x,z\in\mathbb{B}_{\varepsilon}(x_{0}).$ (3.19)

Since $x_{0}$ is a sharp solution to (1.2) with constant $c$, there exists
$\eta>0$ such that

$J(x)-J(x_{0})\geq c\|x-x_{0}\|\quad\text{for all}\quad
x\in\Phi^{-1}y_{0}\cap\mathbb{B}_{\eta}(x_{0}).$ (3.20)

Let $\bar{x}_{\delta}$ be the projection of $x_{\delta}$ onto
$\Phi^{-1}y_{0}$. Thus

$\|\bar{x}_{\delta}-x_{0}\|\leq\|x_{\delta}-\bar{x}_{\delta}\|+\|x_{\delta}-x_{0}\|\leq
2\|x_{\delta}-x_{0}\|.$ (3.21)

Since $x_{0}$ is the unique solution to problem (1.2), Proposition 3.1(i)
tells us that for all $\delta$ small enough,
$x_{\delta}\in\mathbb{B}_{\min\\{\varepsilon,\eta\\}/2}(x_{0})$ and, by
(3.21), $\bar{x}_{\delta}\in\mathbb{B}_{\min\\{\varepsilon,\eta\\}}(x_{0})$,
i.e.,
$\bar{x}_{\delta},x_{\delta}\in\mathbb{B}_{\min\\{\varepsilon,\eta\\}}(x_{0})$
with $\varepsilon,\eta$ in (3.19) and (3.20). We then have

$\displaystyle L\|\bar{x}_{\delta}-x_{\delta}\|$ $\displaystyle\geq
J(\bar{x}_{\delta})-J(x_{\delta})$ $\displaystyle\text{by \eqref{Lip}},$
$\displaystyle\geq J(\bar{x}_{\delta})-J(x_{0})$ $\displaystyle\text{by
optimality of $x_{0}$},$ $\displaystyle\geq c\|\bar{x}_{\delta}-x_{0}\|$
$\displaystyle\text{by \eqref{InSharp}},$ $\displaystyle\geq
c\|x_{\delta}-x_{0}\|-c\|x_{\delta}-\bar{x}_{\delta}\|.$

Combining this with the projection formula (2.3) tells us that

$\displaystyle c\|x_{\delta}-x_{0}\|$
$\displaystyle\leq(L+c)\|x_{\delta}-\bar{x}_{\delta}\|=(L+c)\|\Phi^{\dagger}\Phi(x_{\delta}-x_{0})\|$
$\displaystyle\leq(L+c)\|\Phi^{\dagger}\|\|\Phi(x_{\delta}-x_{0})\|$
$\displaystyle\leq(L+c)\|\Phi^{\dagger}\|(\|y-\Phi x_{\delta}\|+\|y-\Phi
x_{0}\|)$ $\displaystyle\leq(L+c)\|\Phi^{\dagger}\|2\delta,$

which is (3.17).

  2. (ii)

Optimality of $x_{\mu}$ gives

$\displaystyle J(x_{\mu})-J(x_{0})$
$\displaystyle\leq\frac{1}{2\mu}\left(\|y-\Phi x_{0}\|^{2}-\|y-\Phi
x_{\mu}\|^{2}\right)$ $\displaystyle\leq\frac{1}{2\mu}\left(\|y-\Phi
x_{0}\|^{2}-\left(\|y-\Phi x_{0}\|-\|\Phi(x_{\mu}-x_{0})\|\right)^{2}\right)$
$\displaystyle=\frac{1}{2\mu}\left(2\delta\|\Phi(x_{\mu}-x_{0})\|-\|\Phi(x_{\mu}-x_{0})\|^{2}\right).$
(3.22)

Let $\bar{x}_{\mu}$ be the projection of $x_{\mu}$ to $\Phi^{-1}y_{0}$.
Inequality (3.21) remains valid for $x_{\mu}$ and $\bar{x}_{\mu}$ replacing
$x_{\delta}$ and $\bar{x}_{\delta}$ respectively. Moreover, arguing as in the
proof of claim (i), but now invoking Proposition 3.1(ii), we infer that for
$\delta$ sufficiently small,
$x_{\mu},\bar{x}_{\mu}\in\mathbb{B}_{\min\\{\varepsilon,\eta\\}}(\bar{x})$,
where $\varepsilon,\eta$ are those in (3.19) and (3.20). Denote for short
$\alpha=\|\Phi(x_{\mu}-x_{0})\|$. We then get

$\displaystyle J(x_{\mu})-J(x_{0})$
$\displaystyle=J(\bar{x}_{\mu})-J(x_{0})+J(x_{\mu})-J(\bar{x}_{\mu})$
$\displaystyle\geq c\|\bar{x}_{\mu}-x_{0}\|-L\|x_{\mu}-\bar{x}_{\mu}\|$
$\displaystyle\text{by \eqref{InSharp} and \eqref{Lip}},$ $\displaystyle\geq
c\|x_{\mu}-x_{0}\|-(c+L)\|x_{\mu}-\bar{x}_{\mu}\|$
$\displaystyle=c\|x_{\mu}-x_{0}\|-(c+L)\|\Phi^{\dagger}\Phi(x_{\mu}-x_{0})\|$
$\displaystyle\text{by \eqref{Pro}},$ $\displaystyle\geq
c\|x_{\mu}-x_{0}\|-(c+L)\|\Phi^{\dagger}\|\alpha.$

This together with (3.22) gives us that

$\displaystyle c\|x_{\mu}-x_{0}\|$
$\displaystyle\leq\frac{2\delta\alpha-\alpha^{2}}{2\mu}+(c+L)\|\Phi^{\dagger}\|\alpha$
(3.23)
$\displaystyle=\left(\frac{\delta}{\mu}+(c+L)\|\Phi^{\dagger}\|\right)\alpha-\frac{\alpha^{2}}{2\mu}$
$\displaystyle\leq\frac{\mu}{2}\left(\frac{\delta}{\mu}+(c+L)\|\Phi^{\dagger}\|\right)^{2},$

which is clearly (3.18) for the choice $\mu=c_{1}\delta$.

∎

The bounds (3.17) and (3.18) in Theorem 3.10 hold without convexity with the
proviso that $\delta$ is sufficiently small. However, when the function $J$ is
convex and continuous, the bounds are satisfied for any $\delta>0$.

######  Corollary 3.11 (Sharp minima for robust recovery under convexity).

Suppose that $J$ is a convex continuous function. If $x_{0}$ is a sharp
solution to (1.2), then statements (i) and (ii) of Theorem 3.10 hold for any
$\delta>0$ with some constant $L>0$.

###### Proof.

When $J$ is a continuous convex function and $x_{0}$ is a sharp solution to
(1.2), it follows from Lemma 2.5 that the sharpness property (3.20) is global
and $x_{0}$ is also the unique solution to (1.2). In turn, $J$ satisfies (3.2)
in view of Remark 3.2. Therefore, the nets
$\\{x_{\delta}\\}_{\delta>0},\\{x_{\mu}\\}_{\mu>0}$ are bounded as proved in
Proposition 3.1. Thus, there exists some $R>0$ such that
$x_{0},x_{\delta},\bar{x}_{\delta},x_{\mu},\bar{x}_{\mu}\in\mathbb{B}_{R}(0)$.
Convexity and continuity of $J$ also imply that it is Lipschitz continuous on
$\mathbb{B}_{2R}(x_{0})$ with some Lipschitz constant $L>0$. Overall, this
tells us that we can take $\varepsilon,\eta$ in (3.19) and (3.20) in the proof
of Theorem 3.10 by $2R$. The rest of the proof remains valid, whence our claim
follows. ∎

#### Discussion of related work

It is worth noting that Corollary 3.11 covers many results in [14, 19, 39, 13,
42, 44]. When $J=\|\cdot\|_{\mathcal{A}}$ is a norm in $\mathbb{R}^{n}$, claim
(i) of Corollary 3.11 is exactly [10, Proposition 2.2] (see Proposition 3.5)
thanks to Proposition 3.8(ii). In this case the Lipschitz constant $L$ of $J$
is $\|\mathbb{I}\|_{\mathcal{A},2}$.

For the case $J=\|\cdot\|_{\ell_{1}}$, Corollary 3.11 returns [19, Theorem
4.7] (see also [13, Proposition 1]) whose proof is less transparent and
involves deriving linear convergence rate of the Bregman divergence of $J$,
together with the characterizations of solution uniqueness to $\ell_{1}$
optimization problems via the so-called restricted injectivity and non-
degenerate source condition.

When $J(x)=\|D^{*}x\|_{\mathcal{A}}$ with $D$ being an $n\times p$ matrix and
$\|\cdot\|_{\mathcal{A}}$ being a norm in $\mathbb{R}^{p}$, the Lipschitz
constant $L$ of $J$ is $\|\mathbb{I}\|_{\mathcal{A},2}\|D^{*}\|$. Corollary
3.11 covers [14, Theorem 2]. Another result in this direction is [44, Theorem
2], which only obtains linear rate for $\|D^{*}(x_{\mu}-x_{0})\|$ with extra
nontrivial assumptions on $D$.

When $J$ is a general convex continuous regularizer as in Corollary 3.11, [39,
42] use the so-called restricted injectivity and non-degenerate source
condition at $x_{0}$ to obtain robust recovery. In our forthcoming Theorem
4.6, we will show that these two conditions are equivalent to $x_{0}$ being a
sharp solution666The authors in [39, 42] have already proved that these two
conditions are sufficient for $x_{0}$ to be a sharp solution.. It means that
Corollary 3.11 is equivalent to [39, Theorem 6.1] or [42, Theorem 2]. However,
our path to proving robust recovery is radically different. On the one hand,
[39, Theorem 6.1] generalizes the proof strategy initiated in [19] and use
decomposability of $J$ and other arguments that heavily rely on convexity of
$J$. On the other hand, Corollary 3.11 provides a direct proof that involve
natural geometrical properties of $J$ around $x_{0}$. Most importantly,
Theorem 3.10 suggests that robust recovery with linear rate occurs without
convexity and reveals the crucial role played by sharpness of the minimizer to
achieve robust recovery with linear rate. Comparing the constants in our
bounds (3.18)-(3.17) and those in [39, 42], those in [39, 42] depend for
instance on a dual certificate and its ”distance” to degeneracy, while ours
depend on the sharpness parameter $c$ which is not trivial to characterize at
first glance. In Theorem 4.6, we will provide an estimation for $c$ via the
so-called Source Identity that can be computed numerically.

###  3.3 Strong minima and robust recovery

A natural question is to whether robust recovery is still possible if the
sharp minima property is replaced by the weaker strong minima property. We
here show that the answer is affirmative, but at the price of a slower rate of
convergence.

######  Theorem 3.12 (Strong minima for robust recovery).

Suppose that $J$ is a non-negative lsc function which satisfies (3.2), and is
Lipschitz continuous around $x_{0}$ with modulus $L$. If $x_{0}$ is the unique
and strong solution to (1.2) with constant $\kappa>0$, then for all $\delta>0$
sufficiently small, the following statements hold:

  1. (i)

Any solution $x_{\delta}$ to problem (1.4) satisfies

$\displaystyle\|x_{\delta}-x_{0}\|\leq
2\left(\frac{1}{\kappa}L\|\Phi^{\dagger}\|\delta+\|\Phi^{\dagger}\|^{2}\delta^{2}\right)^{\frac{1}{2}}.$
(3.24)

  2. (ii)

For any $c_{1}>0$ and $\mu=c_{1}\delta$, any minimizer $x_{\mu}$ to (1.5)
obeys

$\|x_{\mu}-x_{0}\|\leq\sqrt{\dfrac{c_{1}}{(1-c_{1}\kappa\|\Phi^{\dagger}\|^{2}\delta)\kappa}}\left(\dfrac{1}{c_{1}}+L\|\Phi^{\dagger}\|\right)\delta^{\frac{1}{2}}.$
(3.25)

###### Proof.

  1. (i)

Since $x_{0}$ is a strong solution to (1.2) with constant $\kappa>0$, there
exists $\nu>0$ such that

$J(x)-J(x_{0})\geq\frac{\kappa}{2}\|x-x_{0}\|^{2}\quad\text{for all}\quad
x\in\Phi^{-1}y_{0}\cap\mathbb{B}_{\nu}(x_{0}).$ (3.26)

Let $\bar{x}_{\delta}$ be the projection of $x_{\delta}$ onto
$\Phi^{-1}y_{0}$. Since $x_{0}$ is the unique solution to problem (1.2), we
argue as in the proof of Theorem 3.10(i) to show that for all $\delta$ small
enough, one has
$\bar{x}_{\delta},x_{\delta}\in\mathbb{B}_{\min\\{\varepsilon,\nu\\}}(x_{0})$
with $\varepsilon,\nu$ in (3.19) and (3.26). We then have

$\displaystyle L\|\bar{x}_{\delta}-x_{\delta}\|$ $\displaystyle\geq
J(\bar{x}_{\delta})-J(x_{\delta})$ $\displaystyle\text{by \eqref{Lip}},$
$\displaystyle\geq J(\bar{x}_{\delta})-J(x_{0})$ $\displaystyle\text{by
optimality of $x_{0}$},$
$\displaystyle\geq\frac{\kappa}{2}\|\bar{x}_{\delta}-x_{0}\|^{2}$
$\displaystyle\text{by \eqref{Stron}},$
$\displaystyle=\frac{\kappa}{2}\left(\|x_{\delta}-x_{0}\|^{2}-\|\bar{x}_{\delta}-x_{\delta}\|^{2}\right).$
$\displaystyle\text{by \eqref{Pro}}.$

This together with (2.3) again tells us that

$\displaystyle\frac{\kappa}{2}\|x_{\delta}-x_{0}\|^{2}$ $\displaystyle\leq
L\|\bar{x}_{\delta}-x_{\delta}\|+\frac{\kappa}{2}\|\bar{x}_{\delta}-x_{\delta}\|^{2}$
$\displaystyle=L\|\Phi^{\dagger}\Phi(x_{\delta}-x_{0})\|+\frac{\kappa}{2}\|\Phi^{\dagger}\Phi(x_{\delta}-x_{0})\|^{2}$
$\displaystyle\leq L\|\Phi^{\dagger}\|\|\Phi
x_{\delta}-y_{0}\|+\frac{\kappa}{2}\|\Phi^{\dagger}\|^{2}\|\Phi
x_{\delta}-y_{0}\|^{2}$ $\displaystyle\leq
L\|\Phi^{\dagger}\|2\delta+\frac{\kappa}{2}\|\Phi^{\dagger}\|^{2}4\delta^{2},$

which is (3.24).

  2. (ii)

Let $\bar{x}_{\mu}$ be the projection of $x_{\mu}$ to $\Phi^{-1}y_{0}$.
Arguing as above, we infer that for $\delta$ sufficiently small,
$x_{\mu},\bar{x}_{\mu}\in\mathbb{B}_{\min\\{\varepsilon,\nu\\}}(\bar{x})$,
where $\varepsilon,\eta$ are those in (3.19) and (3.26). Set for short
$\alpha=\|\Phi(x_{\mu}-x_{0})\|$. We then have

$\displaystyle J(x_{\mu})-J(x_{0})$
$\displaystyle=J(\bar{x}_{\mu})-J(x_{0})+J(x_{\mu})-J(\bar{x}_{\mu})$
$\displaystyle\geq\frac{\kappa}{2}\|\bar{x}_{\mu}-x_{0}\|^{2}-L\|\bar{x}_{\mu}-x_{\mu}\|$
$\displaystyle\text{by \eqref{Stron} and \eqref{Lip}},$
$\displaystyle=\frac{\kappa}{2}\left(\|x_{\mu}-x_{0}\|^{2}-\|\bar{x}_{\mu}-x_{\mu}\|^{2}\right)-L\|\bar{x}_{\mu}-x_{\mu}\|$
$\displaystyle\text{by \eqref{Pro}},$
$\displaystyle=\frac{\kappa}{2}\|x_{\mu}-x_{0}\|^{2}-\|\Phi^{\dagger}\Phi(x_{\mu}-x_{0})\|^{2}-L\|\Phi^{\dagger}\Phi(x_{\mu}-x_{0})\|$
$\displaystyle\text{by \eqref{Pro}},$
$\displaystyle\geq\frac{\kappa}{2}\left(\|x_{\mu}-x_{0}\|^{2}-\|\Phi^{\dagger}\|^{2}\alpha^{2}\right)-L\|\Phi^{\dagger}\|\alpha.$

Combining this with (3.22), we arrive at

$\frac{\kappa}{2}\left(\|x_{\mu}-x_{0}\|^{2}-\|\Phi^{\dagger}\|^{2}\alpha^{2}\right)-L\|\Phi^{\dagger}\|\alpha\leq\frac{2\alpha\delta-\alpha^{2}}{2\mu}.$

Making $\delta$ smaller if necessary so that
$\mu=c_{1}\delta<\left(\kappa\|\Phi^{\dagger}\|^{2}\right)^{-1}$, we get

$\displaystyle\frac{\kappa}{2}\|x_{\mu}-x_{0}\|^{2}$
$\displaystyle\leq\left(\frac{\delta}{\mu}+L\|\Phi^{\dagger}\|\right)\alpha-\left(\frac{1}{2\mu}-\frac{\kappa}{2}\|\Phi^{\dagger}\|^{2}\right)\alpha^{2}$
$\displaystyle\leq\frac{1}{2}\left(\frac{1}{\mu}-\kappa\|\Phi^{\dagger}\|^{2}\right)^{-1}\left(\frac{\delta}{\mu}+L\|\Phi^{\dagger}\|\right)^{2},$

which is (3.24) after some simple algebra.

∎

When the regularizer $J$ is convex, the Lipschitz property of J around $x_{0}$
is equivalent to the continuity of $J$ at $x_{0}$; see, e.g., [3, Theorem
8.29]. Moreover, the assumption that $x_{0}$ is the unique minimizer of (1.2)
holds trivially when $x_{0}$ is a strong minimizer. We then obtain the
following corollary of Theorem 3.12.

######  Corollary 3.13.

Suppose that $J$ is a convex function that is continuous at $x_{0}$. If
$x_{0}$ is a strong solution to problem (1.2) then, for $\delta$ sufficiently
small, the convergence rate $\mathcal{O}(\delta^{\frac{1}{2}})$ of Theorem
3.12 holds.

######  Remark 3.14.

Observe that unlike sharp minima, even for the convex case, the property of
strong minima is only local. This is the reason we still require $\delta$ to
be small enough in Corollary 3.13. This is in stark contrast to Corollary 3.11
where sharpness is globalized under convexity.

######  Remark 3.15.

A natural and open question is whether the rate
$\mathcal{O}(\delta^{\frac{1}{2}})$ in Theorem 3.12 is optimal under the
strong solution property. Though we do not have a clear answer yet, we believe
that his may depend on the type of regularizer. For the case of Euclidean norm
$J(x)=\|x\|$, we could prove that the rate could be improved to
$\mathcal{O}(\delta)$. We omit the details here for the sake of brevity.

##  4 Nondegeneracy, restricted injectivity and sharp minima

As shown in Proposition 3.8, sharp minima can be characterized via the descent
and critical cones. However, it is not easy to verify them numerically,
especially when the dimension is large777For some operators $\Phi$ drawn from
some appropriate random ensembles, one can show, using , that sample
complexity bounds in [10, 36] are sufficient for sharpness to hold with high
probability.. In this section, we mainly derive quantitative characterizations
for sharp minima to problem (1.2).

Throughout this section, we suppose that $J$ takes the analysis-type form

$J=J_{0}\circ D^{*},$ (4.1)

where $D^{*}:\mathbb{R}^{n}\to\mathbb{R}^{p}$ is linear, and $J_{0}$ is a non-
negative, convex and continuous function. The reason we take this form is
twofold. First, this is in preparation for Section 5 to make the presentation
easier there. Second, though we could derive the decomposability properties
(see shortly) of $J$ from those of $J_{0}$ using the framework in [40], our
analysis in this section will involve a dual multiplier which is not the same
as the one in that paper.

For some linear subspace $V$ of $\mathbb{R}^{n}$, we will use the shorhand
notation $w_{V}=\mbox{\rm P}_{V}w$ for $w\in\mathbb{R}^{n}$ and
$D_{V}=D\mbox{\rm P}_{V}$ for a linear operator $D$.

###  4.1 Subdifferential decomposability

The following definition taken from [40, Definition 3] is instrumental in our
study.

######  Definition 4.1 (Model Tangent Subspace).

Denote the model vector $e$ of $J_{0}$ at
$u_{0}\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}D^{*}x_{0}$ is the
projection of $0$ onto the affine hull of $\partial J_{0}(u_{0})$

$e\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}\mbox{\rm P}_{\mbox{\rm
aff}\,(\partial J_{0}(u_{0}))}(0).$ (4.2)

The model tangent subspace $T$ at $u_{0}$ associated to $J_{0}$ is defined by

$T\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}S^{\perp}\quad\text{where}\quad
S\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}\mbox{\rm aff}\,(\partial
J_{0}(u_{0}))-e.$ (4.3)

Obviously, $e\in T$.

######  Lemma 4.2 (Decomposability, [40, Theorem 1]).

Let $u_{0}\in\mathbb{R}^{n}\setminus\\{0\\}$ and $v_{0}$ be a vector in
$\mbox{\rm ri}\,\partial J_{0}({u_{0}})$. Then

$\partial
J_{0}(u_{0})=\left\\{v\in\mathbb{R}^{n}|\;v_{T}=e,\gamma_{C}(\mbox{\rm
P}_{S}(v-v_{0}))\leq 1\right\\},$ (4.4)

where $C\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}\partial
J_{0}(u_{0})-v_{0}$ and $\gamma_{C}$ is the gauge function of $C$ defined in
(2.7). Moreover $v\in\mbox{\rm ri}\,\partial J_{0}(u_{0})$ if and only if
$v_{T}=e$ and $\gamma_{C}(\mbox{\rm P}_{S}(v-v_{0}))<1$.

We then have the following necessary and sufficient optimality condition for
problem (1.2).

######  Lemma 4.3.

$x_{0}$ is an optimal solution to problem (1.2) with $J$ in (4.1) if and only
if there exists $v\in\mathbb{R}^{p}$ such that

$v_{T}=e,\gamma_{C}(v_{S}-\mbox{\rm P}_{S}v_{0})\leq
1,\enskip\text{and}\enskip Dv\in\mbox{\rm Im}\,\Phi^{*}.$ (4.5)

###### Proof.

Combine (3.6) and Lemma 4.2. ∎

###  4.2 Quantitative characterization of sharp minima

We start by providing a quantitative condition for checking optimality.

######  Proposition 4.4 (Quantitative characterization of optimality).

$x_{0}$ is an optimal solution to problem (1.2) with $J$ in (4.1) if and only
if the following two conditions are satisfied

$\displaystyle
ND_{S}(ND_{S})^{\dagger}ND_{T}e=ND_{T}e\enskip\text{and}\enskip$ (4.6)
$\displaystyle\rho(e)\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\min_{u\in\mbox{\rm
Ker}\,ND_{S}}\gamma_{C}(-(ND_{S})^{\dagger}ND_{T}e-\mbox{\rm
P}_{S}v_{0}+u)\leq 1,$ (4.7)

where $N$ is a matrix satisfying $\mbox{\rm Ker}\,N=\mbox{\rm Im}\,\Phi^{*}$
and $\mbox{\rm Ker}\,N^{*}=\\{0\\}$. The minimum in (4.7) is well-defined and
achieved at some $u\in\mbox{\rm Ker}\,ND_{S}\cap S$.

###### Proof.

Suppose that $x_{0}$ is a solution to (1.2). It follows from Lemma 4.3 that
there exists $v\in\mathbb{R}^{p}$ such that

$0=NDv=N(D_{T}e+D_{S}v_{S})\Longrightarrow ND_{S}v_{S}=-ND_{T}e.$

This is equivalent, via (2.2), to

$ND_{S}(ND_{S})^{\dagger}ND_{T}e=ND_{T}e\enskip\text{and}\enskip
v_{S}\in-(ND_{S})^{\dagger}ND_{T}e+\mbox{\rm Ker}\,ND_{S}.$

This tells us, using again Lemma 4.3, that

$\rho(e)\leq\gamma_{C}(v_{S}-\mbox{\rm P}_{S}v_{0})\leq 1,$

which proves the necessary part.

Conversely, suppose that both (4.6) and (4.7) hold. Let $u^{\star}\in\mbox{\rm
Ker}\,ND_{S}$ be a minimizer to (4.7). Since $\mbox{\rm dom}\,\gamma_{C}=S$
and $\gamma_{C}$ is coercive on $S$ by [40, Propopsition 2], $u^{\star}$
exists and belongs to $S$. Define
$\bar{u}\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}-(ND_{S})^{\dagger}NDe+u^{\star}$. This vector verifies

$\gamma_{C}(\bar{u}-\mbox{\rm P}_{S}v_{0})=\rho(e)\leq 1.$ (4.8)

Since $0\in\mbox{\rm ri}\,C\subset C$, and in view of (4.8), we infer that
$\bar{u}-\mbox{\rm P}_{S}v_{0}\in C\subset S$. This implies $\bar{u}\in S$.
Note further from (4.6) that

$ND(e+\bar{u})=ND(e+\mbox{\rm
P}_{S}\bar{u})=ND_{T}e-ND_{S}(ND_{S})^{\dagger}ND_{T}e=0,$

which means $D(e+\bar{u})\in\mbox{\rm Im}\,\Phi^{*}$. Altogether, the vector
$e+\bar{u}$ verifies the properties (4.5) in Lemma 4.3 whence we deduce that
$x_{0}$ is an optimal solution to problem (1.2). The proof is complete. ∎

Equation (4.6) means that the linear system

$ND_{S}v=-ND_{T}e$

is consistent. When $D=\mathbb{I}$, Lemma 4.3 and Proposition 4.4 tell us that
conditions (4.6)-(4.7) are equivalent to the so-called Source Condition well-
known in inverse problems (see [34, 19, 39, 42] and referencs therein). We
call $\rho(e)$ the Source Coefficient. Under condition (4.6), $\rho(e)$ is
indeed the optimal value to the following problem

$\min_{v\in\mathbb{R}^{p}}\gamma_{C}(v-\mbox{\rm
P}_{S}v_{0})\quad\text{subject to}\quad ND_{S}v=-ND_{T}e,$

which is equivalent to the following convex optimization problem

$\min_{v\in\mathbb{R}^{p}}\gamma_{C}(v-\mbox{\rm
P}_{S}v_{0})\quad\text{subject to}\quad NDv=-ND_{T}e\enskip\text{and}\enskip
v\in S.$ (4.9)

######  Remark 4.5 (Computing the Source Coefficient $\rho(e)$ for
decomposable norms).

One important class of regularizers is $J(x)=\|D^{*}x\|_{\mathcal{A}}$, where
$J_{0}(\cdot)=\|\cdot\|_{\mathcal{A}}$ is a decomposable norm in
$\mathbb{R}^{p}$. The class of decomposable norms is introduced in [26, 7] and
was generalized in [40] (coined strong gauges there). This class includes the
$\ell_{1}$ norm, the $\ell_{1}/\ell_{2}$ norm, the nuclear norm but not the
$\ell_{\infty}$ norm. According to [7], a norm $\|\cdot\|_{\mathcal{A}}$ is
called decomposable at $u_{0}\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}D^{*}x_{0}$ if there is a subspace $V\subset\mathbb{R}^{p}$ and a
vector $e_{0}\in V$ such that

$\partial\|u_{0}\|_{\mathcal{A}}=\left\\{v\in\mathbb{R}^{p}|\;v_{V}=e_{0}\enskip\text{and}\enskip\|v_{V^{\perp}}\|^{*}_{\mathcal{A}}\leq
1\right\\},$ (4.10)

where $\|\cdot\|^{*}_{\mathcal{A}}$ is the dual norm to
$\|\cdot\|_{\mathcal{A}}$. From [40, Proposition 7], it follows that (4.10)
complies with Lemma 4.2 by taking $V=T=S^{\perp}=\left(\mbox{\rm
aff}\,(\partial J_{0}(u_{0}))-e\right)^{\perp}$, $v_{0}=e\in\mbox{\rm
ri}\,\partial\|u_{0}\|_{\mathcal{A}}$, in which case
$C=\partial\|u_{0}\|_{\mathcal{A}}-v_{0}=\left\\{v\in
S|\;\|v\|^{*}_{\mathcal{A}}\leq 1\right\\}$ and thus for any $v\in S$

$\gamma_{C}(v)=\|v\|^{*}_{\mathcal{A}}.$

Hence, problem (4.9) simplifies to

$\min_{v\in\mathbb{R}^{p}}\|v\|^{*}_{\mathcal{A}}\quad\text{subject to}\quad
NDv=-ND_{T}e\enskip\text{and}\enskip v\in S.$ (4.11)

The matrix $N$ can be chosen from the singular value decomposition of
$\Phi=U\Sigma V^{*}$ as $N=V_{G}^{*}$, where $V_{G}$ is the submatrix of $V$
whose columns are indexed by $G=\\{r+1,r+2,\ldots,n\\}$ with $r={\rm
rank}\,\Phi$. This idea is slightly inspired from [25, 44] for the case where
$\|\cdot\|_{\mathcal{A}}$ is the $\ell_{1}$ norm. We will return in Section 5
to discussing further the use of the Source Coefficient to classify sharp and
strong/unique solutions for the group-sparsity regularization.

We are now in position to state the main result of this section, which
provides equivalent characterizations of sharp minima.

######  Theorem 4.6 (Characterizations of sharp solutions).

Consider $J$ in (4.1). The following statements are equivalent:

  1. (i)

$x_{0}$ is a sharp solution to problem (1.2).

  2. (ii)

The following Restricted Injectivity holds at $x_{0}$

$\mbox{\rm Ker}\,\Phi\cap\mbox{\rm Ker}\,D^{*}_{S}=\\{0\\}$ (4.12)

and the Source Coefficient $\rho(e)<1$.

  3. (iii)

The Restricted Injectivity (4.12) holds and the Nondegenerate Source Condition
is satisfied at $x_{0}$ in the sense that

$\exists v\in\mathbb{R}^{p}\quad\text{such that}\quad Dv\in\mbox{\rm
Im}\,\Phi^{*}\enskip\text{and}\enskip v\in\mbox{\rm ri}\,\partial
J_{0}(x_{0}).$ (4.13)

Moreover, the sharpness constant $c$ at $x_{0}$ can be as large as

$c=(1-\rho(e))sc_{1}>0\quad\text{with}\quad
c_{1}\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}\min_{w\in\mbox{\rm
Ker}\,\Phi\cap\mathbb{S}^{n-1}}\|D^{*}_{S}w\|>0$ (4.14)

and $s>0$ satisfying $\mathbb{B}_{s}(0)\cap S\subset C$.

###### Proof.

[(i)$\Rightarrow$(ii)]. Suppose that $x_{0}$ is a sharp solution to (1.2).
From Lemma 2.4(i), this is equivalent to the existence of some $c>0$ such that
$d\Psi(x_{0})(w)\geq c\|w\|$ for all $w\in\mathbb{R}^{n}$. From (3.6) and
Lemma 4.2, we have

$\displaystyle d\Psi(x_{0})(w)$ $\displaystyle=dJ(x_{0})(w)+\iota_{\mbox{\rm
Ker}\,\Phi}(w)$ (4.15)
$\displaystyle=dJ_{0}(D^{*}x_{0})(D^{*}w)+\iota_{\mbox{\rm Ker}\,\Phi}(w)$
$\displaystyle=\sigma_{\partial J_{0}(D^{*}x_{0})}(D^{*}w)+\iota_{\mbox{\rm
Ker}\,\Phi}(w)$ $\displaystyle=\sup\left\\{\left\langle
v,\,D^{*}w\right\rangle|\;v_{T}=e,v_{S}\in\mbox{\rm
P}_{S}v_{0}+C\right\\}+\iota_{\mbox{\rm Ker}\,\Phi}(w)$
$\displaystyle=\left\langle e,\,D_{T}^{*}w\right\rangle+\left\langle\mbox{\rm
P}_{S}v_{0},\,D_{S}^{*}w\right\rangle+\sup_{z\in C}\left\langle
z,\,D_{S}^{*}w\right\rangle+\iota_{\mbox{\rm Ker}\,\Phi}(w)$
$\displaystyle=\left\langle e,\,D_{T}^{*}w\right\rangle+\left\langle\mbox{\rm
P}_{S}v_{0},\,D_{S}^{*}w\right\rangle+\sigma_{C}(D_{S}^{*}w)+\iota_{\mbox{\rm
Ker}\,\Phi}(w).$

For any $w=N^{*}u\in\mbox{\rm Ker}\,\Phi$, we obtain from (4.15), the
inequality $d\Psi(x_{0})(w)\geq c\|w\|$, and (4.6) that

$\displaystyle\sigma_{C}(D^{*}_{S}w)-c\|w\|$ $\displaystyle\geq-\left\langle
e,\,D^{*}_{T}N^{*}u\right\rangle-\left\langle\mbox{\rm
P}_{S}v_{0},\,D^{*}_{S}N^{*}u\right\rangle$ (4.16)
$\displaystyle=-\left\langle ND_{T}e,\,u\right\rangle-\left\langle\mbox{\rm
P}_{S}v_{0},\,D^{*}_{S}N^{*}u\right\rangle$ $\displaystyle=-\left\langle
ND_{S}(ND_{S})^{\dagger}ND_{T}e,\,u\right\rangle-\left\langle\mbox{\rm
P}_{S}v_{0},\,D^{*}_{S}N^{*}u\right\rangle$
$\displaystyle=-\left\langle(ND_{S})^{\dagger}ND_{T}e+\mbox{\rm
P}_{S}v_{0},\,D^{*}_{S}w\right\rangle.$

If $w\in\mbox{\rm Ker}\,\Phi\cap\mbox{\rm Ker}\,D^{*}_{S}$, we deduce from
(4.16) that $-c\|w\|\geq 0$, which means $w=0$. Thus the Restricted
Injectivity (4.12) is satisfied.

Moreover, as $J_{0}$ is a continuous convex function, $\partial
J_{0}(D^{*}x_{0})$ is compact, and so is $C$, whence it follows that

$\sigma_{C}(D_{S}^{*}w)\leq r\|D^{*}_{S}w\|\leq
r\|D^{*}_{S}\|\|w\|\quad\text{with}\quad
r\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}\max\left\\{\|z\||\;z\in
C\right\\}.$

Combining the latter with (4.16) tells us that for any $v\in\mbox{\rm
Im}\,D^{*}_{S}N^{*}$,

$-\left\langle(ND_{S})^{\dagger}ND_{T}e+\mbox{\rm
P}_{S}v_{0},\,v\right\rangle\leq\left(1-\frac{c}{r\|D^{*}_{S}\|}\right)\sigma_{C}(v).$
(4.17)

Let $C^{\circ}$ be the polar set of $C$ as defined in (2.9), and set
$K\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}C^{\circ}\cap S$. $K$ is a
non-empty closed convex set. Since $0\in\mbox{\rm ri}\,C$, there exists $s>0$
such that and $\mathbb{B}_{s}(0)\cap S\subset C$. For any $v\in
K\setminus\\{0\\}$, we have $s\frac{v}{\|v\|}\in\mathbb{B}_{s}(0)\cap S$ and
thus, using (2.9), $\left\langle
v,\,s\frac{v}{\|v\|}\right\rangle\leq\sigma_{\mathbb{B}_{s}(0)\cap
S}(v)\leq\sigma_{C}(v)\leq 1$ since $v\in C^{\circ}$. It follows that
$\|v\|\leq\frac{1}{s}$. Hence, $K$ is a compact set.

Let us bound from below the right hand side of (4.17). First, we have by
Fenchel-Moreau theorem and the minimax theorem [30, Corollary 37.3.2] (since
$K$ is compact), that

$\displaystyle\max_{v\in K\cap\mbox{\rm
Im}\,D^{*}_{S}N^{*}}\left\langle-(ND_{S})^{\dagger}ND_{T}e-\mbox{\rm
P}_{S}v_{0},\,v\right\rangle$ $\displaystyle=\max_{v\in
K}\left(\left\langle-(ND_{S})^{\dagger}ND_{T}e-\mbox{\rm
P}_{S}v_{0},\,v\right\rangle-\iota_{\mbox{\rm Im}\,D^{*}_{S}N^{*}}(v)\right)$
(4.18) $\displaystyle=\max_{v\in K}\inf_{z\in\mbox{\rm
Ker}\,ND_{S}}\left\langle-(ND_{S})^{\dagger}ND_{T}e-\mbox{\rm
P}_{S}v_{0}+z,\,v\right\rangle$ $\displaystyle=\min_{z\in\mbox{\rm
Ker}\,ND_{S}}\max_{v\in K}\left\langle-(ND_{S})^{\dagger}ND_{T}e-\mbox{\rm
P}_{S}v_{0}+z,\,v\right\rangle$ $\displaystyle=\min_{z\in\mbox{\rm
Ker}\,ND_{S}}\sigma_{K}(-(ND_{S})^{\dagger}ND_{T}e-\mbox{\rm P}_{S}v_{0}+z).$

On the other hand, for any $v\in K\cap\mbox{\rm Im}\,D^{*}_{S}N^{*}\subset
C^{\circ}$, we have $\sigma_{C}(v)\leq 1$ (see (2.9)). Let $v^{\star}\in
K\cap\mbox{\rm Im}\,D^{*}_{S}N^{*}$ be a maximizer of the left hand side of
(4.18). We then have from (4.17) and (4.18) that

$\displaystyle 0\leq\min_{z\in\mbox{\rm
Ker}\,ND_{S}}\sigma_{K}(-(ND_{S})^{\dagger}ND_{T}e-\mbox{\rm P}_{S}v_{0}+z)$
$\displaystyle=-\left\langle(ND_{S})^{\dagger}ND_{T}e+\mbox{\rm
P}_{S}v_{0},\,v^{\star}\right\rangle$ (4.19)
$\displaystyle\leq\left(1-\frac{c}{r\|D^{*}_{S}\|}\right)\sigma_{C}(v^{\star})\leq
1-\frac{c}{r\|D^{*}_{S}\|}<1.$

It remains now to compute $\sigma_{K}$. We have from Fenchel-Moreau theorem,
[30, Corollary 16.4.1], standard conjugacy calculus and (2.10), that

$\displaystyle\sigma_{K}=\left(\iota_{C^{\circ}}+\iota_{S}\right)^{*}=\mbox{\rm
cl}\,\left(\inf_{\eta\in\mathbb{R}^{p}}\sigma_{C^{\circ}}(\cdot+\eta)+\sigma_{S}(\eta)\right)=\mbox{\rm
cl}\,\left(\inf_{\eta\in T}\sigma_{C^{\circ}}(\cdot+\eta)\right)=\mbox{\rm
cl}\,\left(\inf_{\eta\in T}\gamma_{C}(\cdot+\eta)\right).$

Since $\mbox{\rm dom}\,\gamma_{C}=S$ by [40, Propopsition 2], we have for any
$z\in\mathbb{R}^{p}$ that

$\inf_{\eta\in T}\gamma_{C}(z+\eta)=\inf_{\eta\in T}\gamma_{C}(\mbox{\rm
P}_{S}z+\eta)=\gamma_{C}(\mbox{\rm P}_{S}z).$

Thus, the closure operation can be omitted above to get for any $z\in S$

$\sigma_{K}(z)=\gamma_{C}(z).$

Inserting this into (4.19), we get (ii), after observing that $\mbox{\rm
Im}\,(ND_{S})^{\dagger}=\mbox{\rm Im}\,D_{S}^{*}N^{*}\subset S$ and that the
minimum in $\rho(e)$ is achieved on $S$ (see Proposition 4.4).

[(ii)$\Rightarrow$(iii)]. Let $u^{\star}\in S$ be a solution of the
minimization problem in (4.7), denote $\bar{u}=-(ND_{S})^{\dagger}NDe+u^{*}\in
S$ and $\bar{v}=e+\bar{u}$. We have $\bar{v}_{T}=e$ and, since (ii) is
satisfied, $\gamma_{C}(\bar{v}_{S}-\mbox{\rm P}_{S}v_{0})<1$. This is
equivalent to $\bar{v}\in\mbox{\rm ri}\,\partial J(x_{0})$ thanks to the last
claim of Lemma 4.2. It remains to show that $D\bar{v}\in\mbox{\rm
Im}\,\Phi^{*}$. As the Restricted Injectivity condition (4.12) holds,

$ND_{S}(ND_{S})^{\dagger}ND_{T}e=ND_{S}(ND_{S})^{*}(ND_{S}(ND_{S})^{*})^{-1}ND_{T}e=ND_{T}e,$

which verifies (4.6). (4.7) is also verified as shown above and we can then
argue as in the proof of the sufficient part in Proposition 4.4 to deduce that
$D\bar{v}\in\mbox{\rm Im}\,\Phi^{*}$.

[(iii)$\Rightarrow$(i)]. Suppose that the Restricted Injectivity (4.12) holds
at $x_{0}$ and there exists $Dv\in\mbox{\rm Im}\,\Phi^{*}$ and $v\in\mbox{\rm
ri}\,\partial J(x_{0})$. Hence, $v_{T}=e$ and $\gamma_{C}(\mbox{\rm
P}_{S}(v-v_{0}))<1$ thanks to Lemma 4.2. Thus, for any $w\in\mbox{\rm
Ker}\,\Phi$, we get from (4.15) that

$\displaystyle\begin{array}[]{ll}d\Psi(x_{0})(w)&=\left\langle
e,\,D^{*}w\right\rangle+\left\langle\mbox{\rm
P}_{S}v_{0},\,D^{*}_{S}w\right\rangle+\sigma_{C}(D^{*}_{S}w)\\\ &=\left\langle
v-\mbox{\rm P}_{S}v,\,D^{*}w\right\rangle+\left\langle\mbox{\rm
P}_{S}v_{0},\,D^{*}_{S}w\right\rangle+\sigma_{C}(D^{*}_{S}w)\\\
&=\left\langle-\mbox{\rm P}_{S}v,\,D^{*}w\right\rangle+\left\langle\mbox{\rm
P}_{S}v_{0},\,D^{*}_{S}w\right\rangle+\sigma_{C}(D^{*}_{S}w)\\\
&=\left\langle-\mbox{\rm
P}_{S}(v-v_{0}),\,D^{*}_{S}w\right\rangle+\sigma_{C}(\mbox{\rm P}_{S}w)\\\
&\geq-\sigma_{C}(D^{*}_{S}w)\gamma_{C}(\mbox{\rm
P}_{S}(v-v_{0}))+\sigma_{C}(D^{*}_{S}w)\\\ &=\Big{(}1-\gamma_{C}(\mbox{\rm
P}_{S}(v-v_{0}))\Big{)}\sigma_{C}(D^{*}_{S}w),\end{array}$ (4.26)

where in the last two inequalities, we used the duality inequality on
$\mbox{\rm dom}\,\sigma_{C}\times\mbox{\rm
dom}\,\gamma_{C}=\mathbb{R}^{p}\times\mbox{\rm dom}\,S$. Recall that
$0\in\mbox{\rm ri}\,C$ and $\mathbb{B}_{s}(0)\cap S\subset C$ for some $s>0$.
As $D^{*}_{S}w\in S$, we have

$\sigma_{C}(D^{*}_{S}w)\geq\left\langle
D^{*}_{S}w,\,s\frac{D^{*}_{S}w}{\|D^{*}_{S}w\|}\right\rangle=s\|D^{*}_{S}w\|\geq
sc_{1}\|w\|,$

where $c_{1}\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\min\left\\{\|D^{*}_{S}w\||\;w\in\mathbb{S}^{n-1}\cap\mbox{\rm
Ker}\,\Phi\right\\}$, and $c_{1}>0$ by virtue of the Restricted Injectivity
(4.12). We derive from (4.26) that

$d\Psi(x_{0})(w)\geq\Big{(}1-\gamma_{C}(\mbox{\rm
P}_{S}(v-v_{0}))\Big{)}sc_{1}\|w\|\quad\text{for all}\quad w\in\mbox{\rm
Ker}\,\Phi,$

which verifies (i) by Lemma 2.4. Recall that $Dv\in\mbox{\rm Im}\,\Phi^{*}$
and $v_{T}=e$, and thus $NDv_{S}=ND_{T}e$, which in turn shows that the vector
$v_{S}$ obeys the constraint in (4.9), and thus
$\rho(e)\leq\gamma_{C}(\mbox{\rm P}_{S}(v-v_{0}))<1$. The sharpness constant
of $\Psi$ can then be as large as devised in (4.14). The proof is complete. ∎

######  Corollary 4.7 (Sufficient condition for sharp solution).

If the Restricted Injectivity holds at $x_{0}$ and the following condition

$\tau(e)\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\gamma_{C}(-(ND_{S})^{\dagger}NDe-\mbox{\rm P}_{S}v_{0})<1$ (4.27)

is satisfied, then $x_{0}$ is a sharp solution to problem (1.2).

###### Proof.

It is easy to see that $\tau(e)\geq\rho(e)$. The result follows from Theorem
4.6. ∎

######  Remark 4.8.

The Restricted Injectivity (4.12) was proposed in [14, 39, 40, 42]. It also
has tracks in some special cases, e.g., for the $\ell_{1}$ norm problems [16,
17, 19, 25, 41, 45, 44], $\ell_{1}/\ell_{2}$ norm problems [18, 21], and
nuclear norm problems [10, 8, 7]. The form of the Nondegenerate Source
Condition in Theorem 4.6 appears also in [39, 40, 42]. It generalizes the
condition in [19] for the $\ell_{1}$ problem, which actually occurred earlier
in [9]. The combination of Restricted Injectivity and Nondegenerate Source
Condition in the above result are proved in [39, Theorem 5.3] as sufficient
conditions for solution uniqueness to problem (1.2), but they are not
necessary in general. By revisiting Example 3.9, we see that $x_{0}$ is a
unique solution to problem (3.16) but the Nondegenerate Source Condition is
not satisfied. Indeed, the only vector $v\in\mathbb{R}^{2}$ satisfying
$\Phi^{*}v=(v_{1}+v_{2},v_{1},-v_{2})^{\top}\in\partial
J(x_{0})=\\{(0,1)\\}\times[-1,1]$ is $v=(1,-1)$, but
$\Phi^{*}v=(0,1,1)\notin\mbox{\rm ri}\,\partial J(x_{0})$.

Theorem 4.6 strengthens [40, Corollary 1] by showing Restricted Injectivity
and Nondegenerate Source Condition are necessary and sufficient for sharp
minima. In the case of $\ell_{1}$ problem, out result recovers part of [44,
Theorem 2.1] that gives a characterization for solution uniqueness, which is
equivalent to sharp minima in this framework. Some other characterizations are
also studied recently in [17, 24] by exploiting polyhedral structures. It is
worth emphasizing that our result does not need polyhedrality. Our proof
mainly relies on the well-known first-order condition in Lemma 2.4 for sharp
minima and the subdifferential decomposiability (4.4). Theorem 4.6 also covers
many results about solution uniqueness in [10, 8, 7, 9, 16, 18, 17, 19, 21,
25, 33, 41, 37, 38, 45, 44].

######  Remark 4.9.

The idea of using first-order analysis to study solution uniqueness to
regularized optimization problems is not new as discussed above. For instance,
the Null Space Property has been shown to ensure solution uniqueness for
$\ell_{1}$ regularization [12, 25]. A generalization of this condition beyond
the $\ell_{1}$ norm, coined Strong Null Space Property, was proposed in [14,
39, 40]. This property reads

$-\langle e,D_{T}^{*}w\rangle-\langle\mbox{\rm
P}_{S}v_{0},D^{*}_{S}w\rangle<\sigma_{C}(D^{*}_{S}w)\quad\text{for all}\quad
w\in\mbox{\rm Ker}\,\Phi\setminus\\{0\\}.$ (4.28)

It is immediate to see from (4.16) that sharpness at $x_{0}$ entails (4.28).

#### The case of analysis $\ell_{1}$

When $\|\cdot\|_{\mathcal{A}}=\|\cdot\|_{1}$, the model vector $e$ in (4.2) is
indeed $(\mbox{\rm sign}\,(D_{I}^{*}x_{0}),0_{K})$, where
$I\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}\mbox{\rm
supp}\,(D^{*}x_{0})\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\left\\{i\in\\{1,2,\ldots,p\\}|\;(D^{*}x_{0})_{i}\neq 0\right\\}$,
$K\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}\\{1,\ldots,p\\}\setminus
I$, and $D_{I}$ is the submatrix of $D$ with column indices $I$. In his case,
inequality (4.27) takes the form

${\tau}(\mbox{\rm sign}\,(D^{*}_{I}x_{0}))=\|(ND_{K})^{\dagger}ND_{I}\mbox{\rm
sign}\,(D^{*}_{I}x_{0})\|_{\infty}<1,$

which is called the Analysis Exact Recovery Condition in [25]. Another
criterion used in [41] to check solution uniqueness for $\ell_{1}$ problem is
the so-called Analysis Identifiability Criterion at $\mbox{\rm
sign}\,(D^{*}_{I}x_{0})$ denoted by

${\bf IC}(\mbox{\rm
sign}\,(D^{*}_{I}x_{0}))\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\min_{v\in\mbox{\rm
Ker}\,D_{J}}\|D_{K}^{\dagger}(\Phi^{*}(\Phi^{\dagger}_{U})^{*}U^{*}-\mathbb{I})D_{I}\mbox{\rm
sign}\,(D^{*}_{I}x_{0})-v\|_{\infty}<1,$ (4.29)

where $U$ is basis of $\mbox{\rm Ker}\,D_{J}^{*}$ and
$\Phi_{U}\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}\Phi U$. This
condition reduces to the synthesis one introduced in [16] in the case of
$D^{*}=\mathbb{I}$ while ${\tau}(\mbox{\rm sign}\,(D^{*}_{I}x_{0}))$ does not.
As discussed in [25, 41], $\tau(\mbox{\rm sign}\,(D^{*}_{I}x_{0}))$ and ${\bf
IC}(\mbox{\rm sign}\,(D^{*}_{I}x_{0}))$ are different and no one implies the
other even for the case $D=\mathbb{I}$.

For our general framework with $J$ as in (4.1), the Analysis Identifiability
Criterion is satisfied at $x_{0}$ if

${\bf IC}(e)\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\min_{u\in\mbox{\rm
Ker}\,D_{S}}\gamma_{C}(D_{S}^{\dagger}(\Phi^{*}(\Phi^{\dagger}_{U})^{*}U^{*}-\mathbb{I})D_{T}e-\mbox{\rm
P}_{S}v_{0}+u)<1,$ (4.30)

where $U$ is a matrix whose columns form a basis of $\mbox{\rm
Ker}\,D^{*}_{S}$ and $\Phi_{U}\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\Phi U.$

######  Proposition 4.10.

If the Restricted Injectivity (4.12) holds at $x_{0}$ then $\rho(e)\leq{\bf
IC}(e)$. Consequently, if the Analysis Identifiability Criterion holds at
$x_{0}$, then $x_{0}$ is a sharp solution to (1.2).

###### Proof.

(4.12) means that $\mbox{\rm Ker}\,\Phi_{U}=\\{0\\}$ and
$\Phi_{U}^{\dagger}=(\Phi_{U}^{*}\Phi_{U})^{-1}\Phi_{U}^{*}$. Let
$\bar{u}\in\mbox{\rm Ker}\,D_{S}$ be a minimizer of problem (4.30), and define

$\bar{v}\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}D_{S}^{\dagger}(\Phi^{*}(\Phi^{\dagger}_{U})^{*}U^{*}-\mathbb{I})D_{T}e+\bar{u}\quad\mbox{with}\quad\gamma_{C}(\bar{v}-\mbox{\rm
P}_{S}v_{0})={\bf IC}(e).$

Note that

$U^{*}(\Phi^{*}(\Phi^{\dagger}_{U})^{*}U^{*}-\mathbb{I})D_{T}e=(\Phi_{U}^{*}\Phi_{U}(\Phi_{U}^{*}\Phi_{U})^{-1}U^{*}-U^{*})D_{T}e=0.$

It follows that
$(\Phi^{*}(\Phi^{\dagger}_{U})^{*}U^{*}-\mathbb{I})D_{T}e\in\mbox{\rm
Im}\,D_{S},$ which implies that
$D_{S}\bar{v}=(\Phi^{*}(\Phi^{\dagger}_{U})^{*}U^{*}-\mathbb{I})D_{T}e$ by
(2.2). Hence we have

$ND_{S}\bar{v}=(N\Phi^{*}(\Phi^{\dagger}_{U})^{*}U^{*}-N)D_{T}e=-ND_{T}e,$
(4.31)

which implies that $\bar{v}\in-(ND_{S})^{\dagger}ND_{T}e+\mbox{\rm
Ker}\,ND_{S}$ and thus $\rho(e)\leq\gamma_{C}(\bar{v}-\mbox{\rm
P}_{S}v_{0})={\bf IC}(e)$. When the Analysis Identifiability Criterion is
satisfied at $x_{0}$, we have $\rho(e)\leq{\bf IC}(e)<1$ and thus $x_{0}$ is a
sharp solution to (1.2) due to Theorem 4.6. The proof is complete. ∎

In plain words, Proposition 4.10 tells us that $\rho(e)<1$ is weaker than the
Analysis Identifiability Criterion (4.30). In turn Theorem 4.6 is stronger
than [41, Theorem 2] for the analysis $\ell_{1}$ problem. It also covers the
[39, Proposition 5.7]. For the analysis $\ell_{1}$ problem, [44] provides an
example where $\rho(\mbox{\rm sign}\,(D^{*}_{I}x_{0}))$ is strictly smaller
than both $\tau(\mbox{\rm sign}\,(D^{*}_{I}x_{0}))$ and ${\bf IC}(\mbox{\rm
sign}\,(D^{*}_{I}x_{0}))$.

###  4.3 Robust recovery with analysis decomposable priors

The following result proves robust recovery with linear rate under Restricted
Injectivity and Nondegenerate Source Condition.

######  Corollary 4.11 (Robust recovery of decomposable norm minimization).

Suppose that $J_{0}$ is a nonegative continuous convex function satisfying

$(D^{*})^{-1}(\mbox{\rm Ker}\,(J_{0})_{\infty})\cap\mbox{\rm
Ker}\,\Phi=\\{0\\}.$ (4.32)

If (4.12)-(4.13) hold at $x_{0}$, we have linear convergence rate for robust
recovery as in (3.17) and (3.18).

###### Proof.

From [2, Proposition 2.6.3] $J_{\infty}(w)=(J_{0})_{\infty}(D^{*}w)$ for any
$w\in\mathbb{R}^{n}$. Hence, condition (4.32) is exactly (3.2). We obtain the
claim by combining Theorem 4.6 and Corollary 3.11. ∎

The constant in $\mathcal{O}(\delta)$ can be made explicit. In particular the
sharpness constant is given by (4.14). This reveals that the ”distance” to
nondegeneracy is naturally captured by the sharpness constant, which plays a
crucial role. Thus, the less degenerate, the more robust is the recovery.

Corollary 4.11 covers parts of [14, Theorem 2] (see also [39, 42]), [19,
Theorem 4.2], and [44, Theorem 2] for the case of (analysis or synthesis)
$\ell_{1}$ minimization problems. When $D^{*}=\mathbb{I}$ and
$J_{0}(x)=\|x\|_{\mathcal{A}}$, it also covers the results in [10] about
robust recovery for the constrained problem (1.4).

###  4.4 Connections between unique/sharp/strong solutions in the noiseless
case

When there is noise in observation (1.3), problem (1.5) is usually used to
recover the original signal $x_{0}$. Solution uniqueness to (1.5) is
especially important for exact recovery [16, 41]. We show next that Restricted
Injectivity and Nondegenerate Source Condition are sufficient for strong
minima to problem (1.5), and they become necessary for the $\ell_{1}$ problem.
This result is true for a larger class of regularized problems taking the form

$\min_{x\in\mathbb{R}^{n}}\quad\Theta(x)\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}f(\Phi x)+\mu J(x),$ (4.33)

where $\mu$ is a positive parameter and the loss function
$f:\mathbb{R}^{m}\to\overline{\mathbb{R}}$ is an extended real-valued convex
function satisfying the following two conditions:

  1. (A)

$f$ is twice continuously differentiable in $\mbox{\rm int}\,(\mbox{\rm
dom}\,f)$.

  2. (B)

$\nabla f^{2}(x)$ is positive definite for all $x\in\mbox{\rm int}\,(\mbox{\rm
dom}\,f)$, i.e., $f$ is strictly convex in the interior of its domain.

In (1.5), the function $f$ is $\frac{1}{2}\|\cdot-y\|^{2}$ which certainly
satisfies the above two conditions. Moreover, the standing assumptions (A) and
(B) for $f$ cover the important case of the Kullback-Leiber divergence:

$\displaystyle f_{\rm
KL}(z)=\left\\{\begin{array}[]{ll}\displaystyle\sum_{i=1}^{m}y_{i}\log\dfrac{y_{i}}{z_{i}}+z_{i}-y_{i}&\mbox{if}\quad
z\in\mathbb{R}^{m}_{++}\\\ +\infty&\mbox{if}\quad
z\in\mathbb{R}^{m}_{+}\setminus\mathbb{R}^{m}_{++},\end{array}\right.$ (4.36)

where $y\in\mathbb{R}^{m}_{+}$ and $0\log 0=0$. This offers a natural way to
measure of similarity of two nonnegative vectors (e.g., two discrete
distributions) and is broadly used in statistical/machine learning and signal
processing.

In the following result, we provide the connections between
unique/sharp/strong solutions for the two problems (1.2) and (4.33). Part (i)
of this result could be obtained from [24, Proposition 3.2], but we still give
a short proof as our assumptions on $f$ are slightly different, e.g., $f$ may
not have full domain.

######  Proposition 4.12 (Unique/sharp/strong solutions for problems (1.2) and
(4.33)).

Suppose that $\bar{x}$ is an optimal solution to problem (4.33) and
$\Phi\bar{x}\in\mbox{\rm int}\,(\mbox{\rm dom}\,f)$. Then $\bar{x}$ is a
solution to problem (1.2) with $x_{0}=\bar{x}$. Moreover, the following
statements hold:

  1. (i)

$\bar{x}$ is the unique solution to (4.33) if and only if it is the unique
solution to (1.2).

  2. (ii)

If $\bar{x}$ is a sharp solution to (1.2) then it is a strong solution to
problem (4.33).

  3. (iii)

If $\bar{x}$ is a strong solution to (4.33) then it is also a strong solution
to (1.2).

###### Proof.

For any $x\in\Phi^{-1}(\Phi\bar{x})$, we have

$f(\Phi\bar{x})+\mu J(x)=f(\Phi x)+\mu J(x)\geq f(\Phi\bar{x})+\mu
J(\bar{x}).$ (4.37)

It follows that $\bar{x}$ is a solution to problem (1.2) with
$y_{0}=\Phi\bar{x}$.

  1. (i)

If $\bar{x}$ is the unique solution to problem (4.33), we have the strict
inequality in (4.37) provided that $x\neq\bar{x}$, which shows that $\bar{x}$
is also the unique solution to problem (1.2). Assume now that $\bar{x}$ is the
unique solution to (1.2). By contradiction, suppose that $\bar{x}$ is not the
unique solution to (4.33). Since $\mbox{\rm Argmin}\,(\Theta)$ is convex and
$\Phi^{-1}(\mbox{\rm int}\,(\mbox{\rm dom}\,f))$ is an open set containing
$\bar{x}$, there exists $r>0$ such that
$\mathbb{B}_{r}(\bar{x})\subset\Phi^{-1}(\mbox{\rm int}\,(\mbox{\rm dom}\,f))$
and $\mathbb{B}_{r}(\bar{x})\cap\mbox{\rm Argmin}\,(\Theta)\neq\emptyset$,
while the later is not the singleton $\\{\bar{x}\\}$. Choose
$\widehat{x}\in\mathbb{B}_{r}(\bar{x})$ with $\widehat{x}\neq\bar{x}$. We have
$-\Phi^{*}\nabla f(\Phi\widehat{x})\in\partial J(\widehat{x})$ and
$-\Phi^{*}\nabla f(\Phi\bar{x})\in\partial J(\bar{x})$. The monotonicity of
the subdifferential tells us that

$-\left\langle\nabla f(\Phi\widehat{x})-\nabla
f(\Phi\bar{x}),\,\Phi\widehat{x}-\Phi\bar{x}\right\rangle=-\left\langle\Phi^{*}\nabla
f(\Phi\widehat{x})-\Phi^{*}\nabla
f(\Phi\bar{x}),\,\widehat{x}-\bar{x}\right\rangle\geq 0.$

Convexity of $f$ entails the opposite inequality which shows that

$\left\langle\nabla f(\Phi\widehat{x})-\nabla
f(\Phi\bar{x}),\,\Phi\widehat{x}-\Phi\bar{x}\right\rangle=0.$

Since $f$ is twice continuously differentiable in $\mbox{\rm int}\,(\mbox{\rm
dom}\,f)$, we obtain from the mean-value theorem that

$\int_{0}^{1}\left\langle\nabla^{2}f(\Phi(\bar{x}+t(\widehat{x}-\bar{x})))\Phi(\widehat{x}-\bar{x}),\,\Phi(\widehat{x}-\bar{x})\right\rangle
dt=0.$ (4.38)

Since the Hessian is positive definite and continuous on $\mbox{\rm
int}\,(\mbox{\rm dom}\,f)$, there exists some $\tau>0$ such that

$\left\langle\nabla^{2}f(\Phi(\bar{x}+t(\widehat{x}-\bar{x})))\Phi(\widehat{x}-\bar{x}),\,\Phi(\widehat{x}-\bar{x})\right\rangle\geq\tau\|\Phi(\widehat{x}-\bar{x})\|^{2}$

for all $t\in[0,1]$. Combining this with (4.38) implies that
$\Phi\widehat{x}=\Phi\bar{x}$. Using this together with the fact that both
$\widehat{x}$ and $\bar{x}$ are minimizers to (4.33), entails that
$J(\widehat{x})=J(\bar{x})$. This contradicts uniqueness of $\bar{x}$ for
(1.2).

  2. (ii)

Assume that $\bar{x}$ is a sharp solution to (1.2). By Proposition 3.8, we
have

$\mbox{\rm Ker}\,\Phi\cap\mathcal{C}_{J}(x_{0})=\\{0\\}$ (4.39)

where we recall $\mathcal{C}_{J}(x_{0})$ from (3.10). From the sum rule (2.17)
and convexity of $J$, we have

$d^{2}\Theta(\bar{x}|0)(w)=\left\langle\nabla^{2}f(\Phi\bar{x})\Phi w,\,\Phi
w\right\rangle+\mu d^{2}J(\bar{x}|-\mu^{-1}\Phi^{*}\nabla
f(\Phi\bar{x})(w))\geq\left\langle\nabla^{2}f(\Phi\bar{x})\Phi w,\,\Phi
w\right\rangle$ (4.40)

and from (2.15), $\mbox{\rm
dom}\,d^{2}\Theta(\bar{x}|0)\subset\left\\{w\in\mathbb{R}^{n}|\;d\Theta(\bar{x})(w)=0\right\\}$.
We also have

$d\Theta(\bar{x})(w)=\left\langle\nabla f(\Phi\bar{x}),\,\Phi
w\right\rangle+\mu dJ(x_{0})(w).$

It then follows that

$\mbox{\rm
dom}\,d^{2}\Theta(\bar{x}|0)\subset\left\\{w\in\mathbb{R}^{n}|\;\left\langle\nabla
f(\Phi\bar{x}),\,\Phi w\right\rangle+\mu dJ(x_{0})(w)=0\right\\}.$ (4.41)

To verify that $\bar{x}$ is a strong solution to problem (4.33) by using Lemma
2.4, we claim that

$\left\langle\nabla^{2}f(\Phi\bar{x})\Phi w,\,\Phi
w\right\rangle>0\quad\text{for all}\quad w\in\mbox{\rm
dom}\,d^{2}\Theta(\bar{x}|0)\setminus\\{0\\}.$ (4.42)

Suppose that $w\in\mbox{\rm dom}\,d^{2}\Theta(\bar{x}|0)$ satisfying
$\left\langle\nabla^{2}f(\Phi\bar{x})\Phi w,\,\Phi w\right\rangle\leq 0$.
Since $\nabla^{2}f(\Phi\bar{x})\succ 0$, we have $\Phi w=0$. This together
with (4.41) tells us that $w\in\mbox{\rm
Ker}\,\Phi\cap\mathcal{C}_{J}(x_{0})=\\{0\\}$ by (4.39). Thus inequality
(4.42) holds and $\bar{x}$ is a strong solution to problem (4.33).

  3. (iii)

Suppose that $\bar{x}$ is a strong solution to problem (4.33). There exist
constants $\kappa,\gamma>0$ such that

$f(\Phi x)+\mu J(x)\geq f(\Phi\bar{x})+\mu
J(\bar{x})+\frac{\kappa}{2}\|x-\bar{x}\|^{2}\quad\text{for all}\quad
x\in\mathbb{B}_{\gamma}(\bar{x}).$

For any $x\in\mathbb{B}_{\gamma}(\bar{x})\cap\Phi^{-1}(\Phi\bar{x})$, we
obtain that

$J(x)\geq J(\bar{x})+\frac{\kappa}{2\mu}\|x-\bar{x}\|^{2},$

which means that $\bar{x}$ is also a strong solution to (1.2) as claimed.

∎

For the special case (1.5) of (4.33), [14, Theorem 1] shows that if $\bar{x}$
is an optimal solution to (4.33) with $x_{0}=\bar{x}$ and the Strong Null
Space Property (4.28) holds at $\bar{x}$, $\bar{x}$ is the unique solution to
(4.33). As Strong Null Space Property is a characterization for sharp minima
to problem (1.2), Proposition 4.12 advances [14, Theorem 1] and [40, Theorem
3] with further information that $\bar{x}$ is a strong solution to (1.5).

Two natural questions arise from Proposition 4.12: are the converse statements
of (ii)-(iii) true ? That is:

  1. (Q.1)

If $\bar{x}$ is a strong solution to (4.33), can it be a sharp solution to
(1.2) with $x_{0}=\bar{x}$?

  2. (Q.2)

If $\bar{x}$ is a strong solution to (1.2), can it be a strong solution to
(4.33)?

For analysis $\ell_{1}$ problems, i.e., $J_{0}(\cdot)=\|\cdot\|_{1}$, and more
generally for $J_{0}$ the support function of any polyhedral convex compact
$C$ such that $0\in\mbox{\rm ri}\,C$, we have positive answers for both
questions.

######  Corollary 4.13 (Solution uniqueness to $\ell_{1}$ problems).

Let $\bar{x}$ be a minimizer to (4.33) with $J_{0}(\cdot)=\|\cdot\|_{1}$. Then
the following are equivalent:

  1. (i)

$\bar{x}$ is the unique solution to problem (1.2) with $x_{0}=\bar{x}$.

  2. (ii)

$\bar{x}$ is the sharp solution to problem (1.2) with $x_{0}=\bar{x}$.

  3. (iii)

$\bar{x}$ is the unique solution to problem (4.33).

  4. (iv)

$\bar{x}$ is the strong solution to problem (4.33).

###### Proof.

[(i)$\Leftrightarrow$(iii)] and [(ii)$\Rightarrow$(iv)] are from Proposition
4.12. [(iv)$\Rightarrow$(iii)] is trivial. Finally, [(i)$\Leftrightarrow$(ii)]
follows by combining Proposition 3.4 and Proposition 3.8(i) since $J_{0}$ is a
polyhedral norm, in which case the descent and critical cones coincide at any
$x_{0}$ (see Proposition 3.7). ∎

According to Theorem 4.6, conditions $\mbox{\rm Ker}\,\Phi\cap\mbox{\rm
Ker}\,D_{S}^{*}=\\{0\\}$ and $\rho(e)<1$ form a characterization for solution
uniqueness to $\ell_{1}$ problem. A similar result was established in [44,
Theorem 1] for problems (1.2) and (1.5) with the extra assumption that $\Phi$
has full row-rank. Corollary 4.13 is more general and reveals that the unique
solution to problem (4.33) is the strong solution.

The answer is negative for (Q.1) in general; see our Theorem 5.12 and Example
3.9. Regarding (Q.2), we do have a positive answer for group-sparsity ; see
Theorem 5.3 and Theorem 5.12. However, it is not true for the nuclear norm
miniminzation problem as we now show.

######  Example 4.14 (Strong solutions of (1.2) are not those of (4.33)).

Let us consider the following nuclear norm minimization problem

$\min_{X\in\mathbb{R}^{2\times
2}}\Theta(X)\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\dfrac{1}{2}\|Y-\Phi(X)\|^{2}+\|X\|_{*},$ (4.43)

where $\|\cdot\|_{*}$ stands for the nuclear norm of $X$, and
$\Phi:\mathbb{R}^{2\times 2}\to\mathbb{R}^{2}$ is the diagonal operator, i.e.,
$\Phi(X)=(X_{11},X_{22})^{\top}$ and $Y=(2,1)^{\top}$. This is a special case
of (4.33) with $f(\cdot)=\frac{1}{2}\|Y-\cdot\|^{2}$. Let
$\overline{X}=\begin{pmatrix}1&0\\\ 0&0\end{pmatrix}$. We have

$\Phi^{*}\nabla f(\Phi(\overline{X}))=\begin{pmatrix}-1&0\\\
0&-1\end{pmatrix}\enskip\text{and}\enskip\partial\|\overline{X}\|_{*}=\left\\{\begin{pmatrix}1&0\\\
0&\alpha\end{pmatrix}|\;\alpha\in[-1,1]\right\\}.$

Thus $0\in\partial\Theta(\overline{X})$, i.e., $\overline{X}$ is a solution to
(4.43). By Proposition 4.12, it is also a solution to

$\min_{X\in\mathbb{R}^{2\times
2}}\|X\|_{*}\enskip\text{and}\enskip\Phi(X)=(1,0)^{\top}.$ (4.44)

For any $2\times 2$ matrix $X$, let $\sigma_{1},\sigma_{2}$ be its singular
values. We have

$\|X\|_{*}=\sigma_{1}+\sigma_{2}=\sqrt{\sigma_{1}^{2}+\sigma^{2}_{2}+2\sigma_{1}\sigma_{2}}=\sqrt{\|X\|_{F}^{2}+2|{\rm
det}\,(X)|}.$ (4.45)

The feasible set of (4.44) consists of matrices of the form
$X=\begin{pmatrix}1&a\\\ b&0\end{pmatrix}$, and we obtain from (4.45) that

$\|X\|_{*}=\sqrt{1+(|a|+|b|)^{2}}.$

Thus $\overline{X}$ is the unique solution to (4.44) as well as $\eqref{LN}$
due to Proposition 4.12 again. Next we claim that $\overline{X}$ is the strong
solution to (4.44), which means there exist $\kappa,\delta>0$ such that

$\|X\|_{*}-\|\overline{X}\|_{*}\geq\dfrac{\kappa}{2}\|X-\overline{X}\|^{2}_{F}\quad\text{for
all}\quad X=\begin{pmatrix}1&a\\\
b&0\end{pmatrix}\quad\text{with}\quad\|X-\overline{X}\|_{F}=\sqrt{a^{2}+b^{2}}\leq\delta.$
(4.46)

Indeed, we have

$\displaystyle\|X\|_{*}-\|\overline{X}\|_{*}$
$\displaystyle=\sqrt{1+(|a|+|b|)^{2}}-1$
$\displaystyle=\dfrac{a^{2}+b^{2}+2|ab|}{\sqrt{1+a^{2}+b^{2}+2|ab|}+1}$
$\displaystyle\geq\dfrac{a^{2}+b^{2}}{\sqrt{1+2\delta^{2}}+1}$
$\displaystyle=\dfrac{1}{\sqrt{1+2\delta^{2}}+1}\|X-\bar{X}\|_{F}^{2}.$

This certainly verifies (4.46). Next we claim that $\overline{X}$ is not a
strong solution to (4.43). Pick
$X_{\varepsilon}\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\begin{pmatrix}1+\varepsilon^{2}&\varepsilon\\\
\varepsilon&\varepsilon^{2}\end{pmatrix}$ with $\varepsilon>0$ sufficiently
small, observe that
$\|X-\overline{X}\|^{2}_{F}=2(\varepsilon^{2}+\varepsilon^{4})$. It follows
from (4.45) that

$\displaystyle\Theta(X_{\varepsilon})-\Theta(\overline{X})$
$\displaystyle=\dfrac{1}{2}\left\|\begin{pmatrix}\varepsilon^{2}-1\\\
\varepsilon^{2}-1\end{pmatrix}\right\|^{2}+\left\|\begin{pmatrix}1+\varepsilon^{2}&\varepsilon\\\
\varepsilon&\varepsilon^{2}\end{pmatrix}\right\|_{*}-2$
$\displaystyle=(\varepsilon^{2}-1)^{2}+\sqrt{((1+\varepsilon^{2})^{2}+2\varepsilon^{2}+\varepsilon^{4})+2\varepsilon^{4}}-2$
$\displaystyle=(\varepsilon^{2}-1)^{2}+(1+2\varepsilon^{2})-2$
$\displaystyle=\varepsilon^{4}.$

Therefore, $\overline{X}$ cannot be a strong solution to (4.43), which also
implies that $\overline{X}$ is neither a sharp solution to (4.43) nor to
(4.44) due to Proposition 4.12.

##  5 Characterizations of unique/strong solutions for group-sparsity

In this section, we study the following particular case of (1.2), where
$J_{0}$ is the $\ell_{1}/\ell_{2}$ norm that promotes group sparsity [29, 33,
43].

$\min_{x\in\mathbb{R}^{n}}\quad\|D^{*}x\|_{\ell_{1}/\ell_{2}}\quad\mbox{subject
to}\quad\Phi x=\Phi x_{0}.$ (5.1)

Following the notation in [7], we suppose that $\mathbb{R}^{p}$ is decomposed
into $q$ groups by

$\mathbb{R}^{p}=\bigoplus_{g=1}^{q}V_{g},$ (5.2)

where each $V_{g}$ is a subspace of $\mathbb{R}^{p}$ with the same dimension
$G$. For any $u\in\mathbb{R}^{p}$, we write
$u=\displaystyle\sum_{g=1}^{q}u_{g}$ with $u_{g}\in V_{g}$ being the vector in
group $V_{g}$. The $\ell_{1}/\ell_{2}$ norm in $\mathbb{R}^{p}$ is defined by

$\|u\|_{\ell_{1}/\ell_{2}}=\sum_{g=1}^{q}\|u_{g}\|.$ (5.3)

Its dual is the $\ell_{\infty}/\ell_{2}$ norm:

$\|u\|_{\ell_{\infty}/\ell_{2}}=\max_{1\leq g\leq q}\|u_{g}\|.$ (5.4)

With $\bar{u}\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}D^{*}x_{0}$,
define $I\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\left\\{g\in\\{1,\ldots,q\\}|\;\bar{u}_{g}\neq 0\right\\}$, the
index set of active groups of $\bar{u}$, and
$K\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}\\{1,\ldots,q\\}\setminus
I$, the index set of nonactive groups of $\bar{u}$. Note that

$\partial\|\bar{u}\|_{\ell_{1}/\ell_{2}}\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\left\\{v\in\mathbb{R}^{p}|\;v_{g}=\frac{\bar{u}_{g}}{\|\bar{u}_{g}\|_{2}}\mbox{
for }g\in I\mbox{ and }\|v_{g}\|\leq 1\mbox{ for }g\in K\right\\}.$ (5.5)

Thus $\ell_{1}/\ell_{2}$ norm is decomposable at $\bar{u}$ as in Remark 4.5,
where $T=\displaystyle\bigoplus_{g\in I}V_{g}$, $S=T^{\perp}$, and

$e=\sum_{g\in I}\frac{\bar{u}_{g}}{\|\bar{u}_{g}\|}.$ (5.6)

###  5.1 Descent cone of group sparsity

Sharp minima at $x_{0}$ for problem (5.1) is studied in our previous section.
However, unlike the case of $\ell_{1}$ problem, a unique solution to problem
(5.1) may be not sharp; see Example 3.9. To characterize the solution
uniqueness to group sparsity problem (5.1), we compute the descent cone
$\mathcal{D}_{J}(x_{0})$ in (3.8) as follows.

######  Theorem 5.1 (Descent cone to $\ell_{1}/\ell_{2}$ problem and geometric
characterization for solution uniqueness).

The descent cone at $x_{0}$ to problem (5.1) is given by

$\mathcal{D}_{J}(x_{0})=(\mathcal{E}\cap\mbox{\rm
bd}\,\mathcal{C}_{J}(x_{0}))\cup(\mbox{\rm int}\,\mathcal{C}_{J}(x_{0})),$
(5.7)

where

$\mathcal{E}\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\left\\{w\in\mathbb{R}^{n}|\;D_{T}^{*}w\in\mbox{\rm
Im}\,\\{(D^{*}_{T}x_{0})_{g}|\;g\in I\\}\right\\},$ (5.8)

and $\mbox{\rm bd}\,\mathcal{C}_{J}(x_{0})$ stands for the boundary of the
critical cone $\mathcal{C}_{J}(x_{0})$ defined in (3.10), i.e.,

$\mbox{\rm
bd}\,\mathcal{C}_{J}(x_{0})=\left\\{w\in\mathbb{R}^{p}||\;\left\langle
D_{T}e,\,w\right\rangle+\|D^{*}_{S}w\|_{\ell_{1}/\ell_{2}}=0\right\\}.$ (5.9)

Consequently, $x_{0}$ is a unique solution to (5.1) if and only if

$\mbox{\rm Ker}\,\Phi\cap\Big{(}(\mathcal{E}\cap\mbox{\rm
bd}\,\mathcal{C}_{J}(x_{0}))\cup(\mbox{\rm
int}\,\mathcal{C}_{J}(x_{0}))\Big{)}=\\{0\\}.$ (5.10)

###### Proof.

Let us start by verifying the inclusion “$\supset$” in (5.7). Recall that
$J(x)=\|D^{*}x\|_{\ell_{1}/\ell_{2}}$. For any $w\in\mbox{\rm
int}\,(\mathcal{C}_{J}(x_{0}))$, we get from (3.10) that

$dJ(x_{0})(w)=\lim_{t\downarrow 0}\dfrac{J(x_{0}+tw)-J(x_{0})}{t}<0.$

Hence there is some $t_{0}>0$ such that $J(x_{0}+t_{0}w)<J(x_{0})$. This
ensures $w\in\mathcal{D}_{J}(x_{0})$. For any $w\in\mathcal{E}\cap\mbox{\rm
bd}\,\mathcal{C}_{J}(x_{0})$, we represent $D_{T}^{*}w=\sum_{g\in
I}\lambda_{g}(D^{*}x_{0})_{g}$ with $\lambda_{g}\in\mathbb{R}$, $g\in I$ and

$0=\left\langle
D_{T}e,\,w\right\rangle+\|D^{*}_{S}w\|_{\ell_{1}/\ell_{2}}=\left\langle
e,\,D^{*}_{T}w\right\rangle+\|D^{*}_{S}w\|_{\ell_{1}/\ell_{2}}=\sum_{g\in
I}{\lambda_{g}}\|(D^{*}x_{0})_{g}\|+\|D_{S}^{*}w\|_{\ell_{1}/\ell_{2}}.$
(5.11)

Define $I_{-}\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}\\{g\in
I|\;\lambda_{g}<0\\}$. If $I_{-}=\emptyset$, we get from (5.11) that
$D^{*}_{S}w=0$ and $\lambda_{g}=0$ for all $g\in I$, which implies that
$D^{*}_{T}w=0$ and thus $D^{*}w=0$. Therefore, we get

$J(x_{0}+w)=J_{0}(D^{*}(x_{0}+w))=J_{0}(D^{*}x_{0})=J(x_{0}),$

which tells us that $w\in\mathcal{D}_{J}(x_{0})$. If $I_{-}\neq\emptyset$,
define $t_{1}\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\min\left\\{-\dfrac{1}{\lambda_{g}}||\;g\in I_{-}\right\\}>0$, we
obtain from (5.11) that

$\displaystyle J(x_{0}+t_{1}w)-J(x_{0})$
$\displaystyle=\|D^{*}x_{0}+t_{1}D^{*}w\|_{\ell_{1}/\ell_{2}}-\|D^{*}x_{0}\|_{\ell_{1}/\ell_{2}}$
$\displaystyle=\sum_{g\in
I}|1+t_{1}\lambda_{g}|\|(D^{*}x_{0})_{g}\|+t_{1}\|D_{S}^{*}w\|_{\ell_{1}/\ell_{2}}-\|D^{*}x_{0}\|_{\ell_{1}/\ell_{2}}$
$\displaystyle=\sum_{g\in
I}(1+t_{1}\lambda_{g})\|(D^{*}x_{0})_{g}\|+t_{1}\|D_{S}^{*}w\|_{\ell_{1}/\ell_{2}}-\|D^{*}x_{0}\|_{\ell_{1}/\ell_{2}}$
$\displaystyle=t_{1}\left(\sum_{g\in
I}\lambda_{g}\|(D^{*}x_{0})_{g}\|+\|D_{S}^{*}w\|_{\ell_{1}/\ell_{2}}\right)+\sum_{g\in
I}\lambda_{g}\|(D^{*}x_{0})_{g}\|-\|D^{*}x_{0}\|_{\ell_{1}/\ell_{2}}$
$\displaystyle=0,$

where the third equality is from the choice of $t_{1}$. In both cases of
$I_{-}$, $w\in\mathcal{D}_{J}(x_{0})$.

To justify the reverse inclusion “$\subset$” in (5.7), take any
$w\in\mathcal{D}_{J}(x_{0})$ and let $t>0$ such that
$\|D^{*}x_{0}+tD^{*}w\|_{\ell_{1}/\ell_{2}}\leq\|D^{*}x_{0}\|_{\ell_{1}/\ell_{2}}$.
For any $\alpha\in(0,1)$, we have

$\|D^{*}x_{0}\|_{\ell_{1}/\ell_{2}}\geq\alpha\|D^{*}x_{0}+tD^{*}w\|_{\ell_{1}/\ell_{2}}+(1-\alpha)\|D^{*}x_{0}\|_{\ell_{1}/\ell_{2}}\geq\|D^{*}x_{0}+\alpha
tD^{*}w\|_{\ell_{1}/\ell_{2}}.$ (5.12)

Choose $\alpha>0$ sufficiently small such that

$\|(D^{*}x_{0})_{g}+\alpha t(D^{*}w)_{g}\|>0\quad\text{for all}\quad g\in I.$

Since $w\in\mathcal{D}_{J}(x_{0})\subset\mathcal{C}_{J}(x_{0})$ by (3.11), it
suffices to show that if $w\in\mbox{\rm bd}\,\mathcal{C}_{J}(x_{0})$ then
$w\in\mathcal{E}.$ Suppose that $w\in\mbox{\rm bd}\,\mathcal{C}_{J}(x_{0})$,
we have

$0=\left\langle
D_{T}e,\,w\right\rangle+\|D_{S}^{*}w\|_{\ell_{1}/\ell_{2}}=\left\langle
e,\,D^{*}_{T}w\right\rangle+\|D_{S}^{*}w\|_{\ell_{1}/\ell_{2}}.$

It follows from the latter and (5.12) that

$\displaystyle 0$ $\displaystyle\geq\|D^{*}x_{0}+\alpha
tD^{*}w\|_{\ell_{1}/\ell_{2}}-\|D^{*}x_{0}\|_{\ell_{1}/\ell_{2}}$ (5.13)
$\displaystyle=\sum_{g\in I}\|(D^{*}x_{0})_{g}+\alpha t(D^{*}w)_{g}\|+\alpha
t\sum_{g\in K}\|(D^{*}w)_{g}\|-\|D^{*}x_{0}\|_{\ell_{1}/\ell_{2}}$
$\displaystyle=\sum_{g\in I}\Big{(}\|(D^{*}x_{0})_{g}+\alpha
t(D^{*}w)_{g}\|-\|(D^{*}x_{0})_{g}\|-\alpha t\left\langle
e_{g},\,(D^{*}w)_{g}\right\rangle\Big{)}.$

Since $e_{g}=\partial\|(D^{*}x_{0})_{g}\|$, each $\|(D^{*}x_{0})_{g}+\alpha
t(D^{*}w)_{g}\|-\|(D^{*}x_{0})\|_{g}-\alpha t\left\langle
e_{g},\,(D^{*}w)_{g}\right\rangle\geq 0$ for $g\in I$. This together with
(5.13) tells us that

$0=\|(D^{*}x_{0})_{g}+\alpha t(D^{*}w)_{g}\|-\|(D^{*}x_{0})_{g}\|-\alpha
t\left\langle e_{g},\,(D^{*}w)_{g}\right\rangle\quad\text{for all}\quad g\in
I.$

Hence, we have

$0=\|(D^{*}x_{0})_{g}\|-\left\langle
e_{g},\,(D^{*}x_{0})_{g}\right\rangle=\|(D^{*}x_{0})_{g}+\alpha
t(D^{*}w)_{g}\|-\left\langle e_{g},\,(D^{*}x_{0})_{g}+\alpha
t(D^{*}w)_{g}\right\rangle.$

As $\|e_{g}\|=1$ and $(D^{*}x_{0})_{g}+\alpha t(D^{*}w)_{g}\neq 0$, the latter
equality holds when

$(D^{*}x_{0})_{g}+\alpha t(D^{*}w)_{g}=\delta_{g}e_{g}$

for some $\delta_{g}>0$, $g\in I$. It follows that

$(D^{*}w)_{g}=\frac{1}{\alpha t}(\delta_{g}-\|(D^{*}x_{0})_{g}\|)e_{g}$

for any $g\in I$, which ensures that $w\in\mathcal{E}$ and verifies the
equality (5.7).

The characterization for solution uniqueness at $x_{0}$ in (5.10) follows
directly from Proposition 3.4 and (5.7). ∎

###  5.2 Unique vs strong solutions

We show next that a unique solution to (1.2) is indeed a strong solution. The
proof is based on the second-order analysis in Lemma 2.4. We need the
computation of the second subderivative for the function $\Psi$ defined in
(3.3).

######  Lemma 5.2 (Second subderivative to $\ell_{1}/\ell_{2}$ norm).

Suppose that $x_{0}$ is a minimizer to problem (5.1). Then we have

$\mbox{\rm dom}\,d^{2}\Psi(x_{0}|0)=\mbox{\rm Ker}\,\Phi\cap\mbox{\rm
bd}\,\mathcal{C}_{J}(x_{0})$ (5.14)

and

$\displaystyle d^{2}\Psi(x_{0}|0)(w)=\sum_{g\in
I}\dfrac{\|(D^{*}w)_{g}\|^{2}\|(D^{*}x_{0})_{g}\|^{2}-\langle(D^{*}x_{0})_{g},(D^{*}w)_{g}\rangle^{2}}{\|(D^{*}x_{0})_{g}\|^{3}}\;\;\mbox{for}\;\;w\in\mbox{\rm
dom}\,d^{2}\Psi(x_{0}|0).$ (5.15)

###### Proof.

Since $x_{0}$ is an optimal solution to (5.1), we have
$0\in\partial\Psi(x_{0})$. With $C=\Phi^{-1}(\Phi x_{0})$, we have

$\displaystyle d^{2}\Psi(x_{0}|0)(w)$ $\displaystyle=$
$\displaystyle\liminf_{t\downarrow 0,\;w^{\prime}\to
w}\dfrac{\|D^{*}(x_{0}+tw^{\prime})\|_{\ell_{1}/\ell_{2}}+\iota_{C}(x_{0}+tw^{\prime})-\|D^{*}x_{0}\|_{\ell_{1}/\ell_{2}}-\iota_{C}(x_{0})-t\langle
0,w\rangle}{\frac{1}{2}t^{2}}$ $\displaystyle=$
$\displaystyle\liminf_{t\downarrow 0,\;w^{\prime}\to
w}\left(\dfrac{\|D^{*}(x_{0}+tw^{\prime})\|_{\ell_{1}/\ell_{2}}-\|D^{*}x_{0}\|_{\ell_{1}/\ell_{2}}}{\frac{1}{2}t^{2}}+\iota_{\mbox{\rm
Ker}\,\Phi}(w^{\prime})\right).$

It follows that $\mbox{\rm dom}\,d^{2}\Psi(x_{0}|0)\subset\mbox{\rm
Ker}\,\Phi$. Since $D^{*}_{S}x_{0}=0$, we have

$\displaystyle\begin{array}[]{ll}&\displaystyle\liminf_{t\downarrow
0,\;w^{\prime}\stackrel{{\scriptstyle\mbox{\rm
Ker}\,\Phi}}{{\to}}w}\dfrac{\|D^{*}(x_{0}+tw^{\prime})\|_{\ell_{1}/\ell_{2}}-\|D^{*}x_{0}\|_{\ell_{1}/\ell_{2}}}{\frac{1}{2}t^{2}}\\\
&\displaystyle=\liminf_{t\downarrow
0,\;w^{\prime}\stackrel{{\scriptstyle\mbox{\rm
Ker}\,\Phi}}{{\to}}w}\left(\dfrac{\|D_{T}^{*}(x_{0}+tw^{\prime})\|_{\ell_{1}/\ell_{2}}-\|D_{T}^{*}x_{0}\|_{\ell_{1}/\ell_{2}}-t\langle
De,w^{\prime}\rangle}{\frac{1}{2}t^{2}}+\dfrac{\langle
De,w^{\prime}\rangle+\|D_{S}^{*}w^{\prime}\|_{\ell_{1}/\ell_{2}}}{\frac{1}{2}t}\right).\end{array}$
(5.18)

Note that the Euclidean norm $\|u\|$ is twice differentiable at $u\neq 0$ with

$\nabla\|u\|=\frac{u}{\|u\|}\enskip\text{and}\enskip\nabla^{2}\|u\|=\frac{1}{\|u\|}\mathbb{I}-\frac{1}{\|u\|^{3}}uu^{*}$

This together with (2.16) tells us that

$\displaystyle\begin{array}[]{ll}&\displaystyle\liminf_{t\downarrow
0,\;w^{\prime}\stackrel{{\scriptstyle\mbox{\rm
Ker}\,\Phi}}{{\to}}w}\dfrac{\|D_{T}^{*}(x_{0}+tw^{\prime})\|_{\ell_{1}/\ell_{2}}-\|D_{T}^{*}x_{0}\|_{\ell_{1}/\ell_{2}}-t\langle
De,w^{\prime}\rangle}{\frac{1}{2}t^{2}}\\\
&\displaystyle=\displaystyle\liminf_{t\downarrow
0,\;w^{\prime}\stackrel{{\scriptstyle\mbox{\rm Ker}\,\Phi}}{{\to}}w}\sum_{g\in
I}\left(\dfrac{\|(D^{*}(x_{0}+tw^{\prime}))_{g}\|-\|(D^{*}x_{0})_{g}\|-t\langle
e_{g},D^{*}w^{\prime}\rangle}{\frac{1}{2}t^{2}}\right)\\\
&=\displaystyle\sum_{g\in
I}\left\langle(D^{*}w)_{g},\,\dfrac{(D^{*}w)_{g}}{\|(D^{*}x_{0})_{g}\|}-\frac{1}{\|(D^{*}x_{0})_{g}\|^{3}}(D^{*}x_{0})_{g}(D^{*}x_{0})_{g}^{*}(D^{*}w)_{g}\right\rangle\\\
&=\displaystyle\sum_{g\in
I}\dfrac{\|(D^{*}w)_{g}\|^{2}\|(D^{*}x_{0})_{g}\|^{2}-\langle(D^{*}x_{0})_{g},(D^{*}w)_{g}\rangle^{2}}{\|(D^{*}x_{0})_{g}\|^{3}}.\end{array}$
(5.23)

Since $x_{0}$ is an optimal solution to (5.1), there exists
$z\in\mathbb{R}^{p}$ with $P_{T}z=e$, $\|P_{S}z\|_{\ell_{\infty}/\ell_{2}}\leq
1$ and $Dz\in\mbox{\rm Im}\,\Phi^{*}$. For any $w^{\prime}\in\mbox{\rm
Ker}\,\Phi$, we have

$\langle De,w^{\prime}\rangle=\langle D_{T}z,w^{\prime}\rangle=-\langle
D_{S}z,w^{\prime}\rangle=-\langle z,D_{S}^{*}w^{\prime}\rangle.$

It follows that $\langle
De,w^{\prime}\rangle+\|D_{S}^{*}w^{\prime}\|_{\ell_{1}/\ell_{2}}\geq 0$. Hence
we get

$\displaystyle\liminf_{t\downarrow
0,\;w^{\prime}\stackrel{{\scriptstyle\mbox{\rm
Ker}\,\Phi}}{{\to}}w}\dfrac{\langle
De,w^{\prime}\rangle+\|D_{S}^{*}w^{\prime}\|_{\ell_{1}/\ell_{2}}}{\frac{1}{2}t}$
$\displaystyle=$ $\displaystyle\begin{cases}0&\text{ if }\langle
De,w\rangle+\|D_{S}^{*}w\|_{\ell_{1}/\ell_{2}}=0,w\in\mbox{\rm Ker}\,\Phi,\\\
\infty&\text{ otherwise}.\end{cases}$

Since the “liminf” in (5.23) indeed becomes “lim”, the latter together with
(5.23) and (5.18) verifies (5.14) and (5.15). ∎

This calculation allows us to establish the main result in this section, which
gives a quantitative characterization for unique/strong solutions to
$\ell_{1}/\ell_{2}$ problem (5.1).

######  Theorem 5.3 (Characterizations for unique/strong solutions to
$\ell_{1}/\ell_{2}$ problems).

The following assertions are equivalent:

  1. (i)

$x_{0}$ is a unique solution to problem (5.1).

  2. (ii)

$x_{0}$ is a strong solution to problem (5.1).

  3. (iii)

$x_{0}$ is a solution to (5.1), $\mbox{\rm
Ker}\,\Phi\cap\mathcal{E}\cap\mbox{\rm Ker}\,D^{*}_{S}=\\{0\\}$, and

$\zeta(e)\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\displaystyle\min_{u\in\mbox{\rm
Ker}\,MD_{S}}\|(MD_{S})^{\dagger}MD_{T}e-u\|_{\ell_{\infty}/\ell_{2}}<1,$
(5.24)

where $M^{*}$ is a matrix forming a basis matrix to $\mbox{\rm
Ker}\,\Phi\cap\mathcal{E}$.

###### Proof.

We first claim that $x_{0}$ is a solution to (5.1) if and only if

$\mbox{\rm Ker}\,\Phi\cap\mbox{\rm int}\,(\mathcal{C}_{J}(x_{0}))=\emptyset.$
(5.25)

Indeed, $x_{0}$ is a solution to (5.1) if and only if $d\Psi(x_{0})(w)\geq 0$
for all $w\in\mathbb{R}^{n}$. Due to the computation of $d\Psi(\bar{x})(w)$ in
(4.15), $d\Psi(\bar{x})(w)\geq 0$ means

$\langle De,w\rangle+\|D^{*}_{S}w\|_{\ell_{1}/\ell_{2}}\geq 0\quad\mbox{for
all}\quad w\in\mbox{\rm Ker}\,\Phi,$ (5.26)

which is equivalent to (5.25).

Next let us verify the equivalence between (i) and (ii). By Theorem 5.1, it
suffices to show that condition (5.10) implies (ii). Note from (5.14) and
(5.15) that if $d^{2}\Psi(x_{0}|0)(w)\leq 0$ then $w\in\mbox{\rm
Ker}\,\Phi\cap\mbox{\rm bd}\,\mathcal{C}_{J}(x_{0})$ and $w\in\mathcal{E}.$
Since $\mbox{\rm Ker}\,\Phi\cap(\mathcal{E}\cap\mbox{\rm
bd}\,\mathcal{C}_{J}(x_{0}))=\\{0\\}$ by (5.10), we have
$d^{2}\Psi(x_{0}|0)(w)>0$ for all $w\neq 0$. It follows from Lemma 2.4 that
$x_{0}$ is a strong solution. This verifies the equivalence between (i) and
(ii).

To justify the equivalence between (i) and (iii), by (5.25), we only need to
show that condition

$\mbox{\rm Ker}\,\Phi\cap\mathcal{E}\cap\mbox{\rm
bd}\,\mathcal{C}_{J}(x_{0})=\\{0\\}$ (5.27)

in (5.10) is equivalent to the combination of $\mbox{\rm
Ker}\,\Phi\cap\mathcal{E}\cap\mbox{\rm Ker}\,D^{*}_{S}=\\{0\\}$ and (5.24)
provided that $x_{0}$ is a solution to (5.1). According to (5.26), (5.27) is
equivalent to the condition that there exists some $c>0$ such that

$k(w)\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}\langle
De,w\rangle+\|D^{*}_{S}w\|_{\ell_{1}/\ell_{2}}\geq c\|w\|\quad\mbox{for
all}\quad w\in\mbox{\rm Ker}\,\Phi\cap\mathcal{E}.$ (5.28)

Since $x_{0}$ is a solution to (5.1), there exists $v\in\mathbb{R}^{p}$ such
that $v\in\partial\|D^{*}x_{0}\|_{\ell_{1}/\ell_{2}}$ and $Dv\in\mbox{\rm
Im}\,\Phi^{*}$. It follows that $D(e+P_{S}v)\in\mbox{\rm Ker}\,M=\mbox{\rm
Im}\,\Phi^{*}+\mathcal{E}^{\perp}$, we have $MD_{S}v=-MDe$. It follows from
(2.2) that

$MD_{S}(MD_{S})^{\dagger}MD_{T}e=MD_{T}e.$

For any $w=M^{*}u\in\mbox{\rm Ker}\,\Phi\cap C$ it follows that

$\displaystyle\begin{array}[]{ll}k(w)&=k(M^{*}u)=\langle
De,M^{*}u\rangle+\|D^{*}_{S}M^{*}u\|_{\ell_{1}/\ell_{2}}\\\ &=\langle
MD_{T}e,u\rangle+\|D^{*}_{S}w\|_{\ell_{1}/\ell_{2}}\\\
&=\langle(MD_{S})^{\dagger}MD_{T}e,D^{*}_{S}M^{*}u\rangle+\|D^{*}_{S}M^{*}u\|_{\ell_{1}/\ell_{2}}.\end{array}$
(5.32)

Mimicking the proof of Theorem 4.6 by replacing $N$ there by $M$ and
$\mbox{\rm Ker}\,\Phi$ by its subspace $\mbox{\rm Ker}\,\Phi\cap\mathcal{E}$,
the inequality $k(w)\geq c\|w\|$ in (5.28) is equivalent to (iii). The proof
is complete. ∎

It is worth noting that condition

$\mbox{\rm Ker}\,\Phi\cap\mathcal{E}\cap\mbox{\rm Ker}\,D^{*}_{S}=\\{0\\}$
(5.33)

in part (iii) is strictly weaker than the Restricted Injectivity in Theorem
4.6; see Example 3.9. It means that $\Phi$ is injective on the subspace
$\mathcal{E}\cap\mbox{\rm Ker}\,D^{*}_{S}$. We refer (5.33) as Strong
Restricted Injectivity condition. Moreover, we call the constant $\zeta(e)$
Strong Source Coefficient, while the condition $\zeta(e)<1$ is refered as
Analysis Nondegenerate Source Condition for solution uniqueness to
$\ell_{1}/\ell_{2}$ problem (1.2).

######  Remark 5.4 (Checking the Strong Restricted Injectivity and the
Analysis Nondegenerate Source Condition).

Set the matrix $S\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}((D^{*}_{T}x_{0})_{g})_{g\in I}$ to be an $p\times|I|$ matrix,
where $|I|$ is the cardinality of $I$. Observe from (5.15) that
$w\in\mathcal{E}$ if and only if the following system

$D^{*}_{T}w=S\lambda\mbox{ is consistent with }\lambda\in\mathbb{R}^{|I|}.$

Since $S$ is injective, we have
$\lambda=S^{\dagger}D^{*}_{T}w=(S^{*}S)^{-1}S^{*}D^{*}_{T}w$ due to (2.2). It
follows that $w\in\mathcal{E}$ if and only if

$S(S^{*}S)^{-1}S^{*}D^{*}_{T}w-D^{*}_{T}w=0$ (5.34)

Note that $S^{*}S={\rm diag}\,(\|(D^{*}_{T}x_{0})_{g}\|^{2})_{b\in I}$ is an
$|I|\times|I|$ diagonal matrix. Representing $S$ in terms of groups, we have

$S(S^{*}S)^{-1}S^{*}={\rm diag\,}\left(\sum_{g\in
I}\|(D_{T}^{*}x_{0})_{g}\|^{-2}\delta_{g}\right)SS^{*},$

where $\delta_{g}=(0,\ldots,0,\underbrace{1,1,\ldots,1}_{\text{in
$V_{g}$}},0,\ldots,0)$ is the unit vector in $V_{g}$. This together with
(5.34) tells us that $\mathcal{E}$ is the kernel of the following matrix

$Q=\mbox{\rm diag}\,\left(\sum_{g\in
I}\|(D_{T}^{*}x_{0})_{g}\|^{2}\delta_{g}\right)D_{T}^{*}-SS^{*}D_{T}^{*}\quad\mbox{with}\quad
S=((D^{*}_{T}x_{0})_{g})_{g\in I}.$ (5.35)

The Strong Restricted Injectivity (5.33) is equivalent to $\mbox{\rm
Ker}\,\begin{pmatrix}\Phi\\\ Q\end{pmatrix}\cap\mbox{\rm
Ker}\,D^{*}_{S}=\\{0\\}.$

Furthermore, $M^{*}$ forms a basis matrix of $\mbox{\rm
Ker}\,\begin{pmatrix}\Phi\\\ Q\end{pmatrix}$, which is found from the SVD of
$\begin{pmatrix}\Phi\\\ Q\end{pmatrix}$. Similarly to (4.11), $\zeta(e)$ is
the optimal solution to

$\min\|z\|_{\ell_{2}/\ell_{\infty}}\quad\text{such that}\quad
MDz=-MDe\enskip\text{and}\enskip z\in\bigoplus_{g\in I}V_{g}.$ (5.36)

So $\zeta^{2}(e)$ is the optimal value to the following convex optimization
problem

$\min_{t\geq 0,z}t\quad\text{such that}\quad MDz=-MDe,\quad\|z_{g}\|^{2}-t\leq
0,\quad g\in I\quad\mbox{and}\quad z\in\bigoplus_{g\in I}V_{g}$ (5.37)

with $|I|G+1$ variables, which can be solved by available packages such as
cvxopt; see Section 6 for further discussion.

Next we show that $\zeta(e)\leq\rho(e)$ when $x_{0}$ is an optimal solution to
(5.1).

######  Proposition 5.5 (Comparison between $\rho(e)$ and $\zeta(e)$).

Suppose that $x_{0}$ is an optimal solution to (5.1). Then we have
$\zeta(e)\leq\rho(e)\leq 1$.

###### Proof.

It follows from (4.6) that

$ND_{S}(ND_{S})^{\dagger}ND_{T}e=ND_{T}e\enskip\text{and}\enskip\rho(e)\leq
1.$

For any $w\in\mbox{\rm Ker}\,\Phi\cap\mathcal{E}=\mbox{\rm
Im}\,M^{*}\subset\mbox{\rm Ker}\,\Phi=\mbox{\rm Im}\,N^{*}$, it is similar to
(5.32) that

$\langle
De,w\rangle=\langle(MD_{S})^{\dagger}MD_{T}e,D^{*}_{S}w\rangle=\langle(ND_{S})^{\dagger}ND_{T}e,D^{*}_{S}w\rangle$

Note from the definition in (5.24) that

$\displaystyle\begin{array}[]{ll}\zeta(e)&=\displaystyle\sup_{\|v\|\leq
1}\langle-(MD_{S})^{\dagger}MD_{T}e,v\rangle-\iota_{\mbox{\rm
Im}\,D^{*}_{S}M^{*}}(v)\\\ &=\displaystyle\sup_{\|v\|\leq
1}\langle-(ND_{S})^{\dagger}ND_{T}e,v\rangle-\iota_{\mbox{\rm
Im}\,D^{*}_{S}M^{*}}(v)\\\ &=\displaystyle\min_{u\in\mbox{\rm
Ker}\,MD_{S}}\|(ND_{S})^{\dagger}ND_{T}e-u\|_{\ell_{\infty}/\ell_{2}}.\end{array}$
(5.41)

Since $\mbox{\rm Ker}\,ND_{S}\subset\mbox{\rm Ker}\,MD_{S}$, we have
$\zeta(e)\leq\rho(e)$. ∎

Although $\zeta(e)$ could be computed by involving $N$ via (5.41), the format
in (5.24) is more preferable. This is due to the fact that the Moore-Penrose
inverse $MD_{S}^{\dagger}$ has a closed form as
$(MD_{S})^{*}(MD_{S}(MD_{S})^{*})^{-1}$ when the Strong Restricted Injectivity
(5.33) is in charged. In general, $\rho(e)$ is strictly smaller $\zeta(e)$.
This fact is obtained through numerical experiments in our Section 6.

By replacing $\zeta(e)$ by $\rho(e)$ in Theorem 5.3, we do not need to assume
$x_{0}$ to be an optimal solution, but we only have a sufficient condition for
solution of uniqueness.

######  Corollary 5.6 (Sufficient condition for solution uniqueness to
$\ell_{1}/\ell_{2}$ problem).

$x_{0}$ is the unique solution to problem (5.1) provided that $\rho(e)<1$ and
both conditions $\eqref{yz}$ and (5.33) are satisfied.

###### Proof.

It follows directly from Proposition 4.4, Theorem 5.3, and Proposition 5.5. ∎

An simple upper bound for $\zeta(e)$ is

$\zeta(e)\leq\gamma(e)\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\|(MD_{S})^{\dagger}MD_{T}e\|_{\ell_{\infty}/\ell_{2}},$ (5.42)

which is also used in Section 6 to check solution uniqueness. The inequality
is indeed strict. The following result is straightforward from Theorem 5.3.

######  Corollary 5.7 (Sufficient condition for solution uniqueness to
$\ell_{1}/\ell_{2}$ problem).

Suppose that $x_{0}$ is an optimal solution to (5.1). Then the Strong
Restricted Injectivity (5.33) at $x_{0}$ and $\gamma(e)<1$ are sufficient for
solution uniqueness at $x_{0}$. They become necessary conditions provided that
$MD_{S}$ is injective.

In the spirit of Proposition 5.5, it is possible that $x_{0}$ is a unique
solution to (5.1) but $\rho(e)=1$. It means that the Nondegenerate Source
Condition may not happen. However, the following result provides
characterizations for solution uniqueness whose statement closely relates to
the Nondegenerate Source Condition.

######  Corollary 5.8 (Characterization for solution uniqueness to problem
(5.1)).

The following are equivalent:

  1. (i)

$x_{0}$ is the unique solution to problem (5.1).

  2. (ii)

With an arbitrary $v\in\mathbb{R}^{p}$ satisfying $Dv\in\mbox{\rm
Im}\,\Phi^{*}$, $P_{T}v=e$, and $\|P_{S}v\|_{\ell_{\infty}/\ell_{2}}\leq 1$,
the following system has only trivial solution

$\Phi w=0,\quad w\in\mathcal{E},\enskip\text{and}\enskip
D_{S}^{*}w\in\mbox{\rm cone}\,\\{v_{g}|g\in L\\}\times\\{0_{H}\\},$

where $L\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}\\{g\in
K|\;\|v_{g}\|=1\\}$ and $H\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}K\setminus L.$

###### Proof.

Pick an arbitrary $v\in\mathbb{R}^{p}$ satisfying $Dv\in\mbox{\rm
Im}\,\Phi^{*}$, $P_{T}v=e$, and $\|P_{S}v\|_{\ell_{\infty}/\ell_{2}}\leq 1$.
Such an $v$ always exists as when $x_{0}$ is a solution to (5.1), i.e.,
$\mbox{\rm Ker}\,\Phi\cap\mbox{\rm int}\,\mathcal{C}_{J}(x_{0})=\emptyset$. We
claim that

$\mbox{\rm Ker}\,\Phi\cap\mbox{\rm
bd}\,\mathcal{C}_{J}(x_{0})=\\{w\in\mbox{\rm
Ker}\,\Phi|\;D_{S}^{*}w\in\mbox{\rm cone}\,\\{v_{g}|g\in
L\\}\times\\{0_{H}\\}\\}$ (5.43)

with $L=\\{g\in K|\;\|v_{g}\|=1\\}$ and $H=K\setminus L.$ For any
$w\in\mbox{\rm Ker}\,\Phi$, note that

$\begin{array}[]{ll}\displaystyle\langle De,w\rangle+\|D^{*}_{S}w\|&=\langle
Dv,w\rangle-\langle DP_{S}v,w\rangle+\|D^{*}_{S}w\|\\\ &=\displaystyle-\langle
P_{S}v,D^{*}_{S}w\rangle+\|D^{*}_{S}w\|_{\ell_{1}/\ell_{2}}\\\
&\displaystyle=\sum_{g\in L}\left(-\langle
v_{g},(D^{*}_{T}w)_{g}\rangle+\|(D^{*}_{T}w)_{g}\|\right)+\sum_{g\in
H}\left(\langle v_{g},(D^{*}_{T}w)_{g}\rangle+\|(D^{*}_{T}w)_{g}\|\right)\\\
&\displaystyle=\sum_{g\in L}\left(-\langle
v_{g},(D^{*}_{T}w)_{g}\rangle+\|(D^{*}_{T}w)_{g}\|\right)+\sum_{g\in
H}\|(D^{*}_{T}w)_{g}\|\geq 0.\end{array}$

It follows that $w\in\mbox{\rm bd}\,\mathcal{C}_{J}(x_{0})$ if and only if
there exist $\lambda_{g}\geq 0$, $g\in L$ such that
$(D^{*}_{T}w)_{g}=\lambda_{g}v_{g}$ for any $g\in L$ and $(D^{*}_{T}w)_{g}=0$
for any $g\in H$, which verifies (5.43). The equivalence between (i) and (ii)
follows from Theorem 5.1. ∎

As $\mbox{\rm Ker}\,\Phi\cap\mathcal{E}\cap\mbox{\rm
bd}\,\mathcal{C}_{J}(x_{0})\subset\mbox{\rm Ker}\,\Phi\cap\mbox{\rm
Ker}\,D^{*}_{V_{H}}$ with $\displaystyle
V_{H}\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}\bigoplus_{g\in
H}V_{g}$, the following result is straightforward from Corollary 5.6.

######  Corollary 5.9 (Sufficient condition to the solution uniqueness to
problem (5.1)).

$x_{0}$ is the unique solution to problem (5.1) provided that there exists
some $v$ such that $Dv\in\mbox{\rm Im}\,\Phi^{*}$, $P_{T}v=e$,
$\|P_{S}v\|_{\ell_{\infty}/\ell_{2}}\leq 1$, and that

$\mbox{\rm Ker}\,\Phi\cap\mbox{\rm Ker}\,D^{*}_{V_{H}}=\\{0\\}$ (5.44)

with $K=\\{g\in J|\;\|v_{g}\|=1\\}$, $H=J\setminus K$, and $\displaystyle
V_{H}\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}\bigoplus_{g\in
H}V_{g}$.

The sufficient condition in [18, Proposition 7.1] is a special case of
Corollary 5.9 where $D^{*}$ is the discrete gradient operator. Moreover, [21,
Theorem 3.4] and [33, Theorem 3] even assume a stronger condition as they
require $K=\emptyset$. Let us revisit Example 3.9. Pick any
$v\in\partial\|x_{0}\|_{\ell_{1},\ell_{2}}\cap\mbox{\rm Im}\,\Phi^{*}$, i.e.,
$v\in(0,1)\times[-1,1]\cap\mbox{\rm Im}\,\\{(1,1,0),(1,0,-1)\\}$. It follows
that $v=(0,1,1)$ and thus $K=\\{3\\}$, $H=\emptyset$, which clearly implies
(5.44).

According to Theorem 5.3, Theorem 3.12, and Proposition 3.1, solution
uniqueness to group-sparsity problem (5.1) is equivalent to the robust
recovery with rate $\mathcal{O}(\sqrt{\delta})$.

######  Corollary 5.10 (Robust recovery and solution uniqueness for group-
sparsity problems).

The following statements are equivalent:

  1. (i)

$x_{0}$ is a unique solution to (5.1).

  2. (ii)

For sufficiently small $\delta>0$, any solution $x_{\delta}$ to problem (1.4)
with $J_{0}(\cdot)=\|\cdot\|_{\ell_{1}/\ell_{2}}$ satisfies
$\|x_{\delta}-x_{0}\|\leq\mathcal{O}(\sqrt{\delta})$ whenever
$\|y-y_{0}\|\leq\delta.$

  3. (iii)

For any $c_{1}>0$ and sufficiently small $\delta>0$, any solution $x_{\mu}$ to
(1.5) with $J_{0}(\cdot)=\|\cdot\|_{\ell_{1}/\ell_{2}}$ satisfies
$\|x_{\mu}-x_{0}\|\leq\mathcal{O}(\sqrt{\delta})$ whenever
$\|y-y_{0}\|\leq\delta$ and $\mu=c_{1}\delta$.

From Theorem 5.3, it is natural to raise the following question for other
decomposable norm minimization problem.

  1. (Q.3)

If $x_{0}$ is a unique solution to (1.2), can it be a strong solution to
(1.2)?

The answer to (Q.3) is affirmative for $\ell_{1}/\ell_{2}$ problem as in
Theorem 5.3. For the $\ell_{1}$ problem when
$\|\cdot\|_{\mathcal{A}}=\|\cdot\|_{1}$, we also have the positive answer due
to Corollary 4.13. However, it is not the case for the nuclear norm
minimization problem. The following example modifies [4, Example 3.1] to prove
that claim.

######  Example 5.11 (Difference between unique solution and strong solution
to NNM).

Consider the following optimization problem

$\min_{X\in\mathbb{R}^{2\times 2}}\|X\|_{*}\quad\text{such
that}\quad\Phi(X)\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\begin{pmatrix}X_{11}+X_{22}\\\
X_{12}-X_{21}+X_{22}\end{pmatrix}=\begin{pmatrix}1\\\ 0\end{pmatrix}.$ (5.45)

For any $X=\begin{pmatrix}a&b\\\ c&d\end{pmatrix}$ with $a+d=1$ and $b-c+d=0$,
we obtain from (4.45) that

$\|X\|_{*}=\sqrt{a^{2}+b^{2}+c^{2}+d^{2}+2|ad-
bc|}\geq\sqrt{|a+d|^{2}+|b-c|^{2}}\geq 1,$

where the equality occurs when $\|X\|_{*}=1$, $b-c=0$, $a+d=1$, and $b-c+d=0$,
which means $b=c$, $a=1$, $d=0$, and $\|X\|_{*}=\sqrt{1+b^{2}+c^{2}+2|bc|}=1$.
So $\overline{X}=\begin{pmatrix}1&0\\\ 0&0\end{pmatrix}$ is the unique
solution to problem (5.45). Choose
$X_{\varepsilon}=\begin{pmatrix}1-\varepsilon^{1.5}&\varepsilon-\varepsilon^{1.5}\\\
\varepsilon&\varepsilon^{1.5}\end{pmatrix}$ with $\varepsilon>0$ sufficiently
small and note that $X_{\varepsilon}$ satisfies the equation in (5.45). It
follows that

$\displaystyle\|X_{\varepsilon}\|_{*}-\|\overline{X}\|_{*}$
$\displaystyle=\displaystyle\sqrt{(1-\varepsilon^{1.5})^{2}+(\varepsilon-\varepsilon^{1.5})^{2}+\varepsilon^{2}+\varepsilon^{3}+2|(1-\varepsilon^{1.5})\varepsilon^{1.5}-(\varepsilon-\varepsilon^{1.5})\varepsilon|}-1$
$\displaystyle=\displaystyle\sqrt{(1-\varepsilon^{1.5})^{2}+(\varepsilon-\varepsilon^{1.5})^{2}+\varepsilon^{2}+\varepsilon^{3}+2(1-\varepsilon^{1.5})\varepsilon^{1.5}-2(\varepsilon-\varepsilon^{1.5})\varepsilon}-1$
$\displaystyle=\displaystyle\sqrt{1+\varepsilon^{3}}-1={\mathcal{O}}(\varepsilon^{3}).$

Moreover,
$\|X_{\varepsilon}-\overline{X}\|_{F}^{2}=\varepsilon^{3}+(\varepsilon-\varepsilon^{1.5})^{2}+\varepsilon^{2}+\varepsilon^{3}=O(\varepsilon^{2})$.
This tells us that $\overline{X}$ is not a strong solution to (5.45).

###  5.3 Connections between unique/strong solutions in the noiseless case

Let us consider the particular case of problem (4.33), which reads

$\min\Theta(x)\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}f(\Phi
x)+\mu\|D^{*}x\|_{\ell_{1}/\ell_{2}}$ (5.46)

with constant $\mu>0$. In the following result, we show that a unique solution
to (5.46) is also a strong solution. Consequently, all the characterizations
for solution uniqueness to (5.1) in this section can be used to characterize
unique/strong solutions to problem (5.46) due to Proposition 4.12. Moreover,
this result gives an affirmative answer for (Q.2) in the previous section.