# A Unified Recovery of Structured Signals Using Atomic Norm

Xuemei Chen  Department of Mathematics and Statistics, University of North
Carolina Wilmington, NC 28405

###### Abstract

In many applications we seek to recover signals from linear measurements far
fewer than the ambient dimension, given the signals have exploitable
structures such as sparse vectors or low rank matrices. In this paper we work
in a general setting where signals are approximately sparse in an so called
atomic set. We provide general recovery results stating that a convex
programming can stably and robustly recover signals if the null space of the
sensing map satisfies certain properties. Moreover, we argue that such null
space property can be satisfied with high probability if each measurement is
subgaussian even when the number of measurements are very few. Some new
results for recovering signals sparse in a frame, and recovering low rank
matrices are also derived as a result.

##  1 Introduction

Given a compact set $\displaystyle E\subset\mathbb{R}^{d}$, let
$\displaystyle\text{conv}(E)$ be the convex hull of $\displaystyle E$. We
define the _Minkowski functional_ to be

$\inf\\{\lambda>0:\lambda^{-1}v\in\text{conv}(E)\\}.$ (1)

If the centroid of $\displaystyle\text{conv}(E)$ is at the origin, then (1)
can be rewritten as

$\inf\\{\sum_{i\in I}c_{i}:v=\sum_{i\in I}c_{i}x_{i},c_{i}\geq 0\\}.$ (2)

In addition, if $\displaystyle E=-E$, then (1) or (2) is a norm, called the
_atomic norm_ [6].

Throughout this paper, we will assume the _atomic set_
$\displaystyle\mathcal{W}=\\{w_{i}\\}_{i\in I}$ is a compact subset of
$\displaystyle\mathbb{R}^{d}$. Define
$\displaystyle\mathcal{W}_{\text{sym}}:=\mathcal{W}\cup(-\mathcal{W})$ and the
atomic norm associated with $\displaystyle\mathcal{W}$ as

$\|v\|_{\mathcal{W}}:=\inf\\{\lambda>0:\lambda^{-1}v\in\text{conv}(\mathcal{W}_{\text{sym}})\\}=\inf\\{\sum_{i=1}^{N}|c_{i}|:v=\sum_{i=1}^{N}c_{i}w_{i}\\}.$
(3)

Let $\displaystyle C_{\mathcal{W}}$ be the smallest constant such that

$\displaystyle\|v\|_{\mathcal{W}}\leq C_{\mathcal{W}}\|v\|_{2}.$

We let $\displaystyle
B_{\mathcal{W}}:=\\{v\in\mathbb{R}^{d}:\|v\|_{\mathcal{W}}\leq
1\\}=\text{conv}(\mathcal{W}_{\text{sym}})$ be the unit ball with respect to
the atomic norm.

We would like to recover a structured signal $\displaystyle z_{0}$ from few
linear measurements $\displaystyle y=\mathcal{A}z_{0}$ via the convex
minimization problem

$\hat{z}=\arg\min_{z\in\mathbb{R}^{d}}\|z\|_{\mathcal{W}}\quad\text{ subject
to }\quad\mathcal{A}z=y.\\\ $ ($\displaystyle\text{P}_{\mathcal{W}}$)

The vector $\displaystyle\mathcal{A}z_{0}$ contains $\displaystyle m$ inner
products with $\displaystyle z_{0}$, so
$\displaystyle\mathcal{A}z_{0}\in\mathbb{R}^{m}$.

If the measurement is perturbed as $\displaystyle y=\mathcal{A}z_{0}+e$ where
$\displaystyle\|e\|_{2}\leq\epsilon$, then we consider the following version

$\hat{z}=\arg\min_{z\in\mathbb{R}^{d}}\|z\|_{\mathcal{W}}\quad\text{ subject
to }\quad\|\mathcal{A}z-y\|_{2}\leq\epsilon.\\\ $
($\displaystyle\text{P}_{\mathcal{W},\epsilon}$)

By “structured signal”, we mean that it is a linear combination of very few
atoms in $\displaystyle\mathcal{W}$. We say a vector $\displaystyle z$ is
_$\displaystyle\mathcal{W}$ -sparse of order $\displaystyle s$ (or simply
$\displaystyle\mathcal{W}$-$\displaystyle s$-sparse)_ if $\displaystyle z$ can
be written as a linear combination of at most $\displaystyle s$ atoms from
$\displaystyle\mathcal{W}$. Such collection of vectors will be denoted
$\displaystyle\Sigma_{\mathcal{W},s}$, i.e.,

$\displaystyle\Sigma_{\mathcal{W},s}:=\\{z\in\mathbb{R}^{d}:z=\sum_{i\in
J}c_{i}w_{i}\text{ for some }|J|\leq s,c_{i}\in\mathbb{R}\\}.$

Recovering $\displaystyle z_{0}$ through
($\displaystyle\text{P}_{\mathcal{W},\epsilon}$) is possible even when the
number of linear measurement $\displaystyle m$ is far less than the ambient
dimension $\displaystyle d$, if $\displaystyle\mathcal{A}$ is well designed.

We need a way to define the “tail” when a vector is not exactly
$\displaystyle\mathcal{W}$-sparse. This will be an important notion in this
paper. Define

$\sigma_{\mathcal{W},s}(z):=\inf\\{\|z-v\|_{\mathcal{W}}:v\in\Sigma_{\mathcal{W},s}\\}.$
(4)

This tail can also be viewed as the distance from $\displaystyle z$ to the set
$\displaystyle\Sigma_{\mathcal{W},s}$.

In the case that the minimum can be obtained in (4), we write

$z_{s}:=\arg\min\\{\|z-v\|_{\mathcal{W}}:v\in\Sigma_{\mathcal{W},s}\\},$ (5)

and hence $\displaystyle\sigma_{\mathcal{W},s}(z)=\|z-z_{s}\|_{\mathcal{W}}$.

###  1.1 Notations

Given the linear map $\displaystyle\mathcal{A}$,
$\displaystyle\mathcal{N}(\mathcal{A})$ is the null space of
$\displaystyle\mathcal{A}$, and $\displaystyle\nu_{A}$ is the smallest
singular value of the matrix of map $\displaystyle\mathcal{A}$ under an
orthonormal basis. For any matrix $\displaystyle X$,
$\displaystyle\\{\sigma_{i}(X)\\}_{i=1}^{K}$ are the singular values of
$\displaystyle X$, and $\displaystyle\|X\|_{*}=\sum_{i=1}^{K}\sigma_{i}(X)$ is
the nuclear norm of $\displaystyle X$. $\displaystyle\|X\|_{F}$ is the
Frobenius norm of $\displaystyle X$. For any index set $\displaystyle T$,
$\displaystyle|T|$ is the cardinality of $\displaystyle T$, and $\displaystyle
T^{c}$ is the compliment set of $\displaystyle T$. For any $\displaystyle
p\geq 1$, $\displaystyle\|\cdot\|_{p}$ is the $\displaystyle\ell_{p}$ norm.

$\displaystyle\mathbb{S}^{d-1}$ is the unit $\displaystyle\ell_{2}$ norm ball
of $\displaystyle\mathbb{R}^{d}$.

The notation $\displaystyle\mathbb{R}^{d}$ means a finite dimensional real
Hilbert space in general, but also denotes the real Euclidean space in certain
examples which will be clear from context.

###  1.2 Examples

We will now list several examples of atomic sets that are special cases of our
setup. See more examples in [6].

######  Example 1.1 (Compressed Sensing).

As the simplest example, when the atom set $\displaystyle\mathcal{E}$ is the
canonical orthonormal basis of the Euclidean space, we have
$\displaystyle\|v\|_{\mathcal{E}}=\|v\|_{1}$. In this context, an
$\displaystyle\mathcal{E}$-$\displaystyle s$-sparse vector is a vector whose
coordinates are nonzero at most $\displaystyle s$ locations. This is the
classical compressed sensing [7, 10, 9]. It is easy to show that the tail
$\displaystyle\sigma_{\mathcal{E},s}(z)=\|z_{T^{c}}\|_{1}$ where
$\displaystyle T$ is the index set of the largest $\displaystyle s$
coordinates in magnitude of $\displaystyle z$.

######  Example 1.2 (Compressed Sensing with Frames).

Let $\displaystyle\mathcal{F}=\\{f_{i}\\}_{i=1}^{N}$ be a frame of the
Euclidean space $\displaystyle\mathbb{R}^{d}$, hence $\displaystyle N\geq d$.
Let $\displaystyle F=[f_{1},f_{2},\cdots,f_{N}]$ be the $\displaystyle d\times
N$ matrix whose columns are the atoms. We have

$\displaystyle\displaystyle\|z-v\|_{\mathcal{F}}$
$\displaystyle\displaystyle=\min\\{\|c\|_{1}:Fc=z-v\\}$
$\displaystyle\displaystyle=\min\\{\|c+u-u\|_{1}:z=F(c+u),v=Fu\\}$
$\displaystyle\displaystyle=\min\\{\|x-u\|_{1}:z=Fx,v=Fu\\}$ (6)

which implies

$\sigma_{\mathcal{F},s}(z)=\min_{v\in\Sigma_{\mathcal{F},s}}\|z-v\|_{\mathcal{F}}=\min\\{\|x-u\|_{1},z=Fx,\
Fu\in\Sigma_{\mathcal{F},s}\\}.$ (7)

There has been many work on this case [20, 5, 19, 2, 8, 4]. See Section 5 for
more details.

######  Example 1.3 (Low Rank Matrix Recovery).

Let
$\displaystyle\mathcal{M}=\\{uv^{T}:u\in\mathbb{R}^{n_{1}},v\in\mathbb{R}^{n_{2}},\|u\|_{2}=\|v\|_{2}=1\\}$.
For any matrix $\displaystyle X\in\mathbb{R}^{n_{1}\times n_{2}}$, its atomic
norm becomes the nuclear norm. Although
$\displaystyle\|X\|_{\mathcal{M}}=\|X\|_{*}$ is a well known fact, we provide
a proof in the Appendix (Lemma 7.1).
$\displaystyle\Sigma_{\mathcal{M},s}=\\{\sum_{i=1}^{s}c_{i}u_{i}v_{i}^{T}:\|u\|_{2}=\|v\|_{2}=1\\}$
is the set of $\displaystyle n_{1}\times n_{2}$ matrices whose rank is at most
$\displaystyle s$. Let $\displaystyle K=\min\\{n_{1},n_{2}\\}$. Note that the
tail of any matrix $\displaystyle Z$ has a simple expression

$\sigma_{\mathcal{M},s}(Z)=\sum_{j=s+1}^{K}\sigma_{j}(Z).$ (8)

This is due to Lemma 7.2. Specifically, for $\displaystyle
V\in\Sigma_{\mathcal{M},s}$, we have
$\displaystyle\|Z-V\|_{*}=\sum_{i=1}^{K}\sigma_{i}(Z-V)\geq\sum_{i=1}^{K}|\sigma_{i}(Z)-\sigma_{i}(V)|=\sum_{i=1}^{s}|\sigma_{i}(Z)-\sigma_{i}(V)|+\sum_{i=s+1}^{K}\sigma_{i}(Z)\geq\sum_{i=s+1}^{K}\sigma_{i}(Z)$.
So
$\displaystyle\sigma_{\mathcal{M},s}(Z)=\min_{V\in\Sigma_{\mathcal{M},s}}\|Z-V\|_{*}=\sum_{j=s+1}^{K}\sigma_{j}(Z)$.
Low rank matrix recovery through nuclear norm minimization have been
investigated in [21, 22, 16]. See Section 6 for more details.

######  Example 1.4 (Phase Retrieval).

Let $\displaystyle\mathcal{P}=\\{uu^{T}:u\in\mathbb{C}^{n},\|u\|_{2}=1\\}$ be
the collection of unit norm rank-1’s in $\displaystyle\mathcal{H}_{n}$, the
space of complex Hermitian $\displaystyle n\times n$ matrices.
$\displaystyle\mathcal{H}_{n}$ is a real vector space of dimension
$\displaystyle n^{2}$. For any Hermitian matrix $\displaystyle
X\in\mathcal{H}_{n}$, its atomic norm is its nuclear norm.
$\displaystyle\Sigma_{\mathcal{P},s}=\\{\sum_{i=1}^{s}c_{i}u_{i}u_{i}^{*}:\|u_{i}\|_{2}=1\\}$
is the set of $\displaystyle n\times n$ Hermitian matrices whose rank is at
most $\displaystyle s$.

The phase retrieval problem aims to recover $\displaystyle
z_{0}\in\mathbb{C}^{n}$ up to a phase from $\displaystyle\\{|\langle
z_{0},a_{i}\rangle|\\}_{i=1}^{m}$, which is equivalent to recovering
$\displaystyle Z_{0}=z_{0}z_{0}^{*}$ from the linear measurement
$\displaystyle\mathcal{A}(Z_{0})=y:=(\langle
Z_{0},a_{i}a_{i}^{*}\rangle)_{i=1}^{m}$. One may solve (PP,ϵ), which is

$\hat{Z}=\arg\min_{Z\in\mathcal{H}_{n}}\|Z\|_{*}\quad\text{ subject to
}\quad\|\mathcal{A}(Z)-y\|_{2}\leq\epsilon.$ (9)

to recover $\displaystyle Z_{0}\in\Sigma_{\mathcal{P},1}$, hence recover
$\displaystyle z$ up to a phase. See [3, 18].

###  1.3 Contributions and Organizations

Our work has a very general setting for recovering signals sparse in an atomic
set via the convex programming
($\displaystyle\text{P}_{\mathcal{W},\epsilon}$). Many important applications
fall into this general setting as outlined above. Our work has a similar setup
as [6], but it differers from [6] as it provides deterministic recovery
results. Consequently, any probabilistic statements are uniform on the signals
in the sense that the sensing map satisfies certain condition with high
probability, and hence all signals can be recovered robustly.

We provide thorough recovery results in Theorem 2.2, Theorem 2.6, Theorem 2.7,
and Theorem 2.9. Theorem 2.2 characterizes the exact recovery of sparse
signals via ($\displaystyle\text{P}_{\mathcal{W}}$) when no noise is present.
Theorem 2.9 shows that recovery through
($\displaystyle\text{P}_{\mathcal{W},\epsilon}$) is stable with respect to the
tail and robust with respect to measurement noise if the measurement map
$\displaystyle\mathcal{A}$ satisfy a strong null space property. Theorem 2.6
and Theorem 2.7 are similar recovery results that require extra but reasonable
condition on the set $\displaystyle\mathcal{W}$.

We also argue that very few measurements are sufficient for recovery. Theorem
3.4 claims that if there are $\displaystyle N$ atoms in
$\displaystyle\mathcal{W}$, then $\displaystyle O(s\ln(N/s)$ measurements are
required when using ($\displaystyle\text{P}_{\mathcal{W}}$). On the other
hand, Corollary 4.7 shows very few subgaussian measurements provide good
recovery if the number of measurement is on the order of square of a Gaussian
width of a set related to the null space property. This square of Gaussian
width coincides with $\displaystyle O(s\ln(N/s)$ in many applications.

Sections 5 and 6 focus on two special cases, signals sparse in a frame and low
rank matrix recovery. Some consequences of our main results have appeared in
previous literature, like Corollary 5.4, but our analysis is simpler.
Corollary 5.3 and Corollary 5.5 are new results. For low rank matrix recovery,
Corollary 6.2(a)(c) are new results.

##  2 Recovery Results

In this section, we will provide stability and robustness results of
recovering signals through the minimization problem
($\displaystyle\text{P}_{\mathcal{W}}$) or
($\displaystyle\text{P}_{\mathcal{W},\epsilon}$) if the null space of the
linear map $\displaystyle\mathcal{A}$ satisfies certain properties.

Given the set $\displaystyle\mathcal{W}$, and the sparsity level
$\displaystyle s$, we define the set

$E_{\mathcal{W},s}:=\\{z:\|v\|_{\mathcal{W}}<\|z-v\|_{\mathcal{W}},\text{ for
any }v\in\Sigma_{\mathcal{W},s}\\}.$ (10)

Loosely speaking, the signals in $\displaystyle E_{\mathcal{W},s}$ should have
their atomic energy spread out over the atoms of $\displaystyle\mathcal{W}$.
On the other hand, a $\displaystyle\mathcal{W}$-$\displaystyle s$-sparse
vector has its energy concentrated at $\displaystyle s$ atoms only and
obviously does not belong to $\displaystyle E_{\mathcal{W},s}$. Furthermore,
one can easily show that $\displaystyle\Sigma_{\mathcal{W},2s}\cap
E_{\mathcal{W},s}=\emptyset$.

Since the goal is to tell $\displaystyle\mathcal{W}$-$\displaystyle s$-sparse
vectors apart after mapping through $\displaystyle\mathcal{A}$, at minimum, we
need to have
$\displaystyle\mathcal{N}(\mathcal{A})\cap\Sigma_{\mathcal{W},2s}=\\{0\\}$.
The following property of $\displaystyle\mathcal{A}$ can guarantee this.

######  Definition 2.1.

Given the set $\displaystyle\mathcal{W}$, and the sparsity level
$\displaystyle s$, $\displaystyle\mathcal{A}$ is said to have
$\displaystyle\mathcal{W}$ null space property of order $\displaystyle s$
($\displaystyle\mathcal{W}$-$\displaystyle s$-NSP) if
$\displaystyle\mathcal{N}(\mathcal{A})\backslash\\{0\\}\subseteq
E_{\mathcal{W},s}$. Specifically, $\displaystyle\mathcal{W}$-$\displaystyle
s$-NSP is equivalent to

$\|v\|_{\mathcal{W}}<\|z-v\|_{\mathcal{W}},\quad\text{ for any
}z\in\mathcal{N}(\mathcal{A})\backslash\\{0\\}\text{ and any
}v\in\Sigma_{\mathcal{W},s}.$ (11)

The condition $\displaystyle\mathcal{W}$-$\displaystyle s$-NSP is clearly
stronger than the bare minimum
$\displaystyle\mathcal{N}(A)\cap\Sigma_{\mathcal{W},2s}=\\{0\\}$, but it is
also a necessary condition to recover all
$\displaystyle\mathcal{W}$-$\displaystyle s$-sparse signals if we choose to
use the minimization problem ($\displaystyle\text{P}_{\mathcal{W}}$).

######  Theorem 2.2.

$\displaystyle\mathcal{A}$ has $\displaystyle\mathcal{W}$-$\displaystyle
s$-NSP if and only if the method ($\displaystyle\text{P}_{\mathcal{W}}$) is
successful at recovering all signals in $\displaystyle\Sigma_{\mathcal{W},s}$.

###### Proof.

Suppose ($\displaystyle\text{P}_{\mathcal{W}}$) is successful at recovering
all signals in $\displaystyle\Sigma_{\mathcal{W},s}$. Take any $\displaystyle
v\in\Sigma_{\mathcal{W},s}$ and any $\displaystyle
z\in\mathcal{N}(\mathcal{A})\backslash\\{0\\}$. We will use
($\displaystyle\text{P}_{\mathcal{W}}$) to recover $\displaystyle-v$ (with
$\displaystyle y=-\mathcal{A}v$). Both $\displaystyle-v$ and $\displaystyle
z-v$ are feasible in ($\displaystyle\text{P}_{\mathcal{W}}$) and
$\displaystyle-v\neq z-v$. By assumption, $\displaystyle-v$ must be the unique
minimizer, which means
$\displaystyle\|-v\|_{\mathcal{W}}<\|z-v\|_{\mathcal{W}}$.

On the other hand, we assume $\displaystyle\mathcal{A}$ satisfies
$\displaystyle\mathcal{W}$-$\displaystyle s$-NSP. Fix an arbitrary
$\displaystyle v\in\Sigma_{\mathcal{W},s}$, we solve
$\displaystyle\min_{z\in\mathbb{R}^{d}}\|z\|_{\mathcal{W}}$ subject to
$\displaystyle\mathcal{A}z=\mathcal{A}(v)$. For every feasible $\displaystyle
z\neq v$, we have $\displaystyle
v-z\in\mathcal{N}(\mathcal{A})\backslash\\{0\\}$, so by
$\displaystyle\mathcal{W}$-$\displaystyle s$-NSP,
$\displaystyle\|v\|_{\mathcal{W}}<\|v-z-v\|_{\mathcal{W}}=\|z\|_{\mathcal{W}}$,
which shows that the unique minimizer of this problem must be $\displaystyle
v$, the signal to be recovered. ∎

######  Remark 2.3.

In the setting of Example 1.1, Definition 2.1 reduces to the well known null
space property of a matrix $\displaystyle A$, which is:

$\|z_{T}\|_{1}<\|z_{T^{c}}\|_{1},\text{ for any
}z\in\mathcal{N}(A)\backslash\\{0\\}\text{ and any }|T|\leq s.$ (12)

This is because for any $\displaystyle z\in\mathcal{N}(A)\backslash\\{0\\}$
and any $\displaystyle v\in\Sigma_{\mathcal{E},s}$, let $\displaystyle T$ be
the support of $\displaystyle v$, then

$\displaystyle\|v\|_{1}-\|z-v\|_{1}=\|v\|_{1}-\|z_{T}-v\|_{1}-\|z_{T^{c}}\|_{1}\leq\|v+z_{T}-v\|_{1}-\|z_{T^{c}}\|_{1}=\|z_{T}\|_{1}-\|z_{T^{c}}\|_{1}<0.$

In compressed sensing, by a simple compactness argument, the NSP (12) implies
the existence of $\displaystyle\rho<1$ such that
$\displaystyle\|z_{T}\|_{1}\leq\rho\|z_{T^{c}}\|_{1}$ for any $\displaystyle
z\in\mathcal{N}(A)$ and any $\displaystyle|T|\leq s$. However, this is
certainly not the case for Definition 2.1. In fact, we can never have

$\|v\|_{\mathcal{W}}\leq\rho\|z-v\|_{\mathcal{W}},\qquad\text{ for any
}z\in\mathcal{N}(\mathcal{A}),\text{ and any }v\in\Sigma_{\mathcal{W},s}.$
(13)

if $\displaystyle\rho$ is less than 1. This is because with a fixed
$\displaystyle z$, we can choose $\displaystyle v\in\Sigma_{\mathcal{W},s}$
such that $\displaystyle\|v\|_{\mathcal{W}}$ is big enough to make
$\displaystyle\|v\|_{\mathcal{W}}>\rho\|z-v\|_{\mathcal{W}}$.

In order to make (13) feasible, we have to refine the choice of $\displaystyle
v$. Therefore we will propose two strengthened null space properties that
restrict $\displaystyle v$ to be the best $\displaystyle s$-term approximation
of $\displaystyle z$.

######  Definition 2.4.

Recall $\displaystyle z_{s}$ as defined in (5).

(a) $\displaystyle\mathcal{A}$ is said to have the stable
$\displaystyle\mathcal{W}$ null space property of order $\displaystyle s$ with
the NSP constant $\displaystyle\rho<1$
($\displaystyle\mathcal{W}$-$\displaystyle s$-$\displaystyle\rho$-NSP) if

$\|z_{s}\|_{\mathcal{W}}\leq\rho\|z-z_{s}\|_{\mathcal{W}},\qquad\text{ for any
}z\in\mathcal{N}(\mathcal{A}).$ (14)

(b) $\displaystyle\mathcal{A}$ is said to have the robust
$\displaystyle\mathcal{W}$ null space property of order $\displaystyle s$
($\displaystyle\mathcal{W}$-$\displaystyle s$-RNSP) if there exist constants
$\displaystyle\tau>0$ and $\displaystyle 0<\rho<1$ such that

$\|z_{s}\|_{\mathcal{W}}\leq\rho\|z-z_{s}\|_{\mathcal{W}}+\tau\|\mathcal{A}z\|_{2},\qquad\text{for
any }z\in\mathbb{R}^{d}.$ (15)

We want to include Definition 2.4(b) as well since this type of “null space”
property has been used in compressed sensing [11] and low matrix recovery
[16].

We will see in Theorem 2.6 and Theorem 2.7 that both versions of the
strengthened null space property will imply the stable and robust recovery of
any signal via ($\displaystyle\text{P}_{\mathcal{W},\epsilon}$) if the atomic
set $\displaystyle\mathcal{W}$ satisfies certain conditions.

######  Definition 2.5.

We call $\displaystyle\mathcal{W}$ $\displaystyle s$-splittable if for any
$\displaystyle x,y\in\mathbb{R}^{d}$,

$\displaystyle\|x+y\|_{\mathcal{W}}\geq\|x_{s}\|_{\mathcal{W}}-\|y_{s}\|_{\mathcal{W}}+\|y-y_{s}\|-\|x-x_{s}\|_{\mathcal{W}}.$

Definition (2.5) looks strange at first glance, but as two important examples,
both $\displaystyle\mathcal{E}$ and $\displaystyle\mathcal{M}$ are
$\displaystyle s$-splittable. See Lemma 7.3 in the Appendix.

######  Theorem 2.6.

Let $\displaystyle\mathcal{W}$ be $\displaystyle s$-splittable. If
$\displaystyle\mathcal{A}$ has the stable $\displaystyle\mathcal{W}$-NSP of
order $\displaystyle s$ with constant $\displaystyle 0<\rho<1$, then for any
$\displaystyle z_{0}\in\mathbb{R}^{d}$ and $\displaystyle
y=\mathcal{A}z_{0}+e$ where $\displaystyle\|e\|_{2}\leq\epsilon$, we have

$\|\hat{z}-z_{0}\|_{\mathcal{W}}\leq\frac{2+2\rho}{1-\rho}\sigma_{\mathcal{W},s}(z_{0})+\frac{4C_{\mathcal{W}}}{(1-\rho)\nu_{A}}\epsilon,$
(16)

where $\displaystyle\hat{z}$ is from
($\displaystyle\text{P}_{\mathcal{W},\epsilon}$).

###### Proof.

Let $\displaystyle h=\hat{z}-z_{0}$. We decompose $\displaystyle h$ as
$\displaystyle h=a+\eta$ where $\displaystyle a\in N(\mathcal{A})$ and
$\displaystyle\eta\in N(\mathcal{A})^{\perp}$. We have

$\displaystyle\|\eta\|_{2}\leq\frac{1}{\nu_{A}}\|Ah\|_{2}\leq\frac{2\epsilon}{\nu_{A}}.$

On one hand, using $\displaystyle\hat{z}$ is a minimizer and
$\displaystyle\mathcal{W}$ is splittable,

$\displaystyle\displaystyle\|z_{0}\|_{\mathcal{W}}$
$\displaystyle\displaystyle\geq\|\hat{z}\|_{\mathcal{W}}=\|a+\eta+z_{0}\|_{\mathcal{W}}\geq\|z_{0}+a\|_{\mathcal{W}}-\|\eta\|_{\mathcal{W}}$
$\displaystyle\displaystyle\geq\|z_{0,s}\|_{\mathcal{W}}-\|a_{s}\|_{\mathcal{W}}+\|a-a_{s}\|_{\mathcal{W}}-\|z_{0}-z_{0,s}\|_{\mathcal{W}}-\|\eta\|_{\mathcal{W}}$
$\displaystyle\displaystyle\geq\|z_{0}\|_{\mathcal{W}}-\|z_{0}-z_{0,s}\|_{\mathcal{W}}-\|a_{s}\|_{\mathcal{W}}+\|a-a_{s}\|_{\mathcal{W}}-\|z_{0}-z_{0,s}\|_{\mathcal{W}}-\|\eta\|_{\mathcal{W}}.$

If we denote $\displaystyle\|z_{0}-z_{0,s}\|_{\mathcal{W}}$ as
$\displaystyle\sigma$, then the above simplifies to

$\|a-a_{s}\|_{\mathcal{W}}\leq
2\sigma+\|a_{s}\|_{\mathcal{W}}+\|\eta\|_{\mathcal{W}}$ (17)

On the other hand, by stable $\displaystyle\mathcal{W}$-NSP,

$\|a_{s}\|_{\mathcal{W}}\leq\rho\|a-a_{s}\|_{\mathcal{W}}.$ (18)

Combining (17) and (18), we have

$\displaystyle\|a_{s}\|_{\mathcal{W}}\leq
2\rho\sigma+\rho\|a_{s}\|_{\mathcal{W}}+\rho\|\eta\|_{\mathcal{W}},$

which simplifies to

$\|a_{s}\|_{\mathcal{W}}\leq\frac{2\rho}{1-\rho}\sigma+\frac{\rho}{1-\rho}\|\eta\|_{\mathcal{W}}.$
(19)

In the end, using (17) and (19),

$\displaystyle\displaystyle\|h\|_{\mathcal{W}}$
$\displaystyle\displaystyle\leq\|a\|_{\mathcal{W}}+\|\eta\|_{\mathcal{W}}\leq\|a_{s}\|_{\mathcal{W}}+\|a-a_{s}\|_{\mathcal{W}}+\|\eta\|_{\mathcal{W}}$
$\displaystyle\displaystyle\leq\|a_{s}\|_{\mathcal{W}}+2\sigma+\|a_{s}\|_{\mathcal{W}}+\|\eta\|_{\mathcal{W}}+\|\eta\|_{\mathcal{W}}$
$\displaystyle\displaystyle\leq\frac{4\rho}{1-\rho}\sigma+\frac{2\rho}{1-\rho}\|\eta\|_{\mathcal{W}}+2\sigma+2\|\eta\|_{\mathcal{W}}$
$\displaystyle\displaystyle=\frac{2+2\rho}{1-\rho}\sigma+\frac{2}{1-\rho}\|\eta\|_{\mathcal{W}}\leq\frac{2+2\rho}{1-\rho}\sigma+\frac{2C_{\mathcal{W}}}{1-\rho}\|\eta\|_{2}$
$\displaystyle\displaystyle\leq\frac{2+2\rho}{1-\rho}\sigma+\frac{4C_{\mathcal{W}}}{(1-\rho)\nu_{A}}\epsilon.$

∎

######  Theorem 2.7.

Let $\displaystyle\mathcal{W}$ be $\displaystyle s$-splittable. Given
$\displaystyle z_{0}\in\mathbb{R}^{d}$ and the recovered signal
$\displaystyle\hat{z}$ from ($\displaystyle\text{P}_{\mathcal{W},\epsilon}$)
where $\displaystyle y=\mathcal{A}z_{0}+e$ with
$\displaystyle\|e\|_{2}\leq\epsilon$, then the robust
$\displaystyle\mathcal{W}$-NSP of order $\displaystyle s$ yields the following
stability result

$\|\hat{z}-z_{0}\|_{\mathcal{W}}\leq\frac{2(1+\rho)}{1-\rho}\sigma_{\mathcal{W},s}(z_{0})+\frac{4\tau}{1-\rho}\epsilon.$
(20)

###### Proof.

Let $\displaystyle h=\hat{z}-z_{0}$. Denote
$\displaystyle\sigma_{\mathcal{W},s}(z_{0})=\|z\|_{\mathcal{W}}-\|z_{s}\|_{\mathcal{W}}$
by $\displaystyle\sigma$. Using $\displaystyle\hat{z}$ is a minimizer and
$\displaystyle\mathcal{W}$ is splittable,

$\displaystyle\displaystyle\|z_{0}\|_{\mathcal{W}}$
$\displaystyle\displaystyle\geq\|\hat{z}\|_{\mathcal{W}}=\|h+z_{0}\|_{\mathcal{W}}\geq\|z_{0,s}\|_{\mathcal{W}}-\|h_{s}\|_{\mathcal{W}}+\|h-h_{s}\|_{\mathcal{W}}-\sigma$
$\displaystyle\displaystyle\geq\|z_{0}\|_{\mathcal{W}}-\sigma-\|h_{s}\|_{\mathcal{W}}+\|h-h_{s}\|_{\mathcal{W}}-\sigma,$

which simplifies to

$\|h-h_{s}\|_{\mathcal{W}}\leq\|h_{s}\|_{\mathcal{W}}+2\sigma.$ (21)

Now we use the $\displaystyle\mathcal{W}$-RNSP to get

$\|h_{s}\|_{\mathcal{W}}\leq\rho\|h-h_{s}\|_{\mathcal{W}}+\tau\|Ah\|_{2}.$
(22)

(21) and (22) implies

$\|h_{s}\|_{\mathcal{W}}\leq\frac{1}{1-\rho}(2\sigma\rho+\tau\|Ah\|_{2}).$
(23)

Using (21) and (23),

$\displaystyle\displaystyle\|h\|_{\mathcal{W}}$
$\displaystyle\displaystyle\leq\|h_{s}\|_{\mathcal{W}}+\|h-h_{s}\|_{\mathcal{W}}\leq
2\|h_{s}\|_{\mathcal{W}}+2\sigma$
$\displaystyle\displaystyle\leq\frac{2}{1-\rho}(2\sigma\rho+\tau\|Ah\|_{2})+2\sigma=\frac{2(1+\rho)}{1-\rho}\sigma+\frac{2}{1-\rho}\tau\|Ah\|_{2}.$

Finally, the desired result holds because $\displaystyle\|Ah\|_{2}\leq
2\epsilon$. ∎

Finally, we proposed a third kind of null space property.

######  Definition 2.8.

$\displaystyle\mathcal{A}$ is said to have the strong
$\displaystyle\mathcal{W}$ null space property of order $\displaystyle s$
($\displaystyle\mathcal{W}$-$\displaystyle s$-SNSP) if there exists
$\displaystyle c>0$ such that

$\|z-v\|_{\mathcal{W}}-\|v\|_{\mathcal{W}}\geq c\|z\|_{2},\qquad\text{ for any
}z\in\mathcal{N}(\mathcal{A}),\text{ and any }v\in\Sigma_{\mathcal{W},s}.$
(24)

As we will see in the following theorem, recovery results with this property
does not pose further conditions on $\displaystyle\mathcal{W}$. Definition 2.8
is inspired by [8] and will be discussed more in Section 5.

######  Theorem 2.9.

If $\displaystyle\mathcal{A}$ has the strong $\displaystyle\mathcal{W}$-NSP of
order $\displaystyle s$, then for any $\displaystyle z_{0}\in\mathbb{R}^{d}$
and $\displaystyle y=\mathcal{A}z_{0}+e$ where
$\displaystyle\|e\|_{2}\leq\epsilon$, we have

$\displaystyle\|\hat{z}-z_{0}\|_{2}\leq\frac{2}{\nu_{\mathcal{A}}}\left(\frac{C_{\mathcal{W}}}{c}+1\right)\epsilon+\frac{2}{c}\sigma_{\mathcal{W},s}(z_{0}),$

where $\displaystyle\hat{z}$ is from
($\displaystyle\text{P}_{\mathcal{W},\epsilon}$).

###### Proof.

Let
$\displaystyle\sigma_{\mathcal{W},s}(z_{0})=\|z_{0}-v_{0}\|_{\mathcal{W}}$,
where $\displaystyle v_{0}\in\Sigma_{\mathcal{W},s}.$ Let $\displaystyle
h=\hat{z}-z_{0}$. We abbreviate $\displaystyle\sigma_{\mathcal{W},s}(z_{0})$
to $\displaystyle\sigma$, then
$\displaystyle\|v_{0}\|_{\mathcal{W}}+\sigma\geq\|z_{0}\|_{\mathcal{W}}\geq\|\hat{z}\|_{\mathcal{W}}=\|h+z_{0}\|_{\mathcal{W}}=\|h+v_{0}+z_{0}-v_{0}\|_{\mathcal{W}}\geq\|h+v_{0}\|_{\mathcal{W}}-\sigma$,
which simplifies to

$\|h+v_{0}\|_{\mathcal{W}}\leq\|v_{0}\|_{\mathcal{W}}+2\sigma.$ (25)

On the other hand, we decompose $\displaystyle h$ as $\displaystyle h=a+\eta$
where $\displaystyle a\in N(\mathcal{A})$ and $\displaystyle\eta\in
N(\mathcal{A})^{\perp}$. We have

$\displaystyle\|\eta\|_{2}\leq\frac{1}{\nu_{A}}\|Ah\|_{2}\leq\frac{2\epsilon}{\nu_{A}}.$

By strong NSP,

$\|a+v_{0}\|_{\mathcal{W}}-\|v_{0}\|_{\mathcal{W}}\geq c\|a\|_{2}.$ (26)

Combining (25) and (54), we have

$\displaystyle\displaystyle c\|a\|_{2}$
$\displaystyle\displaystyle\leq\|a+v_{0}\|_{\mathcal{W}}-\|h+v_{0}\|_{\mathcal{W}}+2\sigma_{\mathcal{W},s}(z_{0})$
$\displaystyle\displaystyle\leq\|a-h\|_{\mathcal{W}}+2\sigma_{\mathcal{W},s}(z_{0})=\|\eta\|_{\mathcal{W}}+2\sigma_{\mathcal{W},s}(z_{0}).$

In the end,

$\displaystyle\displaystyle\|h\|_{2}$
$\displaystyle\displaystyle\leq\|a\|_{2}+\|\eta\|_{2}\leq\frac{1}{c}\|\eta\|_{\mathcal{W}}+\frac{2}{c}\sigma_{\mathcal{W},s}(z_{0})+\|\eta\|_{2}$
$\displaystyle\displaystyle\leq\left(\frac{C_{\mathcal{W}}}{c}+1\right)\|\eta\|_{2}+\frac{2}{c}\sigma_{\mathcal{W},s}(z_{0})\leq\frac{2}{\nu_{\mathcal{A}}}\left(\frac{C_{\mathcal{W}}}{c}+1\right)\epsilon+\frac{2}{c}\sigma_{\mathcal{W},s}(z_{0})$

∎

##  3 Minimum Number of Measurements

This section provides the smallest number of measurements required for
successful recovery, whether it is through the problem of primary interest
($\displaystyle\text{P}_{\mathcal{W},\epsilon}$), or the existence of a
general decoder $\displaystyle\Delta$. In this section, we will assume that
there are finitely many atoms in $\displaystyle\mathcal{W}$. Moreover, a
condition will be imposed on the set $\displaystyle\mathcal{W}$.

######  Definition 3.1.

The atomic set $\displaystyle\mathcal{W}=\\{w_{i}\\}_{i=1}^{N}$ is said to be
$\displaystyle s$-even if for any index set $\displaystyle|J|\leq s$, and any
scalar $\displaystyle|c_{j}|=1$, we have $\displaystyle\|\sum_{j\in
J}c_{j}w_{j}\|_{\mathcal{W}}=\sum_{j\in J}|c_{j}|=|J|$.

######  Remark 3.2.

In the context of Example 1.2, a sufficient condition for
$\displaystyle\mathcal{F}$ to be $\displaystyle s$-even is for matrix
$\displaystyle F=[f_{1},f_{2},\cdots,f_{n}]$ to have the $\displaystyle s$-NSP
condition. A proof is provided in the Appendix (Lemma 7.4).

######  Lemma 3.3 ([13, Lemma 2.3]).

Suppose $\displaystyle t<N$ are integers. There exists a family
$\displaystyle\mathcal{U}$ of subsets of $\displaystyle[N]$ such that:

  1. 1.

Every set in $\displaystyle\mathcal{U}$ consists of exactly $\displaystyle t$
elements.

  2. 2.

For all $\displaystyle I,J\in\mathcal{U}$ with $\displaystyle I\neq J$, it
holds that $\displaystyle|I\cap J|<\frac{t}{2}$.

  3. 3.

$\displaystyle|\mathcal{U}|\geq\left(\frac{N}{4t}\right)^{t/2}$

######  Theorem 3.4.

Let $\displaystyle\mathcal{W}$ be $\displaystyle s$-even. If for every
$\displaystyle z_{0}\in\Sigma_{\mathcal{W},s}$ and $\displaystyle
y=\mathcal{A}z_{0}$, we have $\displaystyle\hat{z}=z_{0}$ where
$\displaystyle\hat{z}$ is a solution of
($\displaystyle\text{P}_{\mathcal{W}}$), then the number of measurments

$\displaystyle m\geq\frac{1}{8\ln 3}s\ln\frac{N}{2s}.$

###### Proof.

Let $\displaystyle\mathcal{U}$ be a family of subsets of $\displaystyle[N]$
given by Lemma 3.3 with $\displaystyle t=\lfloor s/2\rfloor$. For each
$\displaystyle I\in\mathcal{U}$, define $\displaystyle
z_{I}:=\frac{1}{t}\sum_{i\in I}w_{i}$. We have $\displaystyle|I|=\lfloor
s/2\rfloor$. By definition, $\displaystyle\|z_{I}\|_{\mathcal{W}}\leq 1$.

For $\displaystyle I\neq J$, $\displaystyle z_{I}-z_{J}=\frac{1}{t}(\sum_{i\in
I-J}w_{i}-\sum_{j\in J-I}w_{j})$. Its support
$\displaystyle|I-J|+|J-I|=|I|+|J|-2|I\cap J|$, so $\displaystyle s\geq
2t\geq|I-J|+|J-I|>t$. Since $\displaystyle\mathcal{W}$ is $\displaystyle
s$-even,

$\|z_{i}-z_{j}\|_{\mathcal{W}}=\frac{1}{t}(|I-J|+|J-I|)>1.$ (27)

We claim that
$\displaystyle\\{\mathcal{A}(z_{I}+\frac{1}{2}B_{\mathcal{W}}),I\in\mathcal{U}\\}$
is a disjoint collection of subsets of
$\displaystyle\mathcal{A}(\mathbb{R}^{d})$. Otherwise there exist
$\displaystyle I\neq J$ and $\displaystyle v,v^{\prime}\in B_{\mathcal{W}}$
such that
$\displaystyle\mathcal{A}(z_{I}+\frac{1}{2}v)=\mathcal{A}(z_{J}+\frac{1}{2}v^{\prime})$.
This means that
$\displaystyle\mathcal{A}(z_{I}-z_{J})=\mathcal{A}(\frac{1}{2}v^{\prime}-\frac{1}{2}v)$.
The vector $\displaystyle z_{I}-z_{J}\in\Sigma_{\mathcal{W},s}$, so by our
assumption,

$\|z_{I}-z_{J}\|_{\mathcal{W}}\leq\|\frac{1}{2}v^{\prime}-\frac{1}{2}v\|_{\mathcal{W}}\leq\|\frac{1}{2}v^{\prime}\|_{\mathcal{W}}+\|\frac{1}{2}v\|_{\mathcal{W}}=1,$
(28)

a contradiction to (27).

It is easy to see that
$\displaystyle\mathcal{A}(z_{I}+\frac{1}{2}B_{\mathcal{W}})\subset\frac{3}{2}\mathcal{A}B_{\mathcal{W}}$
for any $\displaystyle I\in\mathcal{U}$. So

$\displaystyle\displaystyle|\mathcal{U}|\mathrm{vol}(\frac{1}{2}AB_{\mathcal{W}})))\leq\mathrm{vol}(\frac{3}{2}AB_{W}).$
(29)

Let $\displaystyle\mathcal{A}B_{\mathcal{W}}$ have Hausdorff dimension
$\displaystyle r\leq m$, so (29) becomes

$\displaystyle\displaystyle\left(\frac{N}{4t}\right)^{t/2}(\frac{1}{2})^{r}\mathrm{vol}(\mathcal{A}B_{\mathcal{W}})\leq(\frac{3}{2})^{r}\mathrm{vol}(\mathcal{A}B_{\mathcal{W}})\Longrightarrow\left(\frac{N}{4t}\right)^{t/2}\leq
3^{r}\leq 3^{m}.$

Taking log of both sides yields

$\displaystyle m\ln
3\geq\frac{t}{2}\ln\frac{N}{4t}\geq\frac{s/2-1}{2}\ln\frac{N}{2s}\geq\frac{s}{8}\ln\frac{N}{2s},$

if $\displaystyle s>2$.

∎

The next theorem is about the existence of any stable decoder. The proof is in
the Appendix since it’s quite similar.

######  Theorem 3.5.

Let $\displaystyle\mathcal{W}$ be $\displaystyle s$-even. Suppose that there
exists a linear map $\displaystyle\mathcal{A}$ and a reconstruction map
$\displaystyle\Delta$ stable in the sense that

$\|z-\Delta(\mathcal{A}z)\|_{\mathcal{W}}\leq
C\sigma_{\mathcal{W},s}(z),\quad\text{ for any }z\in\mathbb{R}^{d},$ (30)

then there exists $\displaystyle C^{\prime}>0$ depending only on
$\displaystyle C$ such that the number of measurments

$\displaystyle m\geq C^{\prime}s\ln(eN/s).$

In the case of compressed sensing, both theorems can be found in [14]. For
example, Theorem 3.4 is reduced to [14, Theorem 10.11].

##  4 Subgaussian Measurements

In this section we show that $\displaystyle\mathcal{W}$-sparse vectors can be
recovered from few random measurements via
($\displaystyle\text{P}_{\mathcal{W},\epsilon}$). The arguments presented here
are similar to those in [4], but the results are still worth stating for the
general setting.

######  Definition 4.1.

The _Gaussian width_ of a set $\displaystyle S\subset\mathbb{R}^{d}$ is
defined as

$\displaystyle w(S):=\mathbb{E}\sup_{x\in S}\langle g,x\rangle,$

where $\displaystyle g\sim N(0,I_{d})$ is a standard Gaussian random vector.

######  Definition 4.2.

A random vector $\displaystyle{\varphi}\in\mathbb{R}^{d}$ is called a
_subgaussian vector_ with parameters $\displaystyle(\alpha,\sigma)$ if it
satisfies the following.

  1. (1)

It is centered, that is, $\displaystyle\mathbb{E}[{\varphi}]=0$.

  2. (2)

There exists a positive $\displaystyle\alpha$ such that
$\displaystyle\mathbb{E}\left[|\langle{\varphi},z\rangle|\right]\geq\alpha$
for every $\displaystyle z\in\mathbb{S}^{d-1}_{2}$.

  3. (3)

There exists a positive $\displaystyle\sigma$ such that
$\displaystyle\Pr\left(|\langle{\varphi},z\rangle|\geq t\right)\leq
2\exp(-\frac{t^{2}}{2\sigma^{2}})$ for every $\displaystyle
z\in\mathbb{S}^{d-1}_{2}$.

The proof of the following lemma can be found in [23, Section 6.5].

######  Lemma 4.3.

If $\displaystyle{f}\in\mathbb{R}^{d}$ is a subgaussian vector with parameters
$\displaystyle(\alpha,\sigma)$, then

$\displaystyle\Pr\left[|\langle{x},{f}\rangle|\geq
t\right]\geq\frac{(\alpha-t)^{2}}{4\sigma^{2}}$

for any $\displaystyle 0<t<\alpha$ and $\displaystyle{x}\in\mathbb{S}^{d-1}$.

If $\displaystyle\\{{\varphi}_{i}\\}_{i=1}^{q}$ are independent copies of the
random distribution $\displaystyle{\varphi}\in\mathbb{R}^{d}$, then we can
define the _mean empirical width_ of a set $\displaystyle
S\subset\mathbb{R}^{d}$ as

$\displaystyle W_{q}(S;{\varphi}):=\mathbb{E}\sup_{x\in
S}\bigg{\langle}x,\dfrac{1}{\sqrt{q}}\sum_{i=1}^{q}\varepsilon_{i}{\varphi}_{i}\bigg{\rangle},$

where $\displaystyle\\{\varepsilon_{i}\\}_{i=1}^{m}$ are independent random
variables taking values uniformly over $\displaystyle\\{\pm 1\\}$ and are
independent from everything else.

The mean empirical width $\displaystyle W_{q}(S;{\varphi})$ is a distribution-
dependent measure of the size of the set $\displaystyle S$. Note that
$\displaystyle W_{q}(S;{\varphi})$ reduces to the usual Gaussian width
$\displaystyle w(S)$ when $\displaystyle{\varphi}$ follows a standard Gaussian
distribution. Estimation of $\displaystyle W_{m}(S;{\varphi})$ for any
subgaussian vector $\displaystyle{\varphi}$ is made in [23], where
$\displaystyle S$ is required to be $\displaystyle\mathbb{S}^{d-1}\cup G$ for
some cone $\displaystyle G$. However, the bound can be relaxed to any subset
$\displaystyle S$ by the observation of the generic chaining bound and the
majorizing measure theorem [24, Theorem 2.2.18 and Theorem 2.4.1]. We will
state this as a lemma.

######  Lemma 4.4.

If $\displaystyle{\varphi}\in\mathbb{R}^{d}$ is subgaussian with parameters
$\displaystyle(\alpha,\sigma)$ and $\displaystyle S$ is any subset of
$\displaystyle\mathbb{R}^{d}$, then

$W_{m}(S;{\varphi})\leq Cw(S)$ (31)

for some universal constant $\displaystyle C$.

The constant $\displaystyle C$ is a universal constant that does not rely on
the choice of subgaussian distribution. See [24] for precise computations of
this constant, and [4, Remark 2.7] for the computation of $\displaystyle C$
when $\displaystyle{\varphi}$ is multivariate normal.

The mean empirical width appears in the following important result. This
theorem was originally stated in [17] and coined as _Mendelson’s Small Ball
Method_ by Tropp [23]. This will be a primary tool in obtaining our main
estimates.

######  Theorem 4.5 ([23, Proposition 5.1], cf. [17, Theorem 2.1]).

Fix a set $\displaystyle S\subset\mathbb{R}^{d}$. Let $\displaystyle{\varphi}$
be a random vector in $\displaystyle\mathbb{R}^{d}$ and let $\displaystyle
A\in\mathbb{R}^{m\times d}$ have rows $\displaystyle\\{a_{i}^{T}\\}_{i=1}^{m}$
that are independent copies of $\displaystyle{\varphi}^{T}$. Define

$\displaystyle Q_{\xi}(S;{\varphi}):=\inf_{{x}\in
S}\Pr\bigg{(}|\langle{x},{\varphi}\rangle|\geq\xi\bigg{)}.$

Then for any $\displaystyle\xi>0$ and $\displaystyle t>0$, we have

$\displaystyle\displaystyle\inf_{{x}\in
S}\|A{x}\|_{2}\geq\xi\sqrt{m}Q_{2\xi}(S;{\varphi})-2W_{m}(S;{\varphi})-\xi t$
(32)

with probability $\displaystyle\geq 1-e^{-t^{2}/2}$.

Let

$\displaystyle
S_{\rho}:=\\{z:\|z_{s}\|_{\mathcal{W}}\geq\rho\|z-z_{s}\|_{\mathcal{W}}\\}\cap\mathbb{S}^{d-1}.$

It is easy to show that $\displaystyle\inf_{{x}\in
S_{\rho}}\|\mathcal{A}{x}\|_{2}>0$ implies $\displaystyle\mathcal{A}$ having
the stable $\displaystyle\mathcal{W}$-$\displaystyle\rho$-NSP. We let
$\displaystyle A$ be the matrix representation of the map
$\displaystyle\mathcal{A}$ under an orthonormal basis.

######  Theorem 4.6.

Assume $\displaystyle{\varphi}\in\mathbb{R}^{d}$ is a subgaussian vector with
parameters $\displaystyle(\alpha,\sigma)$. If $\displaystyle
A\in\mathbb{R}^{m\times d}$ is a measurement matrix with rows that are
independent copies of $\displaystyle{\varphi}^{T}$ and that the number of
measurements satisfies

$\displaystyle m\geq\frac{4^{8}\sigma^{4}}{\alpha^{6}}C^{2}w^{2}(S_{\rho}),$

then with probability at least

$\displaystyle 1-\exp\left({-m\dfrac{\alpha^{4}}{64^{2}\sigma^{4}}}\right),$

we have

$\displaystyle\inf_{{x}\in S_{\rho}}\|\mathcal{A}{x}\|_{2}\geq Cw(S_{\rho}).$
(33)

###### Proof.

We first apply Lemma 4.4 and Theorem 4.5, to obtain the bound

$\inf_{{x}\in
S_{\rho}}\|A{x}\|_{2}\geq\xi\sqrt{m}Q_{2\xi}(S_{\rho};\,{\varphi})-2Cw(S_{\rho})-\xi
t.$ (34)

By Lemma 4.3, provided we choose $\displaystyle\xi<\alpha/2$, we obtain

$\displaystyle\displaystyle Q_{2\xi}(S_{\rho};{\varphi})=\inf_{{x}\in
S_{\rho}}\Pr\left(|\langle{x},{\varphi}\rangle|\geq
2\xi\right)\geq\frac{(\alpha-2\xi)^{2}}{4\sigma^{2}}.$

Placing the bound for $\displaystyle Q_{2\xi}(S_{\rho};{\varphi})$ into (34)
and choosing $\displaystyle\xi=\alpha/4$ gives

$\inf_{{x}\in
S_{\rho}}\|A{x}\|_{2}\geq\frac{\alpha^{3}\sqrt{m}}{4^{3}\sigma^{2}}-2Cw(S_{\rho})-\frac{\alpha
t}{4}:=a-b-\frac{\alpha t}{4}$ (35)

Picking $\displaystyle m$ and $\displaystyle t$ to satisfy $\displaystyle
a\geq 2b$ and $\displaystyle\alpha t/4=(a-b)/2$ gives

$\inf_{x\in S_{\rho}}\|A{x}\|_{2}\geq a-b-(a-b)/2=(a-b)/2\geq
b/2=Cw(S_{\rho}).$

All that is left is to rewrite these conditions in terms of $\displaystyle m$
and $\displaystyle t$. We have

$\displaystyle a\geq
2b\quad\Longleftrightarrow\quad\frac{\alpha^{3}}{4^{3}\sigma^{2}}\sqrt{m}\geq
4Cw(S_{\rho})\quad\Longleftrightarrow\quad
m\geq\frac{4^{8}\sigma^{4}C^{2}}{\alpha^{6}}w^{2}(S_{\rho})$

and

$\displaystyle\frac{\alpha}{4}t=\frac{a-b}{2}\geq\frac{a}{4}=\frac{\alpha}{4^{4}}\left(\frac{\alpha}{\sigma}\right)^{2}\sqrt{m}\quad\Longleftrightarrow\quad
t\geq\frac{1}{64}\sqrt{m}\left(\frac{\alpha}{\sigma}\right)^{2}\quad\Longleftrightarrow\quad-\dfrac{t^{2}}{2}\leq-m\dfrac{\alpha^{4}}{64^{2}\sigma^{4}},$

proving the result. ∎

As mentioned earlier, (33) holds implies $\displaystyle\mathcal{A}$ has the
stable null space property, therefore we have the following corollary.

######  Corollary 4.7.

Let $\displaystyle\mathcal{W}$ be splittable. If $\displaystyle A$ is a
measurement matrix with rows that are independent copies of a subgaussian
vector with parameters $\displaystyle(\alpha,\sigma)$ and $\displaystyle
m\geq\frac{4^{8}\sigma^{4}}{\alpha^{6}}C^{2}w^{2}(S_{\rho})$, then
$\displaystyle A$ has stable $\displaystyle\mathcal{W}$ null space property
with probability at least $\displaystyle
1-\exp\left({-m\dfrac{\alpha^{4}}{64^{2}\sigma^{4}}}\right)$, and therefore
(16) holds.

The computation of Gaussian width is in general difficult. $\displaystyle
w(S_{\rho})$ has been computed in the compressed sensing case, which has an
upper bound of $\displaystyle O(s\ln(d/s)$ [14, Proposition 9.33]. It is also
bounded in the low matrix recovery case in [16]. For the frame case, the
minimum number of subgaussian measurements was computed through bounding a
different Gaussian width [4], instead of $\displaystyle w(S_{\rho})$. It would
be interesting to compute $\displaystyle w(S_{\rho})$ when the atomic set is a
frame.

######  Remark 4.8.

We may define a set according to the strong null space property as
$\displaystyle S_{c}=\\{\|z-v\|_{\mathcal{W}}-\|v\|_{\mathcal{W}}\leq
c\|z\|_{2},\text{ for some
}v\in\Sigma_{\mathcal{W},s}\\}\cap\mathbb{S}^{d-1}$. This way, we will have a
similar result to Corollary 4.7 without requiring $\displaystyle\mathcal{W}$
being splittable. However, computing $\displaystyle w(S_{c})$ could pose
bigger challenge.

##  5 Recovering Vectors Sparse in a Frame

This section will focus on the special case in Example 1.2. Recall
$\displaystyle\mathcal{F}=\\{f_{i}\\}_{i=1}^{N}\subset\mathbb{R}^{d}$, and
$\displaystyle F=[f_{1},f_{2},\cdots,f_{N}]$ is the $\displaystyle d\times N$
matrix whose columns are the atoms. The linear operator
$\displaystyle\mathcal{A}$ will be represented by the matrix $\displaystyle
A$. The minimization problem ($\displaystyle\text{P}_{\mathcal{W},\epsilon}$)
becomes

$\hat{z}=\arg\min_{z\in\mathbb{R}^{d}}\|z\|_{\mathcal{F}}\quad\text{ subject
to }\quad\|Az-y\|_{2}\leq\epsilon.\\\ $
($\displaystyle\text{P}_{\mathcal{F},\epsilon}$)

We will prove that ($\displaystyle\text{P}_{\mathcal{F},\epsilon}$) is the
same as the $\displaystyle\ell_{1}$-synthesis method [20, 8, 4], which is
defined as

$\left\\{\begin{array}[]{l}\hat{x}=\arg\min_{x\in\mathbb{R}^{n}}\|x\|_{1}\quad\text{
subject to }\quad\|AFx-y\|_{2}\leq\epsilon,\\\
\hat{z}=F\hat{x}\end{array}\right.$ (36)

######  Lemma 5.1.

The problem ($\displaystyle\text{P}_{\mathcal{F},\epsilon}$) is equivalent to
(36).

###### Proof.

Let $\displaystyle\bar{z}=F\bar{x}$ be a solution of
($\displaystyle\text{P}_{\mathcal{F},\epsilon}$) and
$\displaystyle\|\bar{z}\|_{\mathcal{F}}=\|\bar{x}\|_{1}$. For an arbitrary
feasible vector $\displaystyle x$ of (36), $\displaystyle Fx$ is feasible in
($\displaystyle\text{P}_{\mathcal{F},\epsilon}$), so we have
$\displaystyle\|\bar{x}\|_{1}=\|\bar{z}\|_{\mathcal{F}}\leq\|Fx\|_{\mathcal{F}}\leq\|x\|_{1}$.
This makes $\displaystyle\bar{z}$ a solution of (36).

On the other hand, let $\displaystyle\hat{z}=F\hat{x}$ be a solution of (36).
For an arbitrary feasible vector $\displaystyle z$ of
($\displaystyle\text{P}_{\mathcal{F},\epsilon}$), let $\displaystyle z=Fx$ and
$\displaystyle\|z\|_{\mathcal{F}}=\|x\|_{1}$. We have that $\displaystyle x$
is feasible in (36), so
$\displaystyle\|\hat{z}\|_{\mathcal{F}}\leq\|\hat{x}\|_{1}\leq\|x\|_{1}=\|z\|_{\mathcal{F}}$,
making $\displaystyle\hat{z}$ a solution of
($\displaystyle\text{P}_{\mathcal{F},\epsilon}$). ∎

It is worthwhile to restate Definition 2.1 for the frame case:

$\text{For any }z\in\mathcal{N}(A)\backslash\\{0\\}\text{ and any
}v\in\Sigma_{F,s},\text{ we have }\|v\|_{\mathcal{F}}<\|z-v\|_{\mathcal{F}}.$
(37)

A direct consequence of Theorem 2.2 is the following:

######  Corollary 5.2.

The matrix $\displaystyle A$ satisfying (37) is the necessary and sufficient
condition for the success recovery of all signals in
$\displaystyle\Sigma_{F,s}$ via
($\displaystyle\text{P}_{\mathcal{F},\epsilon}$) or (36)
($\displaystyle\epsilon=0$).

Corollary 5.2 is the same as [8, Theorem 4.2] since the dictionary NSP
property proposed in [8, Definition 4.1] also characterizes the
$\displaystyle\ell_{1}$-synthesis method, and therefore is equivalent to (37)
here. We argue that (37) is a more concise version than [8, Definition 4.1]. A
direct proof of the equivalence of (37) and [8, Definition 4.1] is very
similar to the proof of Lemma 7.6.

We combine Theorem 2.6 and Theorem 2.7 for the frame case as one corollary.

######  Corollary 5.3.

Suppose $\displaystyle\mathcal{F}$ is $\displaystyle s$-splittable.

(a) If $\displaystyle A$ has the stable $\displaystyle\mathcal{F}$ null space
property of order $\displaystyle s$ as

$\|z_{s}\|_{\mathcal{F}}\leq\rho\|z-z_{s}\|_{\mathcal{F}},\qquad\text{ for any
}z\in\mathcal{N}(A),$ (38)

then for any $\displaystyle z_{0}\in\mathbb{R}^{d}$ and $\displaystyle
y=Az_{0}+e$ where $\displaystyle\|e\|_{2}\leq\epsilon$, we have

$\displaystyle\|\hat{z}-z_{0}\|_{\mathcal{F}}\leq\frac{2+2\rho}{1-\rho}\sigma_{\mathcal{F},s}(z_{0})+\frac{4\sqrt{N}}{(1-\rho)\nu_{A}}\epsilon,$

where $\displaystyle\hat{z}$ is from (37).

(b) If $\displaystyle A$ has the robust $\displaystyle\mathcal{F}$ null space
property of order $\displaystyle s$ as

$\|z_{s}\|_{\mathcal{F}}\leq\rho\|z-z_{s}\|_{\mathcal{F}}+\tau\|Az\|_{2},\qquad\text{for
any }z\in\mathbb{R}^{d},$ (39)

then for any $\displaystyle z_{0}\in\mathbb{R}^{d}$ and $\displaystyle
y=Az_{0}+e$ where $\displaystyle\|e\|_{2}\leq\epsilon$, we have

$\|\hat{z}-z_{0}\|_{\mathcal{F}}\leq\frac{2(1+\rho)}{1-\rho}\sigma_{\mathcal{F},s}(z_{0})+\frac{4\tau}{1-\rho}\epsilon,$
(40)

where $\displaystyle\hat{z}$ is from (37).

Further investigation is needed on when the frame $\displaystyle\mathcal{F}$
is splittable. As a simple example, the frame $\displaystyle\\{(\cos\frac{\pi
n}{8},\sin\frac{\pi n}{8})\\}_{n=0}^{7}$ of $\displaystyle\mathbb{R}^{2}$ is
1-splittable. See Lemma 7.5 in the Appendix.

Theorem 2.9 reduces to the corollary:

######  Corollary 5.4.

If $\displaystyle A$ has the strong $\displaystyle\mathcal{F}$ null space
property of order $\displaystyle s$ as

$\|z-v\|_{\mathcal{F}}-\|v\|_{\mathcal{F}}\geq c\|z\|_{2},\qquad\text{ for any
}z\in\mathcal{N}(A),\text{ and any }v\in\Sigma_{\mathcal{F},s},$ (41)

then for any $\displaystyle z_{0}\in\mathbb{R}^{d}$ and $\displaystyle
y=Az_{0}+e$ where $\displaystyle\|e\|_{2}\leq\epsilon$, we have

$\|\hat{z}-z_{0}\|_{2}\leq\frac{2}{\nu_{A}}\left(\frac{\sqrt{N}}{c}+1\right)\epsilon+\frac{2}{c}\sigma_{\mathcal{F},s}(z_{0}),$
(42)

where $\displaystyle\hat{z}$ is from (37).

A strong null space property for recovery via the $\displaystyle\ell_{1}$
synthesis method was also proposed in [8]. We recall their definition here: A
sensing matrix $\displaystyle A$ is said to have $\displaystyle F$ strong null
space property of order $\displaystyle s$ if there exists a positive constant
c such that

$\text{for }\forall v\in\mathcal{N}(AF),|T|\leq s,\text{ }\exists
u\in\mathcal{N}(F)\text{ satisfying }\|v_{T^{c}}\|-\|v_{T}+u\|_{1}\geq
c\|Fv\|_{2}.$ (43)

It is not surprising that these two conditions (41) and (43) are equivalent.
See Lemma 7.6 in the Appendix.

We compare Corollary 5.4 to [8, Theorem 5.2] as they have the same assumption.
In [8, Theorem 5.2], the conclusion is that
$\displaystyle\|\hat{z}-z_{0}\|_{2}\leq\frac{2}{\nu_{A}}\left(\frac{\sqrt{N}}{c\nu_{F}}+1\right)\epsilon+\frac{2}{c}\min_{Fx=z_{0},|T|\leq
s}\|x_{T^{c}}\|_{1}$. First of all, the estimate in (42) avoids
$\displaystyle\nu_{F}$ which is an improvement. Moreover, The tail
$\displaystyle\min_{Fx=z_{0},|T|\leq
s}\|x_{T^{c}}\|_{1}=\min_{Fx=z_{0},|T|\leq
s}\|x-x_{T}\|_{1}\geq\sigma_{F,s}(z_{0})$ by (7), so Corollary 5.4 implies [8,
Theorem 5.2], but not necessarily the other way around.

Theorem 3.4 reduces to the following corollary.

######  Corollary 5.5.

Let $\displaystyle\mathcal{F}$ be $\displaystyle s$-even. If for every
$\displaystyle z_{0}\in\Sigma_{\mathcal{W},s}$ and $\displaystyle
y=\mathcal{A}z_{0}$, we have $\displaystyle\hat{z}=z_{0}$ where
$\displaystyle\hat{z}$ is a solution of
($\displaystyle\text{P}_{\mathcal{F},\epsilon}$) (with
$\displaystyle\epsilon=0$), then the number of measurments

$\displaystyle m\geq\frac{1}{8\ln 3}s\ln\frac{N}{2s}.$

We have mentioned earlier that $\displaystyle\mathcal{F}$ being $\displaystyle
s$-even is not a harsh condition. For example, the matrix $\displaystyle F$
has $\displaystyle s$-NSP will guarantee that. Corollary 5.5 thus provides the
minimum number of measurements needed using the $\displaystyle\ell_{1}$
synthesis method. It was proven in [4] that $\displaystyle O(s\ln(N/s))$ many
subgaussian measurements do allow stable and robust recovery through
($\displaystyle\text{P}_{\mathcal{F},\epsilon}$) if $\displaystyle F$ has NSP.

When the atoms are the canonical orthonormal basis of
$\displaystyle\mathbb{R}^{d}$, as shown in Example 1.1, we have
$\displaystyle\|v\|_{\mathcal{E}}=\|v\|_{1}$ and $\displaystyle
C_{\mathcal{E}}=\sqrt{d}$. In this case, Theorem 2.2 is a well known result
and can be found in literature like [9] and [14]. Theorem 2.6 reduces to [1,
Theorem 2.4]. Theorem 2.7 is similar to [11, Theorem 5]. Theorem 3.5 and
Theorem 3.4 in this setting can be found in [13] or [14].

##  6 Low Rank Matrices Recovery

This section addresses the case when
$\displaystyle\mathcal{M}=\\{uv^{T}:u\in\mathbb{R}^{n_{1}},v\in\mathbb{R}^{n_{2}},\|u\|_{2}=\|v\|_{2}=1\\}$
as mentioned in Example 1.3.
$\displaystyle\Sigma_{\mathcal{M},s}=\\{\sum_{i=1}^{s}c_{i}u_{i}v_{i}^{T}:c_{i}\in\mathbb{R},\|u\|_{2}=\|v\|_{2}=1\\}$
is the set of $\displaystyle n_{1}\times n_{2}$ matrices whose rank is at most
$\displaystyle s$. The constant $\displaystyle
C_{\mathcal{M}}=\sqrt{n_{1}n_{2}}$. Let $\displaystyle
K=\min\\{n_{1},n_{2}\\}$.

In this case, Definition 2.1 becomes

$\text{for every }Z\in\mathcal{N}(\mathcal{A})\backslash\\{0\\}\text{ and
every }V\in\Sigma_{\mathcal{M},s},\text{we have }\|V\|_{*}<\|Z-V\|_{*},$ (44)

which can be simplified to

$\text{for every }Z\in\mathcal{N}(A)\backslash\\{0\\},\text{we have
}\sum_{i=1}^{s}\sigma_{i}(Z)<\sum_{i=s+1}^{K}\sigma_{i}(Z).$ (45)

The equivalence of (44) and (45) is due to Lemma 7.7 in the Appendix. We have
the best $\displaystyle s$-term approximation of any matrix $\displaystyle Z$
to be

$\displaystyle Z_{s}=\sum_{i=1}^{s}\sigma_{i}(Z)u_{i}v_{i}^{T},$

where $\displaystyle Z=\sum_{i=1}^{K}\sigma_{i}(Z)u_{i}v_{i}^{T}$ is its
singular value decomposition.

Theorem 2.2 reduces to the following corollary.

######  Corollary 6.1.

The nuclear norm minimization problem

$\hat{Z}=\arg\min_{Z\in\mathbb{R}^{n_{1}\times n_{2}}}\|Z\|_{*}\quad\text{
subject to }\quad\mathcal{A}Z=y.$ (46)

is successful at recovering all signals in
$\displaystyle\Sigma_{\mathcal{M},s}$ if and only if (45) holds.

Corollary 6.1 can be found in [21, Theorem 1.1] or [16, Theorem 15] as well,
but our general tail definition provides a more concise proof than the one in
[21].

The recovery scheme ($\displaystyle\text{P}_{\mathcal{W},\epsilon}$) becomes

$\hat{Z}=\arg\min_{Z\in\mathbb{R}^{n_{1}\times n_{2}}}\|Z\|_{*}\quad\text{
subject to }\quad\|\mathcal{A}Z-Y\|_{F}\leq\epsilon.$ (47)

We also rewrite Theorem 2.6, Theorem 2.7, and Theorem 2.9 in this case as one
corollary, as $\displaystyle\mathcal{M}$ is splittable.

######  Corollary 6.2.

(a) If $\displaystyle\mathcal{A}$ has the stable $\displaystyle\mathcal{M}$
null space property of order $\displaystyle s$ as

$\|Z_{s}\|_{*}\leq\rho\|Z-Z_{s}\|_{*},\qquad\text{ for any
}z\in\mathcal{N}(A),$ (48)

then for any $\displaystyle Z_{0}\in\mathbb{R}^{n_{1}\times n_{2}}$ and
$\displaystyle Y=\mathcal{A}Z_{0}+e$ where
$\displaystyle\|e\|_{F}\leq\epsilon$, we have

$\displaystyle\|\hat{Z}-Z_{0}\|_{*}\leq\frac{2+2\rho}{1-\rho}\|Z-Z_{s}\|_{*}+\frac{4\sqrt{n_{1}n_{2}}}{(1-\rho)\nu_{\mathcal{A}}}\epsilon,$

where $\displaystyle\hat{Z}$ is from (47).

(b) If $\displaystyle A$ has the robust $\displaystyle\mathcal{M}$ null space
property of order $\displaystyle s$ as

$\|Z_{s}\|_{\mathcal{F}}\leq\rho\|Z-Z_{s}\|_{*}+\tau\|\mathcal{A}Z\|_{2},\qquad\text{for
any }Z\in\mathbb{R}^{n_{1}\times n_{2}},$ (49)

then for any $\displaystyle Z_{0}\in\mathbb{R}^{n_{1}\times n_{2}}$ and
$\displaystyle Y=\mathcal{A}Z_{0}+e$ where
$\displaystyle\|e\|_{F}\leq\epsilon$, we have

$\|\hat{Z}-Z_{0}\|_{*}\leq\frac{2(1+\rho)}{1-\rho}\|Z-Z_{s}\|_{*}+\frac{4\tau}{1-\rho}\epsilon,$
(50)

where $\displaystyle\hat{Z}$ is from (47).

(c) If $\displaystyle A$ has the strong $\displaystyle\mathcal{M}$ null space
property of order $\displaystyle s$ as

$\|Z-Z_{s}\|_{*}-\|Z_{s}\|_{*}\geq c\|Z\|_{F},\qquad\text{ for any
}Z\in\mathcal{N}(A),$ (51)

then for any $\displaystyle Z_{0}\in\mathbb{R}^{n_{1}\times n_{2}}$ and
$\displaystyle Y=\mathcal{A}Z_{0}+e$ where
$\displaystyle\|e\|_{F}\leq\epsilon$, we have

$\|\hat{Z}-Z_{0}\|_{2}\leq\frac{2}{\nu_{A}}\left(\frac{\sqrt{n_{1}n_{2}}}{c}+1\right)\epsilon+\frac{2}{c}\|Z-Z_{s}\|_{*},$
(52)

where $\displaystyle\hat{Z}$ is from (47).

Corollary 6.2(a)(c) are new results. Note that the strong null space property
is simplifed to (51) due to Lemma 7.7. Corollary 6.2(b) is essentially the
same as [16, Theorem 11]. Compared to [16, Theorem 11], the lack of
$\displaystyle\sqrt{s}$ in (50) is due to the lack of the same term in our
robust null space property (49).

The special case of Example 1.4 has a lot of similarities with low rank matrix
recovery. We leave it to the readers to modify Corollary 6.2 for recovery
results using (9).

##  7 Appendix

######  Lemma 7.1.

Let
$\displaystyle\mathcal{M}=\\{uv^{T}:u\in\mathbb{R}^{n_{1}},v\in\mathbb{R}^{n_{2}},\|u\|_{2}=\|v\|_{2}=1\\}$,
then $\displaystyle\|X\|_{\mathcal{M}}=\|X\|_{*}$

###### Proof.

Let $\displaystyle X=\sum_{i=1}^{K}\sigma_{i}u_{i}v_{i}^{T}$ be its singular
value decomposition. Suppose we can rewrite it as $\displaystyle X=\sum
s_{i}p_{i}q_{i}^{T}$ where
$\displaystyle\|p_{i}\|_{2}=\|q_{i}\|_{2}=1,s_{i}>0$.

$\displaystyle\sum_{i=1}^{K}\sigma_{i}=\|X\|_{*}=\|\sum_{i=1}^{m}s_{i}u_{i}v_{i}^{T}\|_{*}\leq\sum_{i=1}^{m}\|s_{i}u_{i}v_{i}^{T}\|_{*}=\sum_{i=1}^{m}s_{i}$.

By the definition of atomic norm, we directly have
$\displaystyle\|X\|_{\mathcal{M}}=\sum_{i=1}^{m}\sigma_{i}$. ∎

The following lemma is a consequence of [15, Theorem 7.4.51].

######  Lemma 7.2.

$\displaystyle\sum_{i=1}^{K}|\sigma_{i}(X)-\sigma_{i}(Y)|\leq\sum_{i=1}^{K}\sigma_{i}(X-Y)$

######  Lemma 7.3.

Both $\displaystyle\mathcal{E}$ and $\displaystyle\mathcal{M}$ are splittable.

###### Proof.

For $\displaystyle\mathcal{E}$, given $\displaystyle x,y\in\mathbb{R}^{d}$,
let $\displaystyle T$ be the index set such that $\displaystyle x_{s}=x_{T}$.
It is clear that $\displaystyle-\|y_{T}\|_{1}\geq-\|y_{s}\|_{1}$ and
$\displaystyle\|y_{T^{c}}\|_{1}\geq\|y-y_{s}\|_{1}$. Then

$\displaystyle\displaystyle\|x+y\|_{1}$
$\displaystyle\displaystyle=\|x_{T}+y_{T}\|_{1}+\|x_{T^{c}}+y_{T^{c}}\|_{1}$
$\displaystyle\displaystyle\geq\|x_{T}\|_{1}-\|y_{T}\|_{1}+\|y_{T^{c}}\|_{1}-\|x_{T^{c}}\|_{1}$
$\displaystyle\displaystyle\geq\|x_{s}\|_{1}-\|y_{s}\|_{1}+\|y-y_{s}\|_{1}-\|x-x_{s}\|_{1}.$

For $\displaystyle\mathcal{M}$, given $\displaystyle
X,Y\in\mathbb{R}^{n_{1}\times n_{2}}$

$\displaystyle\displaystyle\|X+Y\|_{*}$
$\displaystyle\displaystyle=\sum_{i=1}^{K}\sigma_{i}(X-(-Y))\geq\sum_{i=1}^{K}|\sigma_{i}(X)-\sigma_{i}(Y)|$
$\displaystyle\displaystyle=\sum_{i=1}^{s}|\sigma_{i}(X)-\sigma_{i}(Y)|+\sum_{i=s+1}^{K}|\sigma_{i}(X)-\sigma_{i}(Y)|$
$\displaystyle\displaystyle\geq\sum_{i=1}^{s}\sigma_{i}(X)-\sum_{i=1}^{s}\sigma_{i}(Y)+\sum_{i=s+1}^{K}\sigma_{i}(Y)-\sum_{i=s+1}^{K}\sigma_{i}(X)$
$\displaystyle\displaystyle=\|X_{s}\|_{*}-\|Y_{s}\|_{*}+\|Y-Y_{s}\|_{*}-\|X-X_{s}\|_{*}$

∎

######  Lemma 7.4.

Let $\displaystyle F=[f_{1},f_{2},\cdots,f_{N}]$ has null space property of
order $\displaystyle s$ (see (12)), then the atomic set
$\displaystyle\mathcal{F}=\\{f_{1},f_{2},\cdots,f_{N}\\}$ is $\displaystyle
s$-even.

###### Proof.

Let $\displaystyle z=\sum_{j\in J}c_{j}f_{j}=\sum_{i\in[N]}\alpha_{i}f_{i}$ be
two different representations of $\displaystyle z$ in
$\displaystyle\mathcal{F}$. In the first representation, we have
$\displaystyle|c_{j}|=1$ and $\displaystyle|J|\leq s$. We have
$\displaystyle\sum_{j\in J}(\alpha_{j}-c_{j})f_{j}+\sum_{j\notin
J}\alpha_{j}f_{j}=0$. By the null space property of $\displaystyle F$,
$\displaystyle\sum_{j\notin J}|\alpha_{j}|>\sum_{j\in
J}|\alpha_{j}-c_{j}|\geq\sum_{j\in J}|c_{j}|-\sum_{j\in J}|\alpha_{j}|,$ so
$\displaystyle\sum_{j\in[N]}|\alpha_{j}|>\sum_{j\in J}|c_{j}|$. By definition
of atomic norm, we have $\displaystyle\|z\|_{\mathcal{F}}=\sum_{j\in
J}|c_{j}|$. ∎

###### Proof of Theorem 3.5.

Let $\displaystyle\mathcal{U}$ be a family of subsets of $\displaystyle[N]$
given by Lemma 3.3 with $\displaystyle t=\lfloor s/2\rfloor$. For each
$\displaystyle I\in\mathcal{U}$, define $\displaystyle
z_{I}:=\frac{1}{t}\sum_{i\in I}w_{i}$. We have $\displaystyle|I|=\lfloor
s/2\rfloor$. By definition, $\displaystyle\|z_{I}\|_{\mathcal{W}}\leq 1$.

For $\displaystyle I\neq J$, $\displaystyle z_{I}-z_{J}=\frac{1}{t}(\sum_{i\in
I-J}w_{i}-\sum_{j\in J-I}w_{j})$. Its support
$\displaystyle|I-J|+|J-I|=|I|+|J|-2|I\cap J|$, so $\displaystyle s\geq
2t\geq|I-J|+|J-I|>t$. By the $\displaystyle s$-NSP of $\displaystyle W$,
$\displaystyle\|z_{i}-z_{j}\|_{W}=\frac{1}{t}(|I-J|+|J-I|)>1$.

We claim that $\displaystyle\\{A(z_{I}+\rho B_{W}),I\in\mathcal{U}\\}$ is a
disjoint collection of subsets of $\displaystyle A(\mathbb{R}^{d})$, where
$\displaystyle\rho=\frac{1}{2C+1}$. Otherwise there exist $\displaystyle I\neq
J$ and $\displaystyle v,v^{\prime}\in B_{W}$ such that $\displaystyle
A(z_{I}+\rho v)=A(z_{J}+\rho v^{\prime})$, resulting

$\displaystyle\displaystyle 1$
$\displaystyle\displaystyle<\|z_{I}-z_{J}\|_{W}=\|z_{I}+\rho
v-\Delta(A(z_{I}+\rho v))-z_{J}+\Delta(A(z_{J}+\rho v^{\prime}))-\rho v+\rho
v^{\prime}-\rho v^{\prime}\|_{W}$ $\displaystyle\displaystyle\leq\|z_{I}+\rho
v-\Delta(A(z_{I}+\rho v))\|_{W}+\|\rho v\|_{W}+\|\rho
v^{\prime}\|_{W}+\|\Delta(A(z_{J}+\rho v^{\prime}))-(z_{J}+\rho
v^{\prime})\|_{W}$ $\displaystyle\displaystyle\leq C\sigma_{W,s}(z_{I}+\rho
v)+2\rho+C\sigma_{W,s}(z_{J}+\rho v^{\prime})\leq C\|\rho
v\|_{W}+2\rho+C\|\rho v^{\prime}\|_{W}\leq 1.$

It is easy to see that $\displaystyle A(z_{I}+\rho
B_{w})\subset(1+\rho)AB_{W}$ for any $\displaystyle I\in\mathcal{U}$. So

$\displaystyle\displaystyle|\mathcal{U}|\mathrm{vol}(A(\rho(B_{W})))\leq\mathrm{vol}((1+\rho)AB_{W})$
(53)

Let $\displaystyle AB_{W}$ have Hausdorff dimension $\displaystyle r\leq m$,
so (53) becomes

$\displaystyle\displaystyle\left(\frac{N}{4t}\right)^{t/2}\rho^{r}\mathrm{vol}(AB_{W})\leq(1+\rho)^{r}\mathrm{vol}(AB_{W})$
$\displaystyle\displaystyle\Rightarrow$
$\displaystyle\displaystyle\left(\frac{N}{4t}\right)^{t/2}\leq(1+\frac{1}{\rho})^{r}\leq(2C+3)^{m}.$

Taking log of both sides yields

$\displaystyle
m\ln(2C+3)\geq\frac{t}{2}\ln\frac{N}{4t}\geq\frac{s/2-1}{2}\ln\frac{N}{2s}\geq\frac{s}{8}\ln\frac{N}{2s},$

if $\displaystyle s>2$. ∎

######  Lemma 7.5.

The frame
$\displaystyle\\{f_{n}=(\cos\frac{\pi(n-1)}{8},\sin\frac{\pi(n-1)}{8})\\}_{n=1}^{8}$
of $\displaystyle\mathbb{R}^{2}$ is 1-splittable.

###### Proof.

First, we address that if $\displaystyle z=cf_{n}$ for any $\displaystyle n$,
then $\displaystyle\|z\|_{\mathcal{F}}=|c|$. Due to the symmetry of the frame
vectors, we may assume $\displaystyle z=cf_{1}$. The other different
representation of $\displaystyle z$ is $\displaystyle
z=\frac{2c}{\sqrt{2}}(f_{2}+f_{8})$. It is obvious that the first
representation gives its atomic norm $\displaystyle\|z\|_{\mathcal{F}}=|c|$.

Second, for any vector $\displaystyle x=af_{1}+bf_{3}$ such that
$\displaystyle a\geq b\geq 0,$, we have
$\displaystyle\|x\|_{\mathcal{F}}=a+(\sqrt{2}-1)b$. This is because due to
symmetry, the other representation of $\displaystyle x$ is $\displaystyle
x=af_{1}+b(\frac{2}{\sqrt{2}}f_{2}-f_{1})=(a-b)f_{1}+\frac{2b}{\sqrt{2}}f_{2}$,
since $\displaystyle a-b+\frac{2b}{\sqrt{2}}<a+b$, we have
$\displaystyle\|x\|_{\mathcal{F}}=a+(\sqrt{2}-1)b$.

Third, let $\displaystyle x=\gamma(\cos\alpha f_{1}+\sin\alpha f_{3})$ where
$\displaystyle\gamma>0,\alpha\in[0,\pi/4)$. Since $\displaystyle
f_{3}=\frac{2}{\sqrt{2}}f_{2}-f_{1}$, the other representation of
$\displaystyle x$ is $\displaystyle
x=\gamma(\cos\alpha-\sin\alpha)f_{1}+\frac{2\gamma}{\sqrt{2}}\sin\alpha
f_{2}$. There are four choices for the best 1-term approximation of
$\displaystyle x$, that is $\displaystyle\gamma\cos\alpha
f_{1},\gamma\sin\alpha f_{3},\gamma(\cos\alpha-\sin\alpha)f_{1}$, or
$\displaystyle\frac{2\gamma}{\sqrt{2}}\sin\alpha f_{2}$. The corresponding
tails are $\displaystyle\gamma\sin\alpha f_{3},\gamma\cos\alpha
f_{1},\frac{2\gamma}{\sqrt{2}}\sin\alpha f_{2}$, and
$\displaystyle\gamma(\cos\alpha-\sin\alpha)f_{1}$. If
$\displaystyle\alpha\in[0,\arctan\frac{1}{2})$, this makes
$\displaystyle\gamma\sin\alpha f_{3}$ has the smallest atomic norm, so
$\displaystyle x_{1}=\gamma\cos\alpha f_{1}$ and
$\displaystyle\|x-x_{1}\|_{\mathcal{F}}=\gamma\sin\alpha$. If
$\displaystyle\alpha\in[\arctan\frac{1}{2},\pi/4)$, then $\displaystyle
x_{1}=\sqrt{2}\gamma\sin\alpha
f_{2},\|x-x_{1}\|_{\mathcal{F}}=\gamma(\cos\alpha-\sin\alpha)$.

For arbitrary $\displaystyle x=\gamma(\cos\alpha f_{1}+\sin\alpha f_{3})$ and
$\displaystyle y=\rho(\cos\beta f_{1}+\sin\beta f_{3})$. We may assume without
loss of generality that $\displaystyle\gamma=1,\alpha\in[0,\pi/4)$ and
$\displaystyle\beta\in[0,\pi/4)$. According to fact 2,
$\displaystyle\|x+y\|_{\mathcal{F}}=\|(\cos\alpha+\rho\cos\beta)f_{1}+(\sin\alpha+\rho\sin\beta)f_{3}\|_{\mathcal{F}}=\cos\alpha+\rho\cos\beta-\sin\alpha-\rho\sin\beta+\sqrt{2}(\sin\alpha+\rho\sin\beta)$.

Case 1:
$\displaystyle\alpha\in[0,\arctan\frac{1}{2}),\beta\in[0,\arctan\frac{1}{2})$.
According to the third fact, we have $\displaystyle x_{1}=\cos\alpha
f_{1},\|x-x_{1}\|_{\mathcal{F}}=\sin\alpha,y_{1}=\rho\cos\beta f_{1}$ and
$\displaystyle\|y-y_{1}\|_{\mathcal{F}}=\rho\sin\beta$. So

$\|x_{1}\|_{\mathcal{F}}-\|y_{1}\|_{\mathcal{F}}+\|y-y_{1}\|_{1}-\|x-x_{1}\|_{\mathcal{F}}=\cos\alpha-\rho\cos\beta+\rho\sin\beta-\sin\alpha,$
(54)

which clearly is less than $\displaystyle\|x+y\|_{\mathcal{F}}$.

Case 2:
$\displaystyle\alpha\in[0,\arctan\frac{1}{2}),\beta\in[\arctan\frac{1}{2},\pi/4)$.
According to the third fact, we have $\displaystyle x_{1}=\cos\alpha
f_{1},\|x-x_{1}\|_{\mathcal{F}}=\sin\alpha,y_{1}=\sqrt{2}\rho\sin\beta f_{2}$
and $\displaystyle\|y-y_{1}\|_{\mathcal{F}}=\rho(\cos\beta-\sin\beta)$. So

$\|x_{1}\|_{\mathcal{F}}-\|y_{1}\|_{\mathcal{F}}+\|y-y_{1}\|_{1}-\|x-x_{1}\|_{\mathcal{F}}=\cos\alpha-\sqrt{2}\rho\sin\beta+\rho(\cos\beta-\sin\beta)-\sin\alpha,$
(55)

which clearly is less than $\displaystyle\|x+y\|_{\mathcal{F}}$.

Case 3:
$\displaystyle\alpha\in[\arctan\frac{1}{2},\pi/4),\beta\in[\arctan\frac{1}{2},\pi/4)$.
According to the third fact, we have

$\|x_{1}\|_{\mathcal{F}}-\|y_{1}\|_{\mathcal{F}}+\|y-y_{1}\|_{1}-\|x-x_{1}\|_{\mathcal{F}}=\sqrt{2}\sin\alpha-\sqrt{2}\rho\sin\beta+\rho(\cos\beta-\sin\beta)-(\cos\alpha-\sin\alpha),$
(56)

which is less than $\displaystyle\|x+y\|_{\mathcal{F}}$. ∎

######  Lemma 7.6.

The two conditions (41) and (43) are equivalent.

###### Proof.

((43)$\displaystyle\Longrightarrow$(41)) For any $\displaystyle
z\in\mathcal{N}(A)$ and any $\displaystyle v\in\Sigma_{F,s}$, by (6), let
$\displaystyle\|z-v\|_{\mathcal{F}}=\|x-u_{1}\|_{1}$ where $\displaystyle
z=Fx,v=Fu_{1}=Fu_{2}$ where $\displaystyle\|u_{2}\|_{0}\leq s$. Let
$\displaystyle T$ be the support of $\displaystyle u_{2}$. The vector
$\displaystyle y=x-u_{1}+u_{2}\in\mathcal{N}(AF)$. By assumption, there exists
$\displaystyle u\in\mathcal{N}(F)$ such that
$\displaystyle\|y_{T^{c}}\|_{1}-\|y_{T}+u\|_{1}\geq c\|Fy\|_{2}=c\|z\|_{2}$.
Now we have

$\displaystyle\displaystyle\|z-v\|_{\mathcal{F}}-\|v\|_{\mathcal{F}}$
$\displaystyle\displaystyle\geq\|x-u_{1}\|_{1}-\|u_{2}+u\|_{1}=\|y-u_{2}\|_{1}-\|u_{2}+u\|_{1}$
$\displaystyle\displaystyle=\|y_{T}-u_{2}\|_{1}+\|y_{T^{c}}\|_{1}-\|u_{2}+u\|_{1}$
$\displaystyle\displaystyle\geq\|y_{T}-u_{2}\|_{1}+\|y_{T}+u\|_{1}+c\|z\|_{2}-\|u_{2}+u\|_{1}\geq
c\|z\|_{2}.$

((41)$\displaystyle\Longrightarrow$(43)) For any $\displaystyle
x\in\mathcal{N}(AF)$ and any $\displaystyle|T|\leq s$, let $\displaystyle
v=Fx_{T}\in\Sigma_{F,s}$ and $\displaystyle\|v\|_{\mathcal{F}}=\|y\|_{1}$
where $\displaystyle v=Fy$. Since $\displaystyle z=Fx\in\mathcal{N}(A)$, by
(41), $\displaystyle\|z-v\|_{\mathcal{F}}-\|v\|_{\mathcal{F}}\geq c\|z\|_{2}$.

Clearly $\displaystyle y-x_{T}\in\mathcal{N}(F)$, and
$\displaystyle\|x_{T^{c}}\|_{1}-\|x_{T}+y-x_{T}\|_{1}\geq\|z-v\|_{\mathcal{F}}-\|v\|_{\mathcal{F}}\geq
c\|z\|_{2}=c\|Fx\|_{2}$. ∎

######  Lemma 7.7.

For any $\displaystyle Z\in\mathbb{R}^{n_{1}\times n_{2}}$,

$\displaystyle\min_{V\in\Sigma_{\mathcal{M},s}}\left(\|Z-V\|_{*}-\|V\|_{*}\right)=\|Z-Z_{s}\|_{*}-\|Z_{s}\|_{*}=-\sum_{i=1}^{s}\sigma_{i}(Z)+\sum_{i=s+1}^{K}\sigma_{i}(Z).$

###### Proof.

Let $\displaystyle\sigma_{i}$ be the singular values of $\displaystyle Z$.

$\displaystyle\|Z-V\|_{*}-\|V\|_{*}\stackrel{{\scriptstyle Lemma\
\ref{lem:sv}}}{{\geq}}\sum_{i=1}^{K}|\sigma_{i}-\sigma_{i}(V)|-\sum_{i=1}^{s}\sigma_{i}(V)=\sum_{i=1}^{s}|\sigma_{i}-\sigma_{i}(V)|+\sum_{i=s+1}^{K}\sigma_{i}-\sum_{i=1}^{s}\sigma_{i}(V)$.

It is easy to show that
$\displaystyle\min_{c\in\mathbb{R}}(|\sigma-c|-c)=-\sigma$, therefore we have

$\displaystyle\|Z-V\|_{*}-\|V\|_{*}\geq\sum_{i=1}^{s}(|\sigma_{i}-\sigma_{i}(V)|-\sigma_{i}(V))+\sum_{i=s+1}^{K}\sigma_{i}\geq-\sum_{i=1}^{s}\sigma_{i}+\sum_{i=s+1}^{K}\sigma_{i}.$

∎

## References

  * [1] A. Aldroubi, X. Chen, and A. Powell. _Stability and robustness of $\displaystyle\ell_{q}$ minimization using null space property._ Proceedings of SampTA 2011 (2011).
  * [2] A. Aldroubi, X. Chen, and A. Powell. _Perturbations of measurement matrices and dictionaries in compressed sensing._ Appl. Comput. Harmon. Anal. 33 (2012), no. 2: 282–291.
  * [3] E. Candès, and X. Li. _Solving quadratic equations via PhaseLift when there are about as many equations as unknowns._ Foundations of Computational Mathematics 14.5 (2014): 1017-1026.
  * [4] P. Casazza, X. Chen, and R. Lynch. _Preserving Injectivity under Subgaussian Mappings and Its Application to Compressed Sensing_. arXiv preprint arXiv:1710.09972 (2018).
  * [5] E. J. Candès, Y. Eldar, D. Needell, and P. Randall. _Compressed sensing with coherent and redundant dictionaries._ Appl. Comput. Harmon. Anal. 31 (2011), no. 1: 59–73.
  * [6] V. Chandrasekaran, B. Recht, P. A. Parrilo, and A. S. Willsky. _The convex geometry of linear inverse problems._ Foundations of Computational mathematics 12.6 (2012): 805-849.
  * [7] E. J. Candès, J. Romberg, and T. Tao. _Stable signal recovery from incomplete and inaccurate measurements._ Comm. Pure Appl. Math. 59 (2006), no. 8: 1207–1223.
  * [8] X. Chen, H. Wang, and R. Wang. _A null space analysis of the $\displaystyle\ell_{1}$-synthesis method in dictionary-based compressed sensing._ Applied and Computational Harmonic Analysis 37 (2014), no. 3: 492–515.
  * [9] A. Cohen, W. Dahmen, and R. DeVore. _Compressed sensing and best $\displaystyle k$-term approximation._ Journal of the American mathematical society 22.1 (2009): 211-231.
  * [10] D. L. Donoho. _Compressed sensing._ IEEE Transactions on information theory 52.4 (2006): 1289-1306.
  * [11] S. Foucart. _Stability and robustness of $\displaystyle\ell_{1}$-minimizations with Weibull matrices and redundant dictionaries._ Linear Algebra and its Applications 441 (2014): 4-21.
  * [12] A. Flinth. _A geometrical stability condition for compressed sensing._ Linear Algebra and its Applications 504 (2016): 406-432.
  * [13] S. Foucart, A. Pajor, H. Rauhut, and T. Ullrich. _The Gelfand widths of $\displaystyle\ell_{p}$-balls for $\displaystyle 0<p\leq 1$_. Journal of Complexity 26.6 (2010): 629-640.
  * [14] S. Foucart and H. Rauhut. _A mathematical introduction to compressive sensing._ Boston: Birkhäuser (2013).
  * [15] R. A. Horn, and C. R. Johnson. Matrix analysis. Cambridge university press, 2012.
  * [16] M. Kabanava, R. Kueng, H. Rauhut, and U. Terstiege (2016). Stable low-rank matrix recovery via null space properties. Information and Inference: A Journal of the IMA, 5.4 (2016): 405-441.
  * [17] V. Koltchinskii and S. Mendelson. _Bounding the smallest singular value of a random matrix without concentration._ International Mathematics Research Notices. 2015 (2015), no. 23: 12991–13008.
  * [18] R. Kueng, H. Rauhut, and U. Terstiege. _Low rank matrix recovery from rank one measurements._ Applied and Computational Harmonic Analysis 42.1 (2017): 88-116.
  * [19] S. Li, T. Mi, and Y. Liu. _Performance analysis of $\displaystyle\ell_{1}$-synthesis with coherent frames._ 2012 IEEE International Symposium on Information Theory Proceedings (2012).
  * [20] H. Rauhut, K. Schnass, and P. Vandergheynst. _Compressed sensing and redundant dictionaries._ IEEE Trans. Inform. Theory 54 (2008), no. 5: 2210–2219.
  * [21] B. Recht, W. Xu, and B. Hassibi. _Necessary and sufficient conditions for success of the nuclear norm heuristic for rank minimization._ 2008 47th IEEE Conference on Decision and Control. IEEE, 2008.
  * [22] B. Recht, W. Xu, and B. Hassibi. _Null space conditions and thresholds for rank minimization._ Mathematical programming 127.1 (2011): 175-202.
  * [23] J. A. Tropp. _Convex recovery of a structured signal from independent random linear measurements._ “Sampling theory, a renaissance.” Appl. Numer. Harmon. Anal., Birkhäuser/Springer, Cham, (2015): 67–101.
  * [24] M. Talagrand. “Upper and lower bounds for stochastic processes: modern methods and classical problems.” Springer Science & Business Media (2014).


# Spin-orbit interaction in the HD+ ion

Vladimir I. Korobov1 and Jean-Philippe Karr2,3 1Bogoliubov Laboratory of
Theoretical Physics, Joint Institute for Nuclear Research, Dubna 141980,
Russia  2Laboratoire Kastler Brossel, Sorbonne Université, CNRS, ENS-
Université PSL, Collège de France, 4 place Jussieu, F-75005 Paris, France
3Université d’Evry-Val d’Essonne, Université Paris-Saclay, Boulevard François
Mitterrand, F-91000 Evry, France

###### Abstract

We report on progress in calculation of the spin-orbit interaction for the HD+
molecular ion. This interaction is currently the largest source of theoretical
uncertainty in determination of the hyperfine structure of rovibrational
transition lines. The corrections of order $m\alpha^{7}\ln(\alpha)$ are
derived and numerically calculated. Theoretical hyperfine intervals are
compared with experimental data, and the observed discrepancies are discussed.

In recent years several experiments [1, 2, 3] succeeded in measuring ro-
vibrational transition lines in the HD+ molecular ion with relative precision
of a few ppt. On the theoretical side, the ”spin-averaged” transition energies
were calculated with relative uncertainties of $1.4\times 10^{-11}$ for the
pure rotational transition and of $7.5\times 10^{-12}$ for vibrational
transitions [4, 5]. The main limitation in theoretical predictions comes from
the hyperfine stucture of transition lines [6], although in recent years there
has been significant progress in the calculation of the hyperfine structure
both in the $m\alpha^{6}$ order [7, 8] and in higher orders [9].

The main purpose of this work is to fill in the gap in the theory by
calculating corrections of the order of $m\alpha^{7}\ln(\alpha)$ to the spin-
orbit interaction. This will allow to get theoretical predictions for the
favored hyperfine components of a ro-vibrational transition (which keep the
spin configuration of the molecular ion unchanged) without any significant
loss of precision with respect to the spin-averaged transition energy.

##  I Nonrelativictic QED

In our derivation of the QED corrections to the hyperfine sublevels of the
state we use the Nonrelativictic QED (NRQED) suggested in [10, 11]. The
Lagrangian for the NRQED is expressed in terms of nonrelativistic (two-
component) Pauli spinor fields $\psi$ for each of the electron, positron,
muon, proton, etc. Photons are treated in the same way as in QED. The
Lagrangian is constrained by the natural symmetry requirements such as gauge
invariance, hermiticity, time reversal symmetry, parity conservation, Galilean
invariance and consequently the rotational invariance. The Coulomb gauge is
used for the NRQED calculations.

Following [12] we use operators: $D_{t}=\partial_{t}\\!+\\!ieA_{0}$,
$\mathbf{D}=\boldsymbol{\nabla}\\!-\\!ie\mathbf{A}$, $\mathbf{B}$,
$\mathbf{E}$, $\boldsymbol{\sigma}$, as building blocks of the Lagrangian and
expand it into a series of inverse powers of the electron mass $m$:

$\mathcal{L}=\sum_{n=0}\psi_{f}^{*}\frac{O_{n}}{m_{e}^{n}}\psi_{e}.$ (1)

Spatial parity and time reversal symmetries of the operators are given in
Table 1.

|  $\boldsymbol{\pi}$ |  E |  B | $\boldsymbol{\sigma}$
---|---|---|---|---
$P$ |  $-$ |  $-$ | + | +
$T$ |  $-$ | + |  $-$ | $-$
Dimension |  $M^{1}$ |  $M^{2}$ |  $M^{2}$ | $M^{0}$
Table 1: Spatial parity and time reversal symmetries, and mass dimension of
operators.

Using symmetries imposed on the Lagrangian, one can show that the form of
$\mathcal{L}$ is unique, and the coefficients: $c_{F}$, $c_{D}$, etc. can be
unambiguously obtained from a comparison with the scattering amplitude in QED
after choosing the regularization in NRQED. The only arbitrariness is
associated with the choice of a basis for homogeneous polynomials of
$\mathbf{p}$, $\mathbf{p^{\prime}}$ (the electron impulse before and after
scattering) to express the interactions in momentum space. Namely, for terms
of degree 2, the interactions may be separated into $p^{2}\\!+\\!p^{\prime
2}$, $\mathbf{p}\mathbf{p}^{\prime}$ or
$(\mathbf{p}\\!+\\!\mathbf{p}^{\prime})^{2}$,
$(\mathbf{p}\\!-\\!\mathbf{p}^{\prime})^{2}$.

With the help of these rules we arrive at the NRQED Hamiltonian expanded up to
terms of $1/m^{4}$ order:

$\begin{array}[]{@{}l}\displaystyle
H_{I}=eA_{0}-c_{F}\frac{e}{2m}\boldsymbol{\sigma}\mathbf{B}-c_{D}\frac{e}{8m^{2}}\bigl{[}\boldsymbol{\nabla}\mathbf{E}\bigr{]}+c_{S}\frac{e}{8m^{2}}\,\boldsymbol{\sigma}\\!\cdot\\!\Bigl{(}\boldsymbol{\pi}\\!\times\\!\mathbf{E}-\mathbf{E}\\!\times\\!\boldsymbol{\pi}\Bigr{)}\\\\[8.53581pt]
\hskip
34.1433pt\displaystyle+c_{W}\frac{e}{8m^{3}}\Bigl{\\{}\boldsymbol{\pi}^{2},\boldsymbol{\sigma}\mathbf{B}\Bigr{\\}}-c_{q^{2}}\frac{e}{8m^{3}}\,\boldsymbol{\sigma}\\!\cdot\\![\Delta\mathbf{B}]+c_{p^{\prime}p}\frac{e}{8m^{3}}\Bigl{\\{}\boldsymbol{\pi}\\!\cdot\\!\mathbf{B}\>\boldsymbol{\sigma}\\!\cdot\\!\boldsymbol{\pi}\Bigr{\\}}\\\\[8.53581pt]
\hskip
56.9055pt\displaystyle+c_{M}\frac{e}{8m^{3}}\Bigl{(}\boldsymbol{\pi}\\!\cdot\\![\boldsymbol{\nabla}\\!\times\\!\mathbf{B}]+[\boldsymbol{\nabla}\\!\times\\!\mathbf{B}]\\!\cdot\\!\boldsymbol{\pi}\Bigr{)}+c_{A}\frac{e^{2}}{8m^{3}}\left(\mathbf{E}^{2}-\mathbf{B}^{2}\right)\\\\[8.53581pt]
\hskip
34.1433pt\displaystyle+c_{X_{1}}\frac{e}{128m^{4}}\left[\boldsymbol{\pi}^{2},(\mathbf{D}\mathbf{E}+\mathbf{E}\mathbf{D})\right]+c_{X_{2}}\frac{e}{64m^{4}}\,\Bigl{\\{}\boldsymbol{\pi}^{2},\left[\boldsymbol{\nabla}\mathbf{E}\right]\Bigr{\\}}-c_{X_{3}}\frac{e}{8m^{4}}\,\Bigl{[}\Delta\left[\boldsymbol{\nabla}\mathbf{E}\right]\Bigr{]}\\\\[8.53581pt]
\hskip 56.9055pt\displaystyle-
c_{Y_{1}}\frac{e}{64m^{4}}\Bigl{\\{}\boldsymbol{\pi}^{2},\boldsymbol{\sigma}\\!\cdot\\!\Bigl{(}\boldsymbol{\pi}\\!\times\\!\mathbf{E}\\!-\\!\mathbf{E}\\!\times\\!\boldsymbol{\pi}\Bigr{)}\Bigr{\\}}+c_{Y_{2}}\frac{ie}{4m^{4}}\>\epsilon_{ijk}\sigma^{i}\pi^{j}[\boldsymbol{\nabla}\mathbf{E}]\pi^{k}\>,\end{array}$
(2)

where $\boldsymbol{\pi}=-i\mathbf{D}=\mathbf{p}-e\mathbf{A}$,
$\mathbf{E}=-\partial_{t}\mathbf{A}\\!-\\!\boldsymbol{\nabla}A_{0}$, and
$\mathbf{B}=\boldsymbol{\nabla}\\!\times\\!\mathbf{A}$. Covariant derivatives
in square brackets act only on the fields within the brackets. Similar results
but in the Lagrangian form were obtained previously in [13] for terms up to
$1/m^{3}$ order and in [14] including terms of order $1/m^{4}$.

The coefficients $c_{i}$ are defined as follows:

$\begin{array}[]{@{}l@{\hspace{5mm}}l@{\hspace{5mm}}l}c_{F}=1+a_{e},\hfil\hskip
14.22636pt&c_{S}=1+2a_{e},\hfil\hskip
14.22636pt&c_{D}=1\\!+\\!2a_{e}\\!+\\!\frac{\alpha}{\pi}\frac{8}{3}\left[\ln\left(\frac{m}{2\Lambda}\right)\\!+\\!\frac{5}{6}\\!-\\!\frac{3}{8}\right],\\\\[2.84526pt]
c_{W}=1,\hfil\hskip
14.22636pt&c_{q^{2}}=\frac{a_{e}}{2}\\!+\\!\frac{\alpha}{\pi}\frac{4}{3}\left[\ln\left(\frac{m}{2\Lambda}\right)\\!+\\!\frac{5}{6}\\!-\\!\frac{1}{8}\right],\hfil\hskip
14.22636pt&c_{p^{\prime}p}=a_{e},\\\\[2.84526pt]
c_{M}=\frac{a_{e}}{2}\\!+\\!\frac{\alpha}{\pi}\frac{4}{3}\left[\ln{\frac{m}{2\Lambda}}\\!+\\!\frac{5}{6}\\!-\\!\frac{3}{8}\right],\hfil\hskip
14.22636pt&c_{A}=1\\!+\\!a_{e},\hfil\hskip 14.22636pt\\\\[2.84526pt]
c_{X_{1}}=5\\!+\\!4a_{e},\hfil\hskip
14.22636pt&c_{X_{2}}=3\\!+\\!4a_{e},\hfil\hskip
14.22636pt&c_{X_{3}}=\frac{\alpha}{\pi}\left[\frac{11}{15}\ln\left(\frac{m}{2\Lambda}\right)\\!+\\!\frac{5}{6}\\!-\\!\frac{13}{40}\right],\\\\[2.84526pt]
c_{Y_{1}}=3\\!+\\!4a_{e},\hfil\hskip
14.22636pt&c_{Y_{2}}=-\frac{\alpha}{\pi}\frac{1}{3}\left[\ln\left(\frac{m}{2\Lambda}\right)\\!+\\!\frac{5}{6}\\!+\\!\frac{1}{8}\right].\hfil\hskip
14.22636pt\end{array}$ (3)

where $a_{e}$ is the anomalous magnetic moment of an electron, $\Lambda\approx
m\alpha^{2}$ is a cutoff parameter, which determines the upper limit of the
photon momenta in the NRQED integrations.

When we are interested in calculating contributions only of order
$m\alpha^{7}\ln(\alpha)$, we may replace $\Lambda$ by $m\alpha^{2}$ in the
coefficients and ignore all higher order contributions, as in the following
example:

$c_{q^{2}}\Rightarrow\frac{\alpha}{\pi}\frac{4}{3}\ln\left(\alpha^{-2}\right),\quad\hbox{etc.}$

##  II Advanced hyperfine structure theory of HD+

The effective spin Hamiltonian for the hyperfine splitting of a ro-vibrational
state in the molecular ion HD+ may be written in a form [15]:

$\begin{array}[]{@{}l}\displaystyle H_{\rm
HFS}=E_{1}(\mathbf{L}\cdot\mathbf{s}_{e})+E_{2}(\mathbf{L}\cdot\mathbf{I}_{p})+E_{3}(\mathbf{L}\cdot\mathbf{I}_{d})+E_{4}(\mathbf{I}_{p}\cdot\mathbf{s}_{e})+E_{5}(\mathbf{I}_{d}\cdot\mathbf{s}_{e})\\\\[2.84526pt]
\displaystyle\hskip
42.67912pt+E_{6}\Bigl{\\{}2\mathbf{L}^{2}(\mathbf{I}_{p}\cdot\mathbf{s}_{e})\\!-\\!3[(\mathbf{L}\cdot\mathbf{I}_{p})(\mathbf{L}\cdot\mathbf{s}_{e})\\!+\\!(\mathbf{L}\cdot\mathbf{s}_{e})(\mathbf{L}\cdot\mathbf{I}_{p})]\Bigr{\\}}\\\\[2.84526pt]
\displaystyle\hskip
42.67912pt+E_{7}\Bigl{\\{}2\mathbf{L}^{2}(\mathbf{I}_{d}\cdot\mathbf{s}_{e})\\!-\\!3[(\mathbf{L}\cdot\mathbf{I}_{d})(\mathbf{L}\cdot\mathbf{s}_{e})\\!+\\!(\mathbf{L}\cdot\mathbf{s}_{e})(\mathbf{L}\cdot\mathbf{I}_{d})]\Bigr{\\}}\\\\[2.84526pt]
\displaystyle\hskip
42.67912pt+E_{8}\Bigl{\\{}2\mathbf{L}^{2}(\mathbf{I}_{p}\cdot\mathbf{I}_{d})\\!-\\!3[(\mathbf{L}\cdot\mathbf{I}_{p})(\mathbf{L}\cdot\mathbf{I}_{d})\\!+\\!(\mathbf{L}\cdot\mathbf{I}_{d})(\mathbf{L}\cdot\mathbf{I}_{p})]\Bigr{\\}}\\\\[-2.84526pt]
\displaystyle\hskip
42.67912pt+E_{9}\Bigl{[}\mathbf{L}^{2}\mathbf{I}_{d}^{2}-\frac{3}{2}(\mathbf{L}\cdot\mathbf{I}_{d})-3(\mathbf{L}\cdot\mathbf{I}_{d})^{2}\Bigr{]}.\end{array}$
(4)

Couplings of the nuclear magnetic moments with the orbital magnetic field
(coefficients $E_{2}$, $E_{3}$, and $E_{8}$), as well as the deuteron
quadrupole moment coupling with the orbital part ($E_{9}$) are very small (see
Table 2). They can be treated perturbatively and their values calculated
within the Breit-Pauli approximation as in [15] are sufficiently accurate for
the present level of theoretical precision. Magnitude of other coefficients
(in MHz) is also shown in the Table.

We use the coupling scheme for angular momentum operators:
$\mathbf{F}=\mathbf{s}_{e}+\mathbf{I}_{p}$,
$\mathbf{S}=\mathbf{F}+\mathbf{I}_{d}$, $\mathbf{J}=\mathbf{F}+\mathbf{L}$,
which reflects (see Fig.1) the fact that the hyperfine structure is
predominantly defined by the spin configuration of the system and interaction
of the total spin $\mathbf{S}$ with the total orbital angular momentum is the
smallest coupling in the hyperfine splitting of a ro-vibrational level.

Coefficients $E_{4}$ and $E_{5}$ had been calculated in [9] with a relative
uncertainty of about $10^{-6}$. Coefficients $E_{6}$ and $E_{7}$ were obtained
with account of the terms of $m\alpha^{6}$ order in [8]. Here we focus on the
coefficient $E_{1}$, which requires contributions of the order of
$m\alpha^{7}\ln(\alpha)$ to be taken into account.

Figure 1: Schematic diagram of the hyperfine spliting of a rovibrational state (L,v) of HD+. $E_{1}$ | $E_{2}$ |  $E_{3}$ |  $E_{4}$ |  $E_{5}$ |  $E_{6}$ | $E_{7}$ | $E_{8}$ | $E_{9}$
---|---|---|---|---|---|---|---|---
31.9846 |  $-$3.134[$-$02] |  $-$4.809[$-$03] | 924.569 | 142.161 | 8.6111 | 1.3218 |  $-$3.057[$-$03] | 5.666[$-$03]
Table 2: Coefficients $E_{i}$ of the effective spin Hamiltonian (in MHz) for
the $(L\\!=\\!1,\\!v\\!=\\!0)$ state (from [15]), $a[b]=a\times 10^{b}$.

###  II.1 Spin-orbit interaction

The leading-order $m\alpha^{4}$ relativistic corrections for the spin-orbit
interaction is expressed [8]:

$H_{so}=-c_{F}\left(\frac{Z_{1}}{mM_{1}}\,\frac{[\mathbf{r}_{1}\\!\times\\!\mathbf{P}_{1}]}{r_{1}^{3}}+\frac{Z_{2}}{mM_{2}}\,\frac{[\mathbf{r}_{2}\\!\times\\!\mathbf{P}_{2}]}{r_{2}^{3}}\right)\mathbf{s}_{e}+c_{S}\left(\frac{Z_{1}}{2m^{2}}\,\frac{[\mathbf{r}_{1}\\!\times\\!\mathbf{p}_{e}]}{r_{1}^{3}}+\frac{Z_{2}}{2m^{2}}\,\frac{[\mathbf{r}_{2}\\!\times\\!\mathbf{p}_{e}]}{r_{2}^{3}}\right)\mathbf{s}_{e},$
(5)

where coefficients $c_{F}$ and $c_{S}$ are defined as in Eq. (3),
$\mathbf{p}_{e}$ and $\mathbf{P}_{a}$ are impulses of the electron and nuclei,
correspondingly.

The effective Hamiltonian at $m\alpha^{6}$ and $m\alpha^{7}\ln(\alpha)$ orders
is derived from the NRQED Hamiltonian (2) in the same way as in [8], thus the
spin-orbit interaction is expessed by a sum of the following operators:

$H_{so}^{(6)}=c_{W}\mathcal{U}_{W}+c_{q^{2}}\mathcal{U}_{q^{2}}+c_{Y_{1}}\mathcal{U}_{Y_{1}}+c_{Y_{2}}\mathcal{U}_{Y_{2}}+c_{S}\mathcal{U}_{\rm
CM}+\mathcal{U}_{\mathrm{MM}_{N}},$ (6)

where the first four operators are obtained from the tree-level contributions:

$\begin{array}[]{@{}l}\displaystyle\mathcal{U}_{W}=\frac{Z_{1}}{4m^{3}M_{1}}\left\\{p_{e}^{2},\frac{1}{r_{1}^{3}}\bigl{[}\mathbf{r}_{1}\\!\times\\!\mathbf{P}_{1}\bigr{]}\right\\}\mathbf{s}_{e}+\frac{Z_{2}}{4m^{3}M_{2}}\left\\{p_{e}^{2},\frac{1}{r_{2}^{3}}\bigl{[}\mathbf{r}_{2}\\!\times\\!\mathbf{P}_{2}\bigr{]}\right\\}\mathbf{s}_{e}\,,\\\\[2.84526pt]
\displaystyle\mathcal{U}_{q^{2}}=\frac{iZ_{1}}{8m^{3}M_{1}}\Bigl{\\{}\left[\mathbf{p}_{e}\\!\times\\!\left(4\pi\delta(\mathbf{r}_{1})\right)\mathbf{P}_{1}\right]\Bigr{\\}}\mathbf{s}_{e}+\frac{iZ_{2}}{8m^{3}M_{2}}\Bigl{\\{}\left[\mathbf{p}_{e}\\!\times\\!\left(4\pi\delta(\mathbf{r}_{2})\right)\mathbf{P}_{2}\right]\Bigr{\\}}\mathbf{s}_{e}\,,\\\\[2.84526pt]
\displaystyle\mathcal{U}_{Y_{1}}=-\frac{Z_{1}}{16m^{4}}\left\\{p_{e}^{2},\frac{1}{r_{1}^{3}}[\mathbf{r}_{1}\\!\times\\!\mathbf{p}_{e}]\right\\}\mathbf{s}_{e}-\frac{Z_{2}}{16m^{4}}\left\\{p_{e}^{2},\frac{1}{r_{2}^{3}}[\mathbf{r}_{2}\\!\times\\!\mathbf{p}_{e}]\right\\}\mathbf{s}_{e}\,,\\\\[2.84526pt]
\displaystyle\mathcal{U}_{Y_{2}}=\frac{iZ_{1}}{2m^{4}}\left[\mathbf{p}_{e}\\!\times\\!(4\pi\delta(\mathbf{r}_{1}))\mathbf{p}_{e}\right]\mathbf{s}_{e}+\frac{iZ_{2}}{2m^{4}}\left[\mathbf{p}_{e}\\!\times\\!(4\pi\delta(\mathbf{r}_{2}))\mathbf{p}_{e}\right]\mathbf{s}_{e}\,,\end{array}$
(7a) while the last two are from the seagull-type diagrams:
$\begin{array}[]{@{}l}\displaystyle\mathcal{U}_{\rm
CM}=\frac{Z_{1}^{2}}{4m^{2}M_{1}}\>\frac{1}{r_{1}^{4}}\left[\mathbf{r}_{1}\\!\times\\!\mathbf{P}_{1}\right]\mathbf{s}_{e}+\frac{Z_{2}^{2}}{4m^{2}M_{2}}\>\frac{1}{r_{2}^{4}}\left[\mathbf{r}_{2}\\!\times\\!\mathbf{P}_{2}\right]\mathbf{s}_{e}\\\\[2.84526pt]
\displaystyle\hskip
28.45274pt+\frac{Z_{1}Z_{2}}{4m^{2}M_{1}}\>\frac{1}{r_{1}r_{2}^{3}}\left[\mathbf{r}_{2}\\!\times\\!\mathbf{P}_{1}\right]\mathbf{s}_{e}+\frac{Z_{1}Z_{2}}{4m^{2}M_{2}}\>\frac{1}{r_{1}^{3}r_{2}}\left[\mathbf{r}_{1}\\!\times\\!\mathbf{P}_{2}\right]\mathbf{s}_{e}\\\\[2.84526pt]
\displaystyle\hskip
28.45274pt-\frac{Z_{1}Z_{2}}{4m^{2}M_{1}}\>\frac{1}{r_{1}^{3}r_{2}^{3}}\left[\mathbf{r}_{1}\\!\times\\!\mathbf{r}_{2}\right](\mathbf{r}_{1}\mathbf{P}_{1})\mathbf{s}_{e}+\frac{Z_{1}Z_{2}}{4m^{2}M_{2}}\>\frac{1}{r_{1}^{3}r_{2}^{3}}\left[\mathbf{r}_{1}\\!\times\\!\mathbf{r}_{2}\right](\mathbf{r}_{2}\mathbf{P}_{2})\mathbf{s}_{e}\,,\\\\[8.53581pt]
\displaystyle\mathcal{U}_{{\rm
MM}_{N}}=-\frac{Z_{1}^{2}}{2m^{2}M_{1}}\>\frac{1}{r_{1}^{4}}\left[\mathbf{r}_{1}\\!\times\\!\mathbf{p}_{e}\right]\mathbf{s}_{e}-\frac{Z_{2}^{2}}{2m^{2}M_{2}}\>\frac{1}{r_{2}^{4}}\left[\mathbf{r}_{2}\\!\times\\!\mathbf{p}_{e}\right]\mathbf{s}_{e}\,.\end{array}$
(7b)

The second-order perturbation contributions are expressed as follows:

$\begin{array}[]{@{}l}\displaystyle\Delta E_{so}^{2^{nd}-order}=\Delta
E_{so}^{(6)}+\Delta E_{so\hbox{-}ret}+\Delta E_{so\hbox{-}so}^{(1)}+\Delta
E_{so}^{(7)},\\\\[8.53581pt] \displaystyle\Delta E_{so}^{(6)}=2\left\langle
H_{so}Q(E_{0}-H_{0})^{-1}QH_{B}^{(4)}\right\rangle,\\\\[5.69054pt]
\displaystyle\Delta E_{so\hbox{-}ret}=2\left\langle
H_{so}Q(E_{0}-H_{0})^{-1}QH_{ret}\right\rangle,\\\\[5.69054pt]
\displaystyle\Delta E_{so\hbox{-}so}^{(1)}=\left\langle
H_{so}Q(E_{0}-H_{0})^{-1}QH_{so}\right\rangle^{(1)},\\\\[5.69054pt]
\displaystyle\Delta E_{so}^{(7)}=2\left\langle
H_{so}Q(E_{0}-H_{0})^{-1}QH_{B}^{(5)}\right\rangle.\end{array}$ (8)

Here we include into the Breit-Pauli Hamiltonian radiative corrections (as
contribution to the Darwin coefficient, $c_{D}$, of Eq. (2)):

$\begin{array}[]{@{}l}\displaystyle
H_{B}=-\frac{p^{4}}{8m^{3}}+c_{D}\frac{\pi\alpha}{2m^{2}}\left[Z_{1}\delta(\mathbf{r}_{1})\\!+\\!Z_{2}\delta(\mathbf{r}_{2})\right]=\left\\{-\frac{p^{4}}{8m^{3}}+\frac{\pi\alpha}{2m^{2}}\left[Z_{1}\delta(\mathbf{r}_{1})\\!+\\!Z_{2}\delta(\mathbf{r}_{2})\right]\right\\}\\\\[5.69054pt]
\displaystyle\hskip
79.66771pt+\left(\frac{\alpha}{\pi}\frac{8}{3}\ln{\alpha^{-2}}\right)\frac{\pi\alpha}{2m^{2}}\left[Z_{1}\delta(\mathbf{r}_{1})\\!+\\!Z_{2}\delta(\mathbf{r}_{2})\right]=H_{B}^{(4)}+H_{B}^{(5)}.\end{array}$

It is worth noting that both first and second-order terms are finite and do
not require regularization.

##  III Results

###  III.1 Pure rotational transition

In case of the pure rotational transition [1]:
$(L\\!=\\!0,v\\!=\\!0)\to(L^{\prime}\\!=\\!1,v^{\prime}\\!=\\!0)$, the
hyperfine splitting is essentially larger relative to the transition line
frequency magnitude than in the case of vibrational transitions. Using the six
measured transition lines one can extract the experimental value of the
$E_{1}$ coefficient. To do this, we fixed the coefficients of the effective
HFS Hamiltonian (4), taking the best theoretical values for $E_{i}$, and then
fit either two parameters: $f_{\rm spin-avg}$ and $E_{1}$, the spin-averaged
transition frequency and the spin-orbit coupling coefficient, or four
parameters: $f_{\rm spin-avg}$, $E_{1}$, $E_{6}$, and $E_{7}$. Results
obtained by both methods agree well with each other and provide the following
numbers:

$f_{\rm spin-avg}^{(\rm exp)}=1\,314\,925\,752.905(10)_{\rm fit}(17)_{\rm
exp}\hbox{ kHz},$

and

$E_{1}^{\rm exp}=31984.9(1)\hbox{ kHz}.$

Results of the numerical calculations for the spin-orbit coupling coefficient
are presented in Table 3. From comparison with experimental fit one may see
that there is some disagreement between theory and experiment of about
$5\sigma$. Thus we see that there is room for further careful study of this
transition both in theory and experiment.

| (1,0)
---|---
$E_{1}^{(4)}$ | 31984.645
$E_{1}^{(6)}$ | 1.119
$E_{1}^{(7)}$ |  $-$0.347
$E_{1}^{\rm th}$ | 31985.4(1)
$E_{1}^{\rm exp}$ | 31984.9(1)
Table 3: Contributions to the $E_{1}$ coefficient for the
$(L\\!=\\!1,v\\!=\\!0)$ state (in kHz).

###  III.2 Two-photon vibrational transition

In case of the two-photon vibrational transition:
$(L\\!=\\!3,v\\!=\\!0)\to(L^{\prime}\\!=\\!3,v^{\prime}\\!=\\!9)$, the two
following lines were measured [2]: $f_{0}^{\rm HF}$:
$(F\\!=\\!0,S\\!=\\!1,J\\!=\\!4)\to(F^{\prime}\\!=\\!0,S^{\prime}\\!=\\!1,J^{\prime}\\!=\\!4)$,
and $f_{1}^{\rm HF}$:
$(F\\!=\\!1,S\\!=\\!2,J\\!=\\!5)\to(F^{\prime}\\!=\\!1,S^{\prime}\\!=\\!2,J^{\prime}\\!=\\!5)$.
The hyperfine splitting relative to the transition frequency is smaller, so
that a precision of five significant digits in the coefficients of the
effective HFS Hamiltonian (4) already allows to get a smaller absolute
theoretical uncertainty than that of the spin-averaged transition frequency.

Table 4 summarizes the contributions to the $E_{1}$ coefficient both for the
initial $(3,0)$ and final $(3,9)$ states. Our final prediction for the
$f_{10}^{\rm HF}=f_{0}^{\rm HF}\\!-\\!f_{1}^{\rm HF}$ spitting (see Table 5)
confirms our previous conclusion [8] concerning the disagreement between
theory and experiment with a deviation of about $9\sigma$.

| (3,0) | (3.9)
---|---|---
$E_{1}^{(4)}$ | 31627.352 | 18270.577
$E_{1}^{(6)}$ | 1.093 | 0.488
$E_{1}^{(7)}$ |  $-$0.341 |  $-$0.184
$E_{1}$ | 31628.1(1) | 18270.9(1)
Table 4: Contributions to the $E_{1}$ coefficient for the $(L\\!=\\!3,v\\!=\\!0)$ and $(3,9)$ states (in kHz). $f_{10,theo}^{\rm HF}$ | 178 245.9(0.3)
---|---
$f_{10,exp}^{\rm HF}$ | 178 254.4(0.9)
Table 5: Comparison of the HFS interval $f_{10}$ with the experiment.

###  III.3 Conclusions

In summary, let us formulate the main theoretical results in the hyperfine
structure calculations of the HD+ molecular ion that were obtained in recent
years:

  * •

The spin-spin scalar interaction coefficients ($E_{4}$ and $E_{5}$) are now
available with relative precision of $\sim\\!10^{-6}$ [9].

  * •

The spin-orbit coefficient $E_{1}$ is obtained with corrections up to
$m\alpha^{7}\ln(\alpha)$ order (this work).

  * •

The spin-spin tensor coefficients $E_{6}$ and $E_{7}$ have been obtained up to
$m\alpha^{6}$ order. Improved numerical results for these coefficients will be
presented in a forthcoming publication.

  * •

Other HFS interactions (not included into the effective HFS Hamiltonian (4))
were also studied, particularly the nuclear spin-spin interaction mediated by
the electron spin [16]. It is found [6] that this correction is too small to
explain the observed discrepancies.

In a view of these achievements, it can be stated that the favored hyperfine
components of ro-vibration transition lines can now be obtaied with a
theoretical precision that is mainly limited by the calculation of the spin-
averaged transition frequency, i.e., $1.4\times 10^{-11}$ for pure rotational
transitions and $7.5\times 10^{-12}$ for vibrational transitions. The main
sources of theoretical uncertainty are the $m\alpha^{8}$ order one- and two-
loop contributions to the spin-averaged transition frequency [4, 5].

###  III.4 Acknowledgements

This work was done in collaboration with Laurent Hilico, Mohammad Haidar
(LKB), and Zhen-Xiang Zhong (Wuhan, WIPM CAS) that is gratefully acknowledged.

## References

  * [1] S. Alighanbari, G.S. Giri, F.L. Constantin, V.I. Korobov, and S. Schiller, Precise test of quantum electrodynamics and determination of fundamental constants with HD+ ions, Nature 581, 152 (2020).
  * [2] S. Patra, M. Germann, J.-Ph. Karr, M. Haidar, L. Hilico, V. I. Korobov, F. M. J. Cozijn, K. S. E. Eikema, W. Ubachs, and J. C. J. Koelemeij, Proton-electron mass ratio from laser spectroscopy of HD+ at the part-per-trillion level, Science 369, 1238 (2020).
  * [3] I. Kortunov, S. Alighanbari, M.G. Hansen, G.S. Giri, S. Schiller, and V.I. Korobov, Proton-electron mass ratio by high-resolution optical spectroscopy of ion ensemble in the resolved-carrier regime. Nature Phys. 17, 569 (2021).
  * [4] V.I. Korobov, L. Hilico, and J.-Ph. Karr, Fundamental transitions and ionization energies of the hydrogen molecular ions with few ppt uncertainty. Phys. Rev. Lett. 118, 233001 (2017).
  * [5] V.I. Korobov and J.-Ph. Karr, Rovibrational spin-averaged transitions in the hydrogen molecular ions, Phys. Rev. A 104, 032806 (2021).
  * [6] V.I. Korobov, Precision Spectroscopy of the Hydrogen Molecular Ions: Present Status of Theory and Experiment. Physics of Particles and Nuclei, 53, 787–789 (2022).
  * [7] M. Haidar, Z.-X. Zhong, V.I. Korobov and J.-Ph. Karr, NRQED approach to the fine and hyperfine structure corrections of order $m\alpha^{6}$ and $m\alpha^{6}(m/M)$: Application to the hydrogen atom. Phys. Rev. A 101, 022501 (2020).
  * [8] V.I. Korobov, J.-Ph. Karr, M. Haidar, and Zhen-Xiang Zhong, Hyperfine structure in the H${}_{2}^{+}$ and HD+ molecular ions at $m\alpha^{6}$ order. Phys Rev. A 102, 022804 (2020).
  * [9] J.-Ph. Karr, M. Haidar, L. Hilico, Zhen-Xiang Zhong, and V.I. Korobov, Higher-order corrections to spin-spin scalar interactions in HD+ and H${}_{2}^{+}$. Phys. Rev. A 102, 052827 (2020).
  * [10] W.E. Caswell and G.P. Lepage, Effective Lagrangians for bound state problems in QED, QCD, and other field theories. Phys. Lett. B 167, 437 (1986).
  * [11] T. Kinoshita and M. Nio, Radiative corrections to the muonium hyperfine structure: The $\alpha^{2}(Z\alpha)$ correction. Phys. Rev. D 53, 4909 (1996).
  * [12] G. Paz, An introduction to NRQED. Mod. Phys. Lett. A 80, 1550128 (2015).
  * [13] A.V. Manohar, Heavy quark effective theory and nonrelativistic QCD Lagrangian to order $a_{s}/m^{3}$. Phys. Rev. D 56, 230 (1997).
  * [14] R.J. Hill, G. Lee, G. Paz, and M.P. Solon, NRQED Lagrangian at order $1/M^{4}$. Phys. Rev. D 87, 053017 (2013).
  * [15] D. Bakalov, V.I. Korobov, and S. Schiller, High-precision calculation of the hyperfine structure of the $\mbox{HD}^{+}$ ion, Phys. Rev. Lett. 97, 243001 (2006).
  * [16] N. Ramsey, Electron Coupled Interaction Between Nuclear Spins in Molecule. Phys. Rev. 91, 303 (1953).