\section{Introduction} \label{sec:Intro}
Let
$\mathbf{x}_0 \in \mathbb{R}^{m}$ denote a sparse solution of an underdetermined system of linear equations
\begin{equation} \label{USLE}
\mathbf{b} = \mathbf{A} \mathbf{x}
\end{equation}
in which
$\mathbf{b} \in \mathbb{R}^{n}$ and
$\mathbf{A} \in \mathbb{R}^{n \times m}, m > n$. Suppose that $\| \mathbf{x}_0 \|_0 = k$, where $\| \mathbf{x}_0 \|_0$ designates the number of nonzero components or the $\ell_0$ norm of $\mathbf{x}_0$. Further, let $\spark(\mathbf{A})$ represent the spark of $\mathbf{A}$, defined as the minimum number of columns of $\mathbf{A}$ which are linearly dependent, and let $\delta_{2k}(\mathbf{A})$ denote the restricted isometry constant of order $2k$ for the matrix $\mathbf{A}$ \cite{Cand08}. It is well known that if $k < \spark(\mathbf{A}) / 2$ or $\delta_{2k}(\mathbf{A}) < 1$, then $\mathbf{x}_0$ is the unique sparsest solution of the above set of equations \cite{Cand08,DonoE03}.

When the sparsest solution of \eqref{USLE} is sought, one needs to solve
\begin{equation} \label{l0min}
\min_{\mathbf{x}} \|\mathbf{x}\|_0  \quad \text{subject to} \quad \mathbf{A}\mathbf{x}=\mathbf{b}
\end{equation}
However, the above program is generally NP-hard \cite{Nata95} and becomes very intractable when the dimensions of the problem increase. Since finding the sparse solution of \eqref{USLE} has many applications in various fields of science and engineering (cf. \cite{CandW08} for a comprehensive list of applications), many practical alternatives for \eqref{l0min} have been proposed \cite{CandRT06,Trop04,MohiBJ09,MaleKBJR15}. If the solution obtained by these algorithms satisfies one of the above sufficient conditions, then, assuredly, this solution is the sparsest one.

Now, consider the case that the solution given by an algorithm is only approximately sparse meaning that it has some dominant components, while other components are very small but not equal to zero. If the total number of nonzero components is large such that neither of the mentioned conditions hold, it is not clear whether this solution is close to the true sparse solution or not. However, intuitively, one expects that if the number of effective components is small, then the obtained solution should not be far away from the true solution. Immediately, the following questions may be raised. Is this solution still close to the unique sparse solution of
$\mathbf{b} = \mathbf{A} \mathbf{x}$? Is it possible in this case to establish a bound on the error of finding $\mathbf{x}_0$ without knowing $\mathbf{x}_0$? Similar questions can be asked when there is error or noise in \eqref{USLE}. Taking the noise into account, \eqref{USLE} is updated to
\begin{equation} \label{USLENoisy}
\mathbf{b} = \mathbf{A} \mathbf{x} + \mathbf{e},
\end{equation}
where
$\mathbf{e}$ is the vector of noise or error. In this setting, to estimate $\mathbf{x}_0$ given
$\mathbf{b}$ and $\mathbf{A}$, the equality constraint in \eqref{l0min} is relaxed, and the following optimization problem should be solved:
\begin{equation} \label{l0minNoisy}
\min_{\mathbf{x}} \|\mathbf{x}\|_0  \quad \text{subject to} \quad \| \mathbf{A}\mathbf{x} - \mathbf{b}\| \leq \epsilon,
\end{equation}
where
$\epsilon \geq \| \mathbf{e} \|$ is some constant and $\| \cdot \|$ designates the $\ell_2$ norm.

The answers to the above questions were firstly given in \cite{BabaJM11}. Let $\widetilde{\xb}$ denote the output of an algorithm to find or estimate $\mathbf{x}_0$ from \eqref{USLE} or \eqref{USLENoisy}. Particularly, \cite{BabaJM11} provides two upper bounds on the error $\| \mathbf{x}_0 - \widetilde{\xb} \|$. The first one is rather simple to compute but turns out to be loose. On the other hand, while the second bound is tight, generally, it is much more complicated to compute.

Herein, in the spirit of the loose bound in \cite{BabaJM11}, we provide a better bound which is based on the same parameter of the matrix $\mathbf{A}$, but it is \emph{strictly tighter} than the loose bound in \cite{BabaJM11}. Moreover, our proposed bound is obtained in a much simpler way with a \emph{shorter} algebraic manipulation. The proposed bound is extended to the noisy setting defined in \eqref{USLENoisy}.
Furthermore, these results are also generalized to the problem of low-rank matrix recovery from compressed linear measurements \cite{RechFP10}.

The bounds introduced in this paper can be used in analyzing the performance of algorithms in sparse vector and low-rank matrix recovery, especially those algorithms that provide approximately sparse or low-rank solutions such as \cite{MohiBJ09} and \cite{MaleBAJ14,MaleBS14}. {\color{\RTre_Col} Other algorithms, under some conditions, can also benefit from the analysis presented in this paper. It is known that the solution obtained by some numerical solvers of basis pursuit \cite{ChenDS98}, like $\ell_1$-magic \cite{CandR05}, is not usually exactly sparse. In fact, due to limited numerical accuracy, the obtained solution has some very small nonzero entries. Our results can be used to find upper bounds on the $\ell_2$ norm of this kind of errors. Finally, when greedy algorithms \cite{Trop04} are used with an overestimated number of nonzero components of the true solution, our bound can be exploited to characterize the conditions under which the given solution is close to the true one.}
However, the bounds are obtained without any assumption on the recovery algorithm, and it is possible to improve them by exploiting properties of a specific algorithm. A similar upper bound on the error of sparse recovery in the noisy case has been proposed in \cite{GribFV06}. This upper bound, however, is only applicable when the given solution has a sparsity level{\color{\RTre_Col}, the number of nonzero components,} not greater than that of the true solution, while our bounds are obtained under the opposite assumption on the sparsity level of the given solution.


The rest of this paper is organized as follows. After introducing the notations used throughout the paper, in Section \ref{sec:Bounds}, we first present the upper bounds on the error of sparse vector recovery and, next, generalize them to the low-rank matrix recovery problem. Section \ref{sec:Proofs} is devoted to the proofs of the results in Section \ref{sec:Bounds}, followed by conclusions in Section \ref{sec:Con}.


\emph{Notations}: For a vector $\mathbf{x}$, $\| \mathbf{x} \|, \| \mathbf{x} \|_1$, and $\| \mathbf{x} \|_0$ denote the $\ell_2$, $\ell_1$, and the so-called $\ell_0$ norms, respectively. Moreover, $\xb^{\downarrow}$ denotes a vector obtained by sorting the elements of $\mathbf{x}$ in terms of magnitude in descending order, and $x_i$ designates the $i$th component of $\mathbf{x}$. $\mathbf{x}_{I}$ represents the subvector obtained from $\mathbf{x}$ by keeping components indexed by the set $I$. A vector is called $k$-sparse if it has exactly $k$ nonzero components. For a matrix $\mathbf{A}$, $\mathbf{a}_i$ denotes the $i$th column. Additionally, $\spark(\mathbf{A})$ and $\nullS(\mathbf{A})$ designate the minimum number of columns of $\mathbf{A}$ that are linearly dependent and the null space of $\mathbf{A}$, respectively. Similar to the vectors, $\mathbf{A}_{I}$ represents the submatrix of $\mathbf{A}$ obtained by keeping those columns indexed by $I$. It is always assumed that the singular values of matrices are sorted in descending order, and $\sigma_i(\mathbf{X})$ denotes the $i$th largest singular value of $\mathbf{X}$. Let $\mathbf{X} = \sum_{i=1}^{q} \sigma_i \mathbf{u}_i \mathbf{v}_i^T$, where $q = \rank(\mathbf{X})$, denote the singular value decomposition (SVD) of $\mathbf{X}$. $\mathbf{X}_{(r)} = \sum_{i=1}^{r} \sigma_i \mathbf{u}_i \mathbf{v}_i^T$ represents a matrix obtained by keeping the $r$ first terms in the SVD of $\mathbf{X}$, and $\mathbf{X}_{(-r)} = \mathbf{X} - \mathbf{X}_{(r)}$. $\|\mathbf{X}\|_F$ denotes the Frobenius norm, and $\|\mathbf{X}\|_* \triangleq \sum_{i=1}^{q} \sigma_i(\mathbf{X})$, in which $q = \rank(\mathbf{X})$, stands for the nuclear norm.

\section{Upper Bounds} \label{sec:Bounds}
In this section, the upper bounds on the error of sparse vector and low-rank matrix recovery are presented.
\subsection{Sparse Vector Recovery} \label{SpRec}
Following the common practice in the literature of compressive sensing (CS), we refer to
$\mathbf{b}, \mathbf{A}$, and
$\mathbf{e}$ in \eqref{USLENoisy} as the measurement vector, sensing matrix, and noise vector, respectively. Before stating the results, we recall two definitions.
\newtheorem{Def1}{Definition}
\begin{Def1}[\hspace{-0.05em}\cite{Cand08}]
 For a matrix $\mathbf{A} \in \mathbb{R}^{n \times m}$ and all integers
 $k \leq m$, the restricted isometry constant (RIC) of order $k$ is the smallest constant $\delta_k(\mathbf{A})$ such that
 \begin{equation} \label{RIPDefInEq1}
 (1-\delta_{k}(\mathbf{A})) \|\mathbf{x}\|^2 \leq \|\mathbf{A} \mathbf{x}\|^2 \leq (1+\delta_{k}(\mathbf{A})) \|\mathbf{x}\|^2
 \end{equation}
 holds for all vectors $\mathbf{x}$ with sparsity at most $k$.
 \end{Def1}

 \newtheorem{Def2}[Def1]{Definition}
\begin{Def2}[\hspace{-0.05em}\cite{BabaJM11}]
For a matrix $\mathbf{A} \in \mathbb{R}^{n \times m}$, let $\sigma_{\min,p}(\mathbf{A}) > 0$ for $p \leq \spark(\mathbf{A}) - 1$ be the smallest singular value of all
$\binom{m}{p}$ possible
$n \times p$ submatrices of $\mathbf{A}$.
 \end{Def2}

The following theorem presents the upper bounds for both noisy and noiseless cases. We deliberately separate the noisy and noiseless cases in order to be able to provide a tighter bound in the noiseless setting.

\newtheorem{Thm1}{Theorem}
\begin{Thm1} \label{VecBound}
Let $\mathbf{A} \in \mathbb{R}^{n \times m}$,
$m > n$, denote a sensing matrix. We have the following upper bounds.
\begin{itemize}
  \item Noiseless case: Suppose that $\mathbf{x}_0$ is a $k$-sparse solution of
  $\mathbf{A} \mathbf{x} = \mathbf{b}$, where $k < \spark(\mathbf{A}) / 2$. For all $\widetilde{\xb}$ solutions of
  $\mathbf{A} \mathbf{x} = \mathbf{b}$ satisfying $\widetilde{x}^{\downarrow}_{k+1} \leq \alpha$,
      \begin{equation} \label{InEqVecSigNoNoise}
     
      \| \mathbf{x}_0 - \widetilde{\xb} \|^2 \leq \Big( 1 + (m - 2k) \frac{\max_i \|\mathbf{a}_i\|^2}{\sigma_{\min,2k}^2(\mathbf{A})} \Big) (m - 2k) \alpha^2.
      \end{equation}
  \item Noisy case: Let $\mathbf{x}_0$ be any arbitrary vector with $\| \mathbf{x}_0 \|_0 = k < \spark(\mathbf{A}) / 2$, and let
      $\mathbf{b} = \mathbf{A} \mathbf{x}_0 + \mathbf{e}$, where
      $\mathbf{e}$ is noise with
      $\| \mathbf{e} \| \leq \epsilon$. For all $\widetilde{\xb}$ vectors satisfying
      $\| \mathbf{b} - \mathbf{A} \widetilde{\xb} \| \leq \Delta$ and $\widetilde{x}^{\downarrow}_{k+1} \leq \alpha$, the error $\| \mathbf{x}_0 - \widetilde{\xb} \|$ is bounded by
      \begin{align} \label{InEqVecSigNoisy}
      \| \mathbf{x}_0 - \widetilde{\xb} \| \leq & \Big( 1 + \sqrt{m - 2k}\frac{ \max_i \|\mathbf{a}_i\|}{\sigma_{\min,2k}(\mathbf{A})} \Big) \sqrt{m - 2k} \, \, \alpha \nonumber\\
       & + \frac{\Delta + \epsilon}{\sigma_{\min,2k}(\mathbf{A})}.
      \end{align}
\end{itemize}
\end{Thm1}

In brief, the above bounds say that if we have a solution $\widetilde{\xb}$ that consists of $k$ large components, then this vector is not far from the sparse solution provided that $\sigma_{\min,2k}(\mathbf{A})$ is not very small.
In particular, the bound in \eqref{InEqVecSigNoNoise} vanishes when $\widetilde{\xb}$ is $k$-sparse, reducing to the well-known uniqueness theorem in \cite{DonoE03}. Moreover, notice that these bounds work uniformly for all sparse vectors $\xb_0$ of sparsity level $k$; that is, they are independent from the position and magnitude of nonzero component of $\xb_0$.

{\color{black}\emph{Remark 1.}} The loose bounds in \cite[Theorems 2 \& 4]{BabaJM11} translated to our notations in the noiseless and noisy settings are
\begin{IEEEeqnarray}{rCl} \label{BZBound1}
\| \xb_0 - \widetilde{\xb} \| & \leq & \Big( 1 + \frac{1}{\sigma_{\min,2k}(\mathbf{A})} \Big) m \alpha,\\
\| \xb_0 - \widetilde{\xb} \| & \leq & \Big( 1 + \frac{1}{\sigma_{\min,2k}(\mathbf{A})} \Big) m \alpha + \frac{\Delta + \epsilon}{\sigma_{\min,2k}(\mathbf{A})}. \label{BZBound2}
\end{IEEEeqnarray}
The bounds in \eqref{BZBound1} and \eqref{BZBound2} are applicable only if the sensing matrix has unit $\ell_2$ norm columns, whereas Theorem \ref{VecBound} is valid without this restriction. To compare our bounds in Theorem \ref{VecBound} to \eqref{BZBound1} and \eqref{BZBound2}, let $U$ denote the square root of the upper bound in \eqref{InEqVecSigNoNoise}. Substituting $\max_i \|\mathbf{a}_i\|$ with 1 in $U$, one can write that
\begin{IEEEeqnarray*}{rCl}
U & = & \sqrt{\Big( 1 + \frac{m - 2k}{\sigma_{\min,2k}^2(\mathbf{A})} \Big)(m - 2k)} \, \, \alpha\\
& < & \Big(1 +  \frac{\sqrt{m - 2k}}{\sigma_{\min,2k}(\mathbf{A})} \Big)\sqrt{m - 2k} \, \, \alpha = U_2\\
& = & \Big(\frac{1}{\sqrt{m - 2k}} + \frac{1}{\sigma_{\min,2k}(\mathbf{A})} \Big)(m - 2k) \alpha\\
& < & \Big( 1 + \frac{1}{\sigma_{\min,2k}(\mathbf{A})}\Big) (m - 2k) \alpha\\
& < & \Big( 1 + \frac{1}{\sigma_{\min,2k}(\mathbf{A})}\Big) m \alpha,
\end{IEEEeqnarray*}
where $U_2$ is the first term in the upper bound in \eqref{InEqVecSigNoisy} with $\max_i \|\mathbf{a}_i\| = 1$. The above inequalities prove that the bounds \eqref{InEqVecSigNoNoise} and \eqref{InEqVecSigNoisy} are strictly tighter than the corresponding bounds in \cite{BabaJM11} formulated in \eqref{BZBound1} and \eqref{BZBound2}.

{\color{black}\emph{Remark 2.}} {\color{\RTre_Col}In general, finding $\sigma_{\min,2k}(\mathbf{A})$ is a combinatorial problem\footnote{{\color{\RTre_Col}Since one should calculate the singular values of all $\binom{m}{2k}$ possible $n \times 2k$ submatrices of $\mathbf{A}$.}}
 and NP-hard \cite{BabaJM11}. However, for a random matrix $\mathbf{A}$, under some conditions, the smallest singular value of all $n \times 2k$ submatrices is highly concentrated around a certain value. In particular, let $\mathbf{A}_{(2k)}$ denote any $n \times 2k$ submatrix of $\mathbf{A}$. If all the entries of $\mathbf{A}$ are independent and identically distributed (iid) from a normal distribution $\ensuremath{N(0,\frac{1}{n})}$ and $2k < n$, then for any $t > 0$, we have \cite{BabaJM11}
\begin{equation*}
p\Big\{ \sigma_{min}(\mathbf{A}_{(2k)}) < 1 - \sqrt{ \frac{2k}{n} } - t \Big\} \leq e^{-\frac{nt^2}{2}},
\end{equation*}
where $p\{\cdot\}$ and $\sigma_{min}(\cdot)$ denote the probability of the event described in the braces and the smallest singular value, respectively. This shows that when the dimensions of $\mathbf{A}$ increase, the smallest singular value of all $n \times 2k$ submatrices is equal to or larger than $1 - \sqrt{ \frac{2k}{n} }$ with very high probability. In line with this, for any matrix with iid entries from a zero-mean, $\frac{1}{n}$-variance distribution with a finite fourth-order moment, when $n,m \to \infty$ while $\frac{2k}{n} \to c$, $\sigma_{min}(\mathbf{A}_{(2k)})$ converges to $1 - \sqrt{c}$ almost surely \cite{BaiY93}.}


{\color{black}\emph{Remark 3.}} {\color{black} In addition to the above probabilistic values for $\sigma_{\min,2k}(\mathbf{A})$,}
the bounds in Theorem \ref{VecBound} can be also stated in terms of $\delta_{2k}(\mathbf{A})$ instead of $\sigma_{\min,2k}(\mathbf{A})$. In fact,
\begin{equation*}
\sigma_{\min,2k}(\mathbf{A}) = \min_{\| \mathbf{x} \|_0 \leq 2k} \frac{\| \mathbf{A} \mathbf{x} \|}{\| \mathbf{x} \|},
\end{equation*}
or $\| \mathbf{A} \mathbf{x} \|^2 \geq \sigma_{\min,2k}^2(\mathbf{A}) \| \mathbf{x} \|^2$ for all $\mathbf{x}$ with sparsity at most $2k$. Since $\delta_{2k}(\mathbf{A})$ in \eqref{RIPDefInEq1} is in such a way that both inequalities are satisfied, it can be concluded that $\sigma_{\min,2k}^2(\mathbf{A}) \geq 1 - \delta_{2k}(\mathbf{A})$. Consequently, the following bounds, {\color{\ROne_Col}under the condition $\delta_{2k}(\mathbf{A}) < 1$}, are a reformulation of the bounds in Theorem \ref{VecBound} in terms of $\delta_{2k}(\mathbf{A})$ which is frequently used in CS literature.
\begin{itemize}
\item Noiseless case:
\begin{equation*}
\| \mathbf{x}_0 - \widetilde{\xb} \|^2 \leq \Big( 1 + (m - 2k) \frac{\max_i \|\mathbf{a}_i\|^2}{1 - \delta_{2k}(\mathbf{A})} \Big) (m - 2k) \alpha^2.
\end{equation*}
\item Noisy case:
\begin{align*}
\| \mathbf{x}_0 - \widetilde{\xb} \| \leq & \Big( 1 + \sqrt{m - 2k} \frac{ \max_i \|\mathbf{a}_i\|}{\sqrt{1 - \delta_{2k}(\mathbf{A})}} \Big) \sqrt{m - 2k} \,\, \alpha \nonumber\\
       & + \frac{\Delta + \epsilon}{\sqrt{1 - \delta_{2k}(\mathbf{A})}}.
\end{align*}
\end{itemize}

\subsection{Low-rank Matrix Recovery}
Recovery of a low-rank matrix from compressed linear measurements \cite{RechFP10} is the task of finding the low-rank matrix $\mathbf{X}_0 \in \Rbb^{n_1 \times n_2}$ from underdetermined measurements $\mathbf{b} = \mathcal{A}(\mathbf{X}_0)$ where $\mathbf{b} \in \mathbb{R}^{m}, \mathcal{A}:\Rbb^{n_1 \times n_2} \to \mathbb{R}^{m}$ is a linear operator, and $m < n_1 n_2$. In the presence of noise, the measurement model is changed to $\mathbf{b} = \mathcal{A}(\mathbf{X}_0) + \mathbf{e}$ where $\mathbf{e}$ is the vector of noise.\footnote{The parameters $\mathbf{b},m,\mathbf{e},$ and $n$ (to be defined later on in this subsection) should not be confused with the similar parameters defined in Subsection \ref{SpRec}.} This recovery is a generalization of sparse vector recovery introduced in Section \ref{sec:Intro} to matrix variables. Consequently, the naive approach for recovering $\mathbf{X}_0$ from either noiseless or noisy measurements is
\begin{equation} \label{rankmin}
\min_{\mathbf{X}} \rank(\mathbf{X})  \quad \text{subject to} \quad \| \mathcal{A}(\mathbf{X}) - \mathbf{b} \| \leq \epsilon,
\end{equation}
where $\epsilon$ is some constant not less than $\| \mathbf{e} \|$ in the noisy case and equal to 0 in the noiseless case.

In this subsection, we present upper bounds on the error of recovering or estimating low-rank matrices from noiseless and noisy measurements when the obtained solution is approximately low-rank. Similar to the vector case, a matrix is approximately low rank, if it is composed of a few dominant singular values, while its other singular values are very small. Before stating the results, first the definition of the RIC is recalled.

\newtheorem{Def3}[Def1]{Definition}
\begin{Def3}[\hspace{-0.05em}\cite{CandP11}]
For a linear operator $\ACal: \Rbb^{n_1 \times n_2} \rightarrow \Rbb^m$ and all integers $r \leq \min(n_1,n_2)$, the RIC of order $r$ is the smallest constant $\delta_r(\mathcal{A})$ such that
\begin{equation*}
(1-\delta_{r}(\mathcal{A})) \|\mathbf{X}\|_F^2 \leq \|\mathcal{A}(\mathbf{X})\|^2 \leq (1+\delta_{r}(\mathcal{A})) \|\mathbf{X}  \|_F^2
\end{equation*}
holds for all matrices $\mathbf{X}$ with rank at most $r$.
\end{Def3}


\newtheorem{Thm2}[Thm1]{Theorem}
\begin{Thm2} \label{MatBound}
Let $\ACal: \Rbb^{n_1 \times n_2} \rightarrow \Rbb^m, m < n_1 n_2,$ denote a linear operator, and let $n = \min(n_1,n_2)$. We have the following upper bounds.
\begin{itemize}
  \item Noiseless case: Suppose that $\mathbf{X}_0$ is a rank $r$ solution of $\mathbf{b} = \mathcal{A}(\mathbf{X})$. If $0 < \delta_{2r}(\mathcal{A}) < 1$, then, for all $\widetilde{\Xb}$ solutions of $\mathbf{b} = \mathcal{A}(\mathbf{X})$ satisfying $\sigma_{r+1}(\widetilde{\Xb}) \leq \alpha$,
      \begin{equation} \label{InEqMatSigNoNoise}
      \| \mathbf{X}_0 - \widetilde{\Xb} \|_F^2 \leq \Big( 1 + (n - 2r) \frac{1 + \delta_1(\mathcal{A})}{1 - \delta_{2r}(\mathcal{A})} \Big) (n - 2r) \alpha^2.
      \end{equation}
  \item Noisy case: Let $\mathbf{X}_0$ be any arbitrary matrix of rank $r$, and let $\mathbf{b} = \mathcal{A}(\mathbf{X}_0) + \mathbf{e}$, where $\mathbf{e}$ is noise with $\| \mathbf{e} \| \leq \epsilon$. If $0 < \delta_{2r}(\mathcal{A}) < 1$, then for all $\widetilde{\Xb}$ estimates of $\mathbf{X}_0$ satisfying $\| \mathbf{b} - \mathcal{A}(\widetilde{\Xb}) \| \leq \Delta$ and $\sigma_{r+1}(\widetilde{\Xb}) \leq \alpha$, the error $\| \mathbf{X}_0 - \widetilde{\Xb} \|$ is bounded by
      \begin{align} \label{InEqMatSigNoisy}
      \| \mathbf{X}_0 - \widetilde{\Xb} \|_F \leq & \Bigg( 1 + \sqrt{(n - 2r)\frac{1 + \delta_1(\mathcal{A})}{1 - \delta_{2r}(\mathcal{A})}} \Bigg) \sqrt{n - 2r} \,\, \alpha \nonumber\\
       & + \frac{\Delta + \epsilon}{1 - \delta_{2r}(\mathcal{A})}.
      \end{align}
\end{itemize}

\end{Thm2}


\section{Proofs of Results} \label{sec:Proofs}
\subsection{Proof of Theorem \ref{VecBound}}
We need the following lemmas.

\newtheorem{Lem1}{Lemma}
\begin{Lem1} \label{VecNoNoise}
Let $\mathbf{A} \in \mathbb{R}^{n \times m}$,
$m > n$, be a sensing matrix. For every $\mathbf{x} \in \nullS(\mathbf{A})$ and any subset $I$ of
$\{1,\cdots,m\}$ with cardinality
$m - p$, where $ p \leq \spark(\mathbf{A}) -1$, we have that
\begin{equation} \label{InEqVecSig}
\| \mathbf{x} \|^2 \leq \Big( 1 + (m - p) \frac{\max_i \|\mathbf{a}_i\|^2}{\sigma_{\min,p}^2(\mathbf{A})} \Big) \| \xb_{I} \|^2.
\end{equation}
\begin{IEEEproof}
First, we notice that
\begin{IEEEeqnarray}{rCl}
\Big \| \sum_{i \in I} x_i \mathbf{a}_i \Big \|^2 & \leq & \Big( \sum_{i \in I}  \| x_i \mathbf{a}_i \| \Big)^2 = \Big( \sum_{i \in I} |x_i| \| \mathbf{a}_i \| \Big)^2,\nonumber \\
& \leq & \max_i \| \mathbf{a}_i \|^2 \Big( \sum_{i \in I}| x_{i} | \Big)^2, \nonumber \\
& = & \max_i \| \mathbf{a}_i \|^2 \| \xb_{I} \|_1^2, \nonumber \\
& \leq & (m - p) \max_i \| \mathbf{a}_i \|^2 \| \xb_{I} \|^2, \label{InEq1}
\end{IEEEeqnarray}
where, for the last inequality, we used $\forall \mathbf{z} \in \mathbb{R}^{l}, \| \mathbf{z} \|_1^2 \leq l \| \mathbf{z} \|^2$ \cite{HornJ90}. Next, from $\mathbf{A} \mathbf{x} = \sum_{i \in I} x_i \mathbf{a}_i + \sum_{i \notin I} x_i \mathbf{a}_i = 0$, we get
\begin{equation} \label{InEq2}
\Big \| \sum_{i \in I} x_i \mathbf{a}_i \Big \|^2 = \| \mathbf{A}_{\bar{I}} \xb_{\bar{I}} \|^2 \geq \sigma_{\min,p}^2(\mathbf{A}) \| \xb_{\bar{I}} \|^2,
\end{equation}
where
$\bar{I} = \{1,\cdots,m\} \setminus I$. Combining inequalities \eqref{InEq1} and \eqref{InEq2} and using $\| \mathbf{x} \|^2 = \| \xb_{I} \|^2 + \| \xb_{\bar{I}} \|^2$ prove \eqref{InEqVecSig}.
{\color{\RTre_Col}Note that $p \leq \spark(\mathbf{A}) - 1$ implies that $\sigma_{\min,p}(\mathbf{A}) \neq 0$ and inequality \eqref{InEqVecSig} is not trivial.}
\end{IEEEproof}
\end{Lem1}

\newtheorem{Lem2}[Lem1]{Lemma}
\begin{Lem2} \label{VecNoisy}
Let $\mathbf{A} \in \mathbb{R}^{n \times m}$,
$m > n$, be a sensing matrix. For every $\mathbf{x}$ satisfying $\| \mathbf{A} \mathbf{x} \| \leq \eta$ and every subset $I$ of
$\{1,\cdots,m\}$ with cardinality
$m - p$, where $ p \leq \spark(\mathbf{A}) -1$, we have that
\begin{equation} \label{InEqVecNoisySig}
\| \mathbf{x} \| \leq \Big( 1 + \sqrt{m - p} \frac{\max_i \|\mathbf{a}_i\|}{\sigma_{\min,p}(\mathbf{A})} \Big) \| \xb_{I} \| + \frac{\eta}{\sigma_{\min,p}(\mathbf{A})}.
\end{equation}
\begin{IEEEproof}
Similar to the proof of Lemma \ref{VecNoNoise}, we have
\begin{equation}
\Big \| \sum_{i \in I} x_i \mathbf{a}_i \Big \| \leq \sqrt{m - p} \max_i \| \mathbf{a}_i \| \| \xb_{I} \|.\label{InEq4}
\end{equation}
Furthermore, from $\mathbf{A} \mathbf{x} = \sum_{i \in I} x_i \mathbf{a}_i + \sum_{i \notin I} x_i \mathbf{a}_i$, we get
\begin{IEEEeqnarray}{rCl} \label{InEq5}
\Big \| \sum_{i \in I} x_i \mathbf{a}_i \Big \| & \geq & \| \mathbf{A}_{\bar{I}} \xb_{\bar{I}} \| - \| \mathbf{A} \mathbf{x} \|,\nonumber \\
& \geq & \sigma_{\min,p}(\mathbf{A}) \| \xb_{\bar{I}} \| - \| \mathbf{A} \mathbf{x} \|, \nonumber \\
& \geq & \sigma_{\min,p}(\mathbf{A}) \| \xb_{\bar{I}} \| - \eta.
\end{IEEEeqnarray}
Combining inequalities \eqref{InEq4} and \eqref{InEq5} leads to
\begin{equation*}
\sigma_{\min,p}(\mathbf{A}) \| \xb_{\bar{I}} \| \leq \sqrt{m - p} \max_i \|\mathbf{a}_i\| \| \xb_{I} \| + \eta
\end{equation*}
which is equivalent to
\begin{equation*}
\| \xb_{I} \| + \| \xb_{\bar{I}} \| \leq \Big(1 + \sqrt{m - p}\frac{\max_i \|\mathbf{a}_i\|}{\sigma_{\min,p}(\mathbf{A})} \Big)  \| \xb_{I} \| + \frac{\eta}{\sigma_{\min,p}(\mathbf{A})}.
\end{equation*}
The above inequality together with
\begin{equation*}
\| \mathbf{x} \| = \Bigg \| \begin{bmatrix} \xb_{I} \\ \xb_{\bar{I}} \end{bmatrix} \Bigg \| \leq \Bigg \| \begin{bmatrix} \xb_{I} \\ \mathbf{0} \end{bmatrix} \Bigg \| + \Bigg \| \begin{bmatrix} \mathbf{0} \\ \xb_{\bar{I}} \end{bmatrix} \Bigg \| = \| \xb_{I} \| + \| \xb_{\bar{I}} \|,
\end{equation*}
where $\mathbf{0}$ is a vector of zeros of appropriate length, proves \eqref{InEqVecNoisySig}.
\end{IEEEproof}
\end{Lem2}

\begin{IEEEproof}[Proof of Theorem \ref{VecBound}]
To prove \eqref{InEqVecSigNoNoise}, we first notice that because $\mathbf{x}_0$ has $k$ nonzero components and $\widetilde{x}^{\downarrow}_{k+1} \leq \alpha$, $\mathbf{x} = \mathbf{x}_0 - \widetilde{\xb}$ has at most $2k$ components with magnitude larger than $\alpha$. Alternatively, $\mathbf{x}$ possesses at least
$m - 2k$ components with magnitude not greater than $\alpha$. Now, let $I$ denote a set of indexes of components of $\mathbf{x}$ with magnitude less than or equal to $\alpha$ such that
$|I| = m - 2k$. It is clear that
$\| \xb_{I} \|^2 \leq (m - 2k) \alpha^2$. Consequently, since $\mathbf{x} \in \nullS(\mathbf{A})$, we can apply Lemma \ref{VecNoNoise} to get
\begin{IEEEeqnarray*}{rCl}
\| \mathbf{x}_0 - \widetilde{\xb} \|^2 & \leq & \Big( 1 + (m - 2k) \frac{\max_i \|\mathbf{a}_i\|^2}{\sigma_{\min,2k}^2(\mathbf{A})} \Big) \| \xb_{I} \|^2, \\
& \leq & \Big( 1 + (m - 2k) \frac{\max_i \|\mathbf{a}_i\|^2}{\sigma_{\min,2k}^2(\mathbf{A})} \Big)(m - 2k) \alpha^2.
\end{IEEEeqnarray*}
For proving \eqref{InEqVecSigNoisy}, we start with
\begin{IEEEeqnarray}{rCl}
\| \mathbf{A} (\mathbf{x}_0 - \widetilde{\xb}) \| & = & \| \mathbf{b} - \mathbf{A} \widetilde{\xb} + \mathbf{A} \mathbf{x}_0 - \mathbf{b} \|,\nonumber\\
&  \leq & \| \mathbf{b} - \mathbf{A} \widetilde{\xb} \| + \| \mathbf{A} \mathbf{x}_0 - \mathbf{b} \|,\nonumber\\
& \leq & \Delta + \epsilon. \label{InEqThm1_1}
\end{IEEEeqnarray}
Following the same reasoning as in the proof of \eqref{InEqVecSigNoNoise}, the application of Lemma \ref{VecNoisy} proves \eqref{InEqVecSigNoisy}.
\end{IEEEproof}

\subsection{Proof of Theorem \ref{MatBound}}

\newtheorem{Lem3}[Lem1]{Lemma}
\begin{Lem3} \label{MatNoNoise}
Let $\ACal: \Rbb^{n_1 \times n_2} \rightarrow \Rbb^m, m < n_1 n_2,$ denote a linear operator. For every $r < n = \min(n_1,n_2)$ and every $\mathbf{X} \in \nullS(\mathcal{A})$, if $0 < \delta_{r}(\mathcal{A}) < 1$, then
\begin{equation} \label{InEqLem3_0}
\| \mathbf{X} \|_F^2 \leq \Big( 1 + (n - r) \frac{1 + \delta_{1}(\mathcal{A})}{1 - \delta_{r}(\mathcal{A})} \Big) \| \mathbf{X}_{(-r)} \|_F^2.
\end{equation}
\begin{IEEEproof}
Let $\mathbf{X} = \sum_{i=1}^{n} \sigma_i \mathbf{u}_i \mathbf{v}_i^T$ denote the SVD of $\mathbf{X}$. We can write that
\begin{IEEEeqnarray}{rCl}
\Big \| \mathcal{A}(\mathbf{X}_{(-r)}) \Big \|^2 & = & \Big \| \mathcal{A} \Big ( \sum_{i=r+1}^n \sigma_i \mathbf{u}_i \mathbf{v}_i^T \Big) \Big\|^2,\nonumber\\
 & = & \Big \| \sum_{i=r+1}^n \sigma_i \mathcal{A}( \mathbf{u}_i \mathbf{v}_i^T ) \Big \|^2,\nonumber\\
& \leq &  \Big( \sum_{i=r+1}^n \sigma_i \big \| \mathcal{A}( \mathbf{u}_i \mathbf{v}_i^T ) \big \| \Big) ^2,\nonumber \\
& \overset{(a)}{\leq} &  \Big( \sum_{i=r+1}^n \sigma_i \sqrt{1 + \delta_{1}(\mathcal{A})} \Big)^2,\nonumber \\
& = &  \big(1 + \delta_{1}(\mathcal{A})\big) \big \| \mathbf{X}_{(-r)} \big \|_*^2,\nonumber \\
& \overset{(b)}{\leq} &  (n - r) \big(1 + \delta_{1}(\mathcal{A})\big) \big \| \mathbf{X}_{(-r)} \big \|_F^2,\label{InEqLem3_1}
\end{IEEEeqnarray}
where (a) follows from the definition of the RIC and $\| \mathbf{u}_i \mathbf{v}_i^T \|_F = 1$ and for (b), we used the inequality $\| \mathbf{Y} \|_* \leq \sqrt{\rank(\mathbf{Y})}\| \mathbf{Y} \|_F$ \cite{HornJ90}.

Additionally, $\mathcal{A}(\mathbf{X}) = \mathcal{A}(\mathbf{X}_{(r)}) + \mathcal{A}(\mathbf{X}_{(-r)}) = \mathbf{0}$ implies that
\begin{equation} \label{InEqLem3_2}
\big \| \mathcal{A}(\mathbf{X}_{(-r)}) \big \|^2 = \big \| \mathcal{A}(\mathbf{X}_{(r)}) \big \|^2 \geq \big(1 - \delta_{r}(\mathcal{A}) \big) \| \mathbf{X}_{(r)} \|_F^2.
\end{equation}
Combining \eqref{InEqLem3_1} and \eqref{InEqLem3_2} together with $\| \mathbf{X} \|_F^2 = \| \mathbf{X}_{(r)} \|_F^2 + \| \mathbf{X}_{(-r)} \|_F^2$ leads to inequality \eqref{InEqLem3_0}.
\end{IEEEproof}
\end{Lem3}

\newtheorem{Lem4}[Lem1]{Lemma}
\begin{Lem4} \label{MatNoisy}
Let $\ACal: \Rbb^{n_1 \times n_2} \rightarrow \Rbb^m, m < n_1 n_2$, denote a linear operator. For every $r < n = \min(n_1,n_2)$ and every $\mathbf{X}$ satisfying  $\| \mathcal{A}(\mathbf{X}) \| \leq \eta$, if $0 < \delta_{r}(\mathcal{A}) < 1$, then
\begin{IEEEeqnarray}{rCl}
\| \mathbf{X} \|_F & \leq & \Bigg( 1 + \sqrt{(n - r)\frac{1 + \delta_1(\mathcal{A})}{1 - \delta_r(\mathcal{A})}} \Bigg) \| \mathbf{X}_{(-r)} \|_F \nonumber\\
& & + \frac{\eta}{\sqrt{1 - \delta_r(\mathcal{A})}}. \label{InEqMatNoisy}
\end{IEEEeqnarray}
\begin{IEEEproof}
Inequality \eqref{InEqLem3_1} holds for every $\mathbf{X}$; thus, it is possible to write
\begin{equation}  \label{InEqLem4_1}
\| \mathcal{A}(\mathbf{X}_{(-r)}) \| \leq \sqrt{(n - r)(1 + \delta_1(\mathcal{A}))} \| \mathbf{X}_{(-r)} \|_F.
\end{equation}
Furthermore, applying the triangle inequality on $\mathcal{A}(\mathbf{X}_{(-r)}) = \mathcal{A}(\mathbf{X}) - \mathcal{A}(\mathbf{X}_{(r)})$, one can obtain
\begin{IEEEeqnarray}{rCl} \label{InEqLem4_2}
\big \| \mathcal{A}(\mathbf{X}_{(-r)}) \big \| & \geq & \big \| \mathcal{A}(\mathbf{X}_{(r)}) \big \| - \big \| \mathcal{A}(\mathbf{X}) \big \|,\nonumber \\
& \geq & \sqrt{1 - \delta_r(\mathcal{A})} \| \mathbf{X}_{(r)} \|_F - \eta.
\end{IEEEeqnarray}
Combining inequalities \eqref{InEqLem4_1} and \eqref{InEqLem4_2} together with $\| \mathbf{X} \|_F \leq  \| \mathbf{X}_{(r)} \|_F + \| \mathbf{X}_{(-r)} \|_F$ gives inequality \eqref{InEqMatNoisy}.
\end{IEEEproof}
\end{Lem4}

\begin{IEEEproof}[Proof of Theorem \ref{MatBound}]
To prove \eqref{InEqMatSigNoNoise}, let us first define $\mathbf{X} = \mathbf{X}_0 - \widetilde{\Xb}$. According to \cite[Thmeorem 3.3.16]{HornJ91}, for any $1 \leq i,j \leq n$ and $i + j \leq n+1$,
\begin{equation*}
\sigma_{i+j-1}(\mathbf{X}) \leq \sigma_{i}(\mathbf{X}_0) + \sigma_{j}(\widetilde{\Xb}).
\end{equation*}
Substituting $i$ and $j$ with $r+1$ in the above inequality leads to
\begin{equation*}
\sigma_{2r+1}(\mathbf{X}) \leq \sigma_{r+1}(\mathbf{X}_0) + \sigma_{r+1}(\widetilde{\Xb}) \leq \alpha.
\end{equation*}
Consequently, Lemma \ref{MatNoNoise} implies that
\begin{IEEEeqnarray*}{rCl}
\| \mathbf{X}_0 - \widetilde{\Xb} \|_F^2 & \leq & \Big( 1 + (n - 2r) \frac{1 + \delta_1(\mathcal{A})}{1 - \delta_{2r}(\mathcal{A})} \Big) \| \mathbf{X}_{(-2r)} \|_F^2,\\
& \leq & \Big( 1 + (n - 2r) \frac{1 + \delta_1(\mathcal{A})}{1 - \delta_{2r}(\mathcal{A})} \Big) (n - 2r) \alpha^2.
\end{IEEEeqnarray*}
For proving \eqref{InEqMatSigNoisy}, we start with
\begin{IEEEeqnarray*}{rCl}
\| \mathbf{A} (\mathbf{X}_0 - \widetilde{\Xb}) \| & = & \| \mathbf{b} - \mathcal{A}( \widetilde{\Xb} ) + \mathcal{A}( \mathbf{X}_0 ) - \mathbf{b} \|,\nonumber\\
&  \leq & \Delta + \epsilon.
\end{IEEEeqnarray*}
Following the same reasoning as in the proof of \eqref{InEqMatSigNoNoise}, the application of Lemma \ref{MatNoisy} completes the proof.
\end{IEEEproof}



\section{Conclusion} \label{sec:Con}
In this paper, we proposed upper bounds on the error of sparse vector recovery from both noiseless or noisy measurements when the obtained solution is approximately sparse. While these bounds are based on the same parameters as in the loose bounds of \cite{BabaJM11}, they are strictly tighter. We further generalized them to the problem of low-rank matrix recovery, when the solution at hand to recover the true low-rank matrix is approximately low rank.

\section{Acknowledgement}
{\color{black}The authors would like to thank the anonymous reviewers for their helpful comments.}

\bibliographystyle{elsarticle-num}
