# Solution uniqueness of convex optimization problems via the radial cone

Jalal Fadili111Normandie Université, ENSICAEN, UNICAEN, CNRS, GREYC, France;
email<EMAIL_ADDRESS>, Tran T. A. Nghia222Department of Mathematics
and Statistics, Oakland University, Rochester, MI 48309, USA; email:
<EMAIL_ADDRESS>, and Duy Nhat Phan333University of Dayton Research
Institute, University of Dayton, Dayton, OH 45469, USA;
<EMAIL_ADDRESS>
Abstract. In this paper, we mainly study solution uniqueness of some convex
optimization problems. Our characterizations of solution uniqueness are in
terms of the radial cone. This approach allows us to know when a unique
solution is a strong solution or even a tilt-stable one without checking
second-order information. Consequently, we apply our theory to low-rank
optimization problems. The radial cone is fully calculated in this case and
numerical experiments show that our characterizations are sharp.

##  1 Introduction

In many disciplines of science and engineering, solving the following linear
inverse problem is essential:

$\Phi x=y_{0},$ (1.1)

where $\Phi:\mathbb{X}\to\mathbb{Y}$ is a linear operator between two finite
dimensional vector spaces and $y_{0}=\Phi x_{0}$ is an element of
$\mathbb{Y}$. Particularly, in signal/image processing, $y_{0}$ is a known
observation of an unknown signal $x_{0}\in\mathbb{X}$ through the forward
linear operator $\Phi$. In regression in statistical learning, $y_{0}$ is the
response vector, $x_{0}\in\mathbb{X}$ is the unknown parameter vector, and
$\Phi$ is the design matrix. Recovering exactly the signal $x_{0}$ by solving
the linear system (1.1) through least-squares raises non-uniqueness issues, as
usually the dimension of $\mathbb{Y}$ is much smaller than the dimension of
$\mathbb{X}$, which makes (1.1) underdetermined and thus has infinitely many
solutions. On the other hand, the vector $x_{0}$ usually possesses some
special features (in the form of some low complexity) that cannot be captured
by naive least-squares. Thus, a form complexity regularization is necessary in
which the recovery of $x_{0}$ is cast as the regularized optimization problem:

$\min_{x\in\mathbb{X}}\quad g(x)\quad\mbox{subject to}\quad\Phi x=y_{0},$
(1.2)

where $g:\mathbb{X}\to\mathbb{R}$ is some particular function/regularizer,
which is chosen to promote the low complexity, i.e. the expected features, of
the original vector $x_{0}$. Solving this optimization problems narrows down
the possible candidate solutions for $x_{0}$. And if we want the solution of
(1.2) to be exactly $x_{0}$, it should hopefully be the unique solution. That
is one of the main reasons why solution uniqueness of problem (1.2) has drawn
much attention from different authors and research groups; see, e.g., [3, 9,
11, 13, 17, 18, 19, 20, 22, 24, 26, 36, 42, 45, 46, 50] for an incomplete
list. Although the regularizer $g$ can be nonconvex in many problems [3, 18],
in this paper we focus on the case when it is a continuous convex function.
Unlike system (1.1), problem (1.2) likely has a unique solution provided that
the number of observations, i.e., the dimension of $\mathbb{Y}$ is large
enough compared to some intrinsic dimension of $x_{0}$ (but still much smaller
than that of $\mathbb{X}$) [9, 11, 12].

Another optimization problem relative to (1.2) studied in our paper is

$\min_{x\in\mathbb{X}}\quad f(\Phi x)+g(x),$ (1.3)

where $f:\mathbb{Y}\to\overline{\mathbb{R}}$ is a proper lower semicontinuous
(l.s.c.) convex function that is twice differentiable with positive definite
Hessian in the interior of its domain. This problem is often used when there
is noise in the observation $y_{0}$ and the loss function $f$ measures the
error between $\Phi x$ and the noisy observation. An important class of
problems (1.2) and (1.3) in signal processing and machine learning is when $g$
is the $\ell_{1}$-norm in $\mathbb{X}=\mathbb{R}^{n}$, which is employed to
promote sparsity features of their optimal solutions. Solution uniqueness of
$\ell_{1}$-optimization is characterized by the so-called Nondegenerate Source
Condition and Restricted Injectivity of operator $\Phi$ [13, 19, 24, 46] or
the Null Space Property and its variants [17, 18]; see also [45, 50, 51, 22,
4] for different approaches and characterizations.

When $g$ is the $\ell_{1}/\ell_{2}$ norm in $\mathbb{X}=\mathbb{R}^{n}$ (also
known as the group Lasso regularizer), a popular regularizer in image
processing and statistics when the sparsity is structured in groups,
sufficient conditions for solution uniqueness of problem (1.2) were obtained
in [23, 41, 33, 42]. Full characterizations of this property for
$\ell_{1}/\ell_{2}$ optimization problems were recently established in [20]
via second-order variational analysis and the exact computation of the descent
cone of $\ell_{1}/\ell_{2}$ norm introduced in [9]. Another important class of
functions $g$ popular in matrix optimization is the nuclear norm
$\|\cdot\|_{*}$ in the space of matrices $\mathbb{X}=\mathbb{R}^{n_{1}\times
n_{2}}$. Problem (1.2) in this case is known as the nuclear norm minimization
problem:

$\min_{X\in\mathbb{R}^{n_{1}\times n_{2}}}\quad\|X\|_{*}\quad\mbox{subject
to}\quad\Phi X=Y_{0},$ (1.4)

where $\Phi:\mathbb{R}^{n_{1}\times n_{2}}\to\mathbb{R}^{m}$ is a linear
operator and $Y_{0}$ is a vector in $\mathbb{R}^{m}$. Employing the nuclear
norm enforces the low-rank property of optimal solutions that is required in
many matrix optimization problems; see, e.g., [10, 11, 12]. Sufficient
conditions for solution uniqueness of problem (1.4) play important roles in
obtaining a small bound on the number of measurements $m$ such that solving
problem (1.4) recovers exactly the solution $X_{0}$ [9, 11, 12]. Solution
uniqueness of this problem can be characterized via the descent cone in [9],
whose calculation is not known yet. Recently, [26] obtained a new
characterization for this property. Their condition is verifiable in low
dimensional spaces, but looks very complicated in higher dimensions. A
different characterization is derived in [32, Lemma 3.1] via the so-called
radial cone [6] of the nuclear norm; see also [27, Theorem 3.1] for a more
general class of gauge functions. However, this radial cone is not fully
calculated there and, according to the authors of [32], it is not easy to
check the corresponding characterization (possibly due to non-closedness of
the radial cone). Alternatively, those authors use the closure of the radial
cone, which is known as the tangent cone to check solution uniqueness. In the
recent paper [21], it is shown that using the tangent cone instead of the
radial cone can characterize strong minima [6] of problem (1.4).

Among three different ways of characterizing solution uniqueness of problem
(1.4) in [9, 32, 26] mentioned above, we argue that using the radial cone is
the simplest one. In this paper, we push this direction forward for general
problems (1.2) and (1.3) by providing more analysis, exact calculations of the
radial cone, numerical methods, and making interconnections with some other
advanced results for characterizing sharp minima [14, 38, 20], strong minima
[6, 21], as well as tilt stability [40, 37, 31].

#### Contributions

In Theorem 3.1, we show that $\bar{x}$ is the unique optimal solution of
problem (1.3) if and only if $\bar{y}=-\Phi^{*}\nabla
f(\Phi\bar{x})\in\partial g(\bar{x})$ and

$\mbox{\rm Ker}\,\Phi\cap\mathcal{R}_{(\partial
g)^{-1}(\bar{y})}(\bar{x})=\\{0\\},$ (1.5)

where $\mathcal{R}_{(\partial g)^{-1}(\bar{y})}$ is the radial cone at
$\bar{x}$ to the set $(\partial g)^{-1}(\bar{y})$ defined in Section 2. For
problem (1.2), we also have a similar result that $x_{0}$ is the unique
solution if and only if there exists a dual certificate $y\in\partial
g(x_{0})\cap\mbox{\rm Im}\,\Phi^{*}$ such that

$\mbox{\rm Ker}\,\Phi\cap\mathcal{R}_{(\partial g)^{-1}(y)}(x_{0})=\\{0\\}.$
(1.6)

This characterization was constructed in [32, Lemma 3.1] for the case of
nuclear norm minimization (1.4) and recently in [27, Theorem 3.1] for convex
gauge functions with some additional assumptions. Our results work for any
continuous convex functions $g$. Most importantly, we advance this approach in
the following ways:

  * •

We establish the connection between solution uniqueness and strong minima [6,
44] for problems (1.2) and (1.3). Obviously, a strong solution is a unique
solution for convex optimization problems. The opposite implication is not
true in general. But when $g$ is the $\ell_{1}/\ell_{2}$ norm, [20] recently
shows that unique solutions of problems (1.2) and (1.3) are also strong ones
via second-order analysis. It is not well-understood the reason why the
structure of $\ell_{1}/\ell_{2}$ norm can give such an equivalence. In this
paper, we have a clearer answer for this phenomenon. Closedness of the radial
cone plays an important role there. Indeed, we prove this equivalence in
Corollary 3.2 in the case when the function $g$ satisfies the quadratic growth
condition [6, 21] and the radial cone in (1.5) and (1.6) is closed; see also
Remark 4.7 for similar analysis on problem (1.2). This is quite a surprise
because usually one has to check second-order information for strong minima,
while our conditions (1.5) and (1.6) only use first-order information.

  * •

We unify the two approaches of using radial cones and descent cones for
solution uniqueness. As discussed above, solution uniqueness is also
characterized by descent cones introduced in [9]. In the recent paper [20,
Theorem 5.1], the descent cone of $\ell_{1}/\ell_{2}$ norm (and thus
$\ell_{1}$ norm) has an exact computation via its first-order information. We
generalize that result in this paper for any continuous convex function $g$.
Exact formulae of the descent cone via the radial cone and the critical cone
are provided in Proposition 4.2 and Proposition 4.4. These calculations allow
us to link up the two aforementioned approaches for solution uniqueness in
Theorem 4.5. Consequently, the descent cone of the nuclear norm is also
computed exactly in this paper.

  * •

We are able to apply our general theory to the nuclear norm minimization
problem (1.4). Although solution uniqueness of problem (1.2) was already
characterized in [32, Lemma 3.1] via the radial cone, it was not fully
calculated there. In Lemma 3.5, we provide a complete computation of this
radial cone via initial data. This leads us to a full characterization of
solution uniqueness for problem (1.4) in Corollary 4.8. Other interesting
connections of solution uniqueness with sharp minima [14, 38, 12, 20] and tilt
stability [40, 37, 31, 16] for nuclear norm minimization problems are also
obtained in Sections 3 and 4. One of our most exciting results is to show the
equivalence between solution uniqueness and tilt stability for problem (1.3)
in Corollary 3.10 under Nondegenerate Condition (a.k.a. Strict Complementary
Condition [6]) when $g$ is the nuclear norm. This implicitly indicates that
solution uniqueness makes problem (1.3) stable to be solved. Numerical
experiments on the nuclear norm minimization problem (4.12) in Section 5
confirm that our characterizations of solution uniqueness are sharp and
computationally friendly.

##  2 Preliminaries

Throughout this paper, let $\mathbb{X}$ be an Euclidean space and
$\mathbb{X}^{*}$ be its dual space endowed with the inner product $\langle
v,u\rangle$ for $v\in\mathbb{X}^{*}$ and $u\in\mathbb{X}$. Suppose that
$\|\cdot\|$ is the norm in $\mathbb{X}$ induced by the latter inner product.
We denote $\mathbb{B}_{r}(\bar{x})$ by the open ball with center
$\bar{x}\in\mathbb{X}$ and radius $r>0$. We first recall some notions and
classical results from convex analysis that will be important to our
exposition; see e.g. [43] for a comprehensive account.

Let $\Omega$ be a closed convex set in $\mathbb{X}$ and $\bar{x}\in\Omega$. We
write ${\rm cone}\,\Omega$ for the conic hull of $\Omega$ and ${\rm
aff}\,\Omega$ for the affine hull of $\Omega$. The relative interior of
$\Omega$ is denoted by

${\rm
ri}\,\Omega=\\{x\in\Omega|\;\exists\varepsilon>0,\mathbb{B}_{\varepsilon}(x)\cap{\rm
aff}\,\Omega\neq\emptyset\\};$

The radial cone (known also the cone of feasible directions) and the tangent
cone to $\Omega$ at $\bar{x}$ are defined, respectively, by

$\mathcal{R}_{\Omega}(\bar{x})={\rm
cone}\,(\Omega-\bar{x})=\mathbb{R}_{+}(\Omega-\bar{x})\quad\mbox{and}\quad\mathcal{T}_{\Omega}(\bar{x})=\overline{\mathcal{R}_{\Omega}(\bar{x})},$
(2.1)

which means that $\mathcal{T}_{\Omega}(\bar{x})$ is the topological closure of
the radial cone $\mathcal{R}_{\Omega}(\bar{x})$; see, e.g., [6, Definition
2.54 and Proposition 2.55]. When $\Omega$ is a polyhedral set, i.e., it can be
represented as the intersection of finitely many closed half spaces, the
radial cone is closed and thus is exactly the tangent cone at the same point
$\bar{x}\in\Omega$. But in general, the radial cone is not closed and strictly
smaller than the tangent cone.

Now let
$\varphi:\mathbb{X}\to\overline{\mathbb{R}}\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\mathbb{R}\cup\\{\infty\\}$ be a proper lower semi-continuous
(l.s.c.) convex function with nonempty domain $\mbox{\rm
dom}\,\varphi\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\\{x\in\mathbb{X}|\;\varphi(x)<\infty\\}.$ For $\bar{x}\in\mbox{\rm
dom}\,\varphi$, the subdifferential of $\varphi$ at $\bar{x}$ is defined by

$\partial\varphi(\bar{x})\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\\{v\in\mathbb{X}^{*}|\;\varphi(x)-\varphi(\bar{x})\geq\langle
v,x-\bar{x}\rangle,\forall x\in\mathbb{X}\\}.$

The Legendre-Fenchel conjugate of $\varphi$ is the l.s.c. convex function
$\varphi^{*}:\mathbb{X}^{*}\to\overline{\mathbb{R}}$ defined by

$\varphi^{*}(v)\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}\sup\\{\langle
v,x\rangle-\varphi(x)|\;x\in\mathbb{X}\\}\quad\mbox{for}\quad
v\in\mathbb{X}^{*}.$

Note that $v\in\partial\varphi(x)$ if and only if
$x\in\partial\varphi^{*}(v)$, i.e.,
$\partial\varphi^{*}(v)=(\partial\varphi)^{-1}(v)=\\{x\in
X|\;v\in\partial\varphi(x)\\}$, which plays an important role in our study
later in the paper. The directional derivative of $\varphi$ at $\bar{x}$ in
some direction $w\in\mathbb{X}$ is

$d\varphi(\bar{x})(w)\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\lim_{t\downarrow
0}\dfrac{\varphi(\bar{x}+tw)-\varphi(\bar{x})}{t}.$

If $\varphi$ is continuous around $\bar{x}$, it is well-known that

$d\varphi(\bar{x})(w)=\sup_{v\in\partial\varphi(\bar{x})}\langle v,w\rangle.$
(2.2)

The point $\bar{x}$ is called a minimizer or an optimal solution of the
following problem

$\min_{x\in\mathbb{X}}\quad\varphi(x),$ (2.3)

if $\varphi(x)\geq\varphi(\bar{x})$ for all $x\in\mathbb{X}$, i.e.,
$0\in\partial\varphi(\bar{x})$ or $\bar{x}\in\partial\varphi^{*}(0)$. We say
$\bar{x}$ is a unique (or strict) solution problem (2.3) if
$\varphi(x)>\varphi(\bar{x})$ for all $x\in\mathbb{X}\setminus\\{\bar{x}\\}$,
which means that $\\{\bar{x}\\}=\partial\varphi^{*}(0)$. Moreover, $\bar{x}$
is said to be a sharp solution if there exists some modulus $c>0$ such that

$\varphi(x)-\varphi(\bar{x})\geq c\|x-\bar{x}\|\quad\mbox{for all}\quad
x\in\mathbb{X}.$

The notion of sharp minima was introduced independently by Polyak [38] and
Crome [14] under the name strong uniqueness. On the other hand, $\bar{x}$ is a
strong solution if there exist $\varepsilon>0$ and modulus $\kappa>0$ such
that

$\varphi(x)-\varphi(\bar{x})\geq\frac{\kappa}{2}\|x-\bar{x}\|^{2}\quad\mbox{for
all}\quad x\in\mathbb{B}_{\varepsilon}(\bar{x}).$

The notion of strong minima is weaker than that of sharp minima. For instance,
the former is only a local property. We refer the readers to [6, 39, 44] for
different ways to characterize sharp/strong minima and their roles in
optimization.

Finally in this section, we recall the quadratic growth condition for
functions.

######  Definition 2.1 (Quadratic growth condition).

The convex function $\varphi$ is said to satisfy the quadratic growth
condition at $\bar{x}\in\mbox{\rm dom}\,\varphi$ for
$\bar{v}\in\partial\varphi(\bar{x})$ if there exist $\varepsilon>0$ and
modulus $\kappa>0$ such that

$\varphi(x)-\varphi(\bar{x})-\langle\bar{v},x-\bar{x}\rangle\geq\frac{\kappa}{2}{\rm
dist}\,(x;\partial\varphi^{*}(\bar{v}))^{2}\quad\mbox{for all}\quad
x\in\mathbb{B}_{\varepsilon}(\bar{x}).$ (2.4)

When the function $\varphi$ is convex, the quadratic growth condition is
equivalent to the _Łojasiewicz inequality with exponent $\frac{1}{2}$_ [5] and
the _metric subregularity of the subdifferential_ [2, 16, 49]. There are broad
classes of convex functions satisfying the quadratic growth condition such as
_piece-wise linear quadratic convex_ functions [44, Definition 10.20] and many
convex spectral functions [8]; see also [48] for some other ones.

##  3 Solution uniqueness of convex composite optimization problems

###  3.1 General regularizer

In this section we study the solution uniqueness of the following convex
composite optimization problem

$\min_{x\in\mathbb{X}}\quad\varphi(x)\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}f(\Phi x)+g(x),$ (3.1)

where $\Phi:\mathbb{X}\to\mathbb{Y}$ is a linear operator between two
Euclidean spaces, $f:\mathbb{Y}\to\overline{\mathbb{R}}$ is a proper l.s.c.
convex function that is differentiable in the interior of its domain, and
$g:\mathbb{X}\to\overline{\mathbb{R}}$ is a proper l.s.c. convex function with

$\Phi^{-1}\left({\rm int}\,(\mbox{\rm dom}\,f)\right)\cap\mbox{\rm
dom}\,g\neq\emptyset.$ (3.2)

Throughout this section, we have two additional standing assumptions on the
loss function $f$:

  1. (a)

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

  2. (b)

The Hessian $\nabla^{2}f(y)$ is positive definite for all $y\in{\rm
int}\,(\mbox{\rm dom}\,f)$, which implies that $f$ is strictly convex in the
interior of its domain.

The class of loss functions satisfying the above standing assumptions includes
strongly convex and twice continuously differentiable functions [48] together
with the discrete Kullback-Leiber divergence (known also as relative entropy)
[15] that have been used widely in statistical/machine learning and signal
processing.

Our first result establishes the characterization for solution uniqueness of
problem (3.1) via the radial cone.

######  Theorem 3.1 (Solution uniqueness via the radial cone).

Let $\bar{x}\in\Phi^{-1}\left({\rm int}\,(\mbox{\rm
dom}\,f)\right)\cap\mbox{\rm dom}\,g$ be an optimal solution of problem (3.1)
and $\bar{y}\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}-\Phi^{*}\nabla
f(\Phi\bar{x})\in\partial g(\bar{x})$. Then $\bar{x}$ is the unique solution
if and only if

$\mbox{\rm Ker}\,\Phi\cap\mathcal{R}_{\partial
g^{*}(\bar{y})}(\bar{x})=\\{0\\}.$ (3.3)

###### Proof.

Suppose that $\bar{x}$ is a unique solution of problem (3.1). Pick any
$w\in\mbox{\rm Ker}\,\Phi\cap\mathcal{R}_{\partial g^{*}(\bar{y})}(\bar{x})$,
we find some $t>0$ such that $\bar{x}+tw\in\partial g^{*}(\bar{y})$. As
$\partial g^{*}(\bar{y})$ is a convex set and $\bar{x}\in\partial
g^{*}(\bar{y})$, we have $\bar{x}+\alpha tw\in\partial g^{*}(\bar{y})$ for any
$\alpha\in(0,1)$. Since $\Phi^{-1}\left({\rm int}\,(\mbox{\rm dom}\,f)\right)$
is an open set containing $\bar{x}$, $\bar{x}+\alpha tw\in\Phi^{-1}({\rm
int}\,(\mbox{\rm dom}\,f))$ for sufficiently small $\alpha>0$. It follows that

$\partial\varphi(\bar{x}+\alpha tw)=\Phi^{*}\nabla f(\Phi(\bar{x}+\alpha
tw))+\partial g(\bar{x}+\alpha tw)=\Phi^{*}\nabla f(\Phi\bar{x})+\partial
g(\bar{x}+\alpha tw)\ni 0.$

Hence $\bar{x}+\alpha tw$ is an optimal solution of problem (3.1). Since
$\bar{x}$ is the unique solution of (3.1), we have $\bar{x}=\bar{x}+\alpha
tw$, i.e., $w=0$. This implies condition (3.3).

Conversely, suppose that condition (3.3) holds. Let $\tilde{x}$ be any optimal
solution of problem (3.1). It follows that the whole segment
$[\bar{x},\tilde{x}]$ belong to the solution set of (3.1). Setting
$w=\tilde{x}-\bar{x}$, there exists $t_{0}>0$ sufficiently small such that
$\bar{x}+t_{0}w\in\Phi^{-1}\left({\rm int}\,(\mbox{\rm dom}\,f)\right)$.
Moreover,

$-\Phi^{*}\nabla f(\Phi\bar{x})\in\partial g(\bar{x})\quad{\rm
and}\quad-\Phi^{*}\nabla f(\Phi(\bar{x}+t_{0}w))\in\partial
g(\bar{x}+t_{0}w).$ (3.4)

Due to the monotonicity of $\partial g$, we have

$0\leq\langle-\Phi^{*}\nabla f(\Phi(\bar{x}+t_{0}w))+\Phi^{*}\nabla
f(\Phi\bar{x}),t_{0}w\rangle=t_{0}\langle-\nabla
f(\Phi(\bar{x}+t_{0}w))+\nabla f(\Phi\bar{x}),\Phi w\rangle.$ (3.5)

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

$\langle\nabla f(\Phi(\bar{x}+t_{0}w))-\nabla f(\Phi\bar{x}),\Phi
w\rangle=t_{0}\int_{0}^{1}\langle\nabla^{2}f(\Phi(\bar{x}+tt_{0}w))\Phi w,\Phi
w\rangle dt.$ (3.6)

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

$\langle\nabla^{2}f(\Phi(\bar{x}+tt_{0}w))\Phi w,\Phi w\rangle\geq\mu\|\Phi
w\|^{2}$

for all $t\in[0,1]$. Combining this with (3.6) and (3.5) gives us that $\Phi
w=0$, i.e., $w\in\mbox{\rm Ker}\,\Phi.$ Observe from the inclusion (3.4) that

$\bar{y}=-\Phi^{*}\nabla f(\Phi\bar{x})=-\Phi^{*}\nabla
f(\Phi(\bar{x}+t_{0}w))\in\partial g(\bar{x}+t_{0}w),$

which implies that $\bar{x}+t_{0}w\in\partial g^{*}(\bar{y})$, i.e.,
$w\in\mathcal{R}_{\partial g^{*}(\bar{y})}(\bar{x})$. As condition (3.3) is
satisfied, we have $w=0$. Thus $\tilde{x}=\bar{x}$ which entails uniqueness of
$\bar{x}$. $\hfill\Box$

When the function $g$ additionally satisfies the quadratic growth condition in
Definition 2.1 at $\bar{x}$ for $\bar{y}=-\Phi^{*}\nabla f(\Phi\bar{x})$, the
recent paper [21, Corollary 3.4] shows that the following condition

$\mbox{\rm Ker}\,\Phi\cap\mathcal{T}_{\partial
g^{*}(\bar{y})}(\bar{x})=\\{0\\}$ (3.7)

characterizes strong minima at the optimal solution $\bar{x}$, where
$\mathcal{T}_{\partial g^{*}(\bar{y})}(\bar{x})$ is the tangent cone (2.1) to
$\partial g^{*}(\bar{y})$ at $\bar{x}$. As the tangent cone is the closure of
the radical cone. Condition (3.7) coincides with condition (3.3) when the
radial cone $\mathcal{R}_{\partial g^{*}(\bar{y})}(\bar{x})$ is closed. This
observation allows us to establish the equivalence between solution uniqueness
and strong minima for problem (3.1) in the following result.

######  Corollary 3.2 (Strong minima and solution uniqueness).

Suppose that $\bar{x}\in\Phi^{-1}\left({\rm int}\,(\mbox{\rm
dom}\,f)\right)\cap\mbox{\rm dom}\,g$ is an optimal solution of problem (3.1)
and the function $g$ satisfies the quadratic growth condition at $\bar{x}$ for
$\bar{y}=-\Phi^{*}\nabla f(\Phi\bar{x})$. Suppose further that the radial cone
$\mathcal{R}_{\partial g^{*}(\bar{y})}(\bar{x})$ is closed. Then $\bar{x}$ is
a strong solution of problem (3.1) if and only if it is a unique solution.

######  Remark 3.3 (Closedness of the radial cone).

The radial cone $\mathcal{R}_{\partial g^{*}(\bar{y})}(\bar{x})$ is closed if
and only if

$\mbox{\rm cone}\,\left(\partial g^{*}(\bar{y})-\bar{x}\right)\mbox{ is
closed}.$ (3.8)

This condition is automatic when $\partial g^{*}(\bar{y})$ is a polyhedral
set. A particular example of functions satisfying both (3.8) and the quadratic
growth condition in Corollary 3.2 is the class of convex piecewise linear-
quadratic functions [44, Definition 10.20], i.e., $\mbox{\rm dom}\,g$ is a
union of finitely many polyhedral sets, relative to each of which the function
$g(x)$ has a convex quadratic expression; see also [44, Proposition 10.21 and
Theorem 11.24]. This class of functions covers some important regularizers
such as $\ell_{1}$ (sparsity) norm, the anisotropic total variation, and the
elastic net regularizer widely used in optimization, statistical/machine
learning, and signal processing. The equivalence between solution uniqueness
and strong minima for this class was observed in [4]. That allows [4] to
obtain some new characterizations of solution uniqueness for $\ell_{1}$
optimization problems (Lasso in particular) by using second-order analysis for
strong minima, different from those in [19, 45, 50, 51, 22].

Another important regularizer that is not convex piecewise linear-quadratic is
the $\ell_{1}/\ell_{2}$ norm (a.k.a. group Lasso regularizer) defined by

$g(x)=\|x\|_{1,2}\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\sum_{J\in\mathcal{J}}\|x_{J}\|\quad\mbox{for}\quad
x\in\mathbb{X}=\mathbb{R}^{n},$ (3.9)

where $\mathcal{J}$ is a partition of $\\{1,2,\ldots,n\\}$ with $p$ distinct
groups. It is shown in [48] that $\partial g^{*}(\bar{y})$ is a polyhedral
set. Thus the radial cone $\mathcal{R}_{\partial g^{*}(\bar{y})}(\bar{x})$ is
also closed. It is also known that the $\ell_{1}/\ell_{2}$ norm satisfies the
quadratic growth condition at $\bar{x}$ for $\bar{y}$; see also [48]. By
Corollary 3.2 again, $\bar{x}$ is a strong solution of group Lasso problem
(3.1) if and only if it is a unique solution. This observation was obtained
recently in [20, Theorem 5.3] by a different approach via second-order
analysis and the computation of the descent cone of the $\ell_{1}/\ell_{2}$
norm.

Another situation where condition (3.8) holds is when the dual nondegeneracy
condition is satisfied in the sense that

$\bar{x}\in{\rm ri}\,\partial g^{*}(\bar{y}).$ (3.10)

Indeed, this condition means that $\mbox{\rm cone}\,\left(\partial
g^{*}(\bar{y})-\bar{x}\right)$ is the subspace in $\mathbb{X}$ parallel to
$\partial g^{*}(\bar{y})$, which is closed in finite dimension. $\triangle$

###  3.2 Nuclear norm case

We now study a major class of problem (3.1), the nuclear norm optimization
problem for low-rank matrix recovery:

$\min_{X\in\mathbb{R}^{n_{1}\times n_{2}}}\quad f(\Phi X)+\|X\|_{*},$ (3.11)

where $\Phi:\mathbb{R}^{n_{1}\times n_{2}}\to\mathbb{R}^{m}$ is a linear
operator ($n_{2}\geq n_{1}$), the function
$f:\mathbb{R}^{m}\to\overline{\mathbb{R}}$ is a proper l.s.c. convex function
satisfying the standing assumptions (a)-(b), and $g(X)=\|X\|_{*}$ is the
nuclear norm of $X\in\mathbb{R}^{n_{1}\times n_{2}}$, which is the sum of all
singular values of $X$. The dual norm of nuclear norm is known as the spectral
norm $\|X\|$, the largest singular value of $X$.

We work under the Forbenius inner product in $\mathbb{R}^{n_{1}\times n_{2}}$

$\langle X,Y\rangle={\rm Tr}\,(X^{T}Y)\quad\mbox{for all}\quad
X,Y\in\mathbb{R}^{n_{1}\times n_{2}},$

where ${\rm Tr}\,(\cdot)$ is the trace operator in $\mathbb{R}^{n_{1}\times
n_{2}}$. This induces the Frobenius norm in $\mathbb{R}^{n_{1}\times n_{2}}$
as follows

$\|X\|_{F}\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}\sqrt{\langle
X,X\rangle}=\sqrt{{\rm Tr}\,(X^{T}X)}\quad\mbox{for all}\quad
X\in\mathbb{R}^{n_{1}\times n_{2}}.$

We recall that for $\overline{X}\in\mathbb{R}^{n_{1}\times n_{2}}$, the
singular valued decomposition (SVD, in brief) of $\overline{X}$ reads

$\overline{X}=U\begin{pmatrix}\overline{\Sigma}_{r}&0\\\
0&0\end{pmatrix}_{n_{1}\times
n_{2}}V^{T}\quad\mbox{with}\quad\overline{\Sigma}_{r}=\begin{pmatrix}\sigma_{1}(\overline{X})&\dots&0\\\
\vdots&\ddots&\vdots\\\ 0&\ldots&\sigma_{r}(\overline{X})\end{pmatrix},$
(3.12)

where $r={\rm rank}\,(\overline{X})$, $U\in\mathbb{R}^{n_{1}\times n_{1}}$ and
$V\in\mathbb{R}^{n_{2}\times n_{2}}$ are orthogonal matrices, and
$\sigma_{i}(\overline{X})$ are the ordered positive singular values of
$\overline{X}$, i.e.
$\sigma_{1}(\overline{X})\geq\sigma_{2}(\overline{X})\geq\ldots\geq\sigma_{r}(\overline{X})>0$.
Denote $\mathcal{O}(\overline{X})$ by the set of all such pairs $(U,V)$
satisfying (3.12). We write $U=\begin{pmatrix}U_{I}&U_{J}\end{pmatrix}$ and
$V=\begin{pmatrix}V_{I}&V_{K}\end{pmatrix}$, where $U_{I}$ and $V_{I}$ are the
submatrices of the first $r$ columns of $U$ and $V$, respectively. It follows
from (3.12) that $\overline{X}=U_{I}\overline{\Sigma}_{r}V_{I}^{T}$, which is
known as a compact or reduced SVD of $\overline{X}$.

The subdifferential of the nuclear norm was computed in [47, Example 2]. The
subdifferential of its Legendre-Fenchel conjugate (i.e. the normal cone to the
spectral ball) was formalized in [48, Proposition 10], which can be obtained
from [47, Example 1] via classical convex analysis calculus, i.e. the formula
of the normal cone to a level set [43, Corollary 23.7.1]. We summarize these
results in the following lemma which plays an important role in our paper.

######  Lemma 3.4 (Subdifferentials of the nuclear norm and its conjugate).

The subdifferential of the nuclear norm at
$\overline{X}\in\mathbb{R}^{n_{1}\times n_{2}}$ is computed by

$\partial\|\overline{X}\|_{*}=\left\\{U\begin{pmatrix}\mathbb{I}_{r}&0\\\
0&W\end{pmatrix}V^{T}|\;\|W\|\leq 1\right\\}\quad\mbox{for
any}\quad(U,V)\in\mathcal{O}(\overline{X}).$ (3.13)

Moreover, $\overline{Y}\in\partial\|\overline{X}\|_{*}$ if and only if
$\|\overline{Y}\|\leq 1$ and

$\|\overline{X}\|_{*}=\langle\overline{Y},\overline{X}\rangle.$ (3.14)

Furthermore, for any
$\overline{Y}\in\mathbb{B}\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\\{Z\in\mathbb{R}^{n_{1}\times n_{2}}|\;\|Z\|\leq 1\\}$, we have

$\partial
g^{*}(\overline{Y})=U\begin{pmatrix}\mathbb{S}_{+}^{p(\overline{Y})}&0\\\
0&0\end{pmatrix}V^{T}\quad\mbox{for
any}\quad(U,V)\in\mathcal{O}(\overline{Y}),$ (3.15)

where $\mathbb{S}_{+}^{p}$ is the set of all $p\times p$ symmetric positive
semidefinite matrices and $p(\overline{Y})$ is defined by

$p(\overline{Y})\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\\#\\{i|\;\sigma_{i}(\overline{Y})=1\\}.$ (3.16)

Let $\overline{Y}\in\partial\|\overline{X}\|_{*}$ and
$(U,V)\in\mathcal{O}(\overline{X})$. Note from (3.13) that $\overline{Y}$ can
be written as

$\overline{Y}=U\begin{pmatrix}\mathbb{I}_{r}&0\\\
0&\overline{W}\end{pmatrix}V^{T}$ (3.17)

with some $\overline{W}\in\mathbb{R}^{(n_{1}-r)\times(n_{2}-r)}$ satisfying
$\|\overline{W}\|\leq 1$. Let
$(\widehat{U},\widehat{V})\in\mathcal{O}(\overline{W})$ and
$\widehat{U}\Sigma\widehat{V}^{T}$ be a full SVD of $\overline{W}$. We get
from (3.17) that

$\overline{Y}=\overline{U}\begin{pmatrix}\mathbb{I}_{r}&0\\\
0&\Sigma\end{pmatrix}\overline{V}^{T}\quad\mbox{with}\quad\overline{U}\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}(U_{I}\;U_{J}\widehat{U})\quad\mbox{and}\quad\overline{V}\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}(V_{I}\;V_{K}\widehat{V}).$ (3.18)

Observe that $\overline{U}^{T}\overline{U}=\mathbb{I}_{{n_{1}}}$ and
$\overline{V}^{T}\overline{V}=\mathbb{I}_{n_{2}}$. It follows that
$(\overline{U},\overline{V})\in\mathcal{O}(\overline{X})\cap\mathcal{O}(\overline{Y})$,
which means $\overline{X}$ and $\overline{Y}$ have simultaneous ordered SVD
[29, 30] with orthogonal pair $(\overline{U},\overline{V})$ in the sense that

$\overline{X}=\overline{U}({\rm
Diag}\,\sigma(\overline{X}))\overline{V}^{T}\qquad\mbox{and}\qquad\overline{Y}=\overline{U}({\rm
Diag}\,\sigma(\overline{Y}))\overline{V}^{T},$ (3.19)

where $\sigma(\overline{X})\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\left(\sigma_{1}(\overline{X}),\ldots,\sigma_{n_{1}}(\overline{X})\right)^{T}$
containing all the singular values of $\overline{X}$ in decreasing order and

${\rm Diag}\,\sigma(\overline{X})\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\begin{pmatrix}\sigma_{1}(\overline{X})&\ldots&0&0&\ldots&0\\\
0&\ddots&0&0&\ldots&0\\\
0&\ldots&\sigma_{n_{1}}(\overline{X})&0&\ldots&0\end{pmatrix}_{n_{1}\times
n_{2}}.$

In the spirit of Theorem 3.1, to study the solution uniqueness of problem
(3.11) we have to compute the radial cone of the nuclear norm. Its explicit
formula below is helpful for further studies in this paper and also for the
numerical experiments when checking solution uniqueness in Section 5.

######  Lemma 3.5.

Let $\overline{Y}\in\partial\|\overline{X}\|_{*}$. Suppose that $\overline{X}$
and $\overline{Y}$ have the simultaneous ordered SVD with an orthogonal matrix
pair $(U,V)\in\mathcal{O}(\overline{X})\cap\mathcal{O}(\overline{Y})$. Then we
have

$\mathcal{R}_{\partial
g^{*}(\overline{Y})}(\overline{X})=\left\\{U\begin{pmatrix}A&BC&0\\\
C^{T}B^{T}&C&0\\\ 0&0&0\end{pmatrix}V^{T}\in\mathbb{R}^{n_{1}\times
n_{2}}|\;A\in\mathbb{S}^{r},B\in\mathbb{R}^{r\times(p-r)},C\in\mathbb{S}_{+}^{p-r}\right\\},$
(3.20)

where $\mathbb{S}^{r}$ is the set of $r\times r$ symmetric matrices,
$r=\mbox{\rm rank}\,(\overline{X})$ and $p=p(\overline{Y})$ is defined in
(3.16).

Proof. To verify the inclusion “$\subset$” in (3.20), pick any
$W\in\mathcal{R}_{\partial
g^{*}(\overline{Y})}(\overline{X})\setminus\\{0\\}$. Thus, there exists
$\nu>0$ such that $\overline{X}+\nu W\in\partial g^{*}(\overline{Y})$. By
formulae (3.12) and (3.15), there exist $A\in\mathbb{S}^{r}$,
$D\in\mathbb{R}^{r\times(p-r)}$, and $C\in\mathbb{S}^{p-r}_{+}$ such that
$W=U\begin{pmatrix}A&D&0\\\ D^{T}&C&0\\\ 0&0&0\end{pmatrix}V^{T}$. As
$\partial g^{*}(\overline{Y})$ is a convex set and $\overline{X}\in\partial
g^{*}(\overline{Y})$, we have $\overline{X}+tW\in\partial g^{*}(\overline{Y})$
for any $t\in(0,\nu)$. If follows from (3.15) that

$\begin{pmatrix}\overline{\Sigma}_{r}+tA&tD\\\
tD^{T}&tC\end{pmatrix}\in\mathbb{S}^{p}_{+}.$ (3.21)

Let $\lambda_{\min}:\mathbb{S}^{r}\to\mathbb{R}$ be the smallest eigenvalue
function. It is well-known that this function is $1$-Lipschitz continuous with
respect to the Frobenius norm. As
$\lambda_{\min}(\overline{\Sigma}_{r})=\sigma_{r}(\overline{X})>0$, we have
$\lambda_{\min}(\overline{\Sigma}_{r}+tA)>0$ for all
$t\in[0,\lambda_{\min}(\overline{\Sigma}_{r})/\|A\|_{F})$, i.e., the matrix
$\overline{\Sigma}_{r}+tA$ is positive definite or
$\overline{\Sigma}_{r}+tA\succ 0$ for all such $t$. We then get by the Schur
complement that

$\begin{pmatrix}\overline{\Sigma}_{r}+tA&tD\\\ tD^{T}&tC\end{pmatrix}\succeq
0\quad\mbox{iff}\quad C-tD^{T}(\overline{\Sigma}_{r}+tA)^{-1}D\succeq 0;$
(3.22)

see also [25, Theorem 7.7.6 and its proof]. For any $x\in\mbox{\rm Ker}\,C$,
we derive from (3.21) and (3.22) that

$0\leq
x^{T}\left(C-tD^{T}(\overline{\Sigma}_{r}+tA)^{-1}D\right)x=-tx^{T}D^{T}(\overline{\Sigma}_{r}+tA)^{-1}Dx,$

which implies $Dx=0$ as $\overline{\Sigma}_{r}+tA\succ 0$; i.e. $\mbox{\rm
Ker}\,C\subset\mbox{\rm Ker}\,D$. Define
$\mathcal{X}\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\\{GC|\;G\in\mathbb{R}^{r\times(p-r)}\\}$, a subspace of
$\mathbb{R}^{r\times(p-r)}$. We show next that $D\in\mathcal{X}$. Indeed, by
contradiction suppose that $D\notin\mathcal{X}$, it follows from the
separation theorem that there exists a matrix $H\in\mathbb{R}^{r\times(p-r)}$
such that

$\mbox{\rm Tr}\,(DH^{T})=\langle
D,H\rangle<0=\min_{G\in\mathbb{R}^{r\times(p-r)}}\langle
GC,H\rangle=\min_{G\in\mathbb{R}^{r\times(p-r)}}\mbox{\rm
Tr}\,(C^{T}G^{T}H)=\min_{G\in\mathbb{R}^{r\times(p-r)}}\mbox{\rm
Tr}\,(G^{T}HC^{T}),$ (3.23)

which implies that $HC^{T}=0$, i.e., $CH^{T}=0$. Thus each row of $H$ is a
vector in $\mbox{\rm Ker}\,C$, which implies that $DH^{T}=0$ since we have
shown just before that $\mbox{\rm Ker}\,C\subset\mbox{\rm Ker}\,D$. But this
contradicts (3.23). Thus $D\in\mathcal{X}$, i.e., there exists
$B\in\mathbb{R}^{r\times(p-r)}$ such that $D=BC$. This verifies the inclusion
“$\subset$” in (3.20).

To justify the converse inclusion “$\supset$” in (3.20), pick any
$W=U\begin{pmatrix}A&BC&0\\\ C^{T}B^{T}&C&0\\\
0&0&0\end{pmatrix}V^{T}\in\mathbb{R}^{n_{1}\times n_{2}}$ with
$A\in\mathbb{S}^{r}$, $B\in\mathbb{R}^{r\times(p-r)}$, and
$C\in\mathbb{S}_{+}^{p-r}$. Again, arguing as above, we have
$\lambda_{\min}(\overline{\Sigma}_{r}+tA)>0$ for all $t>0$ small enough,
meaning that $\overline{\Sigma}_{r}+tA$ is nonsingular. According to the Schur
complement (3.22) and formula (3.15) again, $\overline{X}+tW\in\partial
g^{*}(\overline{Y})$ if and only if

$C-tC^{T}B^{T}(\overline{\Sigma}_{r}+tA)^{-1}BC\succeq 0.$

As $C\in\mathbb{S}^{p}_{+}$, it is diagonalizable. Hence we may write
$C=Z\begin{pmatrix}\Lambda&0\\\ 0&0\end{pmatrix}Z^{T}$ with
$\Lambda\in\mathbb{R}^{s\times s}$ being a diagonal matrix of positive
eigenvalues of $C$ for some $s\leq p-r$ and
$Z\in\mathbb{R}^{(p-r)\times(p-r)}$ being an orthogonal matrix. It follows
that $C-tC^{T}B^{T}(\overline{\Sigma}_{r}+tA)^{-1}BC\succeq 0$ if and only if

$0\preceq\begin{pmatrix}\Lambda&0\\\
0&0\end{pmatrix}-t\begin{pmatrix}\Lambda&0\\\
0&0\end{pmatrix}Z^{T}B^{T}(\overline{\Sigma}_{r}+tA)^{-1}BZ\begin{pmatrix}\Lambda&0\\\
0&0\end{pmatrix}=\begin{pmatrix}\Lambda-t\Lambda M_{t}\Lambda&0\\\
0&0\end{pmatrix},$ (3.24)

where $M_{t}\in\mathbb{R}^{s\times s}$ is the submatrix of the positive
semidefinite matrix $Z^{T}B^{T}(\overline{\Sigma}_{r}+tA)^{-1}BZ$ with the
same position as $\Lambda$ in $\begin{pmatrix}\Lambda&0\\\ 0&0\end{pmatrix}$.
As $\overline{\Sigma}_{r}\succ 0$, $Z^{T}B^{T}(\Sigma_{0}+tA)^{-1}BZ$ and
$M_{t}$ are continuous mappings with respect to $t$ around $0$. Since $M_{t}$
is symmetric, we can choose $t>0$ small enough such that $\Lambda-t\Lambda
M_{t}\Lambda\succeq 0$. Thus condition (3.24) is valid, which implies
$C-tC^{T}B^{T}(\overline{\Sigma}_{r}+tA)^{-1}BC\succeq 0$. This together with
the Schur complement (3.22) and formula (3.15) tells us that
$X_{0}+tW\in\partial g^{*}(\overline{Y})$, which implies
$W\in\mathcal{R}_{\partial g^{*}(\overline{Y})}(\overline{X})$. The proof is
complete. $\hfill\Box$

The following result is a direct consequence of Theorem 3.1 and formula (3.20)
of the radial cone.

######  Corollary 3.6 (Solution uniqueness of low-rank optimization problems).

Suppose that $\overline{X}$ is an optimal solution of problem (3.11) with
$\overline{X}\in\Phi^{-1}({\rm int}\,(\mbox{\rm dom}\,f))$ and
$\overline{Y}\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}-\Phi^{*}\nabla
f(\Phi\overline{X})\in\partial\|\overline{X}\|_{*}$. Then $\overline{X}$ is
the unique solution of problem (3.11) if and only if

$\Phi\left(\overline{U}\begin{pmatrix}A&BC&0\\\ C^{T}B^{T}&C&0\\\
0&0&0\end{pmatrix}\overline{V}^{T}\right)=0~{}\mbox{with}~{}A\in\mathbb{S}^{r},B\in\mathbb{R}^{r\times(p-r)},C\in\mathbb{S}_{+}^{p-r}\quad\Longrightarrow\quad
A=C=0,$ (3.25)

where the pair
$(\overline{U},\overline{V})\in\mathcal{O}(\overline{X})\cap\mathcal{O}(\overline{Y})$
is from (3.19), $r={\rm rank}\,(\overline{X})$, and $p=p(\overline{Y})$ from
(3.16).

######  Remark 3.7 (Closedness of the radial cone for the nuclear norm).

As the nuclear norm satisfies the quadratic growth condition [8, 48],
Corollary 3.2 tells us that $\overline{X}$ is a unique solution of problem
(3.11) if and only if it is a strong solution provided that the radial cone
$\mathcal{R}_{\partial g^{*}(\overline{Y})}(\overline{X})$ is closed. Note
that its closure is the tangent cone (2.1) computed in [21, Corollary 4.2]

$\mathcal{T}_{\partial
g^{*}(\overline{Y})}(\overline{X})=\left\\{\overline{U}\begin{pmatrix}A&B&0\\\
B^{T}&C&0\\\ 0&0&0\end{pmatrix}\overline{V}^{T}\in\mathbb{R}^{n_{1}\times
n_{2}}|\;A\in\mathbb{S}^{r},B\in\mathbb{R}^{r\times(p-r)},C\in\mathbb{S}_{+}^{p-r}\right\\};$
(3.26)

see also [32, Lemma 2.3 and Proposition 2.1] for a different computation and
approach. If $p=r$, it is obvious that

$\mathcal{R}_{\partial
g^{*}(\overline{Y})}(\overline{X})=\mathcal{T}_{\partial
g^{*}(\overline{Y})}(\overline{X})=\overline{U}\begin{pmatrix}\mathbb{S}^{r}&0\\\
0&0\end{pmatrix}\overline{V}^{T},$

which implies that the radial cone $\mathcal{R}_{\partial
g^{*}(\overline{Y})}(\overline{X})$ is closed in this case.

If $p>r$, we show next that the radial cone $\mathcal{R}_{\partial
g^{*}(\overline{Y})}(\overline{X})$ is not closed. Indeed, pick

$W_{k}=\overline{U}\begin{pmatrix}0&\mathbb{E}&0\\\
\mathbb{E}^{T}&\frac{1}{k}\mathbb{I}_{p-r}&0\\\
0&0&0\end{pmatrix}\overline{V}^{T}\to
W=\overline{U}\begin{pmatrix}0&\mathbb{E}&0\\\ \mathbb{E}^{T}&0&0\\\
0&0&0\end{pmatrix}\overline{V}^{T}$

as $k\to\infty$, where $\mathbb{E}\in\mathbb{R}^{r\times(p-r)}$ is the matrix
of all entries $1$ and $\mathbb{I}_{p-r}$ is the $(p-r)\times(p-r)$ identity
matrix. Note that $W_{k}\in\mathcal{R}_{\partial
g^{*}(\overline{Y})}(\overline{X})$, but $W\notin\mathcal{R}_{\partial
g^{*}(\overline{Y})}(\overline{X})$. Hence the radial cone
$\mathcal{R}_{\partial g^{*}(\overline{Y})}(\overline{X})$ is not closed. This
situation is very different from the case when the regularizer $g$ is
$\ell_{1}/\ell_{2}$ norm when the corresponding radial cone is always closed;
see Remark 3.3.

Thus the radial cone $\mathcal{R}_{\partial
g^{*}(\overline{Y})}(\overline{X})$ is closed if and only if $p=r$. This is
the case of dual nondegeneracy condition (3.10) discussed in Remark 3.3.
Indeed, note from (3.15) that

${\rm ri}\,(\partial
g^{*}(\overline{Y}))=\overline{U}\begin{pmatrix}\mathbb{S}_{++}^{p}&0\\\
0&0\end{pmatrix}\overline{V}^{T},$ (3.27)

where $\mathbb{S}_{++}^{p}$ is the set of all symmetric and positive definite
$p\times p$ matrices. As
$\overline{X}=\overline{U}\begin{pmatrix}\overline{\Sigma}_{r}&0\\\
0&0\end{pmatrix}\overline{V}^{T}$, $p=r$ if and only if $\overline{X}\in{\rm
ri}\,(\partial g^{*}(\overline{Y}))$. Note further from (3.13) that

${\rm
ri}\,(\partial\|\overline{X}\|_{*})=\left\\{U\begin{pmatrix}\mathbb{I}_{r}&0\\\
0&W\end{pmatrix}V^{T}|\;\|W\|<1\right\\}.$

Thus, the case $p=r$ is also equivalent to the nondegeneracy condition

$\overline{Y}\in{\rm ri}\,(\partial\|\overline{X}\|_{*}).$ (3.28)

Consequently, the radial cone $\mathcal{R}_{\partial
g^{*}(\overline{Y})}(\overline{X})$ is closed if and only if the nondegeneracy
condition (3.28) is satisfied. $\triangle$

######  Remark 3.8 (Checking condition (3.25) via optimization).

Condition (3.25) means that the following optimization problem

$\max\;\frac{1}{2}\|A\|^{2}_{F}+\frac{1}{2}\|C\|_{F}^{2}\;\;\mbox{s.t.}\;\;\Phi\left(\overline{U}\begin{pmatrix}A&BC&0\\\
C^{T}B^{T}&C&0\\\
0&0&0\end{pmatrix}\overline{V}^{T}\right)=0,A\in\mathbb{S}^{r},B\in\mathbb{R}^{r\times(p-r)},C\in\mathbb{S}_{+}^{p-r}$

has global maximum value $0$ and global maximizers
$(0,\overline{B},0)\in\mathbb{S}^{r}\times\mathbb{R}^{r\times(p-r)}\times\mathbb{S}_{+}^{p-r}$
for any $\overline{B}$. This is a nonlinear concave optimization problem.
Unfortunately, most of available solvers will provide local maximizers.
However, if
$(0,\overline{B},0)\in\mathbb{S}^{r}\times\mathbb{R}^{r\times(p-r)}\times\mathbb{S}_{+}^{p-r}$
are local maximizers for any $\overline{B}$, then $0$ is the global maximum
value. Indeed, suppose that
$(A,B,C)\in\mathbb{S}^{r}\times\mathbb{R}^{r\times(p-r)}\times\mathbb{S}_{+}^{p-r}$
satisfies the first equality in (3.25), hence is a feasible point of the above
optimization problem. We observe that $(tA,B,tC)$ is also feasible for any
$t\neq 0$. By choosing sufficiently small $|t|>0$, $(tA,B,tC)$ is in a small
neighborhood of $(0,B,0)$. If $(0,B,0)$ is a local maximizer of the above
optimization problem, we have

$t^{2}\|A\|^{2}_{F}+t^{2}\|C\|^{2}_{F}\leq 0,$

which implies $A=0$ and $C=0$. Hence $0$ is the global maximum value.
$\triangle$

######  Corollary 3.9 (Strong minima vs solution uniqueness).

Let $\overline{X}\in\Phi^{-1}({\rm int}\,(\mbox{\rm dom}\,f))$ be an optimal
solution of problem (3.11). Suppose that Nondegeneracy Condition (3.28) is
satisfied. Then $\overline{X}$ is a unique solution of problem (3.11) if and
only if it is a strong solution.

###### Proof.

Suppose that Nondegeneracy Condition (3.28) is satisfied. As discussed at the
end of Remark 3.7, the radial cone $\mathcal{R}_{\partial
g^{*}(\overline{Y})}(\overline{X})$ is closed. Note also that the nuclear norm
satisfies the quadratic growth condition (2.4) by [48, 8]. By Corollary 3.2,
$\overline{X}$ is a unique solution of problem (3.11) if and only if it is a
strong solution. $\hfill\Box$

When Nondegeneracy Condition (3.28) is satisfied, it follows from [31, Theorem
6.3] that $\overline{X}$ is a strong solution of problem (3.11) if and only if
it is a tilt stable solution of in the sense that the optimal solution set

$S(V)\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}{\rm
argmin}\quad\\{f(\Phi X)+\|X\|_{*}-\langle
V,X\rangle|\;X\in\mathbb{R}^{n_{1}\times n_{2}}\\}\quad\mbox{for}\quad
V\in\mathbb{R}^{n_{1}\times n_{2}}$

is single-valued and Lipschitz continuous around $0$ with
$S(0)=\\{\overline{X}\\}$; see also the recent result [28, Corollary 3.10] for
similar equivalence. Tilt stability was introduced by Poliquin and Rockafellar
[40] for general optimization frameworks. This important stability is
characterized in [40] via the generalized Hessian/second-order limiting
subdifferential introduced by Mordukhovich [34]; see also [2, 16] for
different characterizations for tilt stability. Although the second-order
limiting subdifferential has rich calculus [35, 37], its computation is
nontrivial in many situations including the nuclear norm function in (3.11).
By combining Corollary 3.9 with the aforementioned [31, Theorem 6.3] we obtain
below the equivalence between solution uniqueness and tilt stability for
problem (3.11) under Nondegeneracy Condition (3.28). This equivalence is
interesting, as we see that the assumption of solution uniqueness is already
included in the definition of tilt stability ($S(0)=\\{\overline{X}\\})$.
Somewhat Nondegeracy Condition (3.28) makes the problem stable.

######  Corollary 3.10 (Solution uniqueness and tilt stability).

Suppose that $\overline{X}\in\Phi^{-1}({\rm int}\,(\mbox{\rm dom}\,f))$ is an
optimal solution of problem (3.11) and that Nondegeneracy Condition (3.28)
holds. Then $\overline{X}$ is a tilt-stable solution if and only if it is the
unique solution.

##  4 Solution uniqueness of convex optimization problems with linear
constraints

###  4.1 General regularizer

In this section, we study solution uniqueness of the optimization problem
(1.2)

$\min_{x\in\mathbb{X}}\quad g(x)\quad\mbox{subject to}\quad\Phi x=y_{0},$
(4.1)

where $g:\mathbb{X}\to\mathbb{R}$ is a continuous convex function,
$\Phi:\mathbb{X}\to\mathbb{Y}$ is still a linear operator between two
Euclidean spaces, and $y_{0}$ is a vector in $\mathbb{Y}$. Suppose that
$x_{0}$ is a feasible solution of problem (4.1), i.e., $\Phi x_{0}=y_{0}$.
Solution uniqueness of this problem can be characterized via the so-called
descent cone [9, Proposition 2.1] recalled below.

######  Definition 4.1 (Descent cone [9]).

The descent cone at $x_{0}$ is defined by

$\mathcal{D}_{g}(x_{0})\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}{\rm
cone}\,\\{x-x_{0}|\;g(x)\leq g(x_{0})\\}.$ (4.2)

When $g$ is a polyhedral convex function, the set $\\{x-x_{0}|\;g(x)\leq
g(x_{0})\\}$ is polyhedral and thus $\mathcal{D}_{g}(x_{0})$ is a closed
convex cone. But it is not closed in general; see, e.g., [20, Example 4.3] for
the case of $\ell_{1}/\ell_{2}$ norm. Note that the closure of the descent
cone lies in the critical cone defined by

$\mathcal{C}(x_{0})=\\{w\in\mathbb{X}|\;dg(x_{0})(w)\leq 0\\}$ (4.3)

and the interior of the critical cone is a subset of the descent cone; see,
e.g., [20, Lemma 3.6]. Hence the differences between them are on the boundary
of $\mathcal{C}(x_{0})$ denoted by ${\rm bd}\,\mathcal{C}(x_{0})$. In the
recent paper [20, Theorem 5.1], the descent cone of the $\ell_{1}/\ell_{2}$
norm is computed exactly via the critical cone and first-order information.
Here, we extend that result to the case of general continuous convex function
by involving the radical cone.

######  Proposition 4.2 (Descent cone via radial cone).

Suppose that $g:\mathbb{X}\to\mathbb{R}$ is a continuous convex function. The
descent cone $D_{g}(x_{0})$ in (4.2) is computed by

$D_{g}(x_{0})=\bigcup_{y\in\partial g(x_{0})}\left[\mathcal{R}_{\partial
g^{*}(y)}(x_{0})\cap{\rm bd}\,\mathcal{C}(x_{0})\right]\cup({\rm
int}\,\mathcal{C}(x_{0})).$ (4.4)

###### Proof.

Let us start to prove the inclusion “$\subset$” in (4.4). Pick any $w\in
D_{g}(x_{0})$, there exists some $\tau>0$ such that $g(x_{0}+\tau w)\leq
g(x_{0})$. As the function $g$ is convex and continuous, we derive from (2.2)
that

$0\geq g(x_{0}+\tau w)-g(x_{0})\geq\tau\max_{y\in\partial g(x_{0})}\langle
y,w\rangle=\tau dg(x_{0})(w),$ (4.5)

which implies that $dg(x_{0})(w)\leq 0$. Note further that $dg(x_{0})(\cdot)$
is also a proper convex and continuous function. It follows that

${\rm int}\,\mathcal{C}(x_{0})=\\{u\in\mathbb{X}|\;dg(x_{0})(u)<0\\}.$

If $dg(x_{0})(w)<0$, we have $w\in{\rm int}\,\mathcal{C}(x_{0})$. If
$dg(x_{0})(w)=0$, i.e., $w\in{\rm bd}\,\mathcal{C}(x_{0})$ (the boundary of
$\mathcal{C}(x_{0})$), note from (4.5) that $g(x_{0}+\tau w)=g(x_{0})$ and
there exists some $y\in\partial g(x_{0})$ such that $\langle y,w\rangle=0$.
Hence we have

$g(x_{0}+\tau w)=g(x_{0})=\langle y,x_{0}\rangle-g^{*}(y)=\langle y,x_{0}+\tau
w\rangle-g^{*}(y),$

which implies that $y\in\partial g(x_{0}+\tau w)$, i.e., $x_{0}+\tau
w\in\partial g^{*}(y)$. It follows that $w\in\mathcal{R}_{\partial
g^{*}(y)}(x_{0})$. The inclusion “$\subset$” in (4.4) is verified.

To justify the converse inclusion “$\supset$” in (4.4), we pick any $w$ in the
right-hand side. If $w\in{\rm int}\,\mathcal{C}(x_{0})$, i.e.,
$dg(x_{0})(w)<0$, there exists some $\tau>0$ sufficiently small so that

$g(x_{0}+\tau w)-g(x_{0})\leq 0,$

which means $w\in\mathcal{D}_{g}(x_{0})$. If $w\in{\rm
bd}\,\mathcal{C}(x_{0})$, i.e., $dg(x_{0})(w)=0$, there exists some
$y\in\partial g(x_{0})$ such that $w\in\mathcal{R}_{\partial
g^{*}(y)}(x_{0})$. We find some $t>0$ such that $x_{0}+tw\in\partial
g^{*}(y)$. It follows that

$g(x_{0}+tw)=\langle y,x_{0}+tw\rangle-g^{*}(y)=g(x_{0})+t\langle
y,w\rangle\leq g(x_{0})+tdg(x_{0})(w)=g(x_{0}),$

which also implies that $w\in\mathcal{D}_{g}(\bar{x})$. This verifies the
inclusion “$\supset$” in (4.4). $\hfill\Box$

The following result taken from [9, Proposition 2.1] is the well-known
characterization of solution uniqueness via the descent cone.

######  Proposition 4.3 (Descent cone for solution uniqueness [9]).

A feasible point $x_{0}$ of problem (4.1) is the unique solution if and only
if

$\mbox{\rm Ker}\,\Phi\cap\mathcal{D}_{g}(x_{0})=\\{0\\}.$

The exact computation of the descent cone (4.4) gives the impression that it
is a big and complicated set. But its intersection with $\mbox{\rm Ker}\,\Phi$
seems to be small and simple as in the above result. We enhance this
observation by providing next the calculation of this intersection when
$x_{0}$ is an optimal solution, which means $0\in\partial g(x_{0})+\mbox{\rm
Im}\,\Phi^{*}$, i.e.,

$\Delta(x_{0})\stackrel{{\scriptstyle\text{\rm\tiny def}}}{{=}}\partial
g(x_{0})\cap\mbox{\rm Im}\,\Phi^{*}\neq\emptyset.$ (4.6)

This is known as the Source Condition [24]. An element of $\Delta(x_{0})$ is
called a dual certificate.

######  Proposition 4.4.

Let $x_{0}$ be an optimal solution of problem (4.1). Then we have

$\mbox{\rm Ker}\,\Phi\cap\mathcal{D}_{g}(x_{0})=\mbox{\rm
Ker}\,\Phi\cap\mathcal{R}_{\partial g^{*}(y)}(x_{0})\quad\mbox{for any}\quad
y\in\Delta(x_{0}).$ (4.7)

###### Proof.

As $x_{0}$ is an optimal solution of problem (4.1),
$\Delta(x_{0})\neq\emptyset$. Pick any dual certificate $y\in\Delta(x_{0})$.
To justify the “$\subset$” inclusion in (4.7), take any $w\in\mbox{\rm
Ker}\,\Phi\cap\mathcal{D}_{g}(x_{0})$, we find some $\tau>0$ such that
$g(x_{0}+\tau w)\leq g(x_{0})$. Since $\Phi(x_{0}+\tau w)=\Phi x_{0}=y_{0}$,
we have $g(x_{0}+\tau w)=g(x_{0})$. Note also that $\langle y,w\rangle=0$ as
$y\in\mbox{\rm Im}\,\Phi^{*}$ and $w\in\mbox{\rm Ker}\,\Phi$. It follows that

$g(x_{0}+\tau w)=g(x_{0})=\langle y,x_{0}\rangle-g^{*}(y)=\langle y,x_{0}+\tau
w\rangle-g^{*}(y),$

which implies that $x_{0}+\tau w\in\partial g^{*}(y)$, i.e.,
$w\in\mathcal{R}_{\partial g^{*}(y)}(x_{0})$. This verifies inclusion
“$\subset$” in (4.7).

Conversely, pick any $w\in\mbox{\rm Ker}\,\Phi\cap\mathcal{R}_{\partial
g^{*}(y)}(x_{0})$. We find $t>0$ such that $x_{0}+tw\in\partial g^{*}(y)$. It
follows that

$g(x_{0}+tw)=\langle y,x_{0}+tw\rangle-g^{*}(y)=\langle
y,x_{0}\rangle-g^{*}(y)=g(x_{0}),$

which implies $w\in\mathcal{D}_{g}(x_{0})$ and verifies the converse inclusion
“$\supset$” in (4.7). $\hfill\Box$

Combining this result with Proposition 4.3, we obtain a characterization of
solution uniqueness for problem (4.1) via the radical cone, which is similar
to Theorem 3.1 in Section 3.

######  Theorem 4.5 (Characterizations for solution uniqueness via radial
cones).

The following are equivalent:

  * (i)

$x_{0}$ is a unique optimal solution of problem (4.1).

  * (ii)

Source Condition (4.6) holds and for any dual certificate $y\in\Delta(x_{0})$,
one has

$\mbox{\rm Ker}\,\Phi\cap\mathcal{R}_{\partial g^{*}(y)}(x_{0})=\\{0\\}.$
(4.8)

  * (iii)

Source Condition (4.6) holds and there exists a dual certificate
$\bar{y}\in\Delta(x_{0})$ such that

$\mbox{\rm Ker}\,\Phi\cap\mathcal{R}_{\partial
g^{*}(\bar{y})}(x_{0})=\\{0\\}.$ (4.9)

Proof. Let us start by proving the implication [(i)$\Longrightarrow$(ii)] by
supposing that $x_{0}$ is a unique optimal solution of problem (4.1). Hence
Source Condition (4.6) holds. Moreover, (4.8) comes from Proposition 4.3 and
Proposition 4.4. This verifies (ii).

The implication [(ii)$\Longrightarrow$(iii)] is trivial. Let us justify
[(iii)$\Longrightarrow$(i)] by supposing that there exists some
$\bar{y}\in\Delta(x_{0})\neq\emptyset$ such that condition (4.9) holds. As
Source Condition holds, $x_{0}$ is an optimal solution of problem (4.1). By
Proposition 4.3 and Proposition 4.4 again, $x_{0}$ is the unique solution.
$\hfill\Box$

######  Remark 4.6.

The equivalence between (i) and (iii) in Theorem 4.5 was established recently
in [32, Lemma 3.1] when $g$ is the nuclear norm; see our Corollary 4.8 for
further details about this case. This equivalence is also obtained in [27,
Theorem 3.1] when $g$ is a gauge function. The appearance of (ii) in the above
result is crucial. It tells us that when condition (4.9) holds at some
$\bar{y}\in\Delta(x_{0})$, it is also satisfied at any other dual certificate.
Hence, the choice of $\bar{y}$ in condition (4.9) is not important. If we know
one dual certificate of problem (4.1), we only need to check condition (4.9)
at this dual certificate for solution uniqueness. Such a dual certificate can
be found via solving a “gauge” convex optimization problem; see [20, Section
4] for more details. It is possible to prove Theorem 4.5 directly without
using Proposition 4.3, but our approach here highlights the connection between
the descent cone and the radial cone for solution uniquessness. $\triangle$

######  Remark 4.7 (Strong Minima vs Solution Uniqueness).

When the function $g$ satisfies the quadratic growth condition at $x_{0}$ for
any $y\in\partial g(x_{0})$ and it is second-order regular at $x_{0}$ in the
sense of [6, Definition 3.85], it is shown recently in [21, Theorem 3.5] that
$x_{0}$ is a strong solution if and only if

$\left[\bigcap_{y\in\Delta(x_{0})}\mathcal{T}_{\partial
g^{*}(y)}(x_{0})\right]\cap\mbox{\rm
Ker}\,\Phi\cap\mathcal{C}(x_{0})=\\{0\\}.$ (4.10)

If $x_{0}$ is a strong solution of problem (4.1), it is certainly a unique
solution. Conversely, if $x_{0}$ is a unique solution of problem (4.1) and the
radial cone $\mathcal{R}_{\partial g^{*}(y)}(x_{0})$ is closed at some dual
certificate $y\in\Delta(x_{0})$, Theorem 4.5 tells us that

$0=\mbox{\rm Ker}\,\Phi\cap\mathcal{R}_{\partial g^{*}(y)}(x_{0})=\mbox{\rm
Ker}\,\Phi\cap\mathcal{T}_{\partial g^{*}(y)}(x_{0}),$

which clearly verifies (4.10). Thus $x_{0}$ is a strong solution of problem
(4.1) if and only if it is the unique solution provided that the function $g$
satisfies the quadratic growth condition at $x_{0}$ for any $y\in\partial
g(x_{0})$ and the second-order regularity at $x_{0}$, and that the radial cone
$\mathcal{R}_{\partial g^{*}(y)}(x_{0})$ is closed at some dual certificate
$y\in\Delta(x_{0})$.

The $\ell_{1}/\ell_{2}$ norm satisfies all the three latter conditions; see
also Remark 3.3. Hence, $x_{0}$ is a strong solution of problem (4.1) if and
only if it is the unique solution in this case. This fact was established
recently in [20, Thereom 5.1] by a different approach.

It is also known that the nuclear norm $g(\cdot)=\|\cdot\|_{*}$ satisfies the
quadratic growth condition at $X_{0}\in\mathbb{R}^{n_{1}\times n_{2}}$ for any
$Y\in\partial\|X_{0}\|_{*}$ and second-order regularity at $X_{0}$; see [8,
48], but the radical cone $\mathcal{R}_{\partial g^{*}(Y)}(X_{0})$ is not
always closed. As discussed in Remark 3.7, this radial cone is closed if and
only if $Y\in{\rm ri}\,\partial\|X_{0}\|_{*}$. The existence of such dual
certificate $Y$ means

$\mbox{\rm Im}\,\Phi^{*}\cap{\rm ri}\,\partial\|X_{0}\|_{*}\neq\emptyset,$
(4.11)

which is known as the Nondegeneracy Source Condition introduced in [11, 12]
for nuclear norm minimization problems. We will add some details about this
case in Corollary 4.10. $\triangle$

###  4.2 Nuclear norm case

Next let us consider the nuclear norm optimization problem:

$\min_{X\in\mathbb{R}^{n_{1}\times n_{2}}}\quad\|X\|_{*}\quad\mbox{subject
to}\quad\Phi X=M_{0},$ (4.12)

where $\Phi:\mathbb{R}^{n_{1}\times n_{2}}\to\mathbb{R}^{m}$ is a linear
operator ($n_{2}\geq n_{1}$) and $M_{0}\in\mathbb{R}^{m}$ is some known
vector. The following characterizations of solution uniqueness for nuclear
norm minimization problem (4.12) come directly from Theorem 4.5 and the
calculation of the radial cone in (3.20).

######  Corollary 4.8 (Solution uniqueness of nuclear norm minimization
problem).

Let $X_{0}$ be an optimal solution of problem (4.12). The following are
equivalent

  * (i)

$X_{0}$ is a unique solution of problem (4.12).

  * (ii)

For any dual certificate $Y\in\Delta(X_{0})$, the system

$\Phi\left(U\begin{pmatrix}A&BC&0\\\ C^{T}B^{T}&C&0\\\
0&0&0\end{pmatrix}V^{T}\right)=0\quad\mbox{with}\quad
A\in\mathbb{S}^{r},B\in\mathbb{R}^{r\times(p-r)},C\in\mathbb{S}_{+}^{p-r}$
(4.13)

gives $A=0$ and $C=0$, where the pair
$(U,V)\in\mathcal{O}(X_{0})\cap\mathcal{O}(Y)$ comes from the simultaneous
ordered singular value decomposition of $X_{0}$ and $Y$, $r={\rm
rank}\,(X_{0})$, and $p=p(Y)$ from (3.16).

  * (iii)

Condition (ii) holds at some dual certificate $\overline{Y}\in\Delta(X_{0})$.

######  Remark 4.9.

As discussed in Remark 4.6, solution uniqueness for nuclear norm minimization
problem (4.12) is characterized via the radical cone in [32, Lemma 3.1]. The
above result advances [32, Lemma 3.1] in some ways. The most important thing
is that the radical cone is fully calculated, i.e., the general condition
(4.9) is explicitly expressed by condition (4.13) at some dual certificate.
This condition can be written and solved as a nonlinear optimization problem;
see our previous Remark 3.8. Moreover, we can pick any dual certificate
$Y\in\Delta(X_{0})$ and check (4.13) at $Y$ for solution uniqueness at
$X_{0}$. A particular dual certificate of problem (4.12) can be found by
solving a spectral norm minimization problem [20, Remark 5.5]. Specifically,
suppose that the compact SVD of $X_{0}$ is

$X_{0}=U_{0}\Sigma_{0}V_{0}^{T},$ (4.14)

where $\Sigma_{0}$ is the diagonal matrix including all the positive singular
values of $X_{0}$ with decreasing order and ${\rm rank}\,(\Sigma_{0})=r$, and
$U_{0}\in\mathbb{R}^{n_{1}\times r}$ and $V_{0}\in\mathbb{R}^{n_{2}\times r}$
are orthogonal matrices. Recall the model tangent space [12] at $X_{0}$:

$\mathbb{T}\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\\{U_{0}Y^{T}+XV_{0}^{T}|\;X\in\mathbb{R}^{n_{1}\times
r},Y\in\mathbb{R}^{n_{2}\times r}\\}.$ (4.15)

Consider the following spectral norm minimization problem

$\min_{Z\in\mathbb{T}^{\perp}}\quad\|Z\|\quad\mbox{subject
to}\quad\mathcal{N}Z=-\mathcal{N}E_{0}\quad\mbox{with}\quad
E_{0}=U_{0}V_{0}^{T},$ (4.16)

where $\mathcal{N}$ is a linear operator satisfying $\mbox{\rm
Ker}\,\mathcal{N}=\mbox{\rm Im}\,\Phi^{*}$. When $X_{0}$ is an optimal
solution of problem (4.12), [20, Remark 5.5] shows that the optimal value of
problem (4.16) denoted by $\rho(X_{0})$ is smaller than or equal to $1$.
Moreover, if $Z_{0}$ is an optimal solution of problem (4.16), $Z_{0}+E_{0}$
is a dual certificate of problem (4.12); see our Section 5 for further details
on Numerical Experiment. $\triangle$

The following result is similar to Corollary 3.9, at which we provide the
equivalence between solution uniqueness and strong minima under Nondegenerate
Source Condition (4.11). It is already discussed in Remark 4.7.

######  Corollary 4.10.

Suppose that $X_{0}$ is an optimal solution of problem (4.12) and
Nondegenerate Source Condition (4.11) is satisfied. Then $X_{0}$ is a strong
solution of problem (4.12) if and only if it is the unique solution.

###### Proof.

As discussed in Remark 4.7, Nondegenerate Source Condition (4.11) guarantees
closedness of the radial cone $\mathcal{R}_{\partial g^{*}(Y)}(X_{0})$ for
some dual certificate $Y\in\Delta(X_{0})$. It follows that

$\mathcal{R}_{\partial g^{*}(Y)}(X_{0})=\mathcal{T}_{\partial
g^{*}(Y)}(X_{0}).$

Hence we have

$\mbox{\rm Ker}\,\Phi\cap\mathcal{R}_{\partial g^{*}(Y)}(X_{0})=\mbox{\rm
Ker}\,\Phi\cap\mathcal{T}_{\partial g^{*}(Y)}(X_{0}).$

By Theorem 4.5 and [21, Theorem 5.2], $X_{0}$ is a strong solution of problem
(4.12) if and only if it is the unique solution. $\hfill\Box$

The following result gives a necessary condition for solution uniqueness.

######  Corollary 4.11.

Let $X_{0}$ be an optimal solution of problem (4.12). If $X_{0}$ is a unique
solution, then the following Strict Restricted Injectivity holds

$\mbox{\rm Ker}\,\Phi\cap U_{0}\mathbb{S}^{r}V_{0}^{T}=\\{0\\}.$ (4.17)

If additionally Nondegeneracy Source Condition (4.11) holds, then Strict
Restricted Injectivity is also sufficient for solution uniqueness at $X_{0}$.

###### Proof.

Note from the formula of radial cone (3.20) that

$U_{0}\mathbb{S}^{r}V_{0}^{T}\subset\mathcal{R}_{\partial
g^{*}(Y)}(X_{0})\quad\mbox{for any}\quad Y\in\Delta(X_{0}).$

If $X_{0}$ a unique solution of problem (4.12), we get from Theorem 4.5 that
Strict Restricted Injectivity (4.17) is satisfied.

Conversely, if Nondegeneracy Source Condition (4.11) holds, there exists
$Y\in\Delta(X_{0})$ such that $Y\in{\rm ri}\,\partial\|X_{0}\|$, which means
that $p(Y)=r$. By the formula of radial cone (3.20) again, we have

$\mathcal{R}_{\partial g^{*}(Y)}(X_{0})=U_{0}\mathbb{S}^{r}V_{0}^{T}.$

It follows from Theorem 4.5 that Strict Restricted Injectivity (4.17) is also
sufficient for solution uniqueness at $X_{0}$. $\hfill\Box$

Strict Restricted Injectivity is introduced recently in [21, Corollary 5.7]
for nuclear norm minimization problem (4.12), as a necessary condition for
strong minima at $X_{0}$. The above result is quite similar, but slightly
stronger as a unique solution of problem (4.12) may be not a strong one. The
following example taken from [21, Example 5.11] shows such difference.

######  Example 4.12 (Difference between unique solution and strong solution
in problem (4.12)).

Consider the following optimization problem

$\min_{X\in\mathbb{R}^{2\times 2}}\|X\|_{*}\quad\text{ subject to }\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}.$ (4.18)

Note that $X_{0}=\begin{pmatrix}1&0\\\ 0&0\end{pmatrix}$ is an optimal
solution of problem (4.18). Indeed, it is easy to see that

$\mbox{\rm Im}\,\Phi^{*}={\rm span}\left\\{\begin{pmatrix}1&0\\\
0&1\end{pmatrix},\begin{pmatrix}0&1\\\
-1&1\end{pmatrix}\right\\}\qquad\mbox{and}\qquad\partial\|X_{0}\|_{*}=\begin{pmatrix}1&0\\\
0&[-1,1]\end{pmatrix}.$

It follows that

$\Delta(X_{0})=\mbox{\rm
Im}\,\Phi^{*}\cap\partial\|X_{0}\|_{*}=\begin{pmatrix}1&0\\\
0&1\end{pmatrix}\quad\mbox{and}\quad\mbox{\rm Im}\,\Phi^{*}\cap{\rm
ri}\,\partial\|X_{0}\|_{*}=\emptyset.$

Thus $X_{0}$ is a solution, but Nondegeneracy Source Condition (4.11) is not
satisfied. In the view of Remark 4.7, the latter is well-expected, as we want
$X_{0}$ to be a unique solution, but not a strong solution in this example.

For $Y_{0}=\mathbb{I}_{2}\in\Delta(X_{0})$, we obtain the radial cone from
(3.20) and the tangent cone from (3.26) respectively

$\displaystyle\mathcal{R}_{\partial
g^{*}(Y_{0})}(X_{0})=\left\\{\begin{pmatrix}a&bc\\\
bc&c\end{pmatrix}|\;a,b\in\mathbb{R},c\geq
0\right\\}\mbox{and}\;\mathcal{T}_{\partial
g^{*}(Y_{0})}(X_{0})=\left\\{\begin{pmatrix}a&b\\\
b&c\end{pmatrix}|\;a,b\in\mathbb{R},c\geq 0\right\\}.$ (4.19)

To check condition (4.13) or (4.8), due to (4.19) we solve the system
$\Phi\begin{pmatrix}a&bc\\\ bc&c\end{pmatrix}=0$ with $c\geq 0$, which means

$a+c=0\quad\mbox{and}\quad bc-bc+c=0.$

This clearly gives us $a=c=0$, i.e., condition (4.13) is satisfied. Thus,
$X_{0}$ is a unique solution of problem (4.18).

To check whether $X_{0}$ is a strong solution, we have to verify the condition

$\mbox{\rm Ker}\,\Phi\cap\mathcal{T}_{\partial g^{*}(Y_{0})}(X_{0})=\\{0\\}$

according to [21, Theorem 5.2]. By (4.19), we solve the system
$\Phi\begin{pmatrix}a&b\\\ b&c\end{pmatrix}=0$ with $c\geq 0$:

$a+c=0\quad\mbox{and}\quad b-b+c=0\quad\mbox{for}\quad a,b\in\mathbb{R},c\geq
0,$

which gives us $a=c=0$ and $b\in\mathbb{R}$. Hence the above condition for
strong minima at $X_{0}$ fails, i.e., $X_{0}$ is not a strong solution of
problem (4.18). $\triangle$

######  Remark 4.13 (Comparisons with [28]).

The main advantages of using the descent cone in Proposition 4.3 over the
radial cone in Theorem 4.5 for solution uniqueness are that we do not need to
know if $X_{0}$ is an optimal solution of problem 4.12 initially and do not
need to find a dual certificate. But the descent cone seems to be bigger and
more complicate than the radial cone due to(4.4). In the recent paper [26],
Hoheisel and Paquette introduced the following set

$W(X_{0})=\left\\{UM\begin{pmatrix}\mathbb{I}_{r}&0\\\
0&R\end{pmatrix}V^{T}\left|\;\begin{array}[]{ll}&M\in\mathbb{S}^{n_{1}}_{+}-\mathcal{F}^{n_{1},r},\,{\rm
Tr}\,(M)=0,\\\
&R\in\mathcal{V}_{n_{1}-r,n_{2}-r},\,M\begin{pmatrix}\mathbb{I}_{r}&0\\\
0&RR^{T}\end{pmatrix}=M\end{array}\right.\right\\},$ (4.20)

where $(U,V)\in\mathcal{O}(X_{0})$, the set $\mathcal{F}^{n_{1},r}$ is defined
by

$\mathcal{F}^{n_{1},r}\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\left\\{\begin{pmatrix}A&0\\\
0&0\end{pmatrix}\in\mathbb{S}^{n_{1}}_{+}|\;A\in\mathbb{S}^{r}_{++}\right\\},$

and $\mathcal{V}_{n_{1}-r,n_{2}-r}$ is the Stiefel manifold:

$\mathcal{V}_{n_{1}-r,n_{2}-r}\stackrel{{\scriptstyle\text{\rm\tiny
def}}}{{=}}\\{R\in\mathbb{R}^{(n_{1}-r)\times(n_{2}-r)}|\;R^{T}R=\mathbb{I}\\}.$

In particular [26, Corollary 4.1] shows that $X_{0}$ is a unique solution of
problem (4.12) if and only if $X_{0}$ is an optimal solution and

$\mbox{\rm Ker}\,\Phi\cap W(X_{0})=\\{0\\}.$ (4.21)

The (possibly nonconvex) set $W(X_{0})$ seems to be more complicated than our
radial set (3.20). Computing $W(X_{0})$ seems to be complicated in high
dimensions, but its span [26, Proposition 3.2] is rather simple

$\displaystyle{\rm span}\,W(X_{0})=\left\\{U\begin{pmatrix}A&B\\\
C&D\end{pmatrix}V^{T}|\;A\in\mathbb{S}^{r},B\in\mathbb{R}^{r\times(n_{2}-r)},C\in\mathbb{R}^{(n_{1}-r)\times
r},D\in\mathbb{R}^{(n_{1}-r)\times(n_{2}-r)}\right\\}.$ (4.22)

Thus a sufficient condition for solution uniqueness at $X_{0}$ is

$\mbox{\rm Ker}\,\Phi\cap{\rm span}\,W(X_{0})=\\{0\\};$ (4.23)

see [26, Corollary 4.2]. This fact can be obtained directly from Theorem 4.5
as

$\mathcal{R}_{\partial g^{*}(Y)}(X_{0})\subset{\rm span}\,W(X_{0})$

for any $Y\in\Delta(X_{0})$. The condition (4.23) also shows that $X_{0}$ is a
strong solution of problem (4.12) according to [21, Theorem 5.2]. In our
Example 4.12 later, condition (4.23) fails, but $X_{0}$ is still a unique
solution.

When $X_{0}$ is an optimal solution of problem (4.12) as assumed in [26,
Corollary 4.1], observe from the proof of [26, Theorem 3.2] that

$\mbox{\rm Ker}\,\Phi\cap W(X_{0})=\mbox{\rm Ker}\,\Phi\cap{\rm
cone}\,\\{X-X_{0}|\;\|X\|_{*}=\|X_{0}\|_{*}\\}=\mbox{\rm
Ker}\,\Phi\cap\mathcal{D}(X_{0}),$ (4.24)

where $\mathcal{D}(X_{0})$ is the descent cone of nuclear norm at $X_{0}$.
This together Proposition 4.3 explains why condition (4.21) ensures the
solution uniqueness at $X_{0}$.

Although our condition (4.13) depends on the existence of a dual certificate
when $X_{0}$ is an optimal solution, it is more computable and verifiable than
(4.21); see also our Section 5. In the framework of Example 4.12, the set
$W(X_{0})$ in (4.20) is computed by

$\begin{array}[]{ll}W(X_{0})=\left\\{M\begin{pmatrix}1&0\\\
0&r\end{pmatrix}|\;M\in\mathbb{S}^{2}_{+}-\mathcal{F}^{2,1},{\rm
Tr}\,(M)=0,r\in\\{-1,1\\}\right\\}.\end{array}$

For any $M\in\mathbb{S}^{2}_{+}-\mathcal{F}^{2,1}$ with ${\rm Tr}\,(M)=0$, we
write

$M=\begin{pmatrix}a&b\\\ b&c\end{pmatrix}-\begin{pmatrix}d&0\\\
0&0\end{pmatrix}=\begin{pmatrix}a-d&b\\\
b&c\end{pmatrix}\quad\mbox{with}\quad\begin{pmatrix}a&b\\\
b&c\end{pmatrix}\in\mathbb{S}_{+}^{2}\quad\mbox{and}\quad d>0.$

As ${\rm Tr}\,(M)=0$, we have $d=a+c>0$. Thus

$M=\begin{pmatrix}-c&b\\\ b&c\end{pmatrix}$

Since $\begin{pmatrix}a&b\\\ b&c\end{pmatrix}\in\mathbb{S}^{2}$ and $a+c>0$,
if $c=0$ then $a>0$ and $b=0$. If $c>0$, $b$ is arbitrary, as $a$ can be
chosen sufficiently large. Hence the set of all matrices $M$ is

$\begin{pmatrix}0&0\\\ 0&0\end{pmatrix}\cup\left\\{\begin{pmatrix}-c&b\\\
b&c\end{pmatrix}|\;c>0,b\in\mathbb{R}\right\\}.$

It follows that

$W(X_{0})=\begin{pmatrix}0&0\\\
0&0\end{pmatrix}\cup\left\\{\begin{pmatrix}-c&b\\\
b&c\end{pmatrix}|\;c>0,b\in\mathbb{R}\right\\}\cup\left\\{\begin{pmatrix}-c&-b\\\
b&-c\end{pmatrix}|\;c>0,b\in\mathbb{R}\right\\}$

This set is nonconvex and completely different from the radial cone
$\mathcal{R}_{\partial g^{*}(Y_{0})}(X_{0})$ obtained in (4.19). Moreover,
$\mathcal{R}_{\partial g^{*}(Y_{0})}(X_{0})$ is not a subset of $W(X_{0})$ and
vice versa. This observation highlights our distinct approach for solution
uniqueness from [26]. Nonconvexity of the set $W(X_{0})$ may be a challenge
when checking condition (4.21) in problems with higher dimension. $\triangle$

######  Remark 4.14 (Solution Uniqueness and Sharp Minima).

In [12] Candès and Retch shown that $X_{0}$ is a unique solution of problem
(4.12) if the following Restricted Injectivity

$\mbox{\rm Ker}\,\Phi\cap\mathbb{T}=\\{0\\}$ (4.25)

together with Nondegeneracy Source Condition (4.11) holds. In the spirit of
Theorem 4.5, this fact is explained as follows. When Restricted Injectivity
(4.25) and Nondegeneracy Source Condition (4.11) are satisfied, Strict
Restricted Injectivity (4.17) holds as
$U_{0}\mathbb{S}^{r}V_{0}^{T}\subset\mathbb{T}$. By Corollary 4.11, $X_{0}$ is
the unique solution of problem (4.12). In [26], Hoheisel and Paquette also use
the dual version of Restricted Injectivity:

$\mbox{\rm Im}\,\Phi^{*}+\mathbb{T}^{\perp}=\mathbb{R}^{n_{1}\times n_{2}}$

together with Nondegeneracy Source Condition (4.11) as sufficient conditions
of solution uniqueness.

It is shown in [20, Theorem 4.6] that the combination of Restricted
Injectivity (4.25) and Nondegeneracy Source Condition (4.11) indeed
characterizes the stronger property, sharp minima at $X_{0}$ [14, 38], which
means that there exists some $c>0$ such that

$\|X\|_{*}-\|X_{0}\|_{*}\geq c\|X-X_{0}\|_{F}\quad\mbox{for any \;
$X\in\mathbb{R}^{n_{1}\times n_{2}}$\; satisfying}\quad\Phi X=M_{0}.$

In Example 4.12, we show that a unique solution is not a strong solution, thus
not a sharp solution too. Even if Nondegeneracy Source Condition (4.11) holds,
solution uniqueness and sharp minima of nuclear norm minimization are
different; see, e.g., [21, Example 5.10]. $\triangle$

The next corollary gives the minimum bound for exact recovery. It slightly
enhances the recent [21, Corollary 5.8] by replacing the requirement of strong
minima there by solution uniqueness. Its proof based on Strict Restricted
Injectivity (4.17) is completely the same; so we omit the detail.

######  Corollary 4.15 (Minimum bound for exact recovery).

Suppose that $X_{0}$ is an $n_{1}\times n_{2}$ matrix with rank $r$. Then one
needs at least $\frac{1}{2}r(r+1)$ measurements $m$ of $M_{0}$ so that solving
the nuclear norm minimization problem (4.12) recovers exactly the unique
solution $X_{0}$.

Moreover, there exist infinitely many linear operators
$\Phi:\mathbb{R}^{n_{1}\times n_{2}}\to\mathbb{R}^{\frac{1}{2}r(r+1)}$ such
that $X_{0}$ is the unique solution of problem (4.12).

The rest of the section is devoted to the computation of the descent cone of
the nuclear norm via its first-order information, as it is an important notion
used in [9, 1] to find statistical dimensions in the theory of exact recovery.
According to formula (4.4), we also need to know the critical cone (4.3) of
the nuclear norm:

$\mathcal{C}(X_{0})=\\{W\in\mathbb{R}^{n_{1}\times n_{2}}|\;dg(X_{0})(W)\leq
0\\}.$ (4.26)

For any $(U,V)\in\mathcal{O}(X_{0})$ and $W\in\mathbb{R}^{n_{1}\times n_{2}}$,
we write

$W=U\begin{pmatrix}A&B\\\ C&D\end{pmatrix}V^{T}$

with some $A\in\mathbb{R}^{r\times r}$, $B\in\mathbb{R}^{r\times(n_{2}-r)}$,
$C\in\mathbb{R}^{n_{1}\times r}$, and
$D\in\mathbb{R}^{(n_{1}-r)\times(n_{2}-r)}$. By formula (3.13) and (2.2), we
have

$dg(X_{0})(W)=\max_{Y\in\partial\|X_{0}\|_{*}}\langle Y,W\rangle={\rm
Tr}\,A+\|D\|_{*}.$

Combining this with (4.26) gives us that

$\displaystyle\begin{array}[]{ll}\mbox{\rm
bd}\,\mathcal{C}(X_{0})=\Big{\\{}U\begin{pmatrix}A&B\\\
C&D\end{pmatrix}V^{T}|&A\in\mathbb{R}^{r\times
r},B\in\mathbb{R}^{r\times(n_{2}-r)},C\in\mathbb{R}^{n_{1}\times
r},D\in\mathbb{R}^{(n_{1}-r)\times(n_{2}-r)},\\\ &{\rm
Tr}\,A+\|D\|_{*}=0\Big{\\}}.\end{array}$ (4.29)

Moreover, we have

$\displaystyle\begin{array}[]{ll}{\rm
int}\,\mathcal{C}(X_{0})=\Big{\\{}U\begin{pmatrix}A&B\\\
C&D\end{pmatrix}V^{T}|&A\in\mathbb{R}^{r\times
r},B\in\mathbb{R}^{r\times(n_{2}-r)},C\in\mathbb{R}^{n_{1}\times
r},D\in\mathbb{R}^{(n_{1}-r)\times(n_{2}-r)},\\\ &{\rm
Tr}\,A+\|D\|_{*}<0\Big{\\}}.\end{array}$

The following result gives an exact computation of the descent cone for the
nuclear norm, which is similar with its formula for $\ell_{1}/\ell_{2}$ norm
established in [20, Theorem 5.1].

######  Proposition 4.16 (Descent cone of nuclear norm).

Let $U_{I}\Sigma V_{I}^{T}$ be the SVD of $X_{0}$. The descent cone at $X_{0}$
is calculated by

$\mathcal{D}(X_{0})=\mathcal{E}\cup({\rm int}\,\mathcal{C}(X_{0})),$ (4.31)

where

$\displaystyle\begin{array}[]{ll}\mathcal{E}=\Big{\\{}W\in\mathbb{R}^{n_{1}\times
n_{2}}|&W=U\begin{pmatrix}A&BC&0\\\
C^{T}B^{T}&C&0\end{pmatrix}V^{T},A\in\mathbb{S}^{r},B\in\mathbb{R}^{r\times(n_{1}-r)},C\in\mathbb{S}_{+}^{n_{1}-r},\\\
&{\rm Tr}\,(A+C)=0,(U,V)\in\mathcal{O}(X_{0})\Big{\\}}.\end{array}$ (4.34)

Moreover, if $X_{0}$ is an optimal solution of problem (4.12), we have

$\mbox{\rm Ker}\,\Phi\cap\mathcal{D}(X_{0})=\mbox{\rm
Ker}\,\Phi\cap\left\\{U\begin{pmatrix}A&BC&0\\\ C^{T}B^{T}&C&0\\\
0&0&0\end{pmatrix}V^{T}|\;A\in\mathbb{S}^{r},B\in\mathbb{R}^{r\times(p-r)},C\in\mathbb{S}_{+}^{p-r},{\rm
Tr}\,(A+C)=0\right\\}$

for any dual certificate $Y\in\Delta(X_{0})$ with $p=p(Y)$ from (3.16) and any
pair $(U,V)\in\mathcal{O}(X_{0})\cap\mathcal{O}(Y_{0})$.

###### Proof.

Let us verify the inclusion “$\subset$” in (4.31). Pick any
$W\in\mathcal{D}(X_{0})\setminus{\rm int}\,\mathcal{C}(X_{0})$, by formulae
(4.3) and (3.20) there exist $Y\in\partial\|X_{0}\|_{*}$ and a pair
$(U,V)\in\mathcal{O}(X_{0})\cap\mathcal{O}(Y_{0})$ such that

$W=U\begin{pmatrix}A&BC&0\\\ C^{T}B^{T}&C&0\\\
0&0&0\end{pmatrix}V^{T}\in\mbox{\rm bd}\,\mathcal{C}(X_{0})$

with some $A\in\mathbb{S}^{r}$, $B\in\mathbb{R}^{r\times(p-r)}$,
$C\in\mathbb{S}_{+}^{p-r}$, $p=p(Y)$ defined in (3.16). Define

$\overline{C}=\begin{pmatrix}C&0\\\
0&0\end{pmatrix}\in\mathbb{S}^{n_{1}-r}_{+}\quad\mbox{and}\quad\overline{B}=\begin{pmatrix}B&0\end{pmatrix}\in\mathbb{R}^{r\times(n_{1}-r)}.$

We obtain that $W=U\begin{pmatrix}A&\overline{B}\,\overline{C}&0\\\
\overline{C}^{T}\overline{B}^{T}&\overline{C}&0\end{pmatrix}V^{T}\in\mbox{\rm
bd}\,\mathcal{C}(X_{0})$. Note from (4.29) that

$0={\rm Tr}\,A+\|\overline{C}\|_{*}={\rm Tr}\,A+{\rm Tr}\,\overline{C}.$

This tells us that $W\in\mathcal{E}$ defined in (4.34) and verifies the
inclusion “$\subset$” in (4.31).

To justifies the converse inclusion in (4.31). Pick any $W\in\mathcal{E}$ with
representation

$W=U\begin{pmatrix}A&BC&0\\\ C^{T}B^{T}&C&0\end{pmatrix}V^{T}$

with some $A\in\mathbb{S}^{r}$, $B\in\mathbb{R}^{r\times(n_{1}-r)}$, and
$C\in\mathbb{S}_{+}^{n_{1}-r}$ such that ${\rm Tr}\,(A+C)=0$. By (4.29),
$W\in\mbox{\rm bd}\,\mathcal{C}(X_{0})$. Moreover, define
$Y=U\begin{pmatrix}\mathbb{I}_{n_{1}}&0\end{pmatrix}V^{T}\in\partial\|X_{0}\|_{*}$
by (3.13). Note from formula (3.20), $W\in\mathcal{R}_{\partial
g^{*}(Y)}(X_{0})$. It follows that $\mathcal{E}\subset\mathcal{R}_{\partial
g^{*}(Y)}(X_{0})\cap\mbox{\rm bd}\,\mathcal{C}(X_{0})$. By (4.4), we have the
inclusion “$\supset$” in (4.31). The equality in (4.31) is verified.

The second part of this proposition follows directly from Proposition 4.4 and
the formula (4.29) for the boundary of the critical cone. $\hfill\Box$

##  5 Numerical Experiments

In this section, we conduct numerical experiments to illustrate the solution
uniqueness for the nuclear norm minimization problem (4.12). These experiments
are performed for different matrix ranks $r$ and numbers of measurements $m$.

In the experiment, we generate $X_{0}$, an $n\times n$ matrix of rank $r$, by
sampling two factors $W\in\mathbb{R}^{n\times r}$ and $H\in\mathbb{R}^{n\times
r}$ with independent and identically distributed (i.i.d.) random entries and
setting $X_{0}=WH^{*}$. We vectorize problem (4.12) in the following form:

$\min_{X\in\mathbb{R}^{n\times n}}\quad\|X\|_{*}\quad\mbox{subject
to}\quad\Phi\ \text{vec}(X)=\Phi\ \text{vec}(X_{0}),$ (5.1)

where $\Phi$ is an ${m\times n^{2}}$ matrix drawn from the standard Gaussian
ensemble. The point $X_{0}$ is said to be recovered if solving problem (5.1)
gives us an optimal solution $\overline{X}$ that is relatively close to
$X_{0}$, in particularly, $\|\overline{X}-X_{0}\|_{F}/\|X_{0}\|_{F}<10^{-3}$
as proposed in [11]. We use cvxpy package to solve this problem to find
$\overline{X}$.

In order to check whether $X_{0}$ is a unique solution of problem (5.1), by
Corollary 4.8 and Remark 3.8, we have to verify that the following nonconvex
optimization problem has global maximum value $0$:

$\displaystyle\max\;\frac{1}{2}\|A\|^{2}_{F}+\frac{1}{2}\|C\|_{F}^{2}\;\;$
(5.2) $\displaystyle\mbox{subject to }\;\;\Phi\left(U\begin{pmatrix}A&BC&0\\\
C^{T}B^{T}&C&0\\\
0&0&0\end{pmatrix}V^{T}\right)=0,A\in\mathbb{S}^{r},B\in\mathbb{R}^{r\times(p-r)},C\in\mathbb{S}_{+}^{p-r},$

where $(U,V)\in\mathcal{O}(X_{0})\cap\mathcal{O}(Y)$ is from (3.19) with
$Y\in\Delta(X_{0})$ being a particular dual certificate computed as in Remark
4.9, $r={\rm rank}\,(X_{0})$, and $p=p(Y)$ from (3.16). Indeed, let
$\widehat{U}\Sigma\widehat{V}^{T}$ be an SVD of $\Phi$, $\widehat{V}_{G}$ be
the matrix whose columns are the last $n^{2}-r$ columns of $V$, and
$U_{0}\begin{pmatrix}\Sigma_{0}&0\\\ 0&0\end{pmatrix}V_{0}^{T}$ be a full SVD
of $X_{0}$. To find a particular certificate of (5.1), we solve the following
problem by using the cvxpy package:

$\min_{Z\in\mathbb{T}_{0}^{\perp}}\|Z\|\quad\mbox{subject to}\quad
N\text{vec}(Z)=-N\text{vec}(E_{0}),$

where $N=V_{G}^{T}$, $E_{0}=U_{0}\begin{pmatrix}\mathbb{I}_{r}&0\\\
0&0\end{pmatrix}V_{0}^{T}$, and $\mathbb{T}_{0}^{\perp}$ is known by

$\mathbb{T}_{0}^{\perp}=\left\\{U_{0}\begin{pmatrix}0&0\\\
0&D\end{pmatrix}V_{0}^{T}|\;D\in\mathbb{R}^{(n-r)\times(n-r)}\right\\}.$

Let $\rho(X_{0})$ be the optimal value of this problem and $Z_{0}$ be an
optimal solution. Note also from [20, Proposition 4.4 and Remark 4.5], $X_{0}$
is an optimal solution of problem (5.1) if and only if $\rho(X_{0})\leq 1$.
Due to possible errors in numerical computation, we increase this bound to
$\rho(X_{0})<1.001$ for optimal solutions. It is also known from [20, Section
4] that $Y=Z_{0}+E_{0}$ is a particular dual certificate of (5.1).

Back to the maximum problem above, we rewrite it as follows

$\displaystyle\max\;\frac{1}{2}\|A\|^{2}_{F}+\frac{1}{2}\|C\|_{F}^{2}$ (5.3)
$\displaystyle\mbox{s.t.}\;\;\Phi\left(U\begin{pmatrix}A&D&0\\\ D^{T}&C&0\\\
0&0&0\end{pmatrix}V^{T}\right)=0,D=E,E=BC,A\in\mathbb{S}^{r},B\in\mathbb{R}^{r\times(p-r)},C\in\mathbb{S}_{+}^{p-r}.$

It is worth noting that this problem takes the format of the one considered in
[7], for which a multiblock version of ALBUM (Adaptive Lagrangian-Based
mUltiplier Method) [7], named mALBUM, is investigated. The algorithm mALBUM
for solving (5.3) iteratively generates a sequence
$\\{A^{k},C^{k},B^{k},D^{k},E^{k},F^{k},G^{k})\\}$ by

$\displaystyle(A^{k+1},C^{k+1},D^{k+1})\in$ $\displaystyle\arg\min-\langle
A^{k},A\rangle-\langle C^{k},C\rangle-\langle F^{k},D\rangle-\langle
G^{k},B^{k}C\rangle+\frac{\beta_{k}}{2}\|E^{k}-D\|^{2}$
$\displaystyle\quad\quad+\frac{\beta_{k}}{2}\|E^{k}-B^{k}C\|^{2}$
$\displaystyle\mbox{s.t.}\;\;\Phi\left(U\begin{pmatrix}A&D&0\\\ D^{T}&C&0\\\
0&0&0\end{pmatrix}V^{T}\right)=0,A\in\mathbb{S}^{r},C\in\mathbb{S}_{+}^{p-r},$
$\displaystyle B^{k+1}\in$ $\displaystyle\arg\min-\langle
G^{k},BC^{k+1}\rangle+\frac{\beta_{k}}{2}\|E^{k}-BC^{k+1}\|^{2},$
$\displaystyle E^{k+1}=$
$\displaystyle\left(-F^{k}-G^{k}\right)/(2\beta_{k})+(D^{k+1}+B^{k+1}C^{k+1})/2,$
$\displaystyle F^{k+1}=$ $\displaystyle F^{k}+\beta_{k}(E^{k+1}-D^{k+1}),$
$\displaystyle G^{k+1}=$ $\displaystyle
G^{k}+\beta_{k}(E^{k+1}-B^{k+1}C^{k+1}).$

Here, the parameter $\beta$ is updated adaptively by using the following rule:
if

$\|E^{k+1}-D^{k+1}\|+\|E^{k+1}-B^{k+1}C^{k+1}\|>M\quad\mbox{ for some large
constant $M$},$

then $\beta_{k+1}\leftarrow\nu\beta_{k}$ with some constant $\nu>0$;
otherwise, $\beta_{k+1}\leftarrow\beta_{k}$. In our experiment, we set
$\nu=1.2$, $M=10^{5}$, and $\beta_{0}=1$. We use the cvxpy package to solve
sub-problems.

To start the algorithm, the initial values of
$(A^{0},C^{0},B^{0},D^{0},E^{0},F^{0},G^{0})$ are chosen as follows:
$A^{0}=(V_{1}+V_{1}^{T})$, where $V_{1}\in\mathbb{R}^{r\times r}$ is drawn
from the standard Gaussian ensemble, $B^{0}$ is drawn from the standard
Gaussian ensemble, $C^{0}=V_{2}V_{2}^{T}$, where
$V_{2}\in\mathbb{R}^{(p-r)\times(p-r)}$ is drawn from the standard Gaussian
ensemble, $D^{0}=E^{0}=B^{0}C^{0},F^{0}=0$, and $G^{0}=0$.

We classify solution uniqueness at $X_{0}$ if
$\|\overline{A}\|+\|\overline{C}\|<10^{-5}$ and $\rho(X_{0})<1.001$, where
$\overline{A}$ and $\overline{C}$ are outputs of mALBUM. To demonstrate the
occurrence of solution uniqueness for problem (5.1), we create graphs that
show the proportion of solution uniqueness with respect to the number of
measurements in Figures 1. For each fixed value of $n=40$ and $2\leq r\leq 7$,
we conduct a simulation study on 100 random instances at each number of
measurements $m$. At each $m$, the proportion of cases (among $100$) of
$X_{0}$ that are recovered by solving problem (5.1) are depicted as the red
curve [11]. The percentage of cases of $X_{0}$ that are unique solutions of
problem (5.1) based on the above classification is displayed as the blue
curve. It is natural to see that all solutions $X_{0}$ that can be recovered
by solving problem (5.1) using the cvxpy package are unique solutions. But the
most important observation from Figure 1 is the minimal difference between the
red and blue curves. This suggests that our method in this paper sharply
predicts solution uniqueness for nuclear norm minimization problems (4.12).
Actually, the curve blue is slightly above the red one. The maximum gap
between them is around 3-4% at different ranks, but for most of $m$ (number of
observations) it is unnoticeable. In our opinion this small difference occurs
because the method mALBUM above solves problem (5.3) with only critical
solutions, which may be not global solutions (see discussion in Remark 3.8).
It is possible that some of the solutions of problem (5.2) are still in the
form
$(0,B,0)\in\mathbb{S}^{r}\times\mathbb{R}^{r\times(p-r)}\times\mathbb{S}^{p-r}_{+}$,
but the global optimal value is not $0$. In this case the corresponding
$X_{0}$ is not a unique solution, but this situation seems to be rare from our
experiments described in Figure 1.

Figure 1: Proportions of cases for which $X_{0}$ is the unique solution with
respect to the number of measurements.

## References

  * [1] D. Amelunxen, M. Lotz, M. B. McCoy, and J. A. Tropp: Living on the edge: Phase transitions in convex programs with random data, Information and Inference: A Journal of the IMA, 3 (2014), 224–294.
  * [2] F. J. Aragón Artacho and M. H. Geoffroy: Characterizations of metric regularity of subdifferentials, J. Convex Anal., 15 (2008), 365–380.
  * [3] A. M. Bruckstein, D. L. Donoho, and M. Elad. From sparse solutions of systems of equations to sparse modeling of signals and images, SIAM Rev., 51 (2009), 34–81.
  * [4] Y. Bello-Cruz, G. Li, and T. T. A. Nghia: Quadratic growth condition and uniqueness of optimal solution to Lasso, J. Optim. Theory Appl., 194 (2022), 167–190.
  * [5] J. Bolte, T. P. Nguyen, J. Peypouquet, B. W. Suter: From error bounds to the complexity of first-order descent methods for convex functions, Math. Program., 165 (2017), 471–507.
  * [6] J. F. Bonnans and A. Shapiro.  Perturbation analysis of optimization problems.  Springer Series in Operations Research. Springer-Verlag, New York, 2000\.
  * [7] J. Bolte, S. Sabach, and M. Teboulle: Nonconvex Lagrangian-based optimization: monitoring schemes and global convergence, Mathematics of Operations Research, 43 (2018), 1210–1232.
  * [8] Y. Cui, C. Ding, and X. Zhao: Quadratic growth conditions for convex matrix optimization problems associated with spectral functions, SIAM J. Optim., 27 (2017), 2332–2355.
  * [9] V. Chandrasekaran, B. Recht, P.A Parrilo, and A. S. Willsky: The convex geometry of linear inverse problems, Found Comput Math, 12 (2012), 805–849.
  * [10] E. Candès and Y. Plan: Matrix completion with noise, Proceeding of the IEEE, 98 (2010), 925–936.
  * [11] E. Candès and B. Recht: Exact matrix completion via convex optimization Found. Comput. Math., 9 (2009), 717–772.
  * [12] E. Candès and B. Recht: Simple bounds for recovering low-complexity models, Math. Program., 141 (2013), 577–589.
  * [13] E. J. Candès and T. Tao. Decoding by linear programming, IEEE Trans. Inform. Theory, 51 (2005), 4203–4215.
  * [14] L. Crome: Strong uniqueness, Numer. Math., 29 (1978), 179–193.
  * [15] I. Csiszár: Why least squares and maximum entropy? An axiomatic approach to inference for linear inverse problems, Ann. Statist., 19 (1991), 2032–2066.
  * [16] D. Drusvyatskiy, B. S. Mordukhovich, and T. T. A. Nghia: Second order growth, tilt stability, and metric regularity of the subdifferential, J. Convex Anal., 21 (2014), 1165–1192.
  * [17] D. L. Donoho and X. Huo: Uncertainty principles and ideal atomic decomposition, IEEE Trans. Inform. Theory, 47 (2001), 2845–2862.
  * [18] S. Foucart and H. Rauhut: A Mathematical Introduction to Compressive Sensing, Birkhäuser, New York, 2013.
  * [19] J. J. Fuchs: Recovery of exact sparse representations in the presence of bounded noise, IEEE Trans. Inf. Theory, 51 (2005), 3601–3608.
  * [20] J. Fadili, T. T. A. Nghia, and T. T. T. Tran: Sharp, strong and unique minimizers for low complexity robust recovery, IMA Inf. Inference, 12 (2023), 1461–1513.
  * [21] J. Fadili, T. T. A. Nghia, and D. N. Phan: Geometric characterizations for strong minima with applications to nuclear norm minimization problems, arXiv:2308.09224v1 (2023).
  * [22] J. C. Gilbert: On the solution uniqueness characterization in the $\ell_{1}$ norm and polyhedral gauge recovery,  J. Optim. Theory Appl., 172 (2017), 70–101.
  * [23] M. Grasmair. Linear convergence rates for Tikhonov regularization with positively homogeneous functionals, Inverse Problems, 27 (2011), 075014, 16.
  * [24] M. Grasmair, M. Haltmeier, O. Scherzer: Necessary and sufficient conditions for linear convergence of $\ell_{1}$-regularization, Comm. Pure Applied Math., 64 (2011), 161–182.
  * [25] R. A. Horn and C. R. Johnson: Matrix Analysis, Cambridge University Press, New York, 1985.
  * [26] T. Hoheisel and E. Paquette: Uniqueness in nuclear norm minimization: Flatness of the nuclear norm sphere and simultaneous polarization, J. Optim. Theo. Appl., 197 (2023), 252?-276.
  * [27] J. He, C. Kan, and W. Song: On solution uniqueness and robust recovery for sparse regularization with a gauge: from dual point of view, arXiv:2312.11168 (2023).
  * [28] N. T. V. Hang and E. Sarabi: Smoothness of subgradient mappings and its applications in parametric optimization, arXiv:2311.06026 (2023).
  * [29] A. S. Lewis and H. S. Sendov: Nonsmooth analysis of singular values. I. Theory. Set-Valued Anal., 13 (2005), 213–241.
  * [30] A. S. Lewis and H. S. Sendov: Nonsmooth analysis of singular values. II. Applications, Set-Valued Anal., 13 (2005), 243–264.
  * [31] A. S. Lewis and S. Zhang: Partial smoothness, tilt stability, and generalized Hessians, SIAM J. Optim., 23 (2013), 74–94.
  * [32] Y. Liu, S. Pan, and S. Bi: Isolated calmness of solution mappings and exact recovery conditions for nuclear norm optimization problems, Optimization, 70 (2021), 481–510.
  * [33] J. S. Jørgensen, C. Kruschel, and D. A. Lorenz. Testable uniqueness conditions for empirical assessment of undersampling levels in total variation-regularized X-ray CT, Inverse Probl. Sci. Eng., 23 (2015), 1283–1305.
  * [34] B. S. Mordukhovich: Sensitivity analysis in nonsmooth optimization, in Theoretical Aspects of Industrial Design (D. A. Field and V. Komkov, eds.), SIAM Proc. Applied Math., Vol. 58, pp. 32–46, SIAM, Philadelphia, PA, 1992.
  * [35] B. S. Mordukhovich: Variational Analysis and Generalized Differentiation, Springer, 2006.
  * [36] S. Mousavi and J. Shen: Solution uniqueness of convex piecewise affine functions based optimization with applications to constrained $\ell_{1}$-minimization, ESAIM: Control Optim. Cal. Variations, 25 (2019), No. 56, 27.
  * [37] B. S. Mordukhovich and R. T. Rockafellar:  Second-order subdifferential calculus with applications to tilt stability in optimization.  SIAM J. Optim., 22:953–986, 2012.
  * [38] B. T. Polyak: Sharp minima. Technical report, Institute of Control Sciences Lecture Notes, Moscow, USSR, 1979.
  * [39] B. T. Polyak: Introduction to Optimization, Optimization Software, Inc., Publications Division, New York, 1987.
  * [40] R. A. Poliquin and R. T. Rockafellar: Tilt stability of a local minimum.  SIAM J. Optim., 8(2): 287–299, 1998.
  * [41] N. Rao, B. Recht, and R. Nowak: Universal measurement bounds for structured sparse signal recovery In Proceedings of AISTATS (2012).
  * [42] V. Roth and B. Fischer: The group-lasso for generalized linear models: uniqueness of solutions and efficient algorithms, In Proceedings of the 25th international conference on Machine learning (2008).
  * [43] R. T. Rockafellar: Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970.
  * [44] R. T. Rockafellar and R. J-B. Wets: Variational Analysis, Springer, Berlin, 1998.
  * [45] R. J. Tibshirani: The Lasso problem and uniqueness, Electron. J. Stat., 7 (2013), 1456–1490.
  * [46] S. Vaiter, G. Peyré, C. Dossal, and J. Fadili. Robust sparse analysis regularization, IEEE Trans. Inform. Theory, 59 (2013), 2001–2016.
  * [47] G. A. Watson: Characterization of the subdifferential of some matrix norms, Linear Algebra Appl., 170 (1992), 33–45.
  * [48] Z. Zhou and A. M-C. So: A unified approach to error bounds for structured convex optimization, Math. Program., 165 (2017), 689–728.
  * [49] R. Zhang and J. Treiman: Upper-Lipschitz multifunctions and inverse subdifferentials, Nonlinear Anal., 24 (1995), 273–286.
  * [50] H. Zhang, W. Yin, and L. Cheng: Necessary and sufficient conditions of solution uniqueness in 1-norm minimization,  J. Optim. Theory Appl., 164 (2015), 109–122
  * [51] H. Zhang, H., M. Yan, and W. Yin: One condition for solution uniqueness and robustness of both $\ell_{1}$-synthesis and $\ell_{1}$-analysis minimization, Adv. Comput. Math., 42 (2016), 1381-1399.