\section{Introduction}
\label{intro}

Continual learning is the ability of a model to learn continuously from a stream of data, building on what was previously learned and retaining previously learned skills without the need for retraining. A major obstacle for neural networks to learn continually is the catastrophic forgetting problem: the abrupt drop in performance on previous tasks upon learning new ones. Modern neural networks are typically trained to greedily minimize a loss objective on a training set, and without any regularization, the model's performance on a previously trained task may degrade. Techniques for mitigating catastrophic forgetting fall under three main groups: generative replay, parameter isolation, and regularization methods \cite{delange2021continual}. Generally, the goal of regularization methods is to determine important parameters from previous tasks and constrain them so that they do not get modified too much while training subsequent tasks.  Two common regularization methods are Synaptic Intelligence (SI) \cite{zenke2017continual} and Elastic Weight Consolidation (EWC) \cite{kirkpatrick2017overcoming}.   See Appendix \ref{cl-techniques} for a detailed description of them.

It is well-known that strong generalization performance for neural networks is typically obtained in the overparameterized regime, where the number of learnable parameters is greater than the number of training examples. Work on overparameterized machine learning has led to research on the so-called double descent phenomenon, where test error improves as model complexity increases beyond the level needed to fit the training data,
 outperforming all underparameterized versions of the model \cite{belkin2019reconciling}. One of the first observations of this behavior in modern neural networks was in extremely wide ResNet18 models that generalize better than their underparameterized counterparts on CIFAR-10 despite fitting to label noise \cite{nakkiran2021deep}. This model-wise double descent phenomenon has been demonstrated analytically in a variety of machine learning models \cite{hastie2019surprises, belkin2020two, bartlett2020benign}, including some as simple as linear regression.  Such linear models will be the basis of theoretical analysis in the present paper.

While investigating the relationship of overparameterization with catastrophic forgetting, we  made an interesting experimental observation. We considered 10 permuted-MNIST tasks, where each task has training data given by random permutations of the original MNIST images \cite{lecun1998mnist}.   We trained  2-layer multilayer perceptrons (MLPs) with a variety of layer widths given by $[400w, 400w]$, where $w = 1, 3, 5, 7, 9$, using vanilla stochastic gradient descent and the continual learning algorithms, SI and EWC.  We compared the test accuracy on all seen tasks.  As expected, and as shown in Figure \ref{nn-experiments}, average accuracy with SGD drops significantly after learning multiple tasks, and that drop is mitigated by using SI or EWC.  Interestingly, we observe that a significant fraction of the accuracy gain achieved by SI or EWC can be obtained with vanilla SGD by simply overparameterizing the model.   This can be seen by comparing the $w=1$ and $w=9$ curves with SGD to the curves with SI and EWC.  See Appendix \ref{mnist-appendix} for more details on the experiments.

\begin{figure}
\begin{center}
    \includegraphics[scale=0.42]{images/cf-plot-si2.png}
    \includegraphics[scale=0.42]{images/cf-plot-ewc2.png}
    \caption{Results of permuted MNIST experiment. Red curves denote performance of SI, yellow curves denote performance of EWC, blue curves denote performance of Vanilla SGD. Bolder saturation of lines corresponds to larger width parameters (more overparameterization). Specific hyperparameters are reported in Appendix \ref{mnist-appendix}. Curves for $w=7,9$ for EWC are omitted due to computational constraints on Fisher matrix estimates.}
    \label{nn-experiments}
\end{center}
\end{figure}

The goal of the present paper is to analytically illustrate the effect overparameterization can have on catastrophic forgetting. As with the illustrations of double descent in \cite{hastie2019surprises, belkin2020two, bartlett2020benign}, we choose to study the effect with a linear regression problem for simplicity and mathematical convenience.
While the experiments above study the case of tasks related by random permutations, our analysis will instead study the qualitatively similar case where two tasks are related by a random orthogonal transformation, which results in simpler mathematical analysis, as we discuss in Section \ref{discussion}. The relation given by the random orthogonal transformation gives two data feature spaces corresponding to each task that are approximately but not exactly orthogonal. We construct two tasks, A and B.  Let task A be defined by data matrix $X_A \in \mathbb{R}^{n \times p}$, with rows being $p$ noisy random projections of some low-dimensional latent features, and responses $y\in \mathbb{R}^n$ that are noiseless and linear in the latent features.
Let $O$ be a random $p \times p$ orthogonal matrix. Then task B is defined by data $X_B=X_AO^\top$ and the same responses $y$. Learning tasks A and B involve estimating a $\beta \in \mathbb{R}^p$  for the predictor $f_\beta: x \mapsto x^\top \beta$ to fit the data $(X_A, y)$ and $(X_B, y)$, respectively.

We analyze the increase in statistical risk on task A between an estimator trained on task $A$ by minimizing square loss, with initialization at zero, and one sequentially trained on task $A$ and then task $B$ with no explicit regularization. Let $R(f_{\beta})$ be the risk on task A of an estimator $f$ with parameters $\beta$. Let $\hat{\beta}_A$ be the parameters of the model that is trained on task A. Let $\hat{\beta}_{BA}$ be the parameters of a model that is initialized at $\hat{\beta}_A$ and then trained on task B. Our main result is that if there are more training examples than the intrinsic (latent) dimensionality of the data and if there is not too much noise in the observed features, then

\begin{align}
    R(f_{\hat{\beta}_{BA}})-R(f_{\hat{\beta}_A}) \lesssim \sqrt{\frac{n}{p}}
\end{align}

with high probability. The result asserts that under our linear model, the extent of catastrophic forgetting is arbitrarily small if the overparameterization ratio, $p/n$, is sufficiently large.  We thus see an analytical illustration that catastrophic forgetting can be ameliorated by overparametization in the case of a suitable linear model.
The full theorem is stated in Section \ref{theorem} and its  proof is provided in Appendix \ref{lemmas}.

The contributions of this paper are:
\begin{itemize}
    \item We empirically observe that overparameterization can account for a majority of the performance drop due to catastrophic forgetting in a permuted image task using a multi-layer perceptron.
    \item We provide a  linear regression problem that exhibits a corresponding effect for overparameterization and continual learning.

    \item We establish a non-asymptotic bound on the performance drop of this linear model in an orthogonal transformation task setting using results from random matrix theory.  This result provides a formal illustration that continual learning can in some cases be ameliorated by overparameterization.
\end{itemize}

\section{Analysis of Catastrophic Forgetting in a Linear Model} \label{models}

In this section, we present a latent space model for linear regression that we will analyze in order to illustrate that overparameterization can ameliorate catastrophic forgetting.  Our single task model is the latent space model of \cite{hastie2019surprises} without label noise. Then, we present the analogy between this linear model and neural networks.  Next, we empirically demonstrate that under this model, overparameterization ameliorates catastrophic forgetting.  Finally, we present a theorem that establishes that observation with high probability.

\subsection{Latent Space Models for Two Linear Regression tasks} \label{lsm}

Let $\mathcal{Z} = \mathbb{R}^d$, which we call the latent feature space. Consider data for regression generated by a noiseless linear response to standard Gaussian latent features. That is, for some $\theta \in \mathbb{R}^d$, let an example be given by
\begin{align}
    z &\sim \mathcal{N}(0, I_d), \label{data-start} \\
    y &= z^\top\theta.
\end{align}

Let $\mathcal{X} = \mathbb{R}^p$, which we call the observed feature space. We consider the case where, for each example, we have access only to $p$ observed features, given by noisy random projections of the latent features:

\begin{align}
    x &= Wz + u \label{data-end}
\end{align}

where $W \in \mathbb{R}^{p \times d}$ and $u \sim \mathcal{N}(0, I_p)$.  We could take $W$  to have i.i.d. $\mathcal{N}(0, \gamma)$ entries, but for mathematical convenience, we will instead study the idealization in which $W$ has columns that form a scaled orthonormal basis of a random $d$-dimensional subspace of $\mathbb{R}^p$. Namely, $W^\top W = p\gamma I_d$.  For large $p$, this idealization is approximately satisfied under the above Gaussian model for $W$.

We consider two tasks, $A$ and $B$, both with $n$ examples. Task $A$ has data $(X_A, y) \in \mathbb{R}^{n \times p} \times \mathbb{R}^n$ where each of the $n$ rows of $X_A$ and entries of $y$ are sampled independently by (\ref{data-start}) - (\ref{data-end}). Let $O$ be a random $p \times p$ orthogonal matrix. Task B has data $(X_B, y)$ where $X_B = X_A O^\top$.

We study estimators that are linear in the observed features $x$:

\begin{align}
    f_{\hat{\beta}} : x \mapsto x^\top\hat{\beta},
\end{align}

and we will sometimes refer to the parameters $\hat{\beta}$ as the estimator.
We estimate the parameters of this model by gradient descent with a square loss. We are interested in the case of $d < n < p$. As $n < p$, the solution to this problem depends on initialization and solves the following optimization problem:

\begin{align}
    \arg\min_{\hat{\beta}} \frac{1}{2}\|\hat{\beta} - \beta_0\|^2 \text{ s.t. } y = X\hat{\beta}, \label{opt-prob}
\end{align}

where $\beta_0$ is the initialization, and $X$ is either $X_A$ or $X_B$, depending on the task being solved. To study the sequential training of tasks A and B, we define the following estimators:

\begin{itemize}
\item $\hat{\beta}_A$ is the solution to task $A$ when initialized at $0$,
\item $\hat{\beta}_B$ is the solution to task $B$ when initialized at $0$,
\item $\hat{\beta}_{BA}$ is the solution to task $B$ when initialized at $\hat{\beta}_A$.
\end{itemize}

These parameters are found by solving the following optimization problems:

\begin{align}
    \hat{\beta}_A &= \arg\min_{\hat{\beta}} \frac{1}{2}\|\hat{\beta}\|^2 \text{ s.t. } y = X_A\hat{\beta}, \\
    \hat{\beta}_B &= \arg\min_{\hat{\beta}} \frac{1}{2}\|\hat{\beta}\|^2 \text{ s.t. } y = X_B\hat{\beta}, \\
    \hat{\beta}_{BA} &= \arg\min_{\hat{\beta}} \frac{1}{2}\|\hat{\beta} - \hat{\beta}_A\|^2 \text{ s.t. } y = X_B\hat{\beta}.
\end{align}

The optimization problem in (\ref{opt-prob}) has the following closed form solution when $X$ has rank $n$:

\begin{align}
    \hat{\beta} &=\beta_0 + X^\top(XX^\top)^{-1}y-X^\top(XX^\top)^{-1}X\beta_0 \\
    &=\beta_0 + X^\top(XX^\top)^{-1}y-\mathcal{P}_{X^\top}\beta_0,
\end{align}

where $\mathcal{P}_{X^\top}$ is the orthogonal projector onto the range of $X^\top$. As $n<p$,  $X_A$ and $X_B$ have rank $n$ with probability $1$, and this gives the following closed forms for $\hat{\beta}_A, \hat{\beta}_B, \hat{\beta}_{BA}$:

\begin{align}
    \hat{\beta}_A &= X_A^\top(X_AX_A^\top)^{-1}y, \\
    \hat{\beta}_B &= X_B^\top(X_BX_B^\top)^{-1}y, \\
    \hat{\beta}_{BA} &= \hat{\beta}_A + \hat{\beta}_B - \mathcal{P}_{X_B^\top}\hat{\beta}_A. \label{model-end}
\end{align}

We evaluate these estimators on task A. The risk on task A of an estimator $f$ with parameters $\hat{\beta}$ is given by

\begin{align}
    R(f_{\hat{\beta}}) = \sigma^2 + (\hat{\beta}-\beta)^\top\Sigma(\hat{\beta}-\beta) \label{risk-start}
\end{align}

where
\begin{align}
    \Sigma &= WW^\top + I_p \\
    \beta &= (I+WW^\top)^{-1}W\theta \\
    \sigma^2 &= \theta^\top(W^\top W + I_d)^{-1}\theta \label{risk-end}
\end{align}

See Appendix \ref{risk} for the derivation of (\ref{risk-start})--(\ref{risk-end}). It follows from showing that the latent space model described above is equivalent to an anisotropic regression model where $X_A$ has i.i.d. rows ${X_A}_i \sim \mathcal{N}(0, \Sigma)$ and labels $y = X_A\beta+\epsilon$ where $\epsilon \sim \mathcal{N}(0, \sigma^2I_n)$.

\begin{figure}
\begin{center}
    \includegraphics[scale=0.06]{images/final-proj-fig-6.jpg}
    \caption{The solid black line depicts the span of $W$. The true parameters corresponding to tasks A and B are given by $\beta \in W$ and $O\beta$.  The gray lines depict the set of solutions to $X_A \beta = y$ and $X_B \beta = y$.  The estimators $\hat{\beta}_A, \hat{\beta}_B, \hat{\beta}_{BA}$ are given by orthogonal projections of an initialization on the respective consistent solutions.  The red and blue ellipses depict lines of constant risk for tasks A and B, respectively.

    }
    \label{manifold-fig}
\end{center}
\end{figure}

We aim to bound $R(f_{\hat{\beta}_{BA}})$ relative to $R(f_{\hat{\beta}_A})$. Figure \ref{manifold-fig} illustrates the estimators $\hat{\beta}_A, \hat{\beta}_B, \hat{\beta}_{BA}$ and curves of constant risk.  As depicted, if $p$ is large enough, $\hat{\beta}_{BA}$ has low risk on Task A and Task B simultaneously.

\subsection{Analogy of Linear Model to Neural Networks}

The linear model we study is intended to be a mathematically tractable idealization of a neural network, and it is meant to analytically illustrate that overparameteriation can ameliorate catastrophic forgetting. The analogy of this linear model and neural network training on image data is as follows:

Natural images in a neural network's training distribution can be (approximately) modeled as being on a nonlinear manifold and having a low-dimensional latent representation. Instead of observing the latent representation of an image, the neural network only sees a high-dimensional representation either directly in pixel space or perhaps in a representation computed from pixel space. Either of these representations contain noise in the features used for prediction. Responses can be approximated by a neural network.

In our linear model, the low-dimensional  representation of an input image is in a $d$-dimensional latent feature linear space.  The responses are linear in the latent features. We assume the response is noiseless for the sake of simplicity, though our results could be extended to the noisy case. In our linear model, predictions are made off of a $p$-dimensional model given by noisy random projections of the latent features.
We constrain $W$ to have orthonormal columns which is a mathematical idealization of Gaussian measurements. We study two tasks with the same responses like in the permutation task setup, but for mathematical convenience we study tasks that are related by a random orthogonal transformation instead.

\subsection{Numerical Experiment} \label{num-exp}

Before we establish our theoretical result about the system described in Section \ref{lsm}, we provide empirical evidence that the latent space linear regression model above exhibits the phenomenon that overparameterization can ameliorate catastrophic forgetting.  Specifically, we provide empirical evidence that $R(f_{\hat{\beta}_{BA}}) - R(f_{\hat{\beta}_A})$ decreases with $p$.

Let $d=20$, $n=100, \gamma=1$, $\beta_0 = \vec{0}$, and $\theta \sim \mathcal{N}(0, I_d)$. We plot $R(f_{\hat{\beta}_{BA}})$, $R(f_{\hat{\beta}_A})$, $R(f_{\beta_0})$ as a function of $p \in (n, 2000)$ averaged over 100 samplings of $W, X_A, O, u$.

\begin{figure}[h]
\begin{center}
    \includegraphics[scale=0.5]{images/ooplot2.png}
    \caption{Risk as a function of model complexity $p$ for model (\ref{data-start})--(\ref{model-end}).  The dashed line depics the null risk, corresponding to the zero estimator.  Note the log scale on the vertical axis.  Result of simulated numerical experiment for random orthogonal transformation tasks. Dotted black line denotes risk of null estimator, blue line denotes risk of estimator trained on task A, orange line denotes risk of estimator trained on task A then task B.}
    \label{sim-experiment}
\end{center}
\end{figure}

\noindent
Figure \ref{sim-experiment} shows the results of the experiment.
We first note that both $\hat{\beta}_A$ and $\hat{\beta}_{BA}$ outperform the null risk, given by $\beta=0$.   The null risk, $R(f_{\beta_0})$, defines a baseline that any reasonable model must beat.
We also observe that $R(f_{\hat{\beta}_A})$ and $R(f_{\hat{\beta}_{BA}})$ are  decreasing with $p$ in the overparameterized regime, and that the difference between these risks appears to decrease for increasing $p$. Note the log-scale of the vertical-axis. This provides evidence that catastrophic forgetting is alleviated in the overparameterized regime in our two-task learning setup.

\subsection{Main Result} \label{theorem}

Our main result is an upper bound on the performance drop, defined as $R(f_{\hat{\beta}_A})-R(f_{\hat{\beta}_{BA}})$, for the two-task latent space linear regression model described above and inspired by the double descent literature.  As described in Section \ref{lsm}, we consider (\ref{data-start})--(\ref{model-end}), where $W$ satisfies the following assumption.

\begin{assumption} \label{body-assumption}
    All non-zero singular values of $W$ are equal. Namely, $W^\top W = p\gamma I_d$.
\end{assumption}

We begin with a proposition that defines the unlearned baseline for the problem.

\begin{proposition} \label{proposition}
    Fix $\theta \in \mathbb{R}^d$. Let $W \in \mathbb{R}^{p \times d}$ satisfy Assumption \ref{body-assumption}. Then

    \begin{align}
        R(f_{0}) = \|\theta\|^2.
    \end{align}
\end{proposition}

This risk calculation agrees with the numerical experiment in Section \ref{num-exp} where $\|\theta\|^2 \approx d = 20$. The result is formally stated and proven in Lemma \ref{null-risk}. For our main result, we prove that if the number of examples exceeds the problem's latent dimensionality, if the number of parameters is sufficiently large relative to the number of examples and relative to the noise level of the observable features, then with high probability, the performance drop is small.

\begin{theorem} \label{main}
    Fix $\theta \in \mathbb{R}^d$. Let tasks $A,B$ be given by (\ref{data-start})--(\ref{model-end}). Let $W \in \mathbb{R}^{p \times d}$ satisfy Assumption \ref{body-assumption} and $n \ge d, p \ge max(17n, 1/\gamma)$. Then there exists constant $c>0$ such that with probability at least $1-10e^{-cd}$, the following holds:

    \begin{align}
    R(f_{\hat{\beta}_{BA}}) - R(f_{\hat{\beta}_A}) \le \left(66\sqrt\frac{n}{p} + \frac{12}{p\gamma}\right)\|\theta\|^2
\end{align}

\end{theorem}

Theorem \ref{main} provides an upper bound on the amount of risk gained on task A after subsequential training on task B given by two terms. The first term provides dependence on the overparameterization ratio $p/n$ and decreases as overparameterization becomes more extreme. The second term is given by the signal to noise ratio of the noisy features. This term dominates only when $\gamma \ll 1/\sqrt{np}$. Based on the theorem, we observe that the overparameterization needs only to be linear in $n$ to achieve a negligible performance drop in unregularized sequential task training compared to the baseline of $\|\theta\|^2$ in Proposition \ref{proposition}. This shows that catastrophic forgetting is ameliorated in the overparameterized regime. This result is formally stated in Lemma \ref{perf-drop}. A formal proof and supporting lemmas are supplied in Appendix \ref{lemmas}. We provide a proof sketch here to outline the techniques used.

\subsection{Proof Sketch of Theorem \ref{main}}

For readability, we write $X_A$ as $A$ and $X_B$ as $B$.  As shown in Appendix \ref{risk}, the latent space model described above is equivalent to an anisotropic regression model where $A$ has i.i.d. rows $A_i \sim \mathcal{N}(0, \Sigma)$ and labels $y = A\beta+\epsilon$ where $\epsilon \sim \mathcal{N}(0, \sigma^2I_n)$.

Performance drop is given by

\begin{align}
    R(f_{\hat{\beta}_{BA}}) - R(f_{\hat{\beta}_A}) &= (\hat{\beta}_{BA}-\beta)^\top \Sigma (\hat{\beta}_{BA}-\beta) \notag - (\hat{\beta}_A-\beta)^\top \Sigma (\hat{\beta}_A-\beta).
\end{align}

After substituting the closed form solutions for $\hat{\beta}_A, \hat{\beta}_{BA}$, distributing terms, and applying simple Cauchy-Schwarz and triangle inequalities, we get the following bound:

\begin{align}
    R(f_{\hat{\beta}_{BA}}) - R(f_{\hat{\beta}_A}) &\le 8\frac{p\gamma\sqrt{p\gamma}}{p\gamma+1} \|\theta\|\|\mathcal{P}_W\hat{\beta}_B\| + 14\sqrt{p\gamma} \|\theta\|\|\mathcal{P}_{B^\top} \hat{\beta}_A\| + 12\frac{p\gamma}{(p\gamma+1)^2} \|\theta\|^2 \\
    &= I + II + III
\end{align}

Lemmas \ref{b-helper}, \ref{ba-helper} establish results for orthogonal transformations to help bound $\|\mathcal{P}_W\hat{\beta}_B\|, \|\mathcal{P}_{B^\top} \hat{\beta}_A\|$ respectively. $\mathcal{P}_W$ is a projection onto a $d$-dimensional space which scales the norm in $I$ by $d/p$. $\mathcal{P}_{B^\top}$ is a projection onto an $n$-dimensional space which scales the norm in $II$ by $n/p$. As $d \le n$ by assumption, $II$ dominates $I$ in the final bound. Using these results and simplifying gives the following bound with probability at least $1-10e^{-cd}$ for constant $c>0$:

\begin{align}
    I+II \le 66\sqrt{\frac{n}{p}}\|\theta\|^2
\end{align}

We directly obtain

\begin{align}
    III \le \frac{12}{p\gamma}\|\theta\|^2
\end{align}

Combining these bounds completes the proof.

\section{Discussion} \label{discussion}

Overparameterization is a necessity for continual learning so that there can exist an infinity of potential optima for each task \cite{kirkpatrick2017overcoming}. This makes it likely that there exists an optimum for some task B that is close to the solutions of some task A. We provide experimental evidence that overparameterization can provide additional benefits in combatting catastrophic forgetting for neural networks solving permutation tasks. We use a linear model with clear analogies to neural networks in order to study this behavior theoretically. In our analysis of the linear model in the overparameterized regime, non-asymptotic matrix estimates and results for orthogonal transformations provide bounds on the performance drop. Our main result shows that, under our model, catastrophic forgetting is ameliorated for sufficiently large overparameterization. For the linear setting we study, the behavior we observe can be explained geometrically: overparameterization causes the random orthogonal transformation tasks to live in approximately orthogonal subspaces, so training on subsequent tasks does not interrupt performance on learned tasks.

We view the present work as helping to establish initial results for continual learning theory. Before the field can rigorously understand machine learning algorithms in practice, the behavior of simple systems should be well understood. In particular, the behavior of linear systems with only vanilla SGD is the most natural initial result. Our work remarks that future theory should establish that continual learning algorithms beat not only a moderately parameterized baseline, but also the performance of extremely overparameterized models.

First we address the concern for using permutation tasks as realistic benchmarks for continual learning methods. Researchers believe that permutation tasks only provide a best-case for real world scenarios \cite{farquhar2018towards}. Also, on a number of image classification datasets, MLPs do not experience forgetting when only two permutation tasks are being learned \cite{pfulb2019comprehensive}. Our experiments confirm this effect while also showing that overparameterization mitigates the observable forgetting on 10 task permuted MNIST. Despite these critiques, we use permutation tasks as a launching point for theory because each task is of the same `difficulty' and is amenable to mathematical analysis.

Next we discuss our choice to study the problem with a linear model. Linear regression is the simplest setting, for which we know, that exhibits double descent.  The consensus of several works that study double descent in linear models is that the risk of a model is monotonically decreasing in the overparameterized regime with respect to number of parameters only if the data has low effective dimension and high ambient dimension compared to the number of training samples \cite{dar2021farewell, bartlett2020benign, hastie2019surprises}. In order to have a model that has monotonically decreasing performance drop for a particular continual learning problem, it is a necessity that it exhibits monotonically decreasing risk on a single task. Additionally in recent work, connections have been made between neural networks and linear models using the so-called neural tangent kernel (NTK) phenomenon \cite{jacot2018neural}. The parameterization of a neural network can be so large that training only changes its parameters slightly from its initialization, resulting in functions that can be accurately approximated linearly. Hence it is reasonable that the analysis of linear models can explain the behavior of neural networks.

We now remark at a technical level two choices in our analysis. The first is why we studied the case of random orthogonal transformation tasks instead of permutation tasks. The empirical performance between orthogonal and permutation tasks is similar; they both create tasks that are equally 'difficult' for an MLP to learn, which spares us from needing to quantify problem difficulty. Appendix \ref{perm-exp} provides evidence that permutation and orthogonal transformation tasks have the same difficulty in the linear setting. Also, the mathematical analysis is easier when studying orthogonal transformation tasks. With random orthogonal transformations, any subspace gets mapped to a random subspace, for which the values of coefficients are typically well spread out. With random permutations, some subspaces (e.g. those aligned with the standard basis elements) do not exhibit the same spreading effect, making the technical analysis more involved. Secondly, we do not present a bound on $R(f_{\hat{\beta}_A})$, though it is expected to approach zero for large $p$, as suggested by Figure \ref{sim-experiment}. Whether or not this risk goes to 0 in $p$, the performance drop goes to 0 in $p$ while the null estimator remains with constant risk. So the regression problem is being solved arbitrarily well for sufficiently large $p$.

With the growing popularity of continual learning, much of recent work is focused on developing new algorithms to mitigate catastrophic forgetting \cite{kirkpatrick2017overcoming, zenke2017continual, shin2017continual, li2017learning}. Only a few papers study the problem theoretically \cite{knoblauch2020optimal, bennani2020generalisation, doan2021theoretical, heckel2022provable, benzing2022unifying}. \cite{knoblauch2020optimal} uses set theory to prove that, in general, continual learning problems are NP-hard, explaining why generative replay methods perform so well. \cite{bennani2020generalisation} uses the NTK regime to prove generalisation guarantees for an existing continual learning method. \cite{doan2021theoretical} uses an NTK overlap matrix to define a notion of task similarity and show that catastrophic forgetting is more severe when tasks have high similarity. \cite{heckel2022provable} studies a family of continual learning methods that uses approximations of the Hessian to determine parameter importance, presenting scenarios where continual learning provably fails and succeeds. \cite{benzing2022unifying} shows that a number of regularization techniques that seem to be derived from differing philosophies actually all study a variation of the Fisher information matrix. While prior work has presented generalization bounds for existing continual learning techniques, our work illustrates the relationship between overparameterization and generalization.

A natural next step is to study the regimes in which catastrophic forgetting is most problematic. This includes the setting where tasks do not have a nearly orthogonal relationship but also when data does not necessarily live on a low-dimensional manifold. We are also interested in understanding how the ideas of this paper generalize to other continual learning benchmarks and for more general neural network architectures. Prior work found experimental evidence that catastrophic forgetting is most severe not when tasks are very dissimilar but when they only have an intermediate level of similarity \cite{ramasesh2020anatomy}. Using orthogonality as a proxy for task similarity, this agrees with our work that shows that nearly orthogonal tasks are less prone to catastrophic forgetting. An interesting future work would be to formalize this notion of task similarity for our model. Moving forward, one goal of theory in continual learning is to be able to analytically compare algorithms. Our work provides a foundation of understanding this behavior in a simple linear regression setting. In order to push this work forward, either non-linear models need to be studied or tasks that are related by something more complex than permutations.


\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}