\section{Introduction}
Given a  compact set $E\subset\mathbb{R}^d$, let $\text{conv}(E)$ be the convex hull of $E$. We define the \emph{Minkowski functional} to be
\begin{equation}\label{equ:m}
\inf\{\lambda>0: \lambda^{-1}v\in \text{conv}(E)\}.
\end{equation}
If the centroid of $\text{conv}(E)$ is at the origin, then \eqref{equ:m} can be rewritten as 
\begin{equation}\label{equ:m2}
\inf\{\sum_{i\in I}c_i: v = \sum_{i\in I}c_ix_i, c_i\geq0\}.
\end{equation}
In addition, if $E=-E$, then \eqref{equ:m} or \eqref{equ:m2} is a norm, called the \emph{atomic norm}~\cite{C12}. 

Throughout this paper, we will assume  the \emph{atomic set} $\mathcal{W}=\{w_i\}_{i\in I}$ is a compact subset of $\mathbb{R}^d$.
Define $\mathcal{W}_{\text{sym}}:=\mathcal{W}\cup(-\mathcal{W})$ and the atomic norm associated with $\mathcal{W}$ as
\begin{equation}\label{equ:norm}
\|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}^Nc_iw_i\}.
\end{equation}

Let $C_\mathcal{W}$ be the smallest constant such that
$$\|v\|_\mathcal{W}\leq C_\mathcal{W}\|v\|_2.$$
We let $B_\mathcal{W}:=\{v\in\mathbb{R}^d:\|v\|_\mathcal{W}\leq1\}=\text{conv}(\mathcal{W}_{\text{sym}})$ be the unit ball with respect to the atomic norm.


We would like to recover a structured signal $z_0$ from few linear measurements $y=\mathcal{A} z_0$ via the convex minimization problem
\begin{equation}\label{equ:K0}\tag{$\text{P}_\mathcal{W}$}
\hat{z}=\arg\min_{z\in \mathbb{R}^d} \|z\|_{\mathcal{W}} \quad\text{ subject to } \quad \mathcal{A} z=y.\\
\end{equation}
The vector $\mathcal{A} z_0$ contains $m$ inner products with $z_0$, so $\mathcal{A} z_0\in\mathbb{R}^m$.

If the measurement is perturbed as $y=\mathcal{A} z_0+e$ where $\|e\|_2\leq\epsilon$, then we consider the following version
\begin{equation}\label{equ:K}\tag{$\text{P}_{\mathcal{W},\epsilon}$}
\hat{z}=\arg\min_{z\in \mathbb{R}^d} \|z\|_{\mathcal{W}} \quad\text{ subject to } \quad \|\mathcal{A} z-y\|_2\leq \epsilon.\\
\end{equation}

By ``structured signal'', we mean that it is a linear combination of very few atoms in $\mathcal{W}$.
We say a vector $z$ is \emph{$\mathcal{W}$-sparse of order $s$ (or simply $\mathcal{W}$-$s$-sparse)} if $z$ can be written as a linear combination of at most $s$ atoms from $\mathcal{W}$. Such collection of vectors will be denoted $\Sigma_{\mathcal{W},s}$, i.e., $$\Sigma_{\mathcal{W},s}:=\{z\in\mathbb{R}^d: z = \sum_{i\in J}c_iw_i\text{ for some }|J|\leq s, c_i\in\mathbb{R}\}.$$

Recovering $z_0$ through \eqref{equ:K} is possible even when the number of linear measurement $m$ is far less than the ambient dimension $d$, if  $\mathcal{A}$ is well designed. 

We  need a way to define the ``tail'' when a vector is not exactly $\mathcal{W}$-sparse. This will be an important notion in this paper. Define
\begin{equation}\label{equ:tWW}
\sigma_{\mathcal{W},s}(z):=\inf\{\|z-v\|_{\mathcal{W}}: v\in\Sigma_{\mathcal{W},s}\}.
\end{equation}
This tail can also be viewed as the distance from $z$ to the set $\Sigma_{\mathcal{W},s}$.

In the case that the minimum can be obtained in \eqref{equ:tWW}, we write
\begin{equation}\label{equ:zs}
z_s:=\arg\min\{\|z-v\|_{\mathcal{W}}: v\in\Sigma_{\mathcal{W},s}\},
\end{equation}
and hence $\sigma_{\mathcal{W},s}(z)=\|z-z_s\|_\mathcal{W}$.

\subsection{Notations}
Given the linear map $\mathcal{A}$, $\mathcal{N}(\mathcal{A})$ is the null space of $\mathcal{A}$, and $\nu_A$ is the smallest singular value of the matrix of map $\mathcal{A}$ under an orthonormal basis. For any matrix $X$, $\{\sigma_i(X)\}_{i=1}^K$ are the singular values of $X$, and $\|X\|_*=\sum_{i=1}^K\sigma_i(X)$ is the nuclear norm of $X$. $\|X\|_F$ is the Frobenius norm of $X$.
For any index set $T$, $|T|$ is the cardinality of $T$, and $T^c$ is the compliment set of $T$.
For any $p\geq1$, $\|\cdot\|_p$ is the $\ell_p$ norm.

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

The notation $\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.

\subsection{Examples}
We will now list several examples of atomic sets that are special cases of our setup. See more examples in \cite{C12}.
\begin{example}[Compressed Sensing]\label{exa:cs}
As the simplest example, when the atom set $\mathcal{E}$ is the canonical orthonormal basis of the Euclidean space, we have $\|v\|_\mathcal{E}=\|v\|_1$. In this context, an $\mathcal{E}$-$s$-sparse vector is a vector whose coordinates are nonzero  at most $s$ locations. This is the classical compressed sensing~\cite{CRT06, D06, CDD09}. It is easy to show that the tail $\sigma_{\mathcal{E},s}(z)=\|z_{T^c}\|_1$ where $T$ is the index set of the largest $s$ coordinates in magnitude of $z$.
\end{example}

\begin{example}[Compressed Sensing with Frames]\label{exa:frame}
Let $\mathcal{F}=\{f_i\}_{i=1}^N$ be a frame of the Euclidean space $\mathbb{R}^d$, hence $N\geq d$. Let $F=[f_1,f_2,\cdots,f_N]$ be the $d\times N$ matrix whose columns are the atoms. We have
\begin{align}\notag
\|z-v\|_\mathcal{F}&=\min\{\|c\|_1: Fc=z-v\}\\\notag
&=\min\{\|c+u-u\|_1: z=F(c+u), v=Fu\}\\\label{equ:z-v}
&=\min\{\|x-u\|_1: z=Fx, v=Fu\}
\end{align}
which implies
\begin{equation}\label{equ:tW}
\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}\}.
\end{equation}
There has been many work on this case \cite{RSV08, CENR11,LML12,ACP12,CWW14,CCL18}. See Section \ref{sec:frame} for more details.
\end{example}

\begin{example}[Low Rank Matrix Recovery]\label{exa:matrix}
Let $\mathcal{M}=\{uv^T: u\in\mathbb{R}^{n_1}, v\in\mathbb{R}^{n_2}, \|u\|_2=\|v\|_2=1\}$. For any matrix $X\in\mathbb{R}^{n_1\times n_2}$, its atomic norm becomes the nuclear norm. Although $\|X\|_\mathcal{M}=\|X\|_*$ is a well known fact, we provide a proof in the Appendix (Lemma \ref{lem:nuc}). $\Sigma_{\mathcal{M},s}=\{\sum_{i=1}^sc_iu_iv_i^T: \|u\|_2=\|v\|_2=1\}$ is the set of $n_1\times n_2$ matrices whose rank is at most~$s$. Let $K=\min\{n_1,n_2\}$. Note that the tail of any matrix $Z$ has a simple expression
\begin{equation}
\sigma_{\mathcal{M},s}(Z)=\sum_{j=s+1}^K\sigma_j(Z).
\end{equation}
This is due to Lemma \ref{lem:sv}. Specifically, for $V\in\Sigma_{\mathcal{M},s}$,  we have $\|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 $\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 \cite{RXH08, RXH11, KKRT16}. See Section \ref{sec:matrix} for more details.
\end{example}

\begin{example}[Phase Retrieval]\label{exa:p}
Let $\mathcal{P}=\{uu^T: u\in\mathbb{C}^{n},  \|u\|_2=1\}$ be the collection of unit norm rank-1's  in $\mathcal{H}_n$, the space of complex Hermitian $n\times n$ matrices. $\mathcal{H}_n$ is a real vector space of dimension $n^2$. For any Hermitian matrix $X\in\mathcal{H}_n$, its atomic norm is its nuclear norm. $\Sigma_{\mathcal{P},s}=\{\sum_{i=1}^sc_iu_iu_i^*: \|u_i\|_2=1\}$ is the set of $n\times n$ Hermitian matrices whose rank is at most~$s$.

The phase retrieval problem aims to recover $z_0\in\mathbb{C}^n$ up to a phase from $\{|\langle z_0,a_i\rangle|\}_{i=1}^m$, which is equivalent to recovering $Z_0=z_0z_0^*$ from the linear measurement $\mathcal{A} (Z_0)=y:=(\langle Z_0,a_ia_i^*\rangle)_{i=1}^m$. One may solve (P$_{\mathcal{P},\epsilon}$), which is
\begin{equation}\label{equ:P}
\hat{Z}=\arg\min_{Z\in \mathcal{H}_n} \|Z\|_{*} \quad\text{ subject to } \quad \|\mathcal{A}(Z)-y\|_2\leq \epsilon.
\end{equation}
to recover $Z_0\in\Sigma_{\mathcal{P},1}$, hence recover $z$ up to a phase. See \cite{CL14, KRT17}.
\end{example}

\subsection{Contributions and Organizations}
Our work has a very general setting for recovering signals sparse in an atomic set via the convex programming \eqref{equ:K}. Many important applications fall into this general setting as outlined above. Our work has a similar setup as \cite{C12}, but it differers from \cite{C12} 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 \ref{thm:iff}, Theorem \ref{thm:main}, Theorem \ref{thm:RNSP}, and Theorem \ref{thm:snsp}. Theorem \ref{thm:iff} characterizes the exact recovery of sparse signals via \eqref{equ:K0} when no noise is present. Theorem \ref{thm:snsp} shows that recovery through \eqref{equ:K} is stable with respect to the tail and robust with respect to measurement noise if the measurement map $\mathcal{A}$ satisfy a strong null space property. Theorem \ref{thm:main} and Theorem \ref{thm:RNSP} are similar recovery results that require extra but reasonable condition on the set $\mathcal{W}$.

We also argue that very few measurements are sufficient for recovery. Theorem \ref{thm:min2} claims that if there are $N$ atoms in $\mathcal{W}$, then $O(s\ln(N/s)$ measurements are required when using \eqref{equ:K0}. On the other hand, Corollary \ref{cor:sub} 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 $O(s\ln(N/s)$ in many applications.

Sections \ref{sec:frame} and \ref{sec:matrix} 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 \ref{cor:frame2}, but our analysis is simpler. Corollary \ref{cor:frame} and Corollary \ref{cor:fmin} are new results. For low rank matrix recovery, Corollary \ref{cor:matrix}(a)(c) are  new results. 




\section{Recovery Results}\label{sec:recover}
In this section, we will provide stability and robustness results of recovering signals
 through the minimization problem \eqref{equ:K0} or \eqref{equ:K} if the null space of the linear map $\mathcal{A}$ satisfies certain properties.

Given the set $\mathcal{W}$, and the sparsity level $s$, we define the set
\begin{equation}\label{equ:E}
E_{\mathcal{W},s}:=\{z:\|v\|_\mathcal{W}<\|z-v\|_\mathcal{W},  \text{ for any }v\in\Sigma_{\mathcal{W},s}\}.
\end{equation}
Loosely speaking, the signals in $E_{\mathcal{W},s}$ should have their atomic energy spread out over the atoms of $\mathcal{W}$. On the other hand, a $\mathcal{W}$-$s$-sparse vector has its energy concentrated at $s$ atoms only and obviously does not belong to $E_{\mathcal{W},s}$. Furthermore,  one can easily show  that  $\Sigma_{\mathcal{W},2s}\cap E_{\mathcal{W},s}=\emptyset$.

Since the goal is to tell $\mathcal{W}$-$s$-sparse vectors apart after mapping through $\mathcal{A}$, at minimum, we need to have $\mathcal{N}(\mathcal{A})\cap \Sigma_{\mathcal{W},2s}=\{0\}$. The following property of $\mathcal{A}$ can guarantee this.
\begin{definition}\label{def:wnsp}
Given the set $\mathcal{W}$, and the sparsity level $s$, $\mathcal{A}$ is said to have $\mathcal{W}$ null space property of order $s$ ($\mathcal{W}$-$s$-NSP) if $\mathcal{N}(\mathcal{A})\backslash\{0\}\subseteq E_{\mathcal{W},s}$. Specifically, $\mathcal{W}$-$s$-NSP is equivalent to
\begin{equation}\label{equ:wnsp}
\|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}.
\end{equation}
\end{definition}

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

\begin{theorem}\label{thm:iff}
$\mathcal{A}$ has $\mathcal{W}$-$s$-NSP  if and only if the method \eqref{equ:K0} is successful at recovering all signals in $\Sigma_{\mathcal{W},s}$.
\end{theorem}
\begin{proof}
Suppose \eqref{equ:K0} is successful at recovering all signals in $\Sigma_{\mathcal{W},s}$. Take any $v\in\Sigma_{\mathcal{W},s}$ and any $z\in\mathcal{N} (\mathcal{A})\backslash\{0\}$. We will use \eqref{equ:K0} to recover $-v$ (with $y=-\mathcal{A} v$). Both $-v$ and $z-v$ are feasible in \eqref{equ:K0} and $-v\neq z-v$. By assumption, $-v$ must be the unique minimizer, which means $\|-v\|_\mathcal{W}<\|z-v\|_\mathcal{W}$.

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



\begin{remark}
In the setting of Example \ref{exa:cs}, Definition \ref{def:wnsp} reduces to the well known null space property of a matrix $A$, which is:
\begin{equation}\label{equ:nsp}
\|z_T\|_1<\|z_{T^c}\|_1, \text{ for any }z\in\mathcal{N}(A)\backslash\{0\} \text{ and any }|T|\leq s.
\end{equation}
This is because for any $z\in\mathcal{N}(A)\backslash\{0\}$ and any $v\in\Sigma_{\mathcal{E},s}$, let $T$ be the support of $v$, then
$$\|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.$$
\end{remark}

In compressed sensing, by a simple compactness argument, the NSP \eqref{equ:nsp} implies the existence of $\rho<1$ such that $\|z_T\|_1\leq\rho\|z_{T^c}\|_1$ for any $z\in\mathcal{N}(A)$ and any $|T|\leq s$. However, this is certainly not the case for Definition \ref{def:wnsp}. In fact, we can never have 
\begin{equation}\label{equ:wrong}
\|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}.
\end{equation}
if $\rho$ is less than 1. This is because with a fixed $z$, we can choose $v\in\Sigma_{\mathcal{W},s}$ such that $\|v\|_\mathcal{W}$ is big enough to make $\|v\|_\mathcal{W}>\rho\|z-v\|_\mathcal{W}$.

In order to make \eqref{equ:wrong} feasible, we have to refine the choice of $v$.
Therefore we will propose  two strengthened  null space properties that restrict $v$ to be the best $s$-term approximation of $z$.

\begin{definition}\label{def:wnsp2}
Recall $z_s$ as defined in \eqref{equ:zs}.

(a) $\mathcal{A}$ is said to have the stable $\mathcal{W}$ null space property of order $s$ with the NSP constant $\rho<1$ ($\mathcal{W}$-$s$-$\rho$-NSP) if  
\begin{equation}
\|z_s\|_\mathcal{W}\leq\rho\|z-z_s\|_\mathcal{W}, \qquad  \text{ for any }z\in\mathcal{N}(\mathcal{A}).
\end{equation}

(b) $\mathcal{A}$ is said to have the robust $\mathcal{W}$ null space property of order $s$ ($\mathcal{W}$-$s$-RNSP) if there exist  constants $\tau>0$ and $0<\rho<1$ such that 
\begin{equation}\label{equ:frnsp}
\|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.
\end{equation}
\end{definition}

We want to include Definition \ref{def:wnsp2}(b) as well since this type of ``null space'' property has been used in compressed sensing \cite{F14} and low matrix recovery \cite{KKRT16}.

We will see in Theorem \ref{thm:main} and Theorem \ref{thm:RNSP} that both versions of the strengthened null space property will imply the stable and robust recovery of any signal via \eqref{equ:K} if the atomic set $\mathcal{W}$ satisfies certain conditions. 

\begin{definition}\label{def:split}
We call $\mathcal{W}$ $s$-splittable if for any $x,y\in\mathbb{R}^d$, 
$$\|x+y\|_\mathcal{W}\geq\|x_s\|_\mathcal{W}-\|y_s\|_\mathcal{W}+\|y-y_s\|-\|x-x_s\|_\mathcal{W}.$$
\end{definition}

Definition \eqref{def:split} looks strange at first glance, but as two important examples, both $\mathcal{E}$ and $\mathcal{M}$ are $s$-splittable. See Lemma \ref{lem:split} in the Appendix.

\begin{theorem}\label{thm:main}
Let $\mathcal{W}$ be $s$-splittable. If $\mathcal{A}$ has the stable $\mathcal{W}$-NSP of order $s$ with  constant $0<\rho<1$, then for any $z_0\in\mathbb{R}^d$ and $y=\mathcal{A} z_0+e$ where $\|e\|_2\leq\epsilon$, we have
\begin{equation}\label{equ:main}
\|\hat z-z_0\|_\mathcal{W}\leq\frac{2+2\rho}{1-\rho}\sigma_{\mathcal{W},s}(z_0)+\frac{4 C_\mathcal{W}}{(1-\rho)\nu_A}\epsilon,
\end{equation}
where $\hat z$ is from \eqref{equ:K}. 
\end{theorem}
\begin{proof}
Let $h=\hat z-z_0$.
We decompose $h$ as $h=a+\eta$ where $a\in N(\mathcal{A})$ and $\eta\in N(\mathcal{A})^\perp$. We have $$\|\eta\|_2\leq\frac{1}{\nu_A}\|Ah\|_2\leq\frac{2\epsilon}{\nu_A}.$$

On one hand, using $\hat z$ is a minimizer and $\mathcal{W}$ is splittable,
\begin{align*}
\|z_0\|_\mathcal{W}&\geq\|\hat z\|_\mathcal{W}=\|a+\eta+z_0\|_\mathcal{W}\geq\|z_0+a\|_\mathcal{W}-\|\eta\|_\mathcal{W}\\
&\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}\\
&\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}.
\end{align*}
If we denote $\|z_0-z_{0,s}\|_\mathcal{W}$ as $\sigma$, then the above simplifies to
\begin{equation}\label{equ:snsp1}
\|a-a_s\|_\mathcal{W}\leq2\sigma+\|a_s\|_\mathcal{W}+\|\eta\|_\mathcal{W}
\end{equation}

On the other hand, by stable $\mathcal{W}$-NSP,
\begin{equation}\label{equ:a}
\|a_s\|_\mathcal{W}\leq\rho\|a-a_s\|_\mathcal{W}.
\end{equation}
Combining \eqref{equ:snsp1} and \eqref{equ:a}, we have
$$\|a_s\|_\mathcal{W}\leq2\rho\sigma+\rho\|a_s\|_\mathcal{W}+\rho\|\eta\|_\mathcal{W},$$
 which simplifies to
\begin{equation}\label{equ:v0}
\|a_s\|_\mathcal{W}\leq\frac{2\rho}{1-\rho}\sigma+\frac{\rho}{1-\rho}\|\eta\|_\mathcal{W}.
\end{equation}
In the end, using \eqref{equ:snsp1} and \eqref{equ:v0},
\begin{align*}
\|h\|_\mathcal{W}&\leq\|a\|_\mathcal{W}+\|\eta\|_\mathcal{W}\leq\|a_s\|_\mathcal{W}+\|a-a_s\|_\mathcal{W}+\|\eta\|_\mathcal{W}\\
&\leq\|a_s\|_\mathcal{W}+2\sigma+\|a_s\|_\mathcal{W}+\|\eta\|_\mathcal{W}+\|\eta\|_\mathcal{W}\\
&\leq\frac{4\rho}{1-\rho}\sigma+\frac{2\rho}{1-\rho}\|\eta\|_\mathcal{W}+2\sigma+2\|\eta\|_\mathcal{W}\\
&=\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\\
&\leq\frac{2+2\rho}{1-\rho}\sigma+\frac{4 C_\mathcal{W}}{(1-\rho)\nu_A}\epsilon.
\end{align*}
\end{proof}



\begin{theorem}\label{thm:RNSP}
Let $\mathcal{W}$ be $s$-splittable. Given $z_0\in\mathbb{R}^d$ and the recovered signal $\hat z$ from \eqref{equ:K} where $y=\mathcal{A} z_0+e$ with $\|e\|_2\leq\epsilon$, then the robust $\mathcal{W}$-NSP of order $s$ yields the following stability result
\begin{equation}
\|\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.
\end{equation}
\end{theorem}
\begin{proof}
Let $h=\hat z-z_0$. Denote $\sigma_{\mathcal{W},s}(z_0)=\|z\|_\mathcal{W}-\|z_s\|_\mathcal{W}$ by $\sigma$.
Using $\hat z$ is a minimizer and $\mathcal{W}$ is splittable,
\begin{align*}
\|z_0\|_\mathcal{W}&\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\\
&\geq\|z_0\|_\mathcal{W}-\sigma-\|h_s\|_\mathcal{W}+\|h-h_s\|_\mathcal{W}-\sigma,
\end{align*}
which simplifies to
\begin{equation}\label{equ:rnsp1}
\|h-h_s\|_\mathcal{W}\leq\|h_s\|_\mathcal{W}+2\sigma.
\end{equation}
Now we use the $\mathcal{W}$-RNSP to get
\begin{equation}\label{equ:rnsp2}
\|h_s\|_\mathcal{W}\leq\rho\|h-h_s\|_\mathcal{W}+\tau\|Ah\|_2.
\end{equation}
\eqref{equ:rnsp1} and \eqref{equ:rnsp2} implies
\begin{equation}\label{equ:main3}
\|h_s\|_\mathcal{W}\leq\frac{1}{1-\rho}(2\sigma\rho+\tau\|Ah\|_2).
\end{equation}
Using \eqref{equ:rnsp1} and \eqref{equ:main3},
\begin{align*}
\|h\|_\mathcal{W}&\leq\|h_s\|_\mathcal{W}+\|h-h_s\|_\mathcal{W}\leq2\|h_s\|_\mathcal{W}+2\sigma\\
&\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.
\end{align*}
Finally, the desired result holds because $\|Ah\|_2\leq 2\epsilon$.
\end{proof}

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



\begin{definition}\label{def:snsp}
$\mathcal{A}$ is said to have the strong $\mathcal{W}$ null space property of order $s$ ($\mathcal{W}$-$s$-SNSP) if  there exists $c>0$ such that
\begin{equation}
\|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}.
\end{equation}
\end{definition}

 As we will see in the following theorem, recovery results with this property does not pose further conditions on $\mathcal{W}$. Definition \ref{def:snsp} is inspired by \cite{CWW14} and will be discussed more in Section \ref{sec:frame}. 

\begin{theorem}\label{thm:snsp}
If $\mathcal{A}$ has the strong $\mathcal{W}$-NSP of order $s$, then for any $z_0\in\mathbb{R}^d$ and $y=\mathcal{A} z_0+e$ where $\|e\|_2\leq\epsilon$, we have
$$\|\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 $\hat z$ is from \eqref{equ:K}. 
\end{theorem}
\begin{proof}

Let $\sigma_{\mathcal{W},s}(z_0)=\|z_0-v_0\|_{\mathcal{W}}$, where $v_0\in\Sigma_{\mathcal{W},s}.$ 
 Let $h=\hat z-z_0$. We abbreviate $\sigma_{\mathcal{W},s}(z_0)$ to $\sigma$, then
 $\|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
\begin{equation}\label{equ:main1}
\|h+v_0\|_\mathcal{W}\leq\|v_0\|_\mathcal{W}+2\sigma.
\end{equation}


On the other hand, we decompose $h$ as $h=a+\eta$ where $a\in N(\mathcal{A})$ and $\eta\in N(\mathcal{A})^\perp$. We have $$\|\eta\|_2\leq\frac{1}{\nu_A}\|Ah\|_2\leq\frac{2\epsilon}{\nu_A}.$$

By strong NSP,
\begin{equation}\label{equ:a1}
\|a+v_0\|_\mathcal{W}-\|v_0\|_\mathcal{W}\geq c\|a\|_2.
\end{equation}
Combining \eqref{equ:main1} and \eqref{equ:a1}, we have
\begin{align*}
c\|a\|_2&\leq\|a+v_0\|_\mathcal{W}-\|h+v_0\|_\mathcal{W}+2\sigma_{\mathcal{W},s}(z_0)\\
&\leq\|a-h\|_\mathcal{W}+2\sigma_{\mathcal{W},s}(z_0)=\|\eta\|_\mathcal{W}+2\sigma_{\mathcal{W},s}(z_0).
\end{align*}
In the end,
\begin{align*}
\|h\|_2&\leq\|a\|_2+\|\eta\|_2\leq\frac{1}{c}\|\eta\|_\mathcal{W}+\frac{2}{c}\sigma_{\mathcal{W},s}(z_0)+\|\eta\|_2\\
&\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)
\end{align*}
\end{proof}


\section{Minimum Number of Measurements}\label{sec:min}
This section provides the smallest number of measurements required for successful recovery, whether it is through the problem of primary interest \eqref{equ:K}, or the existence of a general decoder $\Delta$.
In this section, we will assume that there are finitely many atoms in $\mathcal{W}$. Moreover, a condition will be imposed on the set $\mathcal{W}$.


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

\begin{remark}
In the context of Example \ref{exa:frame}, a sufficient condition for $\mathcal{F}$ to be $s$-even is for matrix $F=[f_1,f_2,\cdots,f_n]$ to have the $s$-NSP condition. A proof is provided in the Appendix (Lemma \ref{lem:snsp}).
\end{remark}
 
 

 
\begin{lemma}[{\cite[Lemma 2.3]{FPRT10}}]\label{lem:N}
Suppose $t<N$ are integers. There exists a family $\mathcal{U}$ of subsets of $[N]$ such that:
\begin{enumerate}
\item Every set in $\mathcal{U}$ consists of exactly $t$ elements.
\item For all $I,J\in\mathcal{U}$ with $I\neq J$, it holds that $|I\cap J|<\frac{t}{2}$.
\item $|\mathcal{U}|\geq\left(\frac{N}{4t}\right)^{t/2}$
\end{enumerate}
\end{lemma}

\begin{theorem}\label{thm:min2}
  Let $\mathcal{W}$ be $s$-even. If for every $z_0\in\Sigma_{\mathcal{W},s}$ and $y=\mathcal{A} z_0$, we have $\hat z=z_0$ where $\hat z$ is a solution of \eqref{equ:K0}, then the number of measurments
$$m\geq \frac{1}{8\ln3}s\ln\frac{N}{2s}.$$
\end{theorem}
\begin{proof
Let $\mathcal{U}$ be a family of subsets of $[N]$ given by Lemma \ref{lem:N} with $t=\lfloor s/2\rfloor$. For each $I\in\mathcal{U}$, define $z_I:=\frac{1}{t}\sum_{i\in I}w_i$. We have $|I|=\lfloor s/2\rfloor$. By definition, $\|z_I\|_\mathcal{W}\leq1$.


For $I\neq J$,  $z_I-z_J=\frac{1}{t}(\sum_{i\in I-J}w_i-\sum_{j\in J-I}w_j)$. Its support $|I-J|+|J-I|=|I|+|J|-2|I\cap J|$, so $s\geq2t\geq|I-J|+|J-I|>t$. Since $\mathcal{W}$ is $s$-even, 
\begin{equation}\label{equ:zij}
\|z_i-z_j\|_\mathcal{W}=\frac{1}{t}(|I-J|+|J-I|)>1.
\end{equation}

We claim that $\{\mathcal{A}(z_I+\frac{1}{2} B_\mathcal{W}), I\in\mathcal{U}\}$ is a disjoint collection of subsets of $\mathcal{A}(\mathbb{R}^d)$.
 Otherwise there exist $I\neq J$ and $v, v'\in B_\mathcal{W}$ such that $\mathcal{A}(z_I+\frac{1}{2} v)=\mathcal{A}(z_J+\frac{1}{2} v')$. This means that $\mathcal{A}(z_I-z_J)=\mathcal{A}(\frac{1}{2} v'-\frac{1}{2} v)$. The vector $z_I-z_J\in\Sigma_{\mathcal{W},s}$, so by our assumption,  
 \begin{equation}
 \|z_I-z_J\|_\mathcal{W}\leq\|\frac{1}{2} v'-\frac{1}{2} v\|_\mathcal{W}\leq\|\frac{1}{2} v'\|_\mathcal{W}+\|\frac{1}{2} v\|_\mathcal{W}=1,
 \end{equation}
a contradiction to \eqref{equ:zij}.

It is easy to see that $\mathcal{A}(z_I+\frac{1}{2} B_\mathcal{W})\subset \frac{3}{2}\mathcal{A} B_\mathcal{W}$ for any $I\in\mathcal{U}$. So
\begin{align}\label{equ:vol2}
|\mathcal{U}|\mathrm{vol}(\frac{1}{2}AB_\mathcal{W})))\leq \mathrm{vol}(\frac{3}{2}AB_W).
\end{align}
Let $\mathcal{A} B_\mathcal{W}$ have Hausdorff dimension $r\leq m$, so \eqref{equ:vol2} becomes
\begin{align*}
\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}\leq3^r\leq3^m.
\end{align*}
Taking log of both sides yields
$$m\ln3\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 $s>2$.

\end{proof}

The next theorem is about the existence of any stable decoder. The proof is in the Appendix since it's quite similar.
 \begin{theorem}\label{thm:min}
 Let $\mathcal{W}$ be $s$-even. Suppose that there exists a linear map $\mathcal{A}$ and a reconstruction map $\Delta$ stable in the sense that
 \begin{equation}\label{equ:stable}
 \|z-\Delta(\mathcal{A} z)\|_\mathcal{W}\leq C\sigma_{\mathcal{W},s}(z),\quad\text{ for any }z\in\mathbb{R}^d,
 \end{equation}
 then there exists $C'>0$ depending only on $C$ such that the number of measurments
 $$m\geq C's\ln(eN/s).$$
 \end{theorem}

In the case of compressed sensing, both theorems can be found in  \cite{FRbook}. For example, Theorem \ref{thm:min2} is reduced to \cite[Theorem 10.11]{FRbook}.




\section{Subgaussian Measurements}\label{sec:sub}
In this section we show that $\mathcal{W}$-sparse vectors can be recovered from few random measurements via \eqref{equ:K}. The arguments presented here are similar to those in \cite{CCL18}, but the results are still worth stating for the general setting

\begin{definition}
	The \emph{Gaussian width} of a set $S\subset\mathbb{R}^d$ is defined as
	\[
	w(S) := \mathbb{E} \sup_{x \in S} \langle g , x \rangle,
	\]
	where $g \sim N(0, I_d)$ is a standard Gaussian random vector.
\end{definition}

\begin{definition} A random vector ${\varphi}\in\mathbb{R}^d$ is called a \emph{subgaussian vector} with parameters $(\alpha, \sigma)$ if it satisfies the following.
	\begin{enumerate}[{(1)}]
		\item It is centered, that is, $\mathbb{E} [{\varphi}]= 0$.
		\item There exists a positive $\alpha$ such that $\mathbb{E}\left[|\langle{\varphi}, z\rangle|\right]\geq\alpha$ for every $z\in\mathbb{S}^{d-1}_2$.
		\item There exists a positive $\sigma$ such that $\Pr\left(|\langle{\varphi},z\rangle|\geq t\right)\leq 2\exp(-\frac{t^2}{2\sigma^2})$ for every $z\in\mathbb{S}^{d-1}_2$.
	\end{enumerate}
\end{definition}

The proof of the following lemma can be found in \cite[Section 6.5]{T14}.

\begin{lemma}\label{lem:Q}
	If ${f} \in \mathbb{R}^d$ is a subgaussian vector with parameters $(\alpha, \sigma)$, then 
	\[
	\Pr\left[|\langle { x}, {f} \rangle|\geq t\right] \geq \frac{(\alpha-t)^2}{4\sigma^2}
	\]	
	for any $0<t<\alpha$ and \({ x} \in \mathbb{S}^{d-1}\).
\end{lemma}

If $\{{\varphi}_i\}_{i=1}^q$ are independent copies of the random distribution ${\varphi} \in \mathbb{R}^d$, then we can define the \emph{mean empirical width} of a set $S \subset \mathbb{R}^d$ as
$$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 $\{\varepsilon_i\}_{i = 1}^m$ are independent random variables taking values uniformly over $\{\pm 1\}$ and are independent from everything else. 

	

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

\begin{lemma}\label{lem:W}
If ${\varphi}\in\mathbb{R}^d$ is subgaussian with  parameters $(\alpha,\sigma)$ and $S$ is any subset of $\mathbb{R}^d$, then
\begin{equation}
W_m(S;{\varphi})\leq Cw(S)
\end{equation}
for some universal constant $C$.
\end{lemma}

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


The mean empirical width appears in the following important result. This theorem was originally stated in \cite{KM15} and coined as  \emph{Mendelson's Small Ball Method} by  Tropp \cite{T14}. This will be a primary tool in obtaining our main estimates.

\begin{theorem}[{\cite[Proposition 5.1]{T14}}, cf. {\cite[Theorem 2.1]{KM15}}]\label{thm:QW}
	Fix a set $S \subset \mathbb{R}^d$. Let ${\varphi}$ be a random vector in $\mathbb{R}^d$ and let $A \in \mathbb{R}^{m \times d}$ have rows $\{a_i^T\}_{i = 1}^m$ that are independent copies of ${\varphi}^T$. Define
	\[
	Q_\xi (S; {\varphi}) := \inf_{{ x} \in S} \Pr\bigg(|\langle { x}, {\varphi} \rangle| \geq \xi \bigg).
	\]

	Then for any $\xi > 0$ and $t > 0$, we have
	\begin{align}\label{equ:msbineq}
	\inf_{{ x} \in S} \| A { x} \|_2 \geq \xi \sqrt{m} Q_{2\xi}(S; {\varphi}) - 2 W_m(S;{\varphi}) - \xi t
	\end{align}
	with probability $\geq 1 - e^{-t^2/2}$.
\end{theorem}


Let $$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 $\inf_{{ x}\in S_\rho}\|\mathcal{A} { x}\|_2>0$ implies $\mathcal{A}$ having the stable $\mathcal{W}$-$\rho$-NSP. We let $A$ be the matrix representation of the map $\mathcal{A}$ under an orthonormal basis

\begin{theorem}
Assume \({\varphi} \in \mathbb{R}^d \) is a subgaussian vector with parameters \((\alpha,\sigma) \). If $A\in \mathbb{R}^{m \times d}$ is a measurement matrix with rows that are independent copies of ${\varphi}^T$ and that the number of measurements satisfies 
	\[
	m \geq \frac{4^{8}\sigma^4}{\alpha^6}C^2w^2( S_\rho),
	\]
	then with probability at least  
	\[
	1 -\exp\left({- m\dfrac{\alpha^4}{64^2\sigma^4}}\right),
	\]
	we have  
	\begin{equation}\label{equ:infPhiD}
	\displaystyle\inf_{{ x}\in S_\rho}\|\mathcal{A} { x}\|_2\geq Cw(S_\rho).
	\end{equation}

\end{theorem}
\begin{proof}
	We first apply Lemma \ref{lem:W} and Theorem \ref{thm:QW},  to obtain the bound
	\begin{equation}\label{equ:QW}
	\inf_{{ x} \in S_\rho} \| A  { x} \|_2 \geq \xi \sqrt{m} Q_{2\xi}(S_\rho; \, {\varphi}) - 2 Cw(S_\rho)- \xi t.
	\end{equation}
	By Lemma \ref{lem:Q}, provided we choose $\xi < \alpha/2$, we obtain 
	\begin{align*}
	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}.
	\end{align*}
	
	
	Placing the bound for $Q_{2\xi}(S_\rho; {\varphi})$ into \eqref{equ:QW} and choosing $\xi=\alpha/4$ gives 
\begin{equation}
\inf_{{ x} \in S_\rho} \| A  { x} \|_2\geq\frac{\alpha^3\sqrt{m}}{4^3\sigma^2}-2 Cw(S_\rho)-\frac{\alpha t}{4}:=a-b-\frac{\alpha t}{4}
\end{equation}


	Picking \(m \) and \(t\) to satisfy \(a \geq 2b\) and \(\alpha t /4 = (a - b)/2 \) gives
	\begin{equation*}
	\inf_{x \in S_\rho} \| A  { x} \|_2 \geq
	a - b - (a -b)/2 = (a - b)/2 \geq b/2 = Cw(S_\rho).
	\end{equation*}
	All that is left is to rewrite these  conditions in terms of \(m\) and \(t\). We have 
	\[
	a \geq 2b 
	\quad \Longleftrightarrow \quad
	\frac{\alpha^3}{4^3\sigma^2}\sqrt{m}\geq 4 Cw(S_\rho)
	\quad \Longleftrightarrow \quad 
	m \geq \frac{4^{8}\sigma^4C^2}{\alpha^6}w^2(S_\rho)
	\]
	and
	\[
	\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.
\end{proof}

As mentioned earlier, \eqref{equ:infPhiD} holds implies $\mathcal{A}$ has the stable null space property, therefore we have the following corollary.
\begin{corollary}\label{cor:sub}
Let $\mathcal{W}$ be splittable. If $A$ is a measurement matrix with rows that are independent copies of a subgaussian vector with parameters $(\alpha,\sigma)$ and $m\geq \frac{4^{8}\sigma^4}{\alpha^6}C^2w^2( S_\rho)$, then $A$ has stable $\mathcal{W}$ null space property with probability at least $1 -\exp\left({- m\dfrac{\alpha^4}{64^2\sigma^4}}\right)$, and therefore \eqref{equ:main} holds.
\end{corollary}

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

\begin{remark}
We may define a set according to the strong null space property as $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 \ref{cor:sub} without requiring $\mathcal{W}$ being splittable. However, computing $w(S_c)$ could pose bigger challenge.
\end{remark}





\section{Recovering Vectors Sparse in a Frame}\label{sec:frame}


This section will focus on the special case  in Example \ref{exa:frame}.
Recall $\mathcal{F}=\{f_i\}_{i=1}^N\subset\mathbb{R}^d$, and $F=[f_1,f_2,\cdots,f_N]$ is the $d\times N$ matrix whose columns are the atoms. 
The linear operator $\mathcal{A}$ will be represented by the matrix $A$. The minimization problem \eqref{equ:K} becomes
\begin{equation}\label{equ:F}\tag{$\text{P}_{\mathcal{F},\epsilon}$}
\hat{z}=\arg\min_{z\in \mathbb{R}^d} \|z\|_{\mathcal{F}} \quad\text{ subject to } \quad \|A z-y\|_2\leq \epsilon.\\
\end{equation}

We will prove that \eqref{equ:F} is the same as the  $\ell_1$-synthesis method~\cite{RSV08, CWW14, CCL18}, which is defined as
\begin{equation}\label{equ:l1s}
\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.
\end{equation}

\begin{lemma} 
The problem \eqref{equ:F} is equivalent to \eqref{equ:l1s}.
\end{lemma}
\begin{proof}
Let $\bar z=F\bar x$ be a solution of \eqref{equ:F} and $\|\bar z\|_\mathcal{F}=\|\bar x\|_1$. For an arbitrary feasible vector $x$ of \eqref{equ:l1s}, $Fx$ is feasible in \eqref{equ:F}, so we have $\|\bar x\|_1=\|\bar z\|_\mathcal{F}\leq\|Fx\|_\mathcal{F}\leq\|x\|_1$. This makes $\bar z$ a solution of \eqref{equ:l1s}.

On the other hand, let $\hat z=F\hat x$ be a solution of \eqref{equ:l1s}. For an arbitrary feasible vector $z$ of \eqref{equ:F}, let $z=Fx$ and $\|z\|_\mathcal{F}=\|x\|_1$. We have that $x$ is feasible in \eqref{equ:l1s}, so $\|\hat z\|_\mathcal{F}\leq\|\hat x\|_1\leq\|x\|_1=\|z\|_\mathcal{F}$, making $\hat z$ a solution of \eqref{equ:F}.
\end{proof}

It is worthwhile to restate Definition \ref{def:wnsp} for the frame case: 
\begin{equation}\label{equ:FNSP}
\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}.
\end{equation}  

A direct consequence of Theorem \ref{thm:iff} is the following:
\begin{corollary}\label{cor:FNSP}
 The matrix $A$ satisfying \eqref{equ:FNSP} is the necessary and sufficient condition for the success recovery of all signals in $\Sigma_{F,s}$ via \eqref{equ:F} or \eqref{equ:l1s} ($\epsilon=0$).
\end{corollary}
Corollary \ref{cor:FNSP} is the same as  \cite[Theorem 4.2]{CWW14} since the dictionary NSP property proposed in \cite[Definition 4.1]{CWW14} also characterizes the $\ell_1$-synthesis method, and therefore is equivalent to \eqref{equ:FNSP} here. We argue that \eqref{equ:FNSP} is a more concise version than \cite[Definition 4.1]{CWW14}. A direct proof of the equivalence of \eqref{equ:FNSP} and \cite[Definition 4.1]{CWW14} is very similar to the proof of Lemma \ref{lem:fsnsp}



We  combine  Theorem \ref{thm:main} and Theorem \ref{thm:RNSP} for the frame case as one corollary.
\begin{corollary}\label{cor:frame}
Suppose $\mathcal{F}$ is $s$-splittable.

(a) If $A$ has the stable $\mathcal{F}$ null space property of order $s$ as 
\begin{equation}
\|z_s\|_\mathcal{F}\leq\rho\|z-z_s\|_\mathcal{F}, \qquad  \text{ for any }z\in\mathcal{N}(A),
\end{equation}
then for any $z_0\in\mathbb{R}^d$ and $y=A z_0+e$ where $\|e\|_2\leq\epsilon$, we have
$$\|\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 $\hat z$ is from \eqref{equ:FNSP}. 



(b) If $A$ has the robust $\mathcal{F}$ null space property of order $s$ as
\begin{equation}
\|z_s\|_\mathcal{F}\leq\rho\|z-z_s\|_\mathcal{F}+\tau \|A z\|_2, \qquad \text{for any }z\in\mathbb{R}^d, 
\end{equation}
then for any $z_0\in\mathbb{R}^d$ and $y=A z_0+e$ where $\|e\|_2\leq\epsilon$, we have
\begin{equation}
\|\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,
\end{equation}
where $\hat z$ is from \eqref{equ:FNSP}. 
\end{corollary}

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

Theorem \ref{thm:snsp} reduces to the corollary:
\begin{corollary}\label{cor:frame2}
If $A$ has the strong $\mathcal{F}$ null space property of order $s$ as
\begin{equation}\label{equ:fsnsp}
\|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},
\end{equation}
then for any $z_0\in\mathbb{R}^d$ and $y=A z_0+e$ where $\|e\|_2\leq\epsilon$, we have
\begin{equation}\label{equ:Fsnsp}
\|\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),
\end{equation}
where $\hat z$ is from \eqref{equ:FNSP}. 
\end{corollary}

A strong null space property for recovery via the $\ell_1$ synthesis method was also proposed in \cite{CWW14}. We recall their definition here: A sensing matrix $A$
is said to have $F$ strong null space property of order $s$ if there exists a positive constant c such that
\begin{equation}\label{equ:fsnsp2}
 \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.
\end{equation}

It is not surprising that these two conditions \eqref{equ:fsnsp} and \eqref{equ:fsnsp2} are equivalent. See Lemma \ref{lem:fsnsp} in the Appendix.

We compare Corollary \ref{cor:frame2} to \cite[Theorem 5.2]{CWW14} as they have the same assumption. In \cite[Theorem 5.2]{CWW14}, the conclusion is that $\|\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 \eqref{equ:Fsnsp} avoids $\nu_F$ which is an improvement. Moreover,
The tail $\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 \eqref{equ:tW}, so Corollary \ref{cor:frame2} implies \cite[Theorem 5.2]{CWW14}, but not necessarily the other way around.

Theorem \ref{thm:min2} reduces to the following corollary.

\begin{corollary}\label{cor:fmin}
  Let $\mathcal{F}$ be $s$-even. If for every $z_0\in\Sigma_{\mathcal{W},s}$ and $y=\mathcal{A} z_0$, we have $\hat z=z_0$ where $\hat z$ is a solution of \eqref{equ:F} (with $\epsilon=0$), then the number of measurments
$$m\geq \frac{1}{8\ln3}s\ln\frac{N}{2s}.$$
\end{corollary}

We have mentioned earlier that $\mathcal{F}$ being $s$-even is not a harsh condition. For example, the matrix $F$ has $s$-NSP will guarantee that. Corollary \ref{cor:fmin} thus provides the minimum number of measurements needed using the $\ell_1$ synthesis method. It was proven in \cite{CCL18} that $O(s\ln(N/s))$ many subgaussian measurements do allow stable and robust recovery through \eqref{equ:F} if $F$ has NSP.

When the atoms are the canonical orthonormal basis of $\mathbb{R}^d$, as shown in Example \ref{exa:cs},
we have $\|v\|_\mathcal{E}=\|v\|_1$ and $C_\mathcal{E}=\sqrt{d}$. 
In this case, Theorem \ref{thm:iff} is a well known result and can be found in literature like \cite{CDD09} and \cite{FRbook}. Theorem \ref{thm:main} reduces to \cite[Theorem 2.4]{ACP11}.
Theorem \ref{thm:RNSP} is similar to \cite[Theorem 5]{F14}. Theorem \ref{thm:min} and Theorem \ref{thm:min2} in this setting can be found in \cite{FPRT10} or \cite{FRbook}.


\section{Low Rank Matrices Recovery}\label{sec:matrix}
This section addresses the case when  $\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 \ref{exa:matrix}. 
$\Sigma_{\mathcal{M},s}=\{\sum_{i=1}^sc_iu_iv_i^T: c_i\in\mathbb{R}, \|u\|_2=\|v\|_2=1\}$ is the set of $n_1\times n_2$ matrices whose rank is at most~$s$. The constant $C_\mathcal{M}=\sqrt{n_1n_2}$. Let $K=\min\{n_1,n_2\}$. 


In this case, Definition \ref{def:wnsp} becomes 
\begin{equation}\label{equ:ranknsp}
\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\|_*,
\end{equation} 
which can be simplified to 
\begin{equation}\label{equ:ranknsp2}
\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).
\end{equation}
The equivalence of \eqref{equ:ranknsp} and \eqref{equ:ranknsp2} is due to Lemma \ref{lem:matrix} in the Appendix. We  have the best $s$-term approximation of any matrix $Z$ to be
$$Z_s=\sum_{i=1}^s\sigma_i(Z)u_iv_i^T,$$
where $Z=\sum_{i=1}^K\sigma_i(Z)u_iv_i^T$ is its singular value decomposition.

Theorem \ref{thm:iff} reduces to the following corollary.
\begin{corollary}\label{cor:matrixiff}
The nuclear norm minimization problem
\begin{equation}\label{equ:nucmin}
\hat{Z}=\arg\min_{Z\in \mathbb{R}^{n_1\times n_2}} \|Z\|_{*} \quad\text{ subject to } \quad \mathcal{A} Z=y.
\end{equation}
is successful at recovering all signals in $\Sigma_{\mathcal{M},s}$ if and only if \eqref{equ:ranknsp2} holds.
\end{corollary}
   
Corollary \ref{cor:matrixiff} can be found in \cite[Theorem 1.1]{RXH08} or \cite[Theorem 15]{KKRT16} as well, but our general tail definition provides a more concise proof than the one in \cite{RXH08}.




The recovery scheme \eqref{equ:K} becomes
\begin{equation}\label{equ:nucmine}
\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.
\end{equation}

We also rewrite Theorem \ref{thm:main}, Theorem \ref{thm:RNSP}, and Theorem \ref{thm:snsp} in this case as one corollary, as $\mathcal{M}$ is splittable.

\begin{corollary}\label{cor:matrix}


(a) If $\mathcal{A}$ has the stable $\mathcal{M}$ null space property of order $s$ as 
\begin{equation}
\|Z_s\|_*\leq\rho\|Z-Z_s\|_*, \qquad  \text{ for any }z\in\mathcal{N}(A),
\end{equation}
then for any $Z_0\in\mathbb{R}^{n_1\times n_2}$ and $Y=\mathcal{A} Z_0+e$ where $\|e\|_F\leq\epsilon$, we have
$$\|\hat Z-Z_0\|_*\leq\frac{2+2\rho}{1-\rho}\|Z-Z_s\|_*+\frac{4\sqrt{n_1n_2}}{(1-\rho)\nu_\mathcal{A}}\epsilon,$$
where $\hat Z$ is from \eqref{equ:nucmine}. 



(b) If $A$ has the robust $\mathcal{M}$ null space property of order $s$ as
\begin{equation}\label{equ:matrixrnsp}
\|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}, 
\end{equation}
then for any $Z_0\in\mathbb{R}^{n_1\times n_2}$ and $Y=\mathcal{A} Z_0+e$ where $\|e\|_F\leq\epsilon$, we have
\begin{equation}\label{equ:matrixb}
\|\hat Z-Z_0\|_*\leq\frac{2(1+\rho)}{1-\rho}\|Z-Z_s\|_*+\frac{4\tau}{1-\rho}\epsilon,
\end{equation}
where $\hat Z$ is from \eqref{equ:nucmine}. 

(c) If $A$ has the strong $\mathcal{M}$ null space property of order $s$ as
\begin{equation}\label{equ:msnsp}
\|Z-Z_s\|_*-\|Z_s\|_*\geq c\|Z\|_F, \qquad  \text{ for any }Z\in\mathcal{N}(A),
\end{equation}
then for any $Z_0\in\mathbb{R}^{n_1\times n_2}$ and $Y=\mathcal{A} Z_0+e$ where $\|e\|_F\leq\epsilon$, we have
\begin{equation}
\|\hat Z-Z_0\|_2\leq\frac{2}{\nu_A}\left(\frac{\sqrt{n_1n_2}}{c}+1\right)\epsilon+\frac{2}{c}\|Z-Z_s\|_*,
\end{equation}
where $\hat Z$ is from \eqref{equ:nucmine}. 
\end{corollary}

Corollary \ref{cor:matrix}(a)(c) are  new results. Note that the strong null space property is simplifed to \eqref{equ:msnsp} due to Lemma \ref{lem:matrix}. Corollary \ref{cor:matrix}(b) is essentially the same as \cite[Theorem 11]{KKRT16}. Compared to \cite[Theorem 11]{KKRT16}, the lack of $\sqrt{s}$ in \eqref{equ:matrixb} is due to the lack of the same term in our robust null space property \eqref{equ:matrixrnsp}.




The special case of Example \ref{exa:p} has a lot of similarities with low rank matrix recovery. We leave it to the readers to modify Corollary \ref{cor:matrix} for recovery results using \eqref{equ:P}.





\section{Appendix}
\begin{lemma}\label{lem:nuc}
 Let $\mathcal{M}=\{uv^T: u\in\mathbb{R}^{n_1}, v\in\mathbb{R}^{n_2}, \|u\|_2=\|v\|_2=1\}$, then $\|X\|_\mathcal{M}=\|X\|_*$
\end{lemma}
\begin{proof}
Let $X=\sum_{i=1}^K \sigma_iu_iv_i^T$ be its singular value decomposition.
Suppose we can rewrite it as $X=\sum s_ip_iq_i^T$ where $\|p_i\|_2=\|q_i\|_2=1, s_i>0$.

$\sum_{i=1}^K\sigma_i=\|X\|_*=\|\sum_{i=1}^m s_iu_iv_i^T\|_*\leq\sum_{i=1}^m\|s_iu_iv_i^T\|_*=\sum_{i=1}^ms_i$.

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

The following lemma is a consequence of \cite[Theorem 7.4.51]{HJ}.
\begin{lemma}\label{lem:sv}
$\sum_{i=1}^K|\sigma_i(X)-\sigma_i(Y)|\leq \sum_{i=1}^K\sigma_i(X-Y)$
\end{lemma}


\begin{lemma}\label{lem:split}
Both $\mathcal{E}$ and $\mathcal{M}$ are splittable.
\end{lemma}
\begin{proof}
For $\mathcal{E}$, given $x,y\in\mathbb{R}^d$, let $T$ be the index set such that $x_s=x_T$. It is clear that $-\|y_T\|_1\geq-\|y_s\|_1$ and $\|y_{T^c}\|_1\geq\|y-y_s\|_1$. Then
\begin{align*}
\|x+y\|_1&=\|x_T+y_T\|_1+\|x_{T^c}+y_{T^c}\|_1\\
&\geq\|x_T\|_1-\|y_T\|_1+\|y_{T^c}\|_1-\|x_{T^c}\|_1\\
&\geq\|x_s\|_1-\|y_s\|_1+\|y-y_s\|_1-\|x-x_s\|_1.
\end{align*}
For $\mathcal{M}$, given $X, Y\in\mathbb{R}^{n_1\times n_2}$
\begin{align*}
\|X+Y\|_*&=\sum_{i=1}^K\sigma_i(X-(-Y))\geq \sum_{i=1}^K|\sigma_i(X)-\sigma_i(Y)|\\
&=\sum_{i=1}^s|\sigma_i(X)-\sigma_i(Y)|+\sum_{i=s+1}^K|\sigma_i(X)-\sigma_i(Y)|\\
&\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)\\
&=\|X_s\|_*-\|Y_s\|_*+\|Y-Y_s\|_*-\|X-X_s\|_*
\end{align*}
\end{proof}


\begin{lemma}\label{lem:snsp}
Let $F=[f_1,f_2,\cdots, f_N]$ has null space property of order $s$ (see \eqref{equ:nsp}), then the atomic set $\mathcal{F}=\{f_1,f_2,\cdots,f_N\}$ is $s$-even.

\end{lemma}
\begin{proof}
Let $z=\sum_{j\in J}c_jf_j=\sum_{i\in[N]}\alpha_if_i$ be two different representations of $z$ in $\mathcal{F}$. In the first representation, we have $|c_j|=1$ and $|J|\leq s$. We have $\sum_{j\in J}(\alpha_j-c_j)f_j+\sum_{j\notin J}\alpha_jf_j=0$. By the null space property of $F$, 
$\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 $\sum_{j\in [N]}|\alpha_j|>\sum_{j\in J}|c_j|$. By definition of atomic norm, we have $\|z\|_\mathcal{F}=\sum_{j\in J}|c_j|$.
\end{proof}




\begin{proof}[Proof of Theorem \ref{thm:min}]
Let $\mathcal{U}$ be a family of subsets of $[N]$ given by Lemma \ref{lem:N} with $t=\lfloor s/2\rfloor$. For each $I\in\mathcal{U}$, define $z_I:=\frac{1}{t}\sum_{i\in I}w_i$. We have $|I|=\lfloor s/2\rfloor$. By definition, $\|z_I\|_\mathcal{W}\leq1$.

For $I\neq J$,  $z_I-z_J=\frac{1}{t}(\sum_{i\in I-J}w_i-\sum_{j\in J-I}w_j)$. Its support $|I-J|+|J-I|=|I|+|J|-2|I\cap J|$, so $s\geq2t\geq|I-J|+|J-I|>t$. By the $s$-NSP of $W$, $\|z_i-z_j\|_W=\frac{1}{t}(|I-J|+|J-I|)>1$.

We claim that $\{A(z_I+\rho B_W), I\in\mathcal{U}\}$ is a disjoint collection of subsets of $A(\mathbb{R}^d)$, where $\rho=\frac{1}{2C+1}$. Otherwise there exist $I\neq J$ and $v, v'\in B_W$ such that $A(z_I+\rho v)=A(z_J+\rho v')$, resulting
\begin{align*}
1&<\|z_I-z_J\|_W=\|z_I+\rho v-\Delta(A(z_I+\rho v))-z_J+\Delta(A(z_J+\rho v'))-\rho v+\rho v'-\rho v'\|_W\\
&\leq\|z_I+\rho v-\Delta(A(z_I+\rho v))\|_W+\|\rho v\|_W+\|\rho v'\|_W+\|\Delta(A(z_J+\rho v'))-(z_J+\rho v')\|_W\\
&\leq C\sigma_{W,s}(z_I+\rho v)+2\rho+C\sigma_{W,s}(z_J+\rho v')\leq C\|\rho v\|_W+2\rho+C\|\rho v'\|_W\leq1.
\end{align*}

It is easy to see that $A(z_I+\rho B_w)\subset (1+\rho)AB_W$ for any $I\in\mathcal{U}$. So
\begin{align}\label{equ:vol}
|\mathcal{U}|\mathrm{vol}(A(\rho(B_W)))\leq \mathrm{vol}((1+\rho)AB_W)
\end{align}
Let $AB_W$ have Hausdorff dimension $r\leq m$, so \eqref{equ:vol} becomes
\begin{align*}
&\left(\frac{N}{4t}\right)^{t/2}\rho^r\mathrm{vol}(AB_W)\leq(1+\rho)^r\mathrm{vol}(AB_W)\\
\Rightarrow & \left(\frac{N}{4t}\right)^{t/2}\leq(1+\frac{1}{\rho})^r\leq(2C+3)^m.
\end{align*}
Taking log of both sides yields
$$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 $s>2$.
\end{proof}

\begin{lemma}\label{lem:fsplit}
The frame $\{f_n=(\cos\frac{\pi (n-1)}{8},\sin\frac{\pi (n-1)}{8})\}_{n=1}^8$ of $\mathbb{R}^2$ is 1-splittable.
\end{lemma}
\begin{proof}
First, we address that if $z=c f_n$ for any $n$, then $\|z\|_\mathcal{F}=|c|$. Due to the symmetry of the frame vectors, we may assume $z=c f_1$. The other different representation of $z$ is $z=\frac{2c}{\sqrt{2}}(f_2+f_8)$. It is obvious that the first representation gives its atomic norm $\|z\|_\mathcal{F}=|c|$.


Second, for any vector $x=a f_1+b f_3$ such that $a\geq b\geq0, $, we have $\|x\|_\mathcal{F}=a+(\sqrt{2}-1)b$. This is because due to symmetry, the other representation of $x$ is $x=af_1+b (\frac{2}{\sqrt{2}}f_2-f_1)=(a-b)f_1+\frac{2b}{\sqrt{2}}f_2$, since $a-b+\frac{2b}{\sqrt{2}}<a+b$, we have $\|x\|_\mathcal{F}=a+(\sqrt{2}-1)b$.

Third, let $x=\gamma(\cos\alpha f_1+\sin\alpha f_3)$ where $\gamma>0,\alpha\in[0,\pi/4)$. Since $f_3=\frac{2}{\sqrt{2}}f_2-f_1$, the other representation of $x$ is $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 $x$, that is $\gamma\cos\alpha f_1, \gamma\sin\alpha f_3, \gamma(\cos\alpha-\sin\alpha)f_1$, or $\frac{2\gamma}{\sqrt{2}}\sin\alpha f_2$. The corresponding tails are $\gamma\sin\alpha f_3, \gamma\cos\alpha f_1, \frac{2\gamma}{\sqrt{2}}\sin\alpha f_2$, and $\gamma(\cos\alpha-\sin\alpha)f_1$. If $\alpha\in[0,\arctan\frac{1}{2})$, this makes $\gamma\sin\alpha f_3$ has the smallest atomic norm, so $x_1=\gamma\cos\alpha f_1$ and $\|x-x_1\|_\mathcal{F}=\gamma\sin\alpha$. If $\alpha\in[\arctan\frac{1}{2},\pi/4)$, then $x_1=\sqrt{2}\gamma\sin\alpha f_2, \|x-x_1\|_\mathcal{F}=\gamma(\cos\alpha-\sin\alpha)$.

For arbitrary  $x=\gamma(\cos\alpha f_1+\sin\alpha f_3)$ and $y=\rho(\cos\beta f_1+\sin\beta f_3)$. We may assume without loss of generality that $\gamma=1, \alpha\in[0,\pi/4)$ and $\beta\in[0,\pi/4)$. According to fact 2, $\|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: $\alpha\in[0,\arctan\frac{1}{2}), \beta\in[0,\arctan\frac{1}{2})$. According to the third fact, we have 
$x_1=\cos\alpha f_1, \|x-x_1\|_\mathcal{F}=\sin\alpha, y_1=\rho\cos\beta f_1$ and $\|y-y_1\|_\mathcal{F}=\rho\sin\beta$. So
\begin{equation}\label{equ:a1}
\|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,
\end{equation}
which clearly is less than $\|x+y\|_\mathcal{F}$.

Case 2: $\alpha\in[0,\arctan\frac{1}{2}), \beta\in[\arctan\frac{1}{2},\pi/4)$. According to the third fact, we have 
$x_1=\cos\alpha f_1, \|x-x_1\|_\mathcal{F}=\sin\alpha, y_1=\sqrt{2}\rho\sin\beta f_2$ and $\|y-y_1\|_\mathcal{F}=\rho(\cos\beta-\sin\beta)$. So
\begin{equation}\label{equ:a2}
\|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,
\end{equation}
which clearly is less than $\|x+y\|_\mathcal{F}$.

Case 3: $\alpha\in[\arctan\frac{1}{2},\pi/4), \beta\in[\arctan\frac{1}{2},\pi/4)$. According to the third fact, we have 
\begin{equation}\label{equ:a3}
\|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),
\end{equation}
which  is less than $\|x+y\|_\mathcal{F}$.
\end{proof}

\begin{lemma}\label{lem:fsnsp}
The two conditions \eqref{equ:fsnsp} and \eqref{equ:fsnsp2} are equivalent.
\end{lemma}
\begin{proof}
(\eqref{equ:fsnsp2}$\Longrightarrow$\eqref{equ:fsnsp}) For any $z\in\mathcal{N}(A)$ and any $v\in\Sigma_{F,s}$, by \eqref{equ:z-v}, let $\|z-v\|_\mathcal{F}=\|x-u_1\|_1$ where $z=Fx, v=Fu_1=Fu_2$ where $\|u_2\|_0\leq s$. Let $T$ be the support of $u_2$. The vector $y=x-u_1+u_2\in\mathcal{N}(AF)$. By assumption, there exists $u\in\mathcal{N}(F)$ such that $\|y_{T^c}\|_1-\|y_T+u\|_1\geq c\|Fy\|_2=c\|z\|_2$. Now we have
\begin{align*}
\|z-v\|_\mathcal{F}-\|v\|_\mathcal{F}&\geq\|x-u_1\|_1-\|u_2+u\|_1=\|y-u_2\|_1-\|u_2+u\|_1\\
&=\|y_T-u_2\|_1+\|y_{T^c}\|_1-\|u_2+u\|_1\\
&\geq\|y_T-u_2\|_1+\|y_T+u\|_1+c\|z\|_2-\|u_2+u\|_1\geq c\|z\|_2.
\end{align*}

(\eqref{equ:fsnsp}$\Longrightarrow$\eqref{equ:fsnsp2})
 For any $x\in\mathcal{N}(AF)$ and any $|T|\leq s$,  let $v=Fx_T\in\Sigma_{F,s}$ and $\|v\|_\mathcal{F}=\|y\|_1$ where $v=Fy$. Since $z=Fx\in\mathcal{N}(A)$, by \eqref{equ:fsnsp}, $\|z-v\|_\mathcal{F}-\|v\|_\mathcal{F}\geq c\|z\|_2$.
 
 Clearly $y-x_T\in\mathcal{N}(F)$, and
$\|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$.
\end{proof}



\begin{lemma}\label{lem:matrix}
For any $Z\in\mathbb{R}^{n_1\times n_2}$, 
$$\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).$$
\end{lemma}
\begin{proof}
Let $\sigma_i$ be the singular values of $Z$.

$\|Z-V\|_*-\|V\|_*\stackrel{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 $\min_{c\in\mathbb{R}}(|\sigma-c|-c)=-\sigma$, therefore we have
$$\|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.$$
\end{proof}

