text:
\begin{document}

\title{\Large\bf Truncated Sparse Approximation Property and Truncated $q$-Norm Minimization
\footnotetext{\hspace{-0.35cm}\endgraf Corresponding author: lipengmath@126.com (P. Li).
}}

\author{Wengu Chen and Peng Li\,$^\ast$}

\maketitle
\textbf{Abstract.} This paper considers approximately sparse signal and low-rank matrix's recovery via truncated norm minimization $\min_{x}\|x_T\|_q$
and $\min_{X}\|X_T\|_{S_q}$ from noisy measurements. We first introduce truncated sparse approximation property, a more general robust null space property, and establish the stable recovery of signals and matrices under the truncated sparse approximation property. We also explore the relationship between the restricted isometry property and truncated sparse approximation property. And we also prove that if a measurement matrix $A$ or linear map $\mathcal{A}$ satisfies truncated sparse approximation property of order $k$, then the first inequality in restricted isometry property  of order $k$ and of order $2k$ can hold for certain different constants $\delta_{k}$ and $\delta_{2k}$, respectively. Last, we show that if $\delta_{t(k+|T^c|)}<\sqrt{(t-1)/t}$ for some $t\geq 4/3$, then measurement matrix $A$ and linear map $\mathcal{A}$ satisfy truncated sparse approximation property of order $k$. Which should point out is that when $T^c=\emptyset$, our conclusion implies that sparse approximation property of order $k$ is weaker than restricted isometry property of order $tk$.

\textbf{Key Words and Phrases.} Truncated norm minimization, Truncated sparse approximation property, Restricted isometry property, Sparse signal recovery,
Low-rank matrix recovery, Dantzig selector.

\textbf{Mathematics Subject Classification}. {65K10,90C25,90C26,92C55}

\section{Introduction}\label{s1}

\hskip\parindent

The problem of sparse signal recovery naturally arises in genetics, communications and image processing. Prominent examples include DNA microarrays \cite{ES2005, PVMH2008}, wireless communications \cite{HS2009, THER2010}, magnetic resonance imaging \cite{LDP2007, VAHBPL2010},  and more. In such contexts, we often require to recover an unknown signal $x\in\mathbb{R}^n$ from an underdetermined system of linear equations
\begin{align}\label{systemequationsnoise}
b=Ax+z,
\end{align}
where $b\in\mathbb{R}^m$ are available measurements, the matrix $A\in\mathbb{R}^{m\times n}~(m<n)$ models the linear measurement process and
$z\in\mathbb{R}^m$ is a vector of measurement errors. The constrained $l_q$ minimization method estimates the signal $x$ by
\begin{align}\label{lqminimization}
\hat{x}=\arg\min_{x\in\mathbb{R}^n}\{\|x\|_q^q:~\text{subject~to}~b-Ax\in\mathcal{B}\}
\end{align}
where $0<q\leq 1$ and $\mathcal{B}$ is a set determined by the noise structure.  In  this paper, we consider two types of bounded noises \cite{CW2011}.
One is $l_p$ bounded noises \cite{DET2006}, i.e.,
\begin{align}\label{lpboundednoise}
\mathcal{B}^{l_p}(\eta)=\{z: \|z\|_p\leq\eta\}
\end{align}
for some constant $\eta$; and the other is motivated by \textit{Dantzig~Selector} procedure \cite{CT2007}, where
\begin{align}\label{Dantzigselectornoise}
\mathcal{B}^{DS}(\eta)=\{z: \|A^*z\|_\infty\leq\eta\}.
\end{align}
In particular, when $\mathcal{B}=\{0\}$, it is the noiseless case.

For the $l_q$-minimization problem (\ref{lqminimization}), there are many works under the restricted isometry property \cite{CT2005,CT2006,CS2008,CDD2009, CZ2013,CZ2013-1,CZ2014} and under the null space property \cite{DE2003, CDD2009, S2011, FR2013, F2014}. Let $x_k$ be the best $k$-sparse approximation vector of $x$ and $\sigma_k(x)_q$ be the error of best $k$-term approximation to the vector $x$ in $l_q$-norm.
Specially, we should point out that in 2011, Sun \cite{S2011} introduced the sparse approximation property
\begin{align*}
 \|x_k\|_r^q\leq \beta k^{q/r-1}\sigma_k(x)_q^q +D\|Ax\|_p^q
\end{align*}
where $0<q,p,r\leq\infty$, which was called sparse Riesz property in \cite{ST2016}.
And Sun \cite{S2011} showed that the sparse approximation property is an appropriate condition on a measurement matrix to consider stable recovery of any compressible
signal from its noisy measurements. We should point out that when $q=1$ and $p=2$, the sparse approximation property is equivalent to the $l_r$-robust null
space property \cite{FR2013,F2014}
\begin{align*}
\|x_K\|_r\leq \beta k^{1/r-1}\sigma_k(x)_1 +D\|Ax\|_2,
\end{align*}
where $K$ is any subset of $\subset \{1,\ldots,n\}$ with $|K|\leq k$. Here and what follows, $x_K$ is the vector equal to $x$ on $K$ and to zero on $K^c$; $K^c$ denotes the complementary set of $K$.

Although Basis Pursuit ((\ref{lqminimization}) for $q=1$) is much easy to solve, it requires significantly more measurements. In \cite{WY2010}, Wang and Yin proposed an iterative support detection (ISD) method that runs as fast as the best BP algorithms but requires significantly fewer measurements. From an incorrect reconstruction, support detection identifies an index set $I$ containing some elements of $\text{supp}(\bar{x})=\{j:x_j\neq 0\}$, and signal reconstruction solves
\begin{align}\label{TruncatedBP}
\min_x~\|x_T\|_1~\text{subject~to~}Ax=b,
\end{align}
where $T=I^c$. In fact, $I^{(s+1)}=\text{supp}(x^{(s)})$ in the $s$-th iteration of ISD algorithm.  In \cite{WY2010}, Wang and Yin  also generalized the null space property to the truncated null space property
\begin{align*}
\|v_K\|_1\leq\beta\|v_{T\cap K^c}\|_1 \end{align*}
where $T\subset\{1,\ldots,n\}$ is any set with $|T|=t$,  $K\subset T$ with $|K|\leq k$ and $v\in\mathcal{N}(A)$, and introduced an efficient implementation of ISD for recovering signals with fast decaying distributions of nonzeros from compressive sensing measurements.
Later, in her Dissertation, Zhang \cite{Z2013} considered the model (\ref{TruncatedBP}) in generalized case¡ª¡ªtruncated $l_q$-minimization with noise
\begin{align}\label{Truncatedq2}
\min_x~\|x_T\|_q^q~\text{subject~to~}\|Ax-b\|_2\leq\varepsilon,
\end{align}
where $0<q\leq 1$. Via restricted isometry property (RIP), she got a stable recovery of $x$ by (\ref{Truncatedq2}).

By the fact that the sparse approximation property is an additional strengthening of null space property in noisy case and is weaker than restricted isometry property,  therefore we consider the following question.

\begin{question} Whether can we introduce the truncated sparse approximation property for matrix $A$
and get a stable recovery of any compressible signal from its noisy measurements via the model
\begin{align}\label{Truncatedq}
\min_{x}~\|x_T\|_q^q ~~\text{subject~ to}~ ~b-Ax\in\mathcal{B},
\end{align}
where $0<q\leq 1$.
\end{question}
In this paper, we give affirmative answer for this question. We introduce the truncated sparse approximation property with $l_p$-norm constraint $\|b-Ax\|_p$
and Dantzig selector constraint $\|A^*(b-Ax)\|_{\infty}$, and get a stable recovery of signal $x$ via (\ref{Truncatedq}).

On the other hand, a closely related problem to compressed sensing is the low-rank matrix recovery,
which aims to recover an unknown low-rank matrix based on
its affine transformation
\begin{align}\label{Matrixsystemequationsnoise}
b=\mathcal{A}(X)+z,
\end{align}
where $X\in\mathbb{R}^{m\times n}$ is the decision variable and the linear map $\mathcal{A}: R^{m\times n}\rightarrow \mathbb{R}^l$, $z\in\mathbb{R}^l$ is the measurement error and vector $b\in\mathbb{R}^l$ is given. Low-rank matrices arise in an incredibly wide range of settings throughout science and applied mathematics. To name just a few examples, we commonly encounter low-rank matrices in contexts as varied as: ensembles
of signals \cite{DE2012,AR2015}, system identification \cite{LV2009}, adjacency matrices \cite{LLR1995}, distance matrices \cite{BLWY2006,BG2010,SY2007} and machine learning \cite{AEP2008,OTJ2010,D2004}.

Assume that the singular value decomposition of $X$ is $X=U\Lambda V^{T}=U\text{diag}(\lambda(X))V^{T}$ and $l=\min\{m,n\}$, where $\lambda(X)=(\lambda_1,\ldots,\lambda_{l})$ is the vector of singular values of the matrix $X$ with $\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_{l}\geq 0$.
Let $\|X\|_{S_p}:=\|\lambda(X)\|_p=\big(\sum_{j=1}^{l}|\lambda_j(X)|^p\big)^{1/p}$ denote the Schatten $p$-norm of matrix $X$,  We should point out that $\|X\|_{S_1}=\|X\|_*$ the nuclear norm,
$\|X\|_{S_2}=\|X\|_F$ the Frobenius norm and $\|X\|_{S_{\infty}}=\|X\|_{2\rightarrow 2}$ the operator norm.
In 2010, Recht,  Fazel and Parrilo \cite{RFP2010} generalized the restricted isometry property (RIP) from vectors to matrices and showed that
if certain restricted isometry property holds for the linear transformation $\mathcal{A}$, the minimum-rank solution can be recovered by solving the
minimization of the nuclear norm
\begin{align*}
\min_{X}\|X\|_{*}~~\text{subject~to~}\mathcal{A}(X)=b. \end{align*}
Later, the low-rank matrix recovery problem has been studied by many scholars, readers can refer to
\cite{CP2011,CZ2013,CZ2013-1,CZ2014,CZ2015,ZL2017,ZL2017-1}
under matrix restricted isometry property and \cite{FR2013,KKRT2016} under rank null space property.

Now, a corresponding question is as follows.
\begin{question}
Whether can we introduce a truncated rank null space property, even a truncated rank sparse approximation property for
linear map $\mathcal{A}$ and obtain a stable recovery of the approximately low-rank matrix $X$ from its noisy measurements via the model
\begin{align}\label{MatrixTruncatedq}
\min_{X}~\|X_T\|_{S_q}^q ~~\text{subject~ to}~ ~b-\mathcal{A}(X)\in\mathcal{B},
\end{align}
where $\|X_T\|_{S_q}=\big(\sum_{j\in T}|\lambda_j(X)|^q\big)^{1/q}=\big(\sum_{j={l-t+1}}^l|\lambda_j(X)|^q\big)^{1/q}$ and $0<q\leq 1$.
\end{question}
Our answer to this question is also affirmative.

Our paper is organized as follows.
In Section \ref{s2}, we introduce truncated sparse approximation property for vector and matrix, respectively, and establish a stable recovery of approximately sparse signals and  low-rank matrices.
In Section \ref{s3}, we show that if a measurement matrix $A$ satisfies truncated sparse approximation property of order $k$, then the first inequality in restricted isometry property of order $k$ and of order $2k$ hold for certain different constants $\delta_{k}$ and $\delta_{2k}$, respectively.
And, we also show that if measurement matrix $A$ satisfies restricted isometry property with $\delta_{t(k+|T^c|)}<\sqrt{(t-1)/t}$, then $A$ also satisfies truncated sparse approximation property of order $k$. We note that when $T^c=\emptyset$, this conclusion implies that the $(l_2,l_1)-l_2$ sparse approximation property of order $k$ and and $(l_2,l_1)-\text{Dantzig~selector}$ sparse approximation property of order $k$ is weaker than restricted 2-isometry property of order $tk$.   And these relationships between the restricted isometry property and truncated sparse approximation property also hold for linear map $\mathcal{A}$. Finally, we summarize our conclusions and discuss the drawbacks of our results and file out some proper directions for coming study in Section 4.

\section{Truncated sparse approximation property and Stable Recovery \label{s2}}
\hskip\parindent

In this section, we will introduce $t$-truncated $(l_r,l_q)-l_p$ sparse approximation property and $t$-truncated $(l_r,l_q)-\text{Dantzig~selector}$ sparse approximation property of order $k$ for measurement matrix $A$, and get stable recovery of signal $x$ from (\ref{Truncatedq}) for $\mathcal{B}=\mathcal{B}^{l_p}(\eta)$ and $\mathcal{B}=\mathcal{B}^{DS}(\eta)$.  And we also introduce truncated rank sparse approximation property and establish the same stable recovery for approximately low-rank matrices.  Firstly, we consider the vector case.

\subsection{Vector Case \label{s2.1}}
\hskip\parindent

We introduce the following $t$-truncated sparse approximation property.

\begin{definition}\label{SparseRieszProperty}
Let $0<p,r\leq\infty$ and $0<q<\infty$. An $m\times n$ matrix $A$ satisfies $t$-truncated $(l_r,l_q)-l_p$ sparse approximation property of order $k$ with constants $D$ and $\beta$ if
\begin{align}\label{lpSparseRieszProperty}
\|x_{K}\|_r^q \leq D\|Ax\|_p^q + \beta k^{q/r-1}\sigma_k(x_{T})_q^q,
\end{align}
holds for all sets $T\subset\{1,\ldots,n\}$ with $|T|=t$, and all sets $K\subset T$-the index set of the $k$ largest (in magnitude) coefficients of $x_{T}$.

And an $m\times n$ matrix $A$ satisfies the $t$-truncated $(l_r,l_q)-\text{Dantzig~selector}$ sparse approximation property of order $k$ with constants $D$ and $\beta$ if
\begin{align}\label{DSSparseRieszProperty}
\|x_{K}\|_r^q \leq D\|A^*Ax\|_\infty^q + \beta k^{q/r-1}\sigma_k(x_{T})_q^q
\end{align}
holds for all sets $T\subset\{1,\ldots,n\}$ with $|T|=t$, and all sets $K\subset T$-the index set of the $k$ largest (in magnitude) coefficients of $x_{T}$.
\end{definition}

Next, we give out a proposition and a remark about truncated sparse approximation property.
\begin{proposition}
Let $0<p,r\leq\infty$ and $0<q<\infty$ and matrix $A$ satisfies $t$-truncated $(l_r,l_q)-l_p$ sparse approximation property of order $k$ with $t=|T|$, constants $D$ and $\beta$.
\begin{itemize}
\item[(1)]
  For any $\tilde{T}\subseteq T$ with $|\tilde{T}|=\tilde{t}\geq t$, matrix $A$ also satisfies $\tilde{t}$-truncated $(l_r,l_q)-l_p$ sparse approximation property of order $k$ with  constants $D$ and $\beta$.
\item[(2)]For any $\tilde{k}\leq k$, matrix $A$ also satisfies $t$-truncated $(l_r,l_q)-l_p$ sparse approximation property of order $\tilde{k}$ with $t=|T|$, constants $D$ and $\beta$.
\end{itemize}

And for $t$-truncated $(l_r,l_q)-\text{Dantzig~selector}$ sparse approximation property of order $k$, we have same results.
\end{proposition}
\begin{proof}
Assume that matrix $A$ satisfies $t$-truncated $(l_r,l_q)-l_p$ sparse approximation property of order $k$ with $t=|T|$, constants $D$ and $\beta$, then by the definition, we have
$$
\|x_{K}\|_r^q \leq D\|Ax\|_p^q + \beta k^{q/r-1}\sigma_k(x_{T})_q^q,
$$
holds for all sets $T\subset\{1,\ldots,n\}$ with $|T|=t$, and all sets $K\subset T$-the index set of the $k$ largest (in magnitude) coefficients of $x_{T}$.
For any  $|\tilde{T}|=\tilde{t}\geq t$ with $\tilde{T}\subseteq T$, one can get
$$
\|x_{K}\|_r^q \leq D\|Ax\|_p^q + \beta k^{q/r-1}\sigma_k(x_{T})_q^q\leq D\|Ax\|_p^q + \beta k^{q/r-1}\sigma_k(x_{\tilde{T}})_q^q,
$$
which implies that matrix $A$ also satisfies $\tilde{t}$-truncated $(l_r,l_q)-l_p$ sparse approximation property of order $k$ with  constants $D$ and $\beta$.

And for any $\tilde{k}\leq k$, let $\tilde{K}\subset T$-the index set of the $\tilde{k}$ largest (in magnitude) coefficients of $x_{T}$, then we have
\begin{align*}
\|x_{\tilde{K}}\|_r^q&\leq\|x_{K}\|_r^q\leq D\|Ax\|_P^q+\beta k^{q/r-1}\sigma_{k}(x_{T})_q^q
= D\|Ax\|_p^q + \beta \Big(\frac{\sigma_k(x_{T})_q}{k^{1/q-1/r}}\Big)^q\\
&\leq D\|Ax\|_p^q+\beta\Big(\frac{\sigma_{\tilde{k}}(x_{T})_q}{\tilde{k}^{1/q-1/r}}\Big)^q
=D\|Ax\|_p^q+\beta\tilde{k}^{q/r-1}\sigma_{\tilde{k}}(x_{T})_q^q.
\end{align*}

And for for $t$-truncated $(l_r,l_q)-\text{Dantzig~selector}$ sparse approximation property of order $k$, the proof is similar and we omit it here.
\end{proof}

\begin{remark}
If $x\in\mathcal{N}(A)$, then (\ref{lpSparseRieszProperty}) and (\ref{DSSparseRieszProperty}) become
\begin{align}\label{Nullspaceproperty}
\|x_{K}\|_r^q \leq \beta k^{q/r-1}\sigma_k(x_{T})_q^q.
\end{align}
When $r=q=1$, it is equivalent to the $t$-truncated null space property which was introduced in \cite{WY2010}.
\end{remark}

Next, we consider the model (\ref{systemequationsnoise}) in the setting where the observations contain noise and the signal is not exactly $k$-sparse.

\begin{theorem}\label{vectorstablerecovery}
Consider the signal model (\ref{systemequationsnoise}) with $\|z\|_p\leq\varepsilon$ and suppose $\hat{x}^{l_p}$ is the minimizer of (\ref{Truncatedq}) with
$\mathcal{B}=\mathcal{B}^{l_p}(\eta)$ defined in (\ref{lpboundednoise}) for some $\eta\geq\varepsilon$. Let $0<q\leq 1$, $q\leq r\leq\infty$, $1\leq p
\leq\infty$. If measurement matrix $A$ satisfies $t$-truncated $(l_r,l_q)-l_p$ sparse approximation property of order $k$ with
constants $D\in(0,\infty)$ and $\beta\in(0,1)$, then
\begin{align}\label{vectorstable1}
\|\hat{x}^{l_p}-x\|_r^q&\leq
\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}+1+\Big(\frac{|T|-k}{k}\Big)^{q/r}\bigg)\frac{D}{1-\beta}(\varepsilon+\eta)^q\nonumber\\
&\hspace*{12pt}+\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}+1+\Big(\frac{|T|-k}{k}\Big)^{q/r}\bigg)\frac{2\beta}{1-\beta}
k^{q/r-1}\sigma_k(x_T)_q^q,
\end{align}
and
\begin{align}\label{vectorstable2}
\|\hat{x}^{l_p}-x\|_q^q
&\leq\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}\Big(\frac{|T^c|}{k}\Big)^{1-q/r}+2\bigg)\frac{D}{1-\beta}k^{1-q/r}(\varepsilon+\eta)^q\nonumber\\
&\hspace*{12pt}+\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}\Big(\frac{|T^c|}{k}\Big)^{1-q/r}\frac{2\beta}{1-\beta}+\frac{2(1+\beta)}{1-\beta}\bigg)
\sigma_k(x_T)_q^q
\end{align}
if $q<r$, and
\begin{align}\label{vectorstable3}
\|\hat{x}^{l_p}-x\|_q^q&\leq\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}+2\bigg)\frac{D}{1-\beta}(\varepsilon+\eta)^q\nonumber\\
&\hspace*{12pt}+\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}\frac{2\beta}{1-\beta}+\frac{2(1+\beta)}{1-\beta}\bigg)\sigma_k(x_T)_q^q
\end{align}
if $q=r$.

Consider the signal model (\ref{systemequationsnoise}) with $\|A^*z\|_{\infty}\leq\varepsilon$ and suppose $\hat{x}^{DS}$ is the minimizer of (\ref{Truncatedq}) with $\mathcal{B}=\mathcal{B}^{DS}(\eta)$ defined in (\ref{Dantzigselectornoise}) for some $\eta\geq\varepsilon$. Let $0<q\leq 1$ and $q\leq r\leq\infty$. If measurement matrix $A$ satisfies $t$-truncated $(l_r,l_q)-\text{Dantzig~selector}$ sparse approximation property of order $k$ with constants $D\in(0,\infty)$ and $\beta\in(0,1)$, then we have
\begin{align*}
\|\hat{x}^{DS}-x\|_r^q&\leq
\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}+1+\Big(\frac{|T|-k}{k}\Big)^{q/r}\bigg)\frac{D}{1-\beta}(\varepsilon+\eta)^q\nonumber\\
&\hspace*{12pt}+\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}+1+\Big(\frac{|T|-k}{k}\Big)^{q/r}\bigg)\frac{2\beta}{1-\beta}
k^{q/r-1}\sigma_k(x_T)_q^q,
\end{align*}
and
\begin{align*}
\|\hat{x}^{DS}-x\|_q^q
&\leq\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}\Big(\frac{|T^c|}{k}\Big)^{1-q/r}+2\bigg)\frac{D}{1-\beta}k^{1-q/r}(\varepsilon+\eta)^q\nonumber\\
&\hspace*{12pt}+\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}\Big(\frac{|T^c|}{k}\Big)^{1-q/r}\frac{2\beta}{1-\beta}+\frac{2(1+\beta)}{1-\beta}\bigg)
\sigma_k(x_T)_q^q
\end{align*}
if $q<r$, and
\begin{align*}
\|\hat{x}^{DS}-x\|_q^q&\leq\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}+2\bigg)\frac{D}{1-\beta}(\varepsilon+\eta)^q\nonumber\\
&\hspace*{12pt}+\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}\frac{2\beta}{1-\beta}+\frac{2(1+\beta)}{1-\beta}\bigg)\sigma_k(x_T)_q^q
\end{align*}
if $q=r$.
\end{theorem}

Before proving Theorem \ref{vectorstablerecovery}, we first state an auxiliary lemma.
\begin{lemma}\label{coneconstraint}
Suppose $x,\hat{x}\in\mathbb{R}^{n}$, $v=\hat{x}-x$. If $\|\hat{x}_T\|_{q}^q\leq \|x_T\|_{q}^q$, then we have
$$
\|v_{T\cap K^c}\|_{q}^q\leq2\sigma_k(x_T)_q^q+\|v_{T\cap K}\|_{q}^q,
$$
where $K$ is the index set of $k$ largest (in magnitude) coefficients of $x_{T}$.
\end{lemma}
\begin{proof}
Since $\|\hat{x}_T\|_{q}^q\leq \|x_T\|_{q}^q$, one can get
\begin{align*}
\|x_T\|_q^q&\geq\|\hat{x}_T\|_q^q=\|(v+x)_T\|_q^q=\|(v+x)_{T\cap K}\|_q^q + \|(v+x)_{T\cap K^c}\|_q^q\\
&\geq\big(\|x_{T\cap K}\|_q^q -\|v_{T\cap K}\|_q^q\big) +\big(\|v_{T\cap K^c}\|_q^q-\|x_{T\cap K^c}\|_q^q\big),
\end{align*}
therefore,
\begin{align*}
\|v_{T\cap K^c}\|_q^q&\leq \big(\|x_{T}\|_q^q-\|x_{T\cap K}\|_q^q+\|x_{T\cap K^c}\|_q^q\big)+\|v_{T\cap K}\|_q^q \nonumber\\
&\leq 2\sigma_k(x_T)_q^q+\|v_{T\cap K}\|_q^q.
\end{align*}
\end{proof}

\begin{proof}[Proof of Theorem \ref{vectorstablerecovery}]
We finish our proof via the following seven steps.

\textbf{Step 1}. Tube constraint and cone constraint

Let $v=\hat{x}^{l_p}-x$, we have
\begin{align}\label{lpbounded}
\|Av\|_p&\leq\|A\hat{x}-b\|_p+\|Ax-b\|_p\leq \eta+\varepsilon.
\end{align}

Let $K$ denote the index set of $k$ largest (in magnitude) coefficients of $x_{T}$. By Lemma \ref{coneconstraint}, we have
\begin{align}\label{coneconstraintequation}
\|v_{T\cap K^c}\|_q^q&\leq 2\sigma_k(x_T)_q^q+\|v_{T\cap K}\|_q^q.
\end{align}

\textbf{Step 2}. Partition the set $\{1,\ldots,n\}$.

Let $\{1,\ldots,n\}=T^c\cup T=T^c\cup (T\cap K)\cup(T\cap K^c)$, for any $q\leq\tilde{r}\leq r$, we have
\begin{align}\label{Comininginequality}
\|v\|_{\tilde{r}}^q&=\big(\|v_{T^c}\|_{\tilde{r}}^{\tilde{r}}+\|v_{T\cap K}\|_{\tilde{r}}^{\tilde{r}}+\|v_{T\cap K^c}\|_{\tilde{r}}^{\tilde{r}}\big)^{q/{\tilde{r}}}
\leq \|v_{T^c}\|_{\tilde{r}}^q + \|v_{T\cap K}\|_{\tilde{r}}^q+\|v_{T\cap K^c}\|_{\tilde{r}}^q.
\end{align}
Next, we estimate  $v_{T^c}$, $v_{T\cap K}$ and $v_{T\cap K^c}$, respectively.

\textbf{Step 3}. Estimate $v_{T\cap K}$.

By the $t$-truncated $(l_r,l_q)-l_p$ sparse approximation property, we have
\begin{align*}
\|v_{T\cap K}\|_r^q&\leq D\|Av\|_p^q + \beta k^{q/r-1}\sigma_k(v_T)_q^q\leq D\|Av\|_p^q + \beta k^{q/r-1}\|v_{T\cap K^c}\|_q^q \\
&\leq D(\varepsilon+\eta)^q+\beta k^{q/r-1}\big(\|v_{T\cap K}\|_q^q+2\sigma_k(x_T)_q^q\big) \\
&\leq D(\varepsilon+\eta)^q +\beta k^{q/r-1}\big(|T\cap K|^{1/q-1/r}\|v_{T\cap K}\|_r\big)^q+ 2\beta k^{q/r-1}\sigma_k(x_T)_q^q\\
&\leq D(\varepsilon+\eta)^q +\beta \|v_{T\cap K}\|_r^q+ 2\beta k^{q/r-1}\sigma_k(x_T)_q^q,
\end{align*}
where the third inequality follows by (\ref{coneconstraintequation}).
Therefore, we obtain
\begin{align}\label{TcapK}
\|v_{T\cap K}\|_r^q\leq\frac{D}{1-\beta}(\varepsilon+\eta)^q+ \frac{2\beta}{1-\beta} k^{q/r-1}\sigma_k(x_T)_q^q.
\end{align}
by $0<\beta<1$.

\textbf{Step 4}. Estimate $v_{T\cap K^c}$.

Combining (\ref{coneconstraintequation}) with (\ref{TcapK}) yields
\begin{align}\label{TcapKc1}
\|v_{T\cap K^c}\|_q^q&\leq \|v_{T\cap K}\|_q^q +2\sigma_k(x_T)_q^q\leq \big(|T\cap K|^{1/q-1/r}\|v_{T\cap K}\|_r\big)^q+2\sigma_k(x_T)_q^q \nonumber\\
&\leq k^{1-q/r}\Big(\frac{D}{1-\beta}(\varepsilon+\eta)^q+ \frac{2\beta}{1-\beta} k^{q/r-1}\sigma_k(x_T)_q^q\Big)+2\sigma_k(x_T)_q^q\nonumber\\
&=\frac{D}{1-\beta}k^{1-q/r}(\varepsilon+\eta)^q + \frac{2}{1-\beta}\sigma_k(x_T)_q^q.
\end{align}
And by (\ref{TcapK}), we have
\begin{align}\label{TcapKc2}
\|v_{T\cap K^c}\|_r^q&\leq\big(|T\cap K^c|\max_{j\in T\cap K^c}|v_j|^r\big)^{q/r}\nonumber\\
&\leq\big(|T\cap K^c|\frac{\sum_{j\in T\cap K}|v_j|^r}{|T\cap K|}\big)^{q/r}=\Big(\frac{|T|-k}{k}\Big)^{q/r}\|v_{T\cap K}\|_r^q\nonumber\\
&\leq \Big(\frac{|T|-k}{k}\Big)^{q/r}\Big(\frac{D}{1-\beta}(\varepsilon+\eta)^q+ \frac{2\beta}{1-\beta} k^{q/r-1}\sigma_k(x_T)_q^q\Big).
\end{align}

\textbf{Step 5}. Estimate $v_{T^c}$.

Our idea of proving this part comes from \cite[Theorem 3.3]{WY2010}. Let $K_1=T^c$, $K_2=T\cap K$ and $K_3=T\cap K^c$. Next, we deal with ``$|K_1|\leq k$" and ``$|K_1|>k$", respectively.

\textbf{Case 1}: $|K_1|\leq k$.

We can find $K'\subset K_2$ such that $|K_1\cup K'|=k$ and $|K'|=k-(n-t)$. Let $\tilde{T}=K^c\cup K'$, then  $|\tilde{T}|=|K^c|+|K'|=(n-k)+(k-(n-t))=t$, $(K_1\cup K')\subset \tilde{T}$ and
$(K_1\cup K')^c\cap \tilde{T}=T\cap K^c=K_3$, therefore from the $t$-truncated $(l_r,l_q)-l_p$ sparse approximation property, we have
\begin{align*}
\|v_{T^c}\|_r^q&\leq\|v_{K_1\cup K'}\|_r^q\leq D\|Av\|_p^q+\beta k^{q/r-1}\sigma_k(v_{\tilde{T}})_q^q\\
&\leq D\|Av\|_p^q+\beta k^{q/r-1}\|v_{K_3}\|_q^q\\
&\leq D(\varepsilon+\eta)^q+\beta k^{q/r-1}\|v_{T\cap K^c}\|_q^q.
\end{align*}

\textbf{Case 2}: $|K_1|> k$.

Let $K''\subset K_1$ denote the set of indices corresponding to the largest $k$ entries of $v_{K_1}$. Take $\tilde{\tilde{T}}=K_3\cup K''$, then $|\tilde{\tilde{T}}|=|K_3|+|K''|=t-k+k=t$, $K''\subset \tilde{\tilde{T}}$ and $K''\cap \tilde{\tilde{T}}=K_3$.
Then $t$-truncated $(l_r,l_q)-l_p$ sparse approximation property leads us to conclude that
\begin{align*}
\|v_{T^c}\|_r^q&=\|v_{K_1}\|_r^q\leq\Big(\frac{|K_1|}{k}\|v_{K''}\|_r\Big)^q\\
&\leq \Big(\frac{|K_1|}{k}\Big)^q\big(D\|Av\|_p^q+\beta k^{q/r-1}\sigma_k(v_{\tilde{\tilde{T}}})_q^q\big)\\
&\leq \Big(\frac{|K_1|}{k}\Big)^q\big(D(\varepsilon+\eta)^q+\beta k^{q/r-1}\|v_{T\cap K^c}\|_q^q\big).
\end{align*}

Combining \textbf{Case 1} and \textbf{Case 2}, and using (\ref{TcapKc1}), we have
\begin{align}\label{Tc}
\|v_{T^c}\|_r^q&\leq \max\Big\{\Big(\frac{|K_1|}{k}\Big)^q,1\Big\}\big(D(\varepsilon+\eta)^q+\beta k^{q/r-1}\|v_{T\cap K^c}\|_q^q\big) \nonumber\\
&\leq \max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}
\bigg(D(\varepsilon+\eta)^q+ \beta k^{q/r-1}\Big(\frac{D}{1-\beta}k^{1-q/r}(\varepsilon+\eta)^q + \frac{2}{1-\beta}\sigma_k(x_T)_q^q\Big)\bigg) \nonumber\\
&\leq \max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}\Big(\frac{D}{1-\beta}(\varepsilon+\eta)^q+\frac{2\beta}{1-\beta}k^{q/r-1}\sigma_k(x_T)_q^q\Big).
\end{align}

\textbf{Step 6}. Obtain conclusions for $\mathcal{B}=\mathcal{B}^{l_p}(\eta)$.

For $\tilde{r}=r$, an application (\ref{Tc}) (\ref{TcapK}) and (\ref{TcapKc2}) to (\ref{Comininginequality}) yields
\begin{align*}
\|v\|_r^q&\leq\|v_{T^c}\|_r^q + \|v_{T\cap K}\|_r^q+\|v_{T\cap K^c}\|_r^q\\
&\leq \max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}\Big(\frac{D}{1-\beta}(\varepsilon+\eta)^q+\frac{2\beta}{1-\beta}k^{q/r-1}\sigma_k(x_T)_q^q\Big)\\
&\hspace*{12pt}+\Big(\frac{D}{1-\beta}(\varepsilon+\eta)^q+ \frac{2\beta}{1-\beta} k^{q/r-1}\sigma_k(x_T)_q^q\Big)\\
&\hspace*{12pt}+\Big(\frac{|T|-k}{k}\Big)^{q/r}\Big(\frac{D}{1-\beta}(\varepsilon+\eta)^q+ \frac{2\beta}{1-\beta} k^{q/r-1}\sigma_k(x_T)_q^q\Big)\\
&\leq\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}+1+\Big(\frac{|T|-k}{k}\Big)^{q/r}\bigg)\frac{D}{1-\beta}(\varepsilon+\eta)^q\\
&\hspace*{12pt}+\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}+1+\Big(\frac{|T|-k}{k}\Big)^{q/r}\bigg)\frac{2\beta}{1-\beta} k^{q/r-1}\sigma_k(x_T)_q^q,
\end{align*}
which obtain the inequality (\ref{vectorstable1}).

For $\tilde{r}=q<r$, by (\ref{Tc}), (\ref{TcapK}) and (\ref{TcapKc1}), we have
\begin{align*}
\|v\|_q^q&\leq\|v_{T^c}\|_q^q + \|v_{T\cap K}\|_q^q+\|v_{T\cap K^c}\|_q^q\\
&\leq \big(|T^c|^{1/q-1/r}\|v_{T^c}\|_r\big)^q + \big(k^{1/q-1/r}\|v_{T\cap K}\|_r\big)^{q}+\|v_{T\cap K^c}\|_q^q\\
&\leq |T^c|^{1-q/r} \max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}
\Big(\frac{D}{1-\beta}(\varepsilon+\eta)^q+\frac{2\beta}{1-\beta}k^{q/r-1}\sigma_k(x_T)_q^q\Big)\\
&\hspace*{12pt}+k^{1-q/r}\Big(\frac{D}{1-\beta}(\varepsilon+\eta)^q+ \frac{2\beta}{1-\beta} k^{q/r-1}\sigma_k(x_T)_q^q\Big)\\
&\hspace*{12pt}+\Big(\frac{D}{1-\beta}k^{1-q/r}(\varepsilon+\eta)^q + \frac{2}{1-\beta}\sigma_k(x_T)_q^q\Big)\\
&=\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}\Big(\frac{|T^c|}{k}\Big)^{1-q/r}+2\bigg)\frac{D}{1-\beta}k^{1-q/r}(\varepsilon+\eta)^q\\
&\hspace*{12pt}+\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}\Big(\frac{|T^c|}{k}\Big)^{1-q/r}\frac{2\beta}{1-\beta}+\frac{2(1+\beta)}{1-\beta}\bigg)\sigma_k(x_T)_q^q,
\end{align*}
which finish the inequality (\ref{vectorstable2}).

Last, we turn our attention to prove inequality (\ref{vectorstable3}).
For $r=q$, applying (\ref{Tc}) (\ref{TcapK}) and (\ref{TcapKc1}) to (\ref{Comininginequality}), one can get
\begin{align*}
\|v\|_q^q&\leq\|v_{T^c}\|_q^q + \|v_{T\cap K}\|_q^q+\|v_{T\cap K^c}\|_q^q\\
&\leq\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}\Big(\frac{D}{1-\beta}(\varepsilon+\eta)^q+\frac{2\beta}{1-\beta}\sigma_k(x_T)_q^q\Big)\\
&\hspace*{12pt}+ \Big(\frac{D}{1-\beta}(\varepsilon+\eta)^q+ \frac{2\beta}{1-\beta} \sigma_k(x_T)_q^q\Big)
+ \Big(\frac{D}{1-\beta}(\varepsilon+\eta)^q + \frac{2}{1-\beta}\sigma_k(x_T)_q^q\Big)\\
&\leq\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}+2\bigg)\frac{D}{1-\beta}(\varepsilon+\eta)^q\\
&\hspace*{12pt}+\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}\frac{2\beta}{1-\beta}+\frac{2(1+\beta)}{1-\beta}\bigg)\sigma_k(x_T)_q^q.
\end{align*}

\textbf{Step 7.} Inequalities for Dantzig selector.

In the case of noise type $\mathcal{B}^{DS}$, define $v=\hat{x}^{DS}-x$.
we can obtain
\begin{align}\label{DSbounded}
\|A^*Av\|_\infty&\leq\|A*(A\hat{x}-b)\|_{\infty}+\|A^*(Ax-b)\|_\infty\leq\eta+\varepsilon
\end{align}
and (\ref{DSSparseRieszProperty})
instead of (\ref{lpbounded}) and (\ref{lpSparseRieszProperty}), respectively. The following steps are similar with the case of noise type $\mathcal{B}^{l_p}$, we omit it here.
\end{proof}

For $r=q$, we have a sufficient and necessary condition for guaranteeing truncated sparse approximation property, which is similar to the conclusion of classic robust $l_q$-null space property, see \cite[Chapter 4.3]{FR2013}. We omit the proof details.

\begin{theorem}\label{sufficient-necessary}
\begin{itemize}
\item[(1)]The $m\times n $ measurement matrix $A$  satisfies $t$-truncated $(l_q,l_q)-l_p$ sparse approximation property of order $k$ with $t=|T|$,
    constants $D\in(0,\infty)$ and $\beta\in(0,1)$ if and only if
\begin{align}\label{e5}
\|(y-x)_{T}\|_q^q&\leq\frac{1+\beta}{1-\beta}\big(\|y_T\|_q^q-\|x_T\|_q^q+2\sigma_{k}(x_T)_q^q\big)+\frac{2D}{1-\beta}\|A(y-x)\|_p^q
\end{align}
holds for all vectors $y,x\in\mathbb{C}^n$.
\item[(2)] The $m\times n $ measurement matrix $A$ satisfies $t$-truncated $(l_q,l_q)-\text{Dantzig~selector}$ sparse approximation property of order $k$ with $t=|T|$, constants $D\in(0,\infty)$ and $\beta\in(0,1)$ if and only if
\begin{align}\label{e5}
\|(y-x)_{T}\|_q^q&\leq\frac{1+\beta}{1-\beta}\big(\|y_T\|_q^q-\|x_T\|_q^q+2\sigma_k(x_T)_q^q\big)+\frac{2D}{1-\beta}\|A^*A(y-x)\|_{\infty}^q
\end{align}
holds for all vectors $y,x\in\mathbb{C}^n$.
\end{itemize}
\end{theorem}

Last, we will show that if there exists a stable recovery for compressible signal $x$, then the measurement matrix $A$ also posses the truncated sparse approximation property for $r=p$.

\begin{theorem}\label{SRP}
Let $0<q,p\leq\infty$. If the error between the given vector $x$ and the solution $\hat{x}$ of (\ref{Truncatedq}) satisfies
\begin{align}\label{e7}
\|\hat{x}-x\|_p^q\leq B_1(\varepsilon+\eta)^q+B_2k^{q/p-1}\sigma_k(x_T)_q^q,
\end{align}
where $B_1,~B_2$ are positive constants independent of $\varepsilon,~\eta$ and $x$, and $|T|=t$, then
\begin{align*}
\|x\|_p^q\leq B_1\|Ax\|_p^q+B_2k^{q/p-1}\sigma_k(x_T)_q^q,
\end{align*}
or
\begin{align*}
\|x\|_p^q\leq B_1\|A^*Ax\|_\infty^q+B_2k^{q/p-1}\sigma_k(x_T)_q^q,
\end{align*}
and hence $A$ satisfies the $t$-truncated $(l_p,l_q)-l_p$ sparse approximation property of order $k$ with constants $B_1$ and $B_2$, or the $t$-truncated $(l_p,l_q)-l_p$ sparse approximation property of order $k$ with constants $B_1$ and $B_2$.
\end{theorem}
\begin{proof}
We observe that zero vector is the solution of truncated $l_q$-minimization problem (\ref{Truncatedq}) with $\eta=0$ and $\varepsilon=\|Ax\|_p$
or $\varepsilon=\|A^*Ax\|_\infty$, and $b=Ax$ for any $x\in\mathbb{R}^n$. Therefore the truncated sparse approximation property follows from (\ref{e7}) immediately.
\end{proof}

\begin{remark}\label{Algorithm}
In \cite{WY2010}, Wang and Yin proposed an iterative support detection (ISD) method to compute truncated $\ell_1$ minimization (\ref{TruncatedBP}). And in her Dissertation, Zhang \cite{Z2013} proposed a $\ell_q$-iterative support detection method to compute truncated $\ell_q$ minimization (\ref{Truncatedq}) with $\mathcal{B}=\mathcal{B}^{l_2}(\eta)$. Now another important question is that wether there exists a algorithm to compute truncated $\ell_q$ minimization (\ref{Truncatedq}) with $\mathcal{B}=\mathcal{B}^{DS}(\eta)$ or $\mathcal{B}=\mathcal{B}^{l_q}(\eta)$ for $0<q\leq 1$? This is one direction of our future research.
\end{remark}

\subsection{Matrix Cases \label{s2.2}}
\hskip\parindent

Now, we consider the matrix case. First, we introduce $t$-truncated rank sparse approximation property as follows.

\begin{definition}\label{SparseRieszProperty}
Let $0<p,r\leq\infty$ and $0<q<\infty$. A linear map $\mathcal{A}$ satisfies $t$-truncated $(l_r,l_q)-l_p$ rank sparse approximation property of order $k$ with constants $D$ and $\beta$ if
\begin{align}\label{MatrixlpSparseRieszProperty}
\|X_{K}\|_{S_r}^q \leq D\|\mathcal{A}(X)\|_p^q + \beta k^{q/r-1}\sigma_k(X_{T})_q^q,
\end{align}
holds for all sets $T\subset\{1,\ldots,\min\{m,n\}\}$ with $|T|=t$, and all sets $K\subset T$-the index set of the $k$ largest (in magnitude) coefficients of $\lambda(X)_{T}$.

And a linear map $\mathcal{A}$ satisfies the $t$-truncated $(l_r,l_q)-\text{Dantzig~selector}$ rank sparse approximation property of order $k$ with constants $D$ and $\beta$ if
\begin{align}\label{MatrixDSSparseRieszProperty}
\|X_{K}\|_{S_r}^q \leq D\|\mathcal{A}^{*}\mathcal{A}(X)\|_{S_\infty}^q + \beta k^{q/r-1}\sigma_k(X_{T})_q^q
\end{align}
holds for all sets $T\subset\{1,\ldots,\min\{m,n\}\}$ with $|T|=t$, and all sets $K\subset T$-the index set of the $k$ largest (in magnitude) coefficients of $\lambda(X)_{T}$.
\end{definition}

Let's consider the matrix recovery model (\ref{Matrixsystemequationsnoise}) in the setting where the observations contain noise and matrix is not exactly $k$-low-rank.

\begin{theorem}\label{Matrixstablerecovery}
Consider the matrix model (\ref{Matrixsystemequationsnoise}) with $\|z\|_p\leq\varepsilon$ and suppose $\hat{X}^{l_p}$ is the minimizer of
(\ref{MatrixTruncatedq}) with $\mathcal{B}=\mathcal{B}^{l_p}(\eta)$ defined in (\ref{lpboundednoise}) for some $\eta\geq\varepsilon$. Let $0<q\leq 1$,
$q\leq r\leq\infty$, $1\leq p \leq\infty$. If linear mapping $\mathcal{A}$ satisfies $t$-truncated $(l_r,l_q)-l_p$ sparse approximation property of order $k$ with $t=|T|$, constants $D\in(0,\infty)$ and $\beta\in(0,1)$, then
\begin{align}\label{Matrixstable1}
\|\hat{X}^{l_p}-X\|_{S_r}^q&\leq
\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}+1+\Big(\frac{|T|-k}{k}\Big)^{q/r}\bigg)\frac{D}{1-\beta}(\varepsilon+\eta)^q\nonumber\\
&\hspace*{12pt}+\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}+1+\Big(\frac{|T|-k}{k}\Big)^{q/r}\bigg)\frac{2\beta}{1-\beta}
k^{q/r-1}\sigma_k(X_T)_q^q,
\end{align}
and
\begin{align}\label{Matrixstable2}
\|\hat{X}^{l_p}-X\|_{S_q}^q
&\leq\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}\Big(\frac{|T^c|}{k}\Big)^{1-q/r}+2\bigg)\frac{D}{1-\beta}k^{1-q/r}(\varepsilon+\eta)^q\nonumber\\
&\hspace*{12pt}+\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}\Big(\frac{|T^c|}{k}\Big)^{1-q/r}\frac{2\beta}{1-\beta}+\frac{2(1+\beta)}{1-\beta}\bigg)
\sigma_k(X_T)_q^q
\end{align}
if $q<r$, and
\begin{align}\label{Matrixstable3}
\|\hat{X}^{l_p}-X\|_{S_q}^q&\leq\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}+2\bigg)\frac{D}{1-\beta}(\varepsilon+\eta)^q\nonumber\\
&\hspace*{12pt}+\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}\frac{2\beta}{1-\beta}+\frac{2(1+\beta)}{1-\beta}\bigg)\sigma_k(X_T)_q^q
\end{align}
if $q=r$.

Consider the matrix model (\ref{Matrixsystemequationsnoise}) with $\|\mathcal{A}^*(z)\|_{S_\infty}\leq\varepsilon$ and suppose $\hat{x}^{DS}$ is the minimizer of
(\ref{MatrixTruncatedq}) with $\overline{\mathcal{B}}=\overline{\mathcal{B}}^{DS}(\eta):=\{z\in \mathbb{R}^{l}: \|\mathcal{A}^*(z)\|_{S_\infty}\leq\eta\}$ for some $\eta\geq\varepsilon$. Let $0<q\leq 1$ and $q\leq r\leq\infty$. If linear mapping $\mathcal{A}$ satisfies $t$-truncated $(l_r,l_q)-\text{Dantzig~selector}$ sparse approximation property of order $k$ with $t=|T|$, constants $D\in(0,\infty)$ and $\beta\in(0,1)$, then we have
\begin{align*}
\|\hat{X}^{DS}-X\|_{S_r}^q&\leq
\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}+1+\Big(\frac{|T|-k}{k}\Big)^{q/r}\bigg)\frac{D}{1-\beta}(\varepsilon+\eta)^q\nonumber\\
&\hspace*{12pt}+\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}+1+\Big(\frac{|T|-k}{k}\Big)^{q/r}\bigg)\frac{2\beta}{1-\beta}
k^{q/r-1}\sigma_k(X_T)_q^q,
\end{align*}
and
\begin{align*}
\|\hat{X}^{DS}-X\|_{S_q}^q
&\leq\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}\Big(\frac{|T^c|}{k}\Big)^{1-q/r}+2\bigg)\frac{D}{1-\beta}k^{1-q/r}(\varepsilon+\eta)^q\nonumber\\
&\hspace*{12pt}+\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}\Big(\frac{|T^c|}{k}\Big)^{1-q/r}\frac{2\beta}{1-\beta}+\frac{2(1+\beta)}{1-\beta}\bigg)
\sigma_k(X_T)_q^q
\end{align*}
if $q<r$, and
\begin{align*}
\|\hat{X}^{DS}-X\|_{S_q}^q&\leq\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}+2\bigg)\frac{D}{1-\beta}(\varepsilon+\eta)^q\nonumber\\
&\hspace*{12pt}+\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}\frac{2\beta}{1-\beta}+\frac{2(1+\beta)}{1-\beta}\bigg)\sigma_k(X_T)_q^q
\end{align*}
if $q=r$.
\end{theorem}

To prove the results of matrix recovery, we need following lemma, which $q=1$ comes from \cite[Lemma 2.3]{RFP2010}, and $0<q<1$ comes from \cite[Lemma
2.2]{KX2013} and \cite[Lemma 2.1]{ZHZ2013}.

\begin{lemma}\label{orthogonaldecomposition}
Let $0<q\leq 1$. Let $X,Y\in\mathcal{R}^{m\times n}$ be matrices with $X^{T}Y=O$ and $XY^{T}=O$,  then the following holds:
\begin{itemize}
\item[(1)]$\|X+Y\|_{S_q}^q=\|X\|_{S_q}^q+\|Y\|_{S_q}^q$;
\item[(2)]$\|X+Y\|_{S_q}\geq\|X\|_{S_q}+\|Y\|_{S_q}$.
\end{itemize}
\end{lemma}

In order to get the cone constraint for matrix's  Schatten norm, we also need the following lemma which was gave by Yue and So in \cite{YS2016} and Audenaert \cite{A2014}.

\begin{lemma}\label{perturbationinequality}
Let $X, Y\in\mathbb{R}^{m\times n}$ be given matrices. Suppose that $f: \mathbb{R}_{+}\rightarrow \mathbb{R}_{+}$is a concave function satisfying $f(0)=0$. Then, for any $k\in\{1,\ldots,\min\{m,n\}\}$, we have
$$\sum_{j=1}^k|f(\lambda_j(X))-f(\lambda_j(Y))|\leq\sum_{j=1}^kf(\lambda_j(X-Y)).$$
\end{lemma}

\begin{lemma}
Suppose $X,\hat{X}\in\mathbb{R}^{m\times n}$, $V=\hat{X}-X$. If $\|\hat{X}_T\|_{S_q}^q\leq \|X_T\|_{S_q}^q$, then we have
$$
\|V_{T\cap K^c}\|_{S_q}^q\leq2\sigma_k(\lambda(X)_T)_q^q+\|V_{T\cap K}\|_{S_q}^q,
$$
where $K$ is the index set of $k$ largest (in magnitude) coefficients of $\lambda(X)_{T}$
\end{lemma}
\begin{proof}
By $\|\hat{X}_T\|_{S_q}^q\leq \|X_T\|_{S_q}^q$ and Lemma \ref{orthogonaldecomposition}, one can get
\begin{align*}
\|\lambda(X)_T\|_q^q&=\|X_T\|_{S_q}^q\geq\|\hat{X}_T\|_{S_q}^q=\|(V+X)_T\|_{S_q}^q=\|\lambda(V+X)_{T\cap K}\|_{q}^q + \|\lambda(V+X)_{T\cap K^c}\|_{q}^q.
\end{align*}
Since $x\rightarrow|x|^q$ is concave on $\mathbb{R}_+$ for any $q\in(0, 1]$, by taking $f(\cdot)=(\cdot)^q$ in above Lemma \ref{perturbationinequality}, we immediately obtain
\begin{align*}
\|\lambda(X)_T\|_q^q&\geq\big(\|\lambda(X)_{T\cap K}\|_q^q -\|\lambda(V)_{T\cap K}\|_q^q\big) +\big(\|\lambda(V)_{T\cap K^c}\|_q^q-\|\lambda(X)_{T\cap K^c}\|_q^q\big),
\end{align*}
Therefore,
\begin{align*}
\|V_{T\cap K^c}\|_{S_q}^q&=\|\lambda(V)_{T\cap K^c}\|_{q}^q\leq \big(\|\lambda(X)_{T}\|_q^q-\|\lambda(X)_{T\cap K}\|_q^q+\|\lambda(X)_{T\cap K^c}\|_q^q\big)+\|\lambda(V)_{T\cap K}\|_q^q \nonumber\\
&\leq 2\sigma_k(\lambda(X)_T)_q^q+\|\lambda(V)_{T\cap K}\|_q^q=2\sigma_k(\lambda(X)_T)_q^q+\|V_{T\cap K}\|_{S_q}^q.
\end{align*}
\end{proof}

The proof of these results of matrix case are similar to the vector case and we omit them here.

Conversely, if there exists a stable recovery of approximately low-rank matrix $X$, then the linear map $\mathcal{A}$ also posses the truncated sparse approximation property of $r=p$.

\begin{theorem}\label{MatrixSRP}
Let $0<q,p\leq\infty$. If the error between the given matrix $X$ and the solution $\hat{X}$ of (\ref{MatrixTruncatedq}) satisfies
\begin{align}\label{e8}
\|\hat{X}-X\|_{S_p}^q\leq B_1(\varepsilon+\eta)^q+B_2k^{q/p-1}\sigma_k(X_T)_q^q,
\end{align}
where $B_1,~B_2$ are positive constants independent of $\varepsilon,~\eta$ and $x$, and $|T|=t$, then
\begin{align*}
\|X\|_{S_p}^q\leq B_1\|\mathcal{A}(X)\|_p^q+B_2k^{q/p-1}\sigma_k(X_T)_q^q,
\end{align*}
or
\begin{align*}
\|X\|_{S_p}^q\leq B_1\|\mathcal{A}^*\mathcal{A}(X)\|_{S_\infty}^q+B_2k^{q/p-1}\sigma_k(X_T)_q^q,
\end{align*}
and hence $\mathcal{A}$ satisfies the $t$-truncated $(l_p,l_q)-l_p$ rank sparse approximation property of order $k$ with constants $B_1$ and $B_2$, or the $t$-truncated $(l_p,l_q)-\text{Dantzig-selector}$ rank sparse approximation property of order $k$ with constants $B_1$ and $B_2$.
\end{theorem}

\section{Truncated sparse approximation property and Restricted Isometry Property\label{s3}}
\hskip\parindent

In this section, we will consider the relationship between the restricted isometry property and truncated sparse approximation property. First, we recall the definition of restricted $p$-isometry property, which was introduced in \cite{CT2005} for $p=2$ and in \cite{CS2008} for $0<p\leq 1$.

\begin{definition}\label{RIP}
For an matrix $A$, $k>0$, and $0 < p\leq1$ or $p=2$, the $k$-th restricted $p$-isometry constants $\delta_k=\delta_k(A)$ is the smallest numbers such that
\begin{align*}
(1-\delta_k)\|x\|_2^p\leq\|Ax\|_p^p\leq(1+\delta_k)\|x\|_2^p
\end{align*}
for all $x$ such that $\|x\|_0\leq k$.
\end{definition}

And the matrix-restricted $2$-isometry property was first introduced by Recht,  Fazel and  Parrilo in \cite{RFP2010}. Later, it was extended to
matrix-restricted $p$-isometry property for $0<p\leq 1$ by Zhang, Huang and Zhang in \cite{ZHZ2013}.

\begin{definition}\label{MatrixRIP}
Let $0 < p\leq1$ or $p=2$, $\mathcal{A} : \mathbb{R}^{m¡Á\times n}\rightarrow \mathbb{R}^l$ be a linear map. Without loss of generality,
assume $m \leq n$. For every integer $k$ with $1\leq k\leq \min\{m,n\}$, define the matrix $k$-th restricted $p$-isometry
constant to be the smallest number $\delta_k=\delta_k(\mathcal{A})$ such that
\begin{align*}
(1-\delta_k)\|X\|_{S_2}^p\leq\|\mathcal{A}(X)\|_p^p\leq(1+\delta_k)\|X\|_{S_2}^p
\end{align*}
holds for all matrices $X$ of rank at most $k$.
\end{definition}

\subsection{Truncated sparse approximation property implies the first inequality in Restricted Isometry Property\label{s3.1}}
\hskip\parindent

Firstly, we show that if a measurement matrix satisfies truncated sparse approximation property of order $k$, then the first inequality in restricted isometry property of order $k$ and of order $2k$ hold for certain different constants $\delta_{k}$ and $\delta_{2k}$, respectively.

\begin{theorem}\label{k2ksparsevector}
Let $0<q\leq r\leq\infty$, $0<p\leq\infty$.
\item[(1)]If a matrix $A$ satisfies $t$-truncated $(l_r,l_q)-l_p$ sparse approximation property of order $k$ with $t=|T|$, constants $D\in(0,\infty)$ and $\beta\in(0,1)$, then
for all $x\in\Sigma_k(T)=\{x\in\mathbb{R}^n:\|x_T\|_0\leq k\}$,
\begin{align}
\frac{1}{C_1}\|x\|_r^q\leq\|Ax\|_p^q,
\end{align}
where
$$
C_1=\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}+1\bigg)D,
$$
and for all $x\in\Sigma_{2k}(T)$,
\begin{align}
\frac{1}{C_2}\|x\|_r^q\leq\|Ax\|_p^q,
\end{align}
where
$$
C_2=\Bigg(\frac{2}{1-\beta}+\max\bigg\{\Big(\frac{|T^c|}{k}\Big)^q,1\bigg\}
\bigg(\Big(\frac{|T\cap K^c|}{k}\Big)^{1-q/r}\frac{2\beta}{1-\beta}+1\bigg)\Bigg)D.
$$

\item[(2)]If a matrix $A$ satisfies $t$-truncated $(l_r,l_q)-\text{Dantzig-selsector}$ sparse approximation property of order $k$ with $t=|T|$, constants $D\in(0,\infty)$ and $\beta\in(0,1)$, then
for all $x\in\Sigma_k(T)$,
\begin{align}
\frac{1}{C_1}\|x\|_r^q\leq\|A^*Ax\|_\infty^q,
\end{align}
and for all $x\in\Sigma_{2k}(T)$,
\begin{align}
\frac{1}{C_2}\|x\|_r^q\leq\|A^*Ax\|_\infty^q,
\end{align}
where $C_1$ and $C_2$ are the constants in above (1).
\end{theorem}
\begin{proof}
We only prove part (1).
Let $K$ denotes the index set of the $k$ largest (in magnitude) coefficients of $x_T$.

(a). First, we deal with $k$-sparse vector.
Take a $k$-sparse vector $x_T\in \mathbb{R}^n$, then $x_T=x_{K}$ and $\sigma_k(x_T)_q=\|x_{T\cap K^c}\|_q=0$. From $t$-truncated $(l_r,l_q)-l_p$ sparse approximation property, one can get
$$
\|x_T\|_r^q=\|x_K\|_r^q\leq D\|Ax\|_p^q.
$$
Similar to the \textbf{Step 5} of the proof of Theorem \ref{vectorstablerecovery}, we can get
\begin{align*}
\|x_{T^c}\|_{r}^q&\leq\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}\big(D\|Ax\|_p^q+\beta k^{q/r-1}\|x_{T\cap K^c}\|_q^q\big)\\
&=\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}D\|Ax\|_p^q.
\end{align*}
Therefore,
\begin{align*}
\|x\|_r^q&\leq\|x_T\|_r^q+\|x_{T^c}\|_r^q\leq D\|Ax\|_p^q+\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}D\|Ax\|_p^q\\
&=\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}+1\bigg)D\|Ax\|_p^q\\
&:=C_1\|Ax\|_p^q.
\end{align*}

(b). Next, we consider the $2k$-sparse vector. Take a $2k$-sparse vector $x_{T}\in\mathbb{R}^n$, we can write
$$
x_T=x_{K_1}+x_{K_2},
$$
where $K_1, K_2\subset T$ with $\|x_{K_j}\|_0\leq k$ for $j=1,2$ and $K_1\cap K_2=\emptyset$, then we have
\begin{align}\label{K1K2}
\|x_T\|_r^q\leq \|x_{K_1}\|_r^q+\|x_{K_2}\|_r^q.
\end{align}
The $t$-truncated $(l_r,l_q)-l_p$ sparse approximation property leads us to conclude that
\begin{align}\label{lrKiKj}
\|x_{K_i}\|_r^q\leq D\|Ax\|_p^q+\beta k^{q/r-1}\|x_{K_j}\|_q^q\leq D\|Ax\|_p^q+\beta\|x_{K_j}\|_r^q,
\end{align}
where $i,j\in\{1,2\}$ and $i\neq j$. Therefore, we can get
$$
\|x_{K_1}\|_r^q+\|x_{K_2}\|_r^q\leq 2D\|Ax\|_p^q+\beta(\|x_{K_1}\|_r^q+\|x_{K_2}\|_r^q),
$$
which implies that
\begin{align}\label{e9}
\|x_T\|_r^q\leq\|x_{K_1}\|_r^q+\|x_{K_2}\|_r^q\leq\frac{2D}{1-\beta}\|Ax\|_p^q.
\end{align}

On the other hand, similar to the \textbf{Step 5} of the proof of Theorem \ref{vectorstablerecovery}, we also can get
\begin{align*}
\|x_{T^c}\|_r^q\leq\max\Big\{\Big(\frac{|T^c|}{k}\Big)^q,1\Big\}\big(D\|Ax\|_p^q+\beta k^{q/r-1}\|x_{T\cap K^c}\|_q^q\big),
\end{align*}
and by (\ref{e9}), we get
\begin{align*}
\|x_{T\cap K^c}\|_q^q&\leq|T\cap K^c|^{1-q/r}\|x_{T\cap K^c}\|_r^q\leq|T\cap K^c|^{1-q/r}\|x_T\|_r^q\\
&\leq\frac{2D}{1-\beta}|T\cap K^c|^{1-q/r}\|Ax\|_p^q.
\end{align*}
Therefore, we can obtain a upper bound for $\|x_{T^c}\|_r^q$ as follows
\begin{align}\label{e10}
\|x_{T^c}\|_r^q&\leq\max\bigg\{\Big(\frac{|T^c|}{k}\Big)^q,1\bigg\}
\bigg(\Big(\frac{|T\cap K^c|}{k}\Big)^{1-q/r}\frac{2\beta}{1-\beta}+1\bigg)D\|Ax\|_p^q.
\end{align}

Therefore, combining (\ref{e9}) and (\ref{e10}), we can get
\begin{align*}
\|x\|_r^q&\leq\|x_T\|_r^q+\|x_{T^c}\|_r^q\\
&\leq\frac{2D}{1-\beta}\|Ax\|_p^q
+\max\bigg\{\Big(\frac{|T^c|}{k}\Big)^q,1\bigg\}
\bigg(\Big(\frac{|T\cap K^c|}{k}\Big)^{1-q/r}\frac{2\beta}{1-\beta}+1\bigg)D\|Ax\|_p^q\\
&\leq\Bigg(\frac{2}{1-\beta}+\max\bigg\{\Big(\frac{|T^c|}{k}\Big)^q,1\bigg\}
\bigg(\Big(\frac{|T\cap K^c|}{k}\Big)^{1-q/r}\frac{2\beta}{1-\beta}+1\bigg)\Bigg)D\|Ax\|_p^q\\
&:=C_2\|Ax\|_p^q.
\end{align*}
\end{proof}

\begin{remark}
When $p=2$ or $0<p\leq1$, and $r=2$, we can obtain from Theorem \ref{k2ksparsevector} that if measurement matrix $A$ has the $t$-truncated $(l_r,l_q)-l_p$ sparse approximation property or $t$-truncated $(l_r,l_q)-\text{Dantzig-selsector}$ sparse approximation property of order $k$ with $t=|T|$, constants $D\in(0,\infty)$ and $\beta\in(0,1)$, then the first inequality in the restricted isometry property of order $k$ and of order $2k$ hold for constants $\delta=1-1/{(C_1)^{p/q}}$ and $\delta=1-1/{(C_2)^{p/q}}$, respectively.
\end{remark}

\subsection{Restricted Isometry Property implies Truncated sparse approximation property \label{s3.2}}
\hskip\parindent

In this subsection, we will show that the truncated sparse approximation property of order $k$ can be deduced from the restricted 2-isometry property with $\delta_{tk}<\sqrt{(t-1)/t}$ for some $t\geq4/3$. And especially when $T^c=\emptyset$-the classic case, it shows us that the $(l_2,l_1)-l_2$ sparse approximation property of order $k$ and and $(l_2,l_1)-\text{Dantzig~selector}$ sparse approximation property of order $k$ is weaker than restricted 2-isometry property of order $tk$. Our main result can be stated as follows.

\begin{theorem}\label{RIPSRP}
If $A$ has restricted 2-isometry property of order $t(k+|T^c|)$ with $\delta_{t(k+|T^c|)}<\sqrt{(t-1)/t}$ for some $t\geq 4/3$, then
\begin{align*}
\|x_{K}\|_2&\leq\frac{2\sqrt{1+\delta}}{1-\delta^2}\|Ax\|_2+ \frac{\delta}{\sqrt{(t-1)(1-\delta^2)}}\frac{\sigma_k(x_T)_1}{\sqrt{k}}\\
&=:D_1\|Ax\|_2+\beta \frac{\sigma_k(x_T)_1}{\sqrt{k}}
\end{align*}
and
\begin{align*}
\|x_{K}\|_2&\leq\frac{2\sqrt{2(k+|T^c|)}}{1-\delta^2}\|A^*Ax\|_{\infty}+ \frac{\delta}{\sqrt{(t-1)(1-\delta^2)}}\frac{\sigma_k(x_T)_1}{\sqrt{k}}\\
&=:D_2\|A^*Ax\|_{\infty}+\beta \frac{\sigma_k(x_T)_1}{\sqrt{k}},
\end{align*}
where $T\subset\{1,\ldots,n\}$ is the any set with $|T|=t$, $K\subset T$ is the index set of the $k$ largest (in magnitude) coefficients of $x_T$.
\end{theorem}

\begin{proof}
Our proof adapts Fourcat's \cite[Theorem 5]{F2017} approach.
Let $K_0:=K\cup T^c$ and
$$
\alpha=\frac{\|x_{T\cap K^c}\|_1}{k+|T^c|},
$$
where $k+|T^c|=|K_0|$.
We partition the set $T\cap K^c$-complement of
$K\cup T^c$ as
$$
T\cap K^c=K'\cup K'',
$$
where
\begin{align*}
K'&:=\Big\{j\in T\cap K^c: |x_j|>\frac{\alpha}{t-1}\Big\},\\
K''&:=\Big\{j\in T\cap K^c: |x_j|\leq\frac{\alpha}{t-1}\Big\}.
\end{align*}
Denote that $k'=\|v_{K'}\|_0$, we can derive that $k'\leq (t-1)(k+|T^c|)$ from
$$
\alpha(k+|T^c|)=\|x_{T\cap K^c}\|_1\geq\|x_{K'}\|_1\geq k'\frac{\alpha}{t-1}.
$$
By
$$
\|x_{K''}\|_{\infty}\leq \frac{\alpha}{t-1}
$$
and
$$
\|x_{K''}\|_1=\|x_{T\cap K^c}\|_1-\|x_{K'}\|_1\leq \alpha(k+|T^c|)-\frac{k'\alpha}{t-1}=((t-1)(k+|T^c|)-k')\frac{\alpha}{t-1},
$$
we know that the vector $x_{K''}$ belongs to a scaled version of the polytope $\big((t-1)(k+|T^c|)-k'\big)\mathcal{B}^{l_1}(\alpha/(t-1))\cap \mathcal{B}^{l_\infty}(\alpha/(t-1))$. By sparse representation of a polytope in \cite[Lemma 1.1]{CZ2014}, this polytope can be represented as the convex hull of $\big((t-1)(k+|T^c|)-k'\big)$-sparse vectors:
$$
x_{K''}=\sum_{j=1}^\tau\rho_ju^j,
$$
where $u^j$ is $\big(\big(t-1)(k+|T^c|)-k'\big)$-sparse and
\begin{align*}
\sum_{j=1}^{\tau}&\rho_j=1,~0\leq\rho_j\leq1,j=1,\ldots,\tau\\
\text{supp}&(u^j)\subset \text{supp}(x_{K''})\\
\|u^j\|_1&=\|x_{K''}\|_1, \|u^j\|_{\infty}\leq \frac{\alpha}{t-1}.
\end{align*}
Hence,
\begin{align}\label{e6}
\|u^j\|_2\leq\|u^j\|_{\infty}\sqrt{\|u^j\|_0}\leq \frac{\alpha}{t-1} \sqrt{\big(t-1)(k+|T^c|)-k'}\leq\sqrt{\frac{k+|T^c|}{t-1}}\alpha.
\end{align}

We observe that
\begin{align}\label{e12}
\langle A(x_{K_0}&+x_{K'}),Ax\rangle\\
&=\frac{1}{4\delta}\sum_{j=1}^\tau\rho_j\Big(\|A\big((1+\delta)(x_{K_0}+x_{K'})+\delta
u^j\big)\|_2^2-\|A\big((1-\delta)(x_{K_0}+x_{K'})-\delta u^j\big)\|_2^2\Big).
\end{align}
Owing to
\begin{align*}
\|(1+\delta)(x_{K_0}+x_{K'})+\delta u^j\|_0&=\|(1-\delta)(x_{K_0}+x_{K'})-\delta u^j\|_0\\
&\leq (k+|T^c|)+k'+\big((t-1)(k+|T^c|)-k'\big)=t(k+|T^c|),
\end{align*}
therefore we take $\delta=\delta_{t(k+|T^c|)}$.

By $\|x_{K_0}+x_{K'}\|_0\leq (k+|T^c|)+k'\leq t(k+|T^c|)$,  we give a upper bound estimate for the left-hand side of (\ref{e12}) as follows
\begin{align*}
\langle A(x_{K_0}+x_{K'}),Ax\rangle \leq\|A(x_{K_0}+x_{K'})\|_2\|Ax\|_2\leq\sqrt{1+\delta}\|Ax\|_2\|x_{K_0}+x_{K'}\|_2
\end{align*}
or
\begin{align*}
\langle A(x_{K_0}+x_{K'}),Ax\rangle\leq\|x_{K_0}+x_{K'}\|_1\|A^*Ax\|_\infty\leq\sqrt{t(k+|T^c|)}\|A^*Ax\|_\infty\|x_{K_0}+x_{K'}\|_2.
\end{align*}

On the other hand, by restricted isometry property, the right-hand side of (\ref{e12}) is bounded from below by
\begin{align*}
\frac{1}{4\delta}&\sum_{j=1}^\tau\rho_j\Big((1-\delta)\big((1+\delta)^2\|x_{K_0}+x_{K'}\|_2^2+\delta^2\|u^j\|_2^2\big)
-(1+\delta)\big((1-\delta)^2\|x_{K_0}+x_{K'}\|_2^2+\delta^2 \|u^j\|_2^2\big)\Big)\\
&=\frac{1}{4\delta}\sum_{j=1}^N\rho_j\big(2\delta(1+\delta)(1-\delta)\|x_{K_0}+x_{K'}\|_2^2-2\delta^3\|u^j\|_2^2\big)\\
&\geq\frac{1-\delta^2}{2}\|x_{K_0}+x_{K'}\|_2^2-\frac{\delta^2}{2}\Big(\sqrt{\frac{k+|T^c|}{t-1}}\alpha\Big)^2\\
&=\frac{1-\delta^2}{2}\|x_{K_0}+x_{K'}\|_2^2-\frac{\delta^2}{2}\frac{\|x_{T\cap K^c}\|_1^2}{(t-1)(k+|T^c|)},
\end{align*}
where the last inequality follows by (\ref{e6}).

Combining the two bounds gives
\begin{align*}
\|x_{K_0}+x_{K'}\|_2^2-\frac{\delta^2}{(t-1)(1-\delta^2)}\Big(\frac{\|x_{T\cap K^c}\|_1}{\sqrt{k+|T^c|}}\Big)^2
\leq\frac{2\sqrt{1+\delta}}{1-\delta^2}\|Ax\|_2\|x_{K_0}+x_{K'}\|_2
\end{align*}
or
\begin{align*}
\|x_{K_0}+x_{K'}\|_2^2-\frac{\delta^2}{(t-1)(1-\delta^2)}\Big(\frac{\|x_{T\cap K^c}\|_1}{\sqrt{k+|T^c|}}\Big)^2
\leq\frac{2\sqrt{2(k+|T^c|)}}{1-\delta^2}\|A^*Ax\|_{\infty}\|x_{K_0}+x_{K'}\|_2,
\end{align*}
which is equivalent to
\begin{align*}
\Big(\|x_{K_0}+x_{K'}\|_2-\frac{\sqrt{1+\delta}}{1-\delta^2}\|Ax\|_2\Big)^2
\leq\frac{\delta^2}{(t-1)(1-\delta^2)}\Big(\frac{\|x_{T\cap K^c}\|_1}{\sqrt{k+|T^c|}}\Big)^2
+\frac{1+\delta}{(1-\delta^2)^2}\|Ax\|_2^2
\end{align*}
or
\begin{align*}
\Big(\|x_{K_0}+x_{K'}\|_2-\frac{\sqrt{2(k+|T^c|)}}{1-\delta^2}\|A^*Ax\|_{\infty}\Big)^2
\leq\frac{\delta^2}{(t-1)(1-\delta^2)}\Big(\frac{\|x_{T\cap K^c}\|_1}{\sqrt{k+|T^c|}}\Big)^2
+\frac{2(k+|T^c|)}{(1-\delta^2)^2}\|A^*Ax\|_2^2.
\end{align*}

As a result, we obtain
\begin{align*}
\|x_{K}\|_2\leq\|x_{K_0}\|_2\leq\|x_{K_0}+x_{K'}\|_2
&\leq\frac{2\sqrt{1+\delta}}{1-\delta^2}\|Ax\|_2+ \frac{\delta}{\sqrt{(t-1)(1-\delta^2)}}\frac{\sigma_k(x_T)_1}{\sqrt{k+|T^c|}}\\
&\leq\frac{2\sqrt{1+\delta}}{1-\delta^2}\|Ax\|_2+ \frac{\delta}{\sqrt{(t-1)(1-\delta^2)}}\frac{\sigma_k(x_T)_1}{\sqrt{k}}\\
&=:D_1\|Ax\|_2+\beta \frac{\sigma_k(x_T)_1}{\sqrt{k}}
\end{align*}
and
\begin{align*}
\|x_{K}\|_2\leq\|x_{K_0}\|_2\leq\|x_{K_0}+x_{K'}\|_2
&\leq\frac{2\sqrt{2(k+|T^c|)}}{1-\delta^2}\|A^*Ax\|_{\infty}+ \frac{\delta}{\sqrt{(t-1)(1-\delta^2)}}\frac{\sigma_k(x_T)_1}{\sqrt{k+|T^c|}}\\
&\leq\frac{2\sqrt{2(k+|T^c|)}}{1-\delta^2}\|A^*Ax\|_{\infty}+ \frac{\delta}{\sqrt{(t-1)(1-\delta^2)}}\frac{\sigma_k(x_T)_1}{\sqrt{k}}\\
&=:D_2\|A^*Ax\|_2+\beta \frac{\sigma_k(x_T)_1}{\sqrt{k}},
\end{align*}
which are the desired inequalities with
$$
\beta=\frac{\delta}{\sqrt{(t-1)(1-\delta^2)}}<1
$$
when $\delta_{t(k+|T^c|)}=\delta <\sqrt{\frac{t-1}{t}}$, and with
$$
D_1=\frac{2\sqrt{1+\delta}}{1-\delta^2},
D_2=\frac{2\sqrt{2(k+|T^c|)}}{1-\delta^2}.
$$
\end{proof}

From Theorems \ref{RIPSRP} and Theorem \ref{vectorstablerecovery}, we can obtain that under the condition $\delta_{t(k+|T^c|)}<\sqrt{\frac{t-1}{t}}$, the
stable recovery holds as follows.

\begin{theorem}\label{vectorstabilityrobustnessestimate}
Consider the signal model (\ref{systemequationsnoise}) with $\|z\|_2\leq\varepsilon$ and let $\hat{x}^{l_2}$ is the minimizer of (\ref{Truncatedq}) with
$\mathcal{B}=\mathcal{B}^{l_2}(\eta)$ defined in (\ref{lpboundednoise}) for some $\eta\geq\varepsilon$. If measurement matrix $A$ has restricted isometry property of order $t(k+|T^c|)$ with $\delta_{t(k+|T^c|)}<\sqrt{(t-1)/t}$ for some $t\geq4/3$, then
\begin{align*}
\|\hat{x}^{l_2}-x\|_2&\leq
\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big),1\Big\}+1+\Big(\frac{|T|-k}{k}\Big)^{1/2}\bigg)\frac{D_1}{1-\beta}(\varepsilon+\eta)\nonumber\\
&\hspace*{12pt}+\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big),1\Big\}+1+\Big(\frac{|T|-k}{k}\Big)^{1/2}\bigg)\frac{2\beta}{1-\beta}
k^{-1/2}\sigma_k(x_T)_1,
\end{align*}
where $D_1$ is the constant in above Theorem \ref{RIPSRP}.

Consider the signal model (\ref{systemequationsnoise}) with $\|A^*z\|_\infty\leq\varepsilon$ and let $\hat{x}^{DS}$ is the minimizer of (\ref{Truncatedq}) with $\mathcal{B}=\mathcal{B}^{DS}(\eta)$ defined in (\ref{Dantzigselectornoise}) for some $\eta\geq\varepsilon$. If measurement matrix $A$ has restricted isometry property of order $t(k+|T^c|)$ with $\delta_{t(k+|T^c|)}<\sqrt{(t-1)/t}$ for some $t\geq4/3$, then
\begin{align*}
\|\hat{x}^{l_2}-x\|_2&\leq
\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big),1\Big\}+1+\Big(\frac{|T|-k}{k}\Big)^{1/2}\bigg)\frac{D_1}{1-\beta}(\varepsilon+\eta)\nonumber\\
&\hspace*{12pt}+\bigg(\max\Big\{\Big(\frac{|T^c|}{k}\Big),1\Big\}+1+\Big(\frac{|T|-k}{k}\Big)^{1/2}\bigg)\frac{2\beta}{1-\beta}
k^{-1/2}\sigma_k(x_T)_1,
\end{align*}
where $D_2$ is the constant in above Theorem \ref{RIPSRP}.
\end{theorem}

\begin{remark}
It should be point out that Theorem \ref{RIPSRP} and Theorem \ref{vectorstabilityrobustnessestimate} also hold for $1<t<4/3$ with the same proof. However the bound $\sqrt{(t-1)/t}$ is not sharp for $1<t<4/3$. See Cai and Zhang's \cite{CZ2014} for further discussions.
\end{remark}

\begin{remark}
We point out that if we take $T^c=\emptyset$, Theorem \ref{RIPSRP} implies that if  $A$ has restricted 2-isometry property of order $tk$ with $\delta_{tk}<\sqrt{(t-1)/t}$ for some $t\geq 4/3$ , then $A$ satisfies $(l_2,l_1)-l_2$ sparse approximation property of order $k$ certain constants $0<\beta<1$ and $D_1>0$,  and $(l_2,l_1)-\text{Dantzig~selector}$ sparse approximation property of order $k$ with certain constants $0<\beta<1$ and $D_2>0$, i.e $l_2$-robust null space property of order $k$ \cite{F2014}. This shows that the $(l_2,l_1)-l_2$ sparse approximation property of order $k$ and and $(l_2,l_1)-\text{Dantzig~selector}$ sparse approximation property of order $k$ is weaker than restricted 2-isometry property of order $tk$.
\end{remark}

Combining this result with \cite[Theorem 1.1]{S2011}, we get following robust estimate, which is same as \cite[Theorem 2.1]{CZ2014} but with different constants.

\begin{theorem}\label{VS-Cai-Zhang-2014}
Consider the signal model (\ref{systemequationsnoise}) with $\|z\|_2\leq\varepsilon$ and let $\hat{x}^{l_2}$ is the minimizer of (\ref{lqminimization}) with $\mathcal{B}=\mathcal{B}^{l_2}(\eta)$ defined in (\ref{lpboundednoise}) for some $\eta\geq\varepsilon$. If measurement matrix $A$ has restricted 2-isometry property of order $tk$ with $\delta_{tk}<\sqrt{(t-1)/t}$ for some $t\geq4/3$, then
\begin{align*}
\|\hat{x}^{l_2}-x\|_2&\leq
\frac{2\sqrt{1+\delta}\big(3\sqrt{(t-1)(1-\delta^2)}+\delta\big)}{(1-\delta^2)(\sqrt{(t-1)(1-\delta^2)}-\delta)}(\varepsilon+\eta)\\
&\hspace*{12pt}+\frac{\big(\sqrt{(t-1)(1-\delta^2)}+\delta\big)^2}{\sqrt{(t-1)(1-\delta^2)}\big(\sqrt{(t-1)(1-\delta^2)}-\delta\big)}\frac{2\sigma_k(x)_1}{\sqrt{k}}.
\end{align*}

Consider the signal model (\ref{systemequationsnoise}) with $\|A^*z\|_\infty\leq\varepsilon$ and let $\hat{x}^{DS}$ is the minimizer of (\ref{lqminimization}) with $\mathcal{B}=\mathcal{B}^{DS}(\eta)$ defined in (\ref{Dantzigselectornoise}) for some $\eta\geq\varepsilon$. If measurement matrix $A$ has restricted 2-isometry property of order $tk$ with $\delta_{tk}<\sqrt{(t-1)/t}$ for some $t\geq4/3$, then
\begin{align*}
\|\hat{x}^{DS}-x\|_2&\leq
\frac{2\sqrt{2k}\big(3\sqrt{(t-1)(1-\delta^2)}+\delta\big)}{(1-\delta^2)(\sqrt{(t-1)(1-\delta^2)}-\delta)}(\varepsilon+\eta)\\
&\hspace*{12pt}+\frac{\big(\sqrt{(t-1)(1-\delta^2)}+\delta\big)^2}{\sqrt{(t-1)(1-\delta^2)}\big(\sqrt{(t-1)(1-\delta^2)}-\delta\big)}\frac{2\sigma_k(x)_1}{\sqrt{k}}.
\end{align*}
\end{theorem}

\begin{remark}
It also should be point out that Zhang and Li \cite{ZL2017} gave a complete answer to the
conjecture on restricted isometry property constants $\delta_{tk}~(0<t<4/3)$ which was proposed by Cai and Zhang \cite{CZ2014}.
They showed that when $0<t<4/3$, the condition $\delta_{tk}<t/(4-t)$ is sufficient to guarantee the exact recovery for all
$k$-sparse signals in the noiseless case via the constrained $\ell_q$-norm minimization for $0<q\leq 1$ and these bounds are also sharp.
\end{remark}

We propose the following conjecture.

\begin{conjecture}\label{SRPweakerRIP}
If $A$ has restricted 2-isometry property of order $tk$ with $\delta_{tk}<(4-t)/t$ for some $t\in(0,4/3)$ , then $A$ satisfies $(l_2,l_1)-l_2$ sparse approximation property of order $k$ with certain constants $0<\gamma<1$ and $0<D_3<\infty$,  and  $(l_2,l_1)-\text{Dantzig~selector}$ sparse approximation property of order $k$ with certain constants $0<\gamma<1$ and $0<D_4<\infty$.
\end{conjecture}

\begin{remark}
We should point out that the above Theorem \ref{RIPSRP}, Theorem \ref{vectorstabilityrobustnessestimate} Theorem \ref{VS-Cai-Zhang-2014} and Theorem \ref{k2ksparsevector} also hold for matrix case.
\end{remark}

\section{Conclusions and Discussion \label{s4}}
\hskip\parindent

To solve truncated norm minimization (\ref{Truncatedq}) or (\ref{MatrixTruncatedq}) with noise, we introduce truncated sparse approximation property, and obtain the stable recovery of signals and matrices under the truncated sparse approximation property (see Theorem \ref{vectorstablerecovery} and Theorem \ref{Matrixstablerecovery}). When we investigate the relationship between the truncated sparse approximation property and  restricted isometry property, we find that if a measurement matrix satisfies truncated sparse approximation property of order $k$, then the first inequality in restricted isometry property of order $k$ and of order $2k$ hold for certain different constants $\delta_{k}$ and $\delta_{2k}$, respectively (see Theorem \ref{k2ksparsevector}). And we also find that the truncated sparse approximation property of order $k$ can be deduced from the restricted isometry property with $\delta_{tk}<\sqrt{(t-1)/t}$ for some $t\geq4/3$ (see Theorem \ref{RIPSRP}). And especially when $T^c=\emptyset$-the classic case, it shows us that the $(l_2,l_1)-l_2$ sparse approximation property of order $k$ and and $(l_2,l_1)-\text{Dantzig~selector}$ sparse approximation property of order $k$ is weaker than restricted 2-isometry property of order $tk$. And combining this result with \cite[Theorem 1.1]{S2011}, we get the stable recovery of signals and matrices under the restricted isometry property of order $tk$ with $\delta_{tk}<\sqrt{(t-1)/t}$ for some $t\geq 4/3$ (see Theorem \ref{VS-Cai-Zhang-2014}), which is the same as \cite[Theorem 2.1]{CZ2014} but with different constants. Therefore, these results in our paper may guide the practitioners to apply robust null space property in compressed sensing, low-rank matrix recovery and sparse phase retrieval, especially in truncated norm minimization problem.

However, Zhang and Li \cite{ZL2017} showed that for $0<t<4/3$, the condition $\delta_{tk}<t/(4-t)$ is sufficient to guarantee the exact recovery for all $k$-sparse signals in the noiseless case via the constrained $l_q$-norm minimization and these bounds are also sharp. Whether the truncated sparse approximation property of order $k$ can be deduced from the restricted isometry property with $\delta_{tk}<t/(4-t)$ for some $0<t<4/3$? But our method in Theorem \ref{RIPSRP} may not fit for this question. This is one direction of our future research (see Conjecture \ref{SRPweakerRIP}).
And another question is there exist't any algorithm for computing truncated $\ell_q$ minimization (\ref{Truncatedq}) with $\mathcal{B}=\mathcal{B}^{DS}(\eta)$ or $\mathcal{B}=\mathcal{B}^{l_q}(\eta)$ for $0<q\leq 1$ (see Remark \ref{Algorithm})? This is anther direction of our future research.

\textbf{Acknowledgement}: Wengu Chen is supported by National Natural Science Foundation of China (No. 11371183).


TITLE: Determining $a+b$
QUESTION [0 upvotes]: The sum of the digits of $x$ is $17$. When $(x^3+x^5)$ and $(x^2+7!)$ are divided by $3$ and $9$, the remainder outcomes as $a$ and $b$ respectively. Then determine $a+b$

I couldn't think of any way to solve this problem. Could I get help?
Regards!

REPLY [0 votes]: THe is a well known (to some) theorem that if $s(x) = $ sum of the digits and $a \equiv x \mod n$ means that $a$ and $x$ have the same remainder when divided by $n$ that:
$x \equiv s(x) \mod 3$
and $x \equiv s(x) \mod 9$.
Always.  For all $x$.
So if $s(x) = 17$ then $s(x) \equiv 2\equiv -1 \mod 3$ and $s(x) \equiv 8 \equiv -1 \mod 9$.  (Note:  $-1 = -1*3 + 2$ and $-1 = -1*9 + 8$ so $-1$ has remainder $2$ when divided by $3$ and $-1$ has remainder $8$ when divided by $9$
Now $7! = 1* 2*3*4*5*6*7 \equiv 0 \mod 3$ and $7! \equiv 0 \mod 9$.
And "remainder arithmetic" is consistent under addition.  If $a$ has remainder $a'$ and $b$ has remainder $b'$ then $a + b$ will have the same remainder as $a' + b'$.  So "remainder arithmetic" is consistent under subtraction (the inverse of addition) and multiplication (addition multiple times), NOT division, and exponential powers (multplication multiple times).
.....
So $s(x) =17\equiv -1 \mod 3,9$ then $x^3 + x^5 \equiv (-1)^3 + (-1)^5 = -1 -1 \equiv -2 \mod 3,9$ and $x^3 + x^5 \equiv -2\equiv 1 \mod 3$ and $x^3 + x^5 \equiv -2\equiv 7 \mod 9$.
And $x^2 + 7! \equiv (-1)^2 + 0 \equiv 1 \mod 3,9$.
Now I do not know what "When (x3+x5) and (x2+7!) are divided by 3 and 9, the remainder outcomes as a and b respectively" is supposed to mean.
$x^3 + x^5$ when divided by $3$ has the remainder $1$ and $x^3 + x^5$ when divide by $9$ has remainder $7$.  And $x^2 + 7!$ when divided by $3$ or $9$ has remainder $1$.  So I guess $a$ and $b$ are supposed to be $1$ and $7$ and $a+b=8$.
I guess.  The question was not very clear.


TITLE: word problem from kangaroo math contest
QUESTION [1 upvotes]: Albert and Ben each have several marbles. if Albert gives 6 of his
  marbles to Ben, they will have the have the same amount of marbles. if
  Albert gives half of his marbles to Ben, then Ben will have 8 more
  marbles then Albert will have. how many marbles in total do they have?

The correct answer is 28.
When I solved it, I got 14 marbles for Albert and 8 for Ben which in total is 22 but it wasn't any of the 5 options so I want to know how they got 28.
How I tried solving it:
first, I put a random number of marbles that Albert could have. lets say I put 18. then I subtracted 6 from it to get the number of marbles Ben could have as it says in the first statement $(18-6=12).$ After that, I divided the amount of marbles Albert has by 2 $(18/2=9).$ Then I added 9 to 12 to get the amount of marbles Ben could have. Then I subtracted 9 from 18 and I got 9. If that subtracted from 12 would give a number less then 8, I would lower the amount of marbles Albert could have in the beginning and start over. If it was higher then 8, I would up the amount Albert could have in the beginning and start over. I would do this until it matched the 2 statements in the question.

REPLY [1 votes]: Let set $x$ the number of Albert's marbles and $y$ the number of Ben's marbles. Since we have two unknowns, we need two equations. Then the statements gives us
$$x-6=y+6$$
$$\frac x2+8=y+\frac x2$$
Solving for $x$ and $y$, we have
$$y=8\text{ and }x=20$$
Thus the marbles' total is $28$.

Simplifier proof would be the second statement give us how manyarbles Ben have. Since Albert splits His marbles in two and give half to Ben, the difference between the two is the amount Ben has. Then Ben has $8$ marbles and the other value follows from the first statement.


TITLE: Reference: probability distribution of first meeting time of two random walks on a cycle graph
QUESTION [1 upvotes]: I am looking for a reference or derivation for the following question:
Consider a cycle graph $G$ with $N$ vertices (see example here). Let two independent continuous-time random walkers$^\star$ start on node $i$ and node $j$. Let $T$ be the time when the two walkers meet for the first time.
What will be the probability density function of $T$?
I am looking for the exact expression of that pdf for finite $N$. I am sure this is a well known question with a precise formula but I have not been able to find a clear reference solving it. This is a new field for me so perhaps I am using the wrong vocabulary? With the hope that this post will help. Thanks!
($^\star$: each walker jumps to a neighboring vertex (chosen at random) with rate one.)

REPLY [0 votes]: Assume that $i<j.$ You can reduce this to the following simpler-looking question: Consider a continuous-time RW on the integers, moving at rate two, started at $k:=j-i$. Let $T$ be the hitting time of $\{0,N\}$ by this walk, also known as as the exit time from $[1,N-1]$. Let $\tau$ denote  the hitting time of $\{0,N\}$ by discrete-time random walk. The distribution of $\tau$   can be determined from the arguments in Chapter 21 of [1]. (Spitzer gives the general method, and then provides all the details only for the case $k=N/2$.) Then you can deduce the distribution of $T$ via
$$P_k[T>q] = \sum_n P[{\rm Poisson}(2q)=m] \cdot P_k[\tau>m] \,.$$
See also [2].
[1] Spitzer, Frank. Principles of random walk. GTM Vol. 34. Second edition, Springer.
[2]https://www.researchgate.net/publication/254211645_Exit_times_for_a_class_of_random_Walks_Exact_distribution_results


TITLE: How to find coordinates of vertices of an integer triangle?
QUESTION [0 upvotes]: We know that, there exist integer triangles with three rational medians. The smallest has sides ($68, 85, 87$). Others include ($127, 131, 158$), ($113, 243, 290$), ($145, 207, 328$) and ($327, 386, 409$). For example, How to find coordinates of vertices of an integer triangle has sides ($68, 85, 87$)? Please help me to get them. I don't know how to start?

REPLY [1 votes]: I don't see what rational medians has to do with it. If there is a triangle with sides $a,b,c$ (integer or not), you can put one vertex at $(0,0)$, a second one at $(a,0)$, and then the third at $(x,y)$, and solve the equations $x^2+y^2=b^2$, $(x-a)^2+y^2=c^2$.


TITLE: Rules for modulus of a (|a|)?
QUESTION [0 upvotes]: So I am wondering about this statement:
$|a| = a$ if $a \le 0$ and $-a$ if $a<0$
Why is it $-a$ if $a<0$? Shouldn't the modulus always be positive?

REPLY [1 votes]: It might help to not think of "$-a$" as a negative number, because its sign depends on what $a$ actually is. You might rather think of $-a$ as meaning "the opposite of $a$" or as "the additive inverse of $a$."
The opposite of $1$ is $-1$ since $1\ + \ -1 = 0$.
The opposite of $-2$ is $2$ since $-2\ + \ 2 = 0$.
The opposite of $0$ is $0$ since $0\ + \ 0 = 0$.
What $|a|$ actually is, is the distance the number $a$ is from $0$. Distance is never negative. If $a$ is negative then it lies a distance of $|a|=-a$ from $0$. If it is positive it lies a distance of $|a|=a$ from $0$.


TITLE: Two basis for a vector Space $V$ has the same coordinates. Does that follow both basis are identical?
QUESTION [1 upvotes]: Let $\beta_{1} = \{v_1,v_2,\ldots,v_n\}$ and $\beta_{2} = \{u_1,u_2,\ldots,u_n\}$ be two bases for some vector space $V$. If the coordinates for every vector $x\in V$ are identical with respect to both bases, does it follow that $v_i = u_i$ for all $i=1,2,\ldots, n$?
Since both coordinates are identical to each other, does that not force $v_i = u_i$? Am I approaching this right?

REPLY [0 votes]: Indeed, since  in basis $\beta_1$, each $v_i$ has coordinates $(0,\dots,0,\underset{\substack{\uparrow\\i\text{-th}\\ \text{coordinate}}}{1},0,\dots,0)$, and it has the same coordinate in basis $\beta_2$.


TITLE: What categorical property of monoidal categories picks out the ones with duals?
QUESTION [18 upvotes]: Recall that a monoidal category $\mathcal C$ is rigid if every object $X\in \mathcal C$ has both left and right duals, i.e. objects $X^l$ and $X^r$ with maps $X^l \otimes X \to \mathbf 1 \to X \otimes X^l$ and $X \otimes X^r \to \mathbf 1 \to X^r \otimes X$ satisfying certain equations.  It is a fundamental fact about monoidal categories that "having a left dual" and "having a right dual" are properties of an object, not data: given $X$, the objects $X^l$ and $X^r$, if they exist, are uniquely determined up to unique isomorphism.  As such, for a monoidal category itself to be rigid is also property --- the only data is the data of being monoidal.
This should remind you of groups.  Given a monoid $G$, an element $x\in G$ is invertible if there are elements $x^l$ and $x^r$ and equalities $x^l x = 1 = x x^r$.  (Undergraduate exercise: $x^l = x^r$.)  Being invertible is property.  A monoid $G$ is a group if every element therein is invertible.  Thus this too is a property.
In some cases (e.g. algebraic geometry) you don't always want to think about the elements of a group $G$.  Fortunately, there is a very nice way to say when a monoid is a group that does not directly refer to invertibility of elements.  Let $G$ be a monoid and consider the map $G \times G \to G\times G$ (a map of underlying spaces, not of groups) that takes $(x,y)$ to $(x,xy)$.  The monoid $G$ is a group iff this map is an isomorphism (of underlying spaces).

Is there a similar characterization of when a monoidal category is rigid?  Something like "consider the map $\mathcal C \times \mathcal C \to \mathcal C \times \mathcal C$, and ask that it be a left adjoint"?

REPLY [8 votes]: The notion of rigidity can be defined for any pseudomonoid in a monoidal proarrow equipment.  See for instance Dualizations and Antipodes by Day, McCrudden, and Street (although they work only with monoidal bicategories and don't make the equipments explicit).


TITLE: A general solution to $\min_{v\in L^2(0,1)} \|v-w\|^2_{L(0,1)}$ s.t. $v(x) \geq 0 $ almost everywhere
QUESTION [1 upvotes]: As the title states, I need to find a solution to
$$\min_{v\in L^2(0,1)} \|v-w\|^2_{L(0,1)}$$
s.t. $v(x) \geq 0  $ almost everywhere,
where  $w \in L^2(0,1)$ is given.
$L^2(0,1)$ is the lebesgue space
I know that there is a solution if $v$ was bounded to a convex and bounded subset of $L^2(0,1)$ and there were no additional constraints.
So my idea was to somehow put the constraint $v(x) \geq 0$ into the set over which we minimize since $ L^2(0,1)$ is allready a convex set(right?). However I do not really seem to get far with this.

REPLY [1 votes]: Hint :
$$||v-w||^{2}_{L^2(0,1)}=\int_{\{x \in(0,1),w(x) \ge 0 \}} |v(x)-w(x)|^2dx+\int_{\{x \in(0,1),w(x) < 0 \}} |v(x)-w(x)|^2dx.$$
How would you chose $v$ on $\{x \in(0,1),w(x) \ge 0 \}$ such that $\int_{\{x \in(0,1),w(x) \ge 0 \}} |v(x)-w(x)|^2dx$ is minimal ? And what about the other set ?


TITLE: Centralizer of one element on a compact connected Lie group
QUESTION [10 upvotes]: Exercise 16.2 from Daniel Bump - Lie Groups.
Let $G$ be a compact connected Lie group and let $g\in G$. Show that
the centralizer $C_{G(g)}$ of $g$ is connected.
I have some problems verifying this, i have tried to use that in that case the exponential map is surjective, and things of maximal torus, but i have not achieved it, i would appreciate some answer.

REPLY [3 votes]: This is not true in general. Consider $SO(3)$ and the matrix $$ \begin{bmatrix}
  1 & 0 & 0\\ 0 & -1 & 0 \\ 0&0&-1
\end{bmatrix} $$
Then $C_G(g)=\left\{ \begin{bmatrix}
  a & 0 & 0\\ 0 & \pm \cos \theta & \mp \sin \theta \\ 0&\sin\theta&\cos\theta
\end{bmatrix}: a\in \{\pm 1\}, \theta\in \mathbb{R}  \right\}   $.
We can fix the problem statement by adding that $G$ is simply connected. Then we can argue using a long exact sequence in homotopy groups.


TITLE: What is the function $f(x)$ which is differentiable everywhere and $f(x-1)f(x-2)+1=f(x)$?
QUESTION [11 upvotes]: What is the function $f(x)$ which is differentiable everywhere and $f(x-1)f(x-2)+1=f(x)$ and $f(1)=f(2)=1$ ?

I've been wondering about this problem for about $1 \frac{1}{2}$ years.
I don't know the tools to solve this problem. So, if you could show me how to find a solution, I would like that.
I found the values of $f(x)$ from $0$ to $10$:
$$0,1,1,2,3,7,22,155,3411,528706,1803416167,\dots,f(n)$$
I realized that at $f(-1)$ can't be found just using $f(x-1)f(x-2)+1=f(x)$ because $n\times f(0)=f(1)$ has infinite solutions. $f(-1)$ can't be zero because then $f(-2)$ wouldn't be defined because $n\times 0=-1$. So maybe if I add $f(x)$ must differentiable everywhere I could get an answer.

REPLY [2 votes]: I will prove the
Statement
There is no continuous function $f : \mathbb{R} \rightarrow \mathbb{R}$ such that it satisfies following conditions:

$\exists x \in \mathbb{R}$ s.t. $f\left(x\right) = 0$;
$\forall x \in \mathbb{R}$
$$ f\left(x - 1\right)f\left(x\right) + 1 = f\left(x + 1\right)$$

Proof
Assume that there is such $f$. Let $\mathbb{U}$ be the set of zeros of $f$. $\mathbb{U}$ is nonemtpy.
Let $u \in \mathbb{U}$. Then we have that
$$ f\left(u - 2\right)f\left(u - 1\right) = -1$$
Meaning that both $f\left(u - 2\right)$ and $f\left(u - 1\right)$ are nonzero and have different signs. By continuity there exists
$$\mathbb{U} \ni u' \in \left(u - 2, u - 1\right)$$
Thus we have shown that for any $x \in \mathbb{R}$ there is $u \in \mathbb{U}$ such $u < x$.
If $u \in \mathbb{U}$, then we have the following equalities:
$$\begin{align*}
f\left(u + 0\right) &= 0 \\
f\left(u + 1\right) &= 1 \\
f\left(u + 2\right) &= 1 \\
f\left(u + 3\right) &= 2 \\
f\left(u + n\right) &= a_{n + 1},\quad n \in \mathbb{N} \tag{1} \label{u+n}
\end{align*}$$
, where $a_{n}$ defined here. From this sequence we only need to know that $a_{n}$ is non-decreasing and
$$ \lim\limits_{n \rightarrow \infty} a_{n} = +\infty \tag{2} \label{a_n}$$
By the Weierstrass theorem $f$ reaches its maximum $\mathsf{M} \in \mathbb{R}$ on $\left[0, 1\right]$. By \eqref{a_n} we can find $n \in \mathbb{N}$ such that $a_{n} > \mathsf{M}$. Then we find $u \in \mathbb{U}$ and $m \in \mathbb{N}$ s.t. $-m \leq u \leq -m + 1 \leq -n$. It follows that $u + m \in \left[0, 1\right]$ and $m > n$. But by \eqref{u+n}
$$\begin{align*} \mathsf{M} &\geq f\left(u + m\right) \\
&\geq a_{m + 1} \\
&\geq a_{n} \\
&> \mathsf{M} \end{align*}$$
This completes the proof.
It follows that there is no function you are looking for, if it's defined like $f : \mathbb{R} \rightarrow \mathbb{R}$.
P. S. English is not my native language. I apologize for any possible mistakes when writing the answer in English.


TITLE: finding tangents where the curve meets itself by solving two equations with two variables
QUESTION [1 upvotes]: I was asked to finn the equation of the tangents  where the curve
$x=t^2 - t$
$y=t^3-3t+1$
meets itself. So first I need to know where the curve meets itself by finding two values of the parameter $t_0$ and $t_1$ such that
$t_{0}^2 - t_0=t_{1}^2 - t_1$
$t_{0}^3-3t_0+1=t_{1}^3-3t_1+1$
Fron the first one I solve for $t_0$ using the quadratic formula but thn substituting in the second one I get nothing. I appreciate any hint

REPLY [4 votes]: Hint:
(I use $t=t_0$ and $s=t_1$). For the $x$ coordinate :
$$
t^2-t=s^2-s \iff  (s-t)(s+t-1)=0
$$
for $s\ne t$ this means $s=1-t$, so, for the $y$ coordinate :
$$
t^3-3t+1=s^3-3s+1 \iff t^3-3t+1=(1-t)^3+3(1-t)+1
$$
solve for $t$ the equation:
$$
t^3-3t+1-(1-t)^3-3(1-t)-1=0 \iff (2t-1)(t+1)(t-2)=0
$$
and test the solutions that really gives the double point.


TITLE: Why $\gcd(b,qb+r)=\gcd(b,r),\,$ so $\,\gcd(b,a) = \gcd(b,a\bmod b)$
QUESTION [44 upvotes]: Given: $a = qb + r$. Then it holds that $\gcd(a,b)=\gcd(b,r)$. That doesn't sound logical to me. Why is this so?

Addendum by LePressentiment on 11/29/2013: (in the interest of http://meta.math.stackexchange.com/a/4110/53259 and averting a duplicate)
What's the intuition behind this result? I only recognise the proof and examples solely due to algebraic properties and formal definitions; I'd like to apprehend the result naturally.

REPLY [2 votes]: Let
$$a = qb + r \implies a\equiv r (\text{ mod }b)\implies r = a\text{ mod }b$$
Bey GCD recursion theorem we have:
$$\gcd\big(a, b\big) = \gcd\big(a, a\text{ mod } b\big)$$
Therefore

$$\gcd\big(a, b\big) = \gcd\big(a, a\text{ mod } b\big) = \gcd\big(a, r\big)$$

See reference

Bibliographic reference:
Thomas H. Cormen (2009). Introduction to Algorithms 3rd, 934.


TITLE: Chemical Potential of Ideal Fermi Gas
QUESTION [5 upvotes]: In Wikipedia's article on Fermi Gases, they have the following equation for the chemical potential:

$$\mu = E_0 + E_F \left[ 1- \frac{\pi ^2}{12} \left(\frac{kT}{E_F}\right) ^2 - \frac{\pi^4}{80} \left(\frac{kT}{E_F}\right)^4 + \cdots \right]$$
  where $E_0$ is the potential energy per particle, $k$ is the Boltzmann constant and $T$ is the temperature.

I don't understand how they get the third term, particularly the 1/80 factor. I've often seen this equation expressed just to the tau^2 term, and I understand how to get the 1/12 factor from a binomial expansion of
$$\left( 1 + \frac{\pi^{2}}{8} \left(\frac{\tau}{E}\right)^{2}\right)^{-2/3} $$
However, I've tried continuing the binomial expansion and cannot figure out why the factor is 1/80.

REPLY [2 votes]: I not sure how you obtained the last expression. The standard Sommerfeld expansion (for details, see e.g. Ashcroft & Mermin) gives a slightly different result, which is
$$
E_{F} \approx \mu\left[1+\frac{\pi^{2}}{8}\left(\frac{k_{B}T}{\mu}\right)^{2}\,\right]^{2/3} \approx \mu\left[1+\frac{\pi^{2}}{12}\left(\frac{k_{B}T}{\mu}\right)^{2}\right]
$$
to leading non-trivial order in $k_{B}T/\mu$, i.e., $O\big((k_{B}T/\mu)^{2}\big)$.
(I have set $E_{0}=0$ in the expression from Wikipedia.)
We can invert this relation by substituting  $\mu = E_{F}\left[1 + c_{2} (k_{B}T/E_{F})^{2} + \cdots \right]$ into the above. That is,
$$
E_{F} = E_{F}\left[1 + c_{2} (k_{B}T/E_{F})^{2} + \cdots \right]\left\{1+\frac{\pi^{2}}{12}\left(\frac{k_{B}T}{E_{F}}\right)^{2}\left[1 + c_{2} (k_{B}T/E_{F})^{2} + \cdots\right]^{-2}\right\}.
$$
Comparing the zeroth order terms in $k_{B}T/E_{F}$ on both sides of the above equation, we simply obtain $E_{F}=E_{F}$. Comparing the second order terms, we have $0 = \frac{\pi^{2}}{12} + c_{2}$. Hence
$$
\mu = E_{F}\left[1-\frac{\pi^{2}}{12}\left(\frac{k_{B}T}{E_{F}}\right)^{2}\right]
$$
up to $O\Big((k_{B}T/E_{F})^{2}\Big)$.
To determine the next-order correction to $\mu$, you should include one higher order term in the Sommerfeld expansion, which gives
$$
E_{F} \approx \mu\left[1+\frac{\pi^{2}}{8}\left(\frac{k_{B}T}{\mu}\right)^{2}+\frac{7\pi^{4}}{640}\left(\frac{k_{B}T}{\mu}\right)^{4}\,\right]^{2/3}.
$$
Expanding this up to $O\big((k_{B}T/\mu)^{4}\big)$, then substituting $\mu = E_{F}\left[1 + c_{2} (k_{B}T/E_{F})^{2} + c_{4} (k_{B}T/E_{F})^{4}+\cdots\right]$ (where we have already determined $c_{2}$ before) into it, and then matching the coefficients of both sides up to $O\Big((k_{B}T/E_{F})^{4}\Big)$ will lead to the desired result.


TITLE: Neumann series and spectral radius
QUESTION [8 upvotes]: I have a question about the convergence of the Neumann series:
Let $A$ be a matrix with spectral radius $\rho(A)<1$, i.e., all eigenvalues of $A$ are strictly less than $1$. Does that imply that the series
\begin{equation}
\sum_{i=0}^{\infty}A^i
\end{equation}
converges (in the operator norm)?
I know how to prove it if the operator norm of $A$ is strictly less than $1$, but I don't know how to prove it if I only know that the spectral radius is less than $1$.
Many thanks for any help!

REPLY [1 votes]: Let us start defining a function $T:\mathbb{R}^{n \times n}\rightarrow \mathbb{R}^{n \times n}$ such that $T(x)=I+xA,$ for all $x\in\mathbb{R}^{n\times n}.$ Note that the fixed point iteration $x_{n+1} = T(x_n)$ staring with $x_0=I$ is equal to the sum $x_k=\sum^{k}_{i=0}A^i.$ Hence, we only need to show that $x_k$ converges to show that $\sum^{k}_{i=0}A^i$ converges.
Note that $$ \begin{split} T^{k+1}(x)-T^{k+1}(y) = & (I + T^{k}(x) A) - (I + T^{k}(y) A)\\ =&  T^{k}(x) A - T^{k}(y) A \\ = & (T^{k}(x)-T^{k}(y))A, \end{split} $$ for all $x,y\in \mathbb{R}^{n \times n}. $Thus, by induction, $$T^{k}(x)-T^{k}(y) = (x-y)A^{k},$$ for all $k\in\mathbb{N}$ and all $x,y\in \mathbb{R}^{n \times n}$. Now, choosing your favorite submultiplicative norm, since $\lim_{k\rightarrow \infty} \|A^{k}\|^{1/k} = \rho(A)<1,$ we can choose $k_0$ big enough such that $\|A^{k_{0}}\|<1.$ Hence, $$\|T^{k_0}(x)-T^{k_0}(y)\| \leq \|x-y\|\|A^{k_0}\|.$$ Hence, $T^{k_0}$ is a contraction. Consequently, the fixed point iteration $z_{k+1}=g(z_k)$, with $g$ given by $g(x)=T^{k_0}(x),$ for all $x\in\mathbb{R}^{n \times n},$ converges to the unique fixed point of $g$ independently to the starting point $z_0\in\mathbb{R}^{n \times n}, $ as stated here.
Let $y^{*}\in\mathbb{R}^{n\times n}$ be the unique fixed point for $g$. Given a natural number $0 \leq i< k_0$, as previously commented, the fixed point iteration $z_{k+1} = g(z_{k})$ staring with $z_0=T^{i}(x_0)$ will converge to $y^{*}$. Since $g$ commutes with $T$, we have that $$\begin{split} y^{*} =& \lim_{k \rightarrow \infty} z_{k} \\
=& \lim_{k \rightarrow \infty} g^{k}(T^{i}(x_0))\\
 =& \lim_{k \rightarrow \infty} T^{i}(g^{k}(x_0))\\ =& \lim_{k \rightarrow \infty} T^{i}(T^{k_0 k} (x_0))\\ =& \lim_{k \rightarrow \infty} T^{k_0 k + i} (x_0)\\
=& \lim_{k \rightarrow \infty} x_{k_0 k + i}.\end{split}$$ Taking into account that the last conclusion is true for all $0 \leq i<k_0$, all of the subsequences $\{x_{k_0 k +i}\}_{k\in\mathbb{N}}$ of $\{x_{k}\}_{k\in\mathbb{N}}$ converges to $y^{*}$. Thanks to Division theorem, this is enough to show that that $\{x_{k}\}_{k\in\mathbb{N}}$ converges to $y^{*}$.
As a last observation, I will show that $y^{*}$ is actually the inverse of $I-A.$ Considering that $y^{*}$ is the fixed point of $g$ and limit of the sequence defined by $y_{k+1}=g(y_{k})$ staring with $x_0=T(y^{*}).$ The calculations $$\begin{split} y^{*} =& \lim_{k \rightarrow \infty} y_{k} \\
=& \lim_{k \rightarrow \infty} g^{k}(T(y^{*}))\\
 =& \lim_{k \rightarrow \infty} T(g^{k}(y^{*}))\\ =& \lim_{k \rightarrow \infty} T(y^{*})\\ =& T(y^{*}).\end{split}$$ shows that $y^{*}=T(y^{*})=I-Ay^{*}$. Hence, $y^{*}(I-A) = I.$ This shows that $(I-A)y^{*}=I$ also, since all square matrices which has a left inverse has a right inverse as well. This shows that $y^{*}$ is the inverse of $I-A.$


TITLE: If $2^{x + 1} < y$, then what is the "smallest" function of $x$ that cannot be an upper bound for $y$?
QUESTION [0 upvotes]: (This is a follow-up question to this MSE post.)
The title says it all.
Let $x$ be a positive integer.

If $2^{x + 1} < y$, then does there exist a minimum function $f(x)$ that cannot be an upper bound of $y$?

So for example, I know that $f(x) = x^2$ cannot be an upper bound because $2^{x + 1} < x^2$ does not hold for all integer values of $x$.
I was wondering if there was some sort of systematic procedure for finding the minimum (or maximum, for that matter) function $F(x)$ satisfying the given conditions.

REPLY [1 votes]: Suppose that $f(x)$ is such that at some $x = x_0$, we have $f(x_0)<2^{x_0+1}$.
Consider $\frac{f(x)}{2}$...


text:
For reader's convenience, we recall some background information.
\subsection{Descending plane partitions}
\label{sec:background-dpp}
Here is the definition of \DPP s as given by Mills, Robbins and Rumsey \cite[Definitions 2--4]{MillsRobbinsRumsey:1983}:
\begin{dfn}[\DPP]
\label{dfn:dpp}
A \EM{\DPP} is an array $\pi=\pas{a_{i,j}}$, $1\leq i\leq j<\infty$, of
\EM{positive integers}
$$
\pi=\;\;
\begin{matrix}
a_{1,1} & a_{1,2} & a_{1,3} &         & \cdots       &        & \cdots      & a_{1,\mu_1} \\
        & a_{2,2} & a_{2,3} &         & \cdots       & \cdots & a_{2,\mu_2} & \\
        &         &         &         & \cdots       &        &             & \\
        &         &         &         & \cdots       &        &             & \\
        &         &         & a_{k,k} & \cdots &  a_{k,\mu_k} &             &
\end{matrix}
$$
such that
\begin{enumerate}
\item rows are \EM{weakly decreasing}, i.e., $a_{i,j}\geq a_{i,j+1}$ for all $i=1,\dots,k$ and $i\leq j < \mu_i$,
\item columns are \EM{strictly decreasing}, i.e., $a_{i,j}> a_{i+1,j}$ for all $i=1,\dots,k-1$ and $i<j\leq \mu_{i+1}$,
\item $a_{i,i}>\mu_i-i+1$ for all $i=1,\dots,k$,
\item $a_{i,i}\leq \mu_{i-1}-i+2$ for all $i=2,\dots,k$.
\end{enumerate}

Clearly, conditions 3 and 4 imply
$$
\mu_1\geq\mu_2\geq\cdots\geq\mu_k\geq k.
$$
The \EM{parts} of a \DPP\ are the \EM{numbers} (with repetitions) that appear in the array.
The \EM{empty} array, which we denote by $\emptyset$, is explicitly allowed.

A \DPP\ $\pi$ where no part is greater than $n$ (i.e., $\pi$ has at most $n-1$ rows)
is said to have dimension $n$. (So a \DPP\ of dimension $n$ may also be viewed as
a \DPP\ of dimension $k$, for all $k>n$.)

By the \EM{length} of row $i$ in \DPP\ $\pi$ we define the number of parts it contains (i.e. $\mu_i-i+1$).
So we may rephrase conditions 3 and 4 as follows:
\bit
\item[$3^\prime$.] The first part of row $i$ is greater than the length of row $i$ for $i=1,\dots,k$,
\item[$4^\prime$.] The first part of row $i$ is less or equal than the length of the preceding row ${i-1}$ for $i=2,\dots,k$.
\eit

A part $a_{i,j}$ in a \DPP\ is called \EM{special} if it does not exceed the number of parts to
its left (in its row $i$), i.e., if
$$
a_{i,j}\leq j-i.
$$
\end{dfn}

\begin{ex}
A typical example is the array
$$
\begin{matrix}
6 & 6 & 6 & 4 & {\red\underline 2} \\
  & 5 & 3 & {\red\underline 2} & {\red\underline 1} \\
  &   & 2 &   &
\end{matrix}
$$
with $3$ rows and $10$ parts (written in descending order)
$$
6,6,6,5,4,3,2,{\red\underline 2,\underline 2,\underline 1},
$$
three of which are  special parts (indicated as underlined numbers;
note that the $2$ in the last row is \EM{not}
a special part):
$$
{\red \underline 2,\underline 2,\underline 1}.
$$
(This is the example $D_0$ considered by Lalonde \cite[Fig.~1]{Lalonde:2003}.)
\end{ex}

From now on, we shall use the shortcut \EM{DPP} for \DPP s.
\def\DPP{DPP}

\subsection{Alternating sign matrices}
Here is the definition of \ASMes\ as given by Mills, Robbins and Rumsey, see \cite[Definition 1]{MillsRobbinsRumsey:1983}:
\begin{dfn}[\ASM]
An \EM{\ASM} of dimension $n$ is an $n\times n$ square matrix which satisfies
\bit
\item all entries are $1$, $-1$ or $0$,
\item every row and column has sum $1$,
\item in every row and column the nonzero entries alternate in sign.
\eit

Suppose that $A=\pas{A_{i,j}}_1^n$ is an alternating sign matrix of dimension $n$.
Then the number of \EM{inversions} in $A$ is defined to be \cite[p.\ 344]{MillsRobbinsRumsey:1983}
\begin{equation}
\label{eq:inversions}
\sum_{\substack{1\leq i<k\leq n\\1\leq l<j\leq n}}A_{i,j}\cdot A_{k,l}.
\end{equation}

\end{dfn}

\begin{ex}
The following matrix is an example of an \ASM\ of dimension $5$:
$$
\begin{bmatrix}
0 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 \\
1 & -1 & 0 & 1 & 0 \\
0 & 1 & 0 & -1 & 1 \\
0 & 0 & 0 & 1 & 0.
\end{bmatrix}
$$
\end{ex}
From now on, we shall use the shortcut \EM{ASM} for \ASMes.
\def\ASM{ASM}
\def\ASMes{ASMs}

\subsection{The Mills--Robbins--Rumsey conjecture}
Here is the Conjecture of Mills, Robbins and Rumsey \cite[Conjecture 3]{MillsRobbinsRumsey:1983},
slightly rephrased to fit our exposition:
\begin{con}
\label{con:MRR}
Suppose that $n, \statp, \stati, \stats$ are nonnegative integers, $0\leq \statp\leq n-1$.
Let $\asmset{n}\of{\statp, \stati, \stats}$ be the set of \ASMes\ such that
\begin{enumerate}
\item the size of the matrix is $n\times n$ (i.e., its dimension is $n$),
\item the number of $0$'s to the left of the $1$ in the first row is $\statp$,
\item the number of $-1$'s in the matrix is $\stats$,
\item the number of inversions in the matrix is $\stati+\stats$.
\end{enumerate}
On the other hand, let $\dppset{n}\of{\statp, \stati, \stats}$ be the set of \DPP s such that
\begin{enumerate}
\item no part exceeds $n$ (i.e., the dimension of the \DPP\ is $n$),
\item there are exactly $\statp$ parts equal to $n$,
\item there are exactly $\stati$ special parts,
\item there are a total of $\stati+\stats$ parts.
\end{enumerate}
Then $\asmset{n}\of{\statp, \stati, \stats}$ and $\asmset{n}\of{\statp, \stati, \stats}$
have the same cardinality --- the sets $\asmset{n}$ and $\dppset{n}$ are equidistributed
with respect to the \EM{triplet of statistics} $\pas{\statp, \stati, \stats}$.
\end{con}
This conjecture was proved by Behrend, Di Francesco and Zinn--Justin \cite[Theorem 1]{Behrend:2012}.

\subsection{The fourth statistic given by Behrend, Di Francesco and Zinn--Justin}
In \cite{Behrend:2013}, Behrend, Di Francesco and Zinn--Justin presented a fourth
statistic $\statb$ for \ASM s and \DPP s and showed that \ASM s and \DPP s are equidistributed
with respect to the \EM{quadruplet of statistics} $\quadruplet$ \cite[Theorem 1]{Behrend:2013}:
This statistic $\statb$ is
\bit
\item for $n$--dimensional \ASMes\ equal to the number of $0$'s to the right of the $1$ in the last row,
\item for $n$--dimensional \DPP s equal to the number of parts $n-1$ plus the number of rows of length $n-1$.
\eit

\secB{Permutation matrices and inversions}
Let $\sigma\in\symm_n$ be a permutation of the first $n$ natural numbers $\setof{1,2,\dots,n}$.
\secC{Inversions of a permutation}
Recall that an \EM{inversion} of $\sigma$ is a pair $\pas{i,j}$ such that
$i<j$ and $\sigma\of i > \sigma\of j$.
For the number $\inv\of\sigma$ of \EM{all} inversions of
$\sigma$ we have $0\leq\inv\of\sigma\leq \frac{n\cdot\pas{n+1}}2$.

We may assign to $\sigma$ its \EM{inversion word} $\pas{a_1, a_2,\dots, a_{n-1}}$, where
$a_k$ is the number of inversions $\pas{i,j}$ with $\sigma\of j=k$, $k = 1,2,\dots, n-1$.
Clearly we have $0\leq a_k\leq n-k$ and $a_1+a_2+\cdots+a_{n-1} = \inv\of\sigma$.

Considering the \EM{permutation word}
$$
\pas{\sigma\of 1,\sigma\of 2,\dots,\sigma\of n},
$$
of $\sigma$, the inversion word's $k$--th entry $a_k$ is simply the number of elements
\EM{to the left} of $k$ (in the permutation word) which are \EM{greater} than $k$, and
it is easy to see that \EM{every} word $\pas{b_1,b_2,\dots,b_{n-1}}$ with $0\leq b_k\leq n-k$
determines a \EM{unique} permutation: Inversion words are, in this sense, just another
``encoding'' for permutations.

\secC{Permutation matrices}
A permutation $\sigma\in\symm_n$ can be represented by an $n\times n$--matrix $M$ with
entries
$$
M_{i,j} = \delta_{\sigma\of i,j}
$$
(where $\delta_{x,y}$ denotes Kronecker's delta: $\delta_{x,y} = 1$ if $x=y$,
$\delta_{x,y} = 0$ if $x\neq y$). We call this matrix the \EM{permutation matrix}
of $\sigma$: Clearly, it contains precisely one entry $1$ in every row and column.
\begin{ex}
Let $n=6$ and $\sigma\in\symm_6$ be the permutation with permutation word
$$
\sigma=\pas{3 5 2 4 6 1}.
$$
The corresponding permutation matrix is
$$
\begin{bmatrix}
0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0
\end{bmatrix},
$$
and the corresponding inversion word is
$$
\pas{2,3,1,1,1}.
$$
\end{ex}
Note that every \EM{permutation matrix} is an \ASM\ (which does not contain entries
$-1$), and that the definition of inversions \eqref{eq:inversions} for \ASMes\ is a generalization
of the number of inversions of a permutation (see also \secref{sec:asminvs}).

config: arxiv


TITLE: If $S_{1},S_{2}$ be subsets of complex numbers then $\inf\lbrace |z_{1} - z_{2}| \rbrace > 0\; (z_{1} \in S_{1}\text{ and }z_{2} \in S_{2})$.
QUESTION [1 upvotes]: Problem: "Suppose that $S_{1}$ be a compact subset of $\Bbb C$ (complex numbers) and  $S_{2}$ be a closed subset of $\Bbb C$(complex numbers). If $S_{1} \cap S_{2} = \varnothing$, then show that $\inf\lbrace |z_{1} - z_{2}| \rbrace  > 0\; (z_{1} \in S_{1}\text{ and }z_{2} \in S_{2})$".
I supposed that $A=\lbrace|z_{1} - z_{2}| : z_{1} \in S_{1} , z_{2} \in S_{2} \rbrace $ and $a = \inf A$.
If $a \in A$ then $a > 0$.
For "If $a \notin A$" I can't show that $a > 0$. Can you help me? Or have you another way for this problem? Can I solve this problem using Heine-Borel theorem?

REPLY [1 votes]: Suppose that $\inf\{|z-y|:\textrm{ }z\in S_1, y\in S_2\}=0$, so we can find a sequence $(z_n)$ on $S_1$ and a sequence $(y_n)$ on $S_2$ such that $|z_n-y_n|\rightarrow 0$, now use the compactness of $S_1$ and that $S_2$ is closed to show that there is a point on $S_1\cap S_2$ this show the result.


TITLE: Best approach or algorithm to solve equation with multiple variables?
QUESTION [0 upvotes]: I have an equation :
$A^6x_1 + A^5x_2 + A^4x_3 + A^3x_4 + A^2x_5 + A^1x_6 + x_7 = B$
What can be the best algorithm/approach I can use to crack this?
$A$ and $B$ are constants. $x_1,x_2...x_7$ are variables.
A is a prime number.
Sorry for not stating this earlier variables can have values from 0 to 15.
The algorithm should be efficient.

REPLY [1 votes]: Let $x_7$ be the remainder when $B$ is divided by $A$. Let $B_1 = (B-x_7)/A$.
Let $x_6$ be the remainder when $B_1$ is divided by $A$. Let $B_2 = (B_1-x_6)/A$.
Let $x_5$ be the remainder when $B_2$ is divided by $A$. Let $B_3 = (B_2-x_5)/A$.
...
Let $x_2$ be the remainder when $B_5$ is divided by $A$. Let $B_6 = (B_5-x_2)/A$.
Finally, let $x_1 = B_6/A$.
This is basically the algorithm to write an integer $B$ in base-$A$, except you stop after getting $7$ digits.


TITLE: Summing divergent series based on physics
QUESTION [5 upvotes]: Solving a heat equation with central symmetry i got the following result:
The problem is to find a sphere center temperature vs. time given that the surface of the sphere is kept constant at $$T_1$$ and at initial moment t=0 the temperature inside the sphere is distributed uniformly with value $$T_0$$
A solution is following:
$$T(t)=T_1+2 (T_0-T_1)\sum_{k=1}^\infty (-1)^{k+1} e^{-t(\frac{k\pi a}{r})^2}$$
Here r is the radius of the sphere and a=const is a coefficient of thermal conductivity.
Now the solution must satisfy the initial condition $$T(0)=T_0$$:
$$T(0)=T_1+2 (T_0-T_1)\sum_{k=1}^\infty (-1)^{k+1} $$
This is satisfied only if the following holds:
1-1+1-1+1-1+ ... =1/2
So, we found this divergent sum  through physical arguments? Is this appropriate for the pure mathematician?
Lets go a step further and differentiate the solution by t:
$$\frac {d T(t)}{dt}=-2 (T_0-T_1)(\frac{\pi a}{r})^2\sum_{k=1}^\infty (-1)^{k+1} k^2 e^{-t(\frac{k\pi a}{r})^2}$$
Now, at initial moment t=0 we have:
$$\frac {d T(0)}{dt}=-2 (T_0-T_1)(\frac{\pi a}{r})^2\sum_{k=1}^\infty (-1)^{k+1} k^2 $$
Obviously  $$\frac {d T(0)}{dt}=0$$  because  the maximum speed in the universe is limited.
Thus the following must be valid:
1^2 - 2^2 + 3^2 - 4^2 + ... =0
Here we can say what has been said previously, i think. But at the moment i'm not sure about the following divergent sum:
1 - 2 + 3 - 4 + ...

REPLY [1 votes]: The following literature may be of use here:

SOURCE: "Analysis I" (second edition) by Terence Tao


TITLE: Acceleration reaches speed of light?
QUESTION [0 upvotes]: Hi, I am thinking about acceleration. Let's think we have a force of $1$ N and a particle of $1$ kg, then acceleration will be $1$. So the speed gets higher every second and $c$ seconds later, in Newtonian mechanics, the particle will  reach the speed of light. In relativity, of course, something like that cannot happen.  So, what are the equations that describe acceleration in relativity?

REPLY [0 votes]: Classicaly you have
$$
m\frac{\mathrm{d}v}{\rm{d}t}=F
$$
In relativity, closer to speed of light the particle is, higher mass it gets. This increase of mass is expressed by gamma factor: $\gamma=1/\sqrt{1-v^2/c^2}$. See it is dependent on $v$. Therefore:
$$
\frac{\mathrm{d}(\gamma m v)}{\rm{d}t}=F
$$


TITLE: Current through Circular Circuit as a Function of Theta
QUESTION [2 upvotes]: I am struggling with this question. I know this question was already posted on the site but there was no clear answer.

So far, I have tried visualizing the circuit as $4$ resistors connected in parallel ($2$ resistors in $2$ branches) with a wire connecting the $2$ branches. Then these resistors would have resistance proportional to the length of wire they represent. I didn't know what to do after this step. Any help is appreciated!

REPLY [0 votes]: You need 5 resistors. The circuit is connected from A to B with the same type of wire, which has resistance.
Let's call the start and end S and E, you have five different current $I_{SA}, I_{SB},I_{AB},I_{AE},I_{BE}$. You need to find out what $I_{AB}$ is.
At any junction of three wires in the circuit, no charge will pile up, so the current flowing in must be the same as current flowing out. (This is called Kirchhoff's current law).

I think you can take it from here, good luck!