text:
\section{AMP algorithmic phase transition}\label{app:matrixWalgo}

We begin with the proof of Theorem~\ref{AMP-theorem} in Section~\ref{eq:appsec:AMPtheory}, assuming the result in \eqref{eq:finite_sample} is true, and then we discuss the proof of \eqref{eq:finite_sample} which is a generalization of \cite[Theorem 1]{RushVenkataramanan} in Section~\ref{eq:appsec:finitesample}.

\subsection{Proof of Theorem~\ref{AMP-theorem}} \label{eq:appsec:AMPtheory}
We begin by restating Theorem~\ref{AMP-theorem}, the result we would like to prove, for the readers' convenience.

 \begin{thm}\label{AMP-theorem_app}
 For the AMP algorithm in \eqref{eq:AMP} using the conditional expectation denoiser in \eqref{eq:denoiser}, with $\epsilon \in (0,1)$, we have that

 \begin{align}
&\mathbb{P} \Big(\Big| \frac{1}{n}\|\bX -  f_{t}(\bx^{t})\|^2 -  (\rho_n -  \tau^n_{t+1})\Big| \geq \epsilon \Big) \leq C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon^2}{\lambda_n^{2t}}\Big\},  \label{eq:finite_sample_vector}\\

&\mathbb{P} \Big(\Big| \frac{1}{n^2}\|\bX \bX^T -  f_{t}(\bx^{t}) [ f_{t}(\bx^{t})]^T\|_F^2 -  (\rho_n^2 -    (\tau^n_{t+1})^2) \Big| \geq \epsilon \Big) \leq C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon^2}{\lambda_n^{2t}}\Big\},  \label{eq:finite_sample_matrix}
 \end{align}

where $X_0^n \sim P_{X, n}$ and $\tau_t^n$ is defined in \eqref{eq:state_evolution2}.  The constants $C_t, C_t$ are given by
$C_t =C_1^{t} (t!)^{C_2},  c_t = [c_1^{t} (t!)^{c_2}]^{-1}$  and $C, C_1, C_2, c, c_1, c_2$ are universal constants not depending on $n$ or $\epsilon$.

 \end{thm}

 The proof of Theorem~\ref{AMP-theorem_app} uses the following finite sample guarantee for the symmetric AMP algorithm in \eqref{eq:AMP}.
 The performance guarantees concern the convergence of the empirical distribution of $x^t_i$ to its approximating distribution with mean and variance determined by the state evolution, in the following sense. Recall the following definition of a pseudo-Lipschitz function.

 \begin{defi}  \label{def:PL}
 For any $n,m \in \mathbb{N}_{>0}$, a function $\phi : \mathbb{R}^n\to \mathbb{R}^m$ is \emph{pseudo-Lipschitz of order $2$} if there exists a constant $L>0$ such that  for $\bx, \by \in \mathbb{R}^n$, $$\left|\left|\phi(\bx)-\phi(\by)\right|\right|\leq L\left(1+ \|\bx\|+ \|\by\|\right) \|\bx-\by\|.$$
 \end{defi}

 Now, for all order $2$ pseudo-Lipschitz functions denoted $\psi: \mathbb{R} \rightarrow \mathbb{R}$ with Lipschitz constant $L_{\psi}> 0$, for $\epsilon \in (0,1)$ and $t \geq 0$,

 \begin{equation}
 \begin{split}
 \mathbb{P} \Big(\Big| \frac{1}{n} \sum_{i=1}^n \psi(X_i, f_{t}(x^{t}_i)) -  \mathbb{E}\Big\{\psi\big(X_0^n,  f_{t}(\mu^n_{t} X_0^n + \sqrt{\tau^n_t} Z)\big) \Big\} \Big| \geq \epsilon \Big) \leq C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon^2}{\lambda_n^{2 t} L_{\psi}^{2t}}\Big\},
 \label{eq:finite_sample_app}
 \end{split}
 \end{equation}

 where $\bX = (X_1, \ldots, X_n)$ is the true signal, $C, C_t, c, c_t$ are universal constants not depending on $n$ or $\epsilon$, with the values of $C_t, c_t$ given in Theorem~\ref{AMP-theorem_app}. Finally, we note that \eqref{eq:finite_sample} matches \eqref{eq:finite_sample_app} when we use the conditional expectation denoiser as in \eqref{eq:denoiser}, since then we have that
 $L_f = \sqrt{\lambda_n}$ as shown in Lemma~\ref{lem:PL} for the Bernoulli and Bernoulli-Rademacher signal priors considered here.
We discuss the proof of \eqref{eq:finite_sample} in Section~\ref{eq:appsec:finitesample}, but for the time being, we assume that it is true and use it to prove Theorem~\ref{AMP-theorem_app}.

First, notice that Theorem~\ref{AMP-theorem_app} result \eqref{eq:finite_sample_vector} follows directly from \eqref{eq:finite_sample_app} using the pseudo-Lipschitz function $\psi(X_i, f_{t}(x^{t}_i))  = (X_i -  f_{t}(x^{t}_i))^2$. This function is pseudo-Lipschitz with constant $L_{\psi} $ by Lemma~\ref{lem:PL}.  To see how this proves result \eqref{eq:finite_sample_vector} in more details, notice that

 \begin{equation*}
 \frac{1}{n} \sum_{i=1}^n \psi(X_i, f_{t}(x^{t}_i))  = \frac{1}{n} \sum_{i=1}^n (X_i - f_{t}(x^{t}_i))^2 = \frac{1}{n}\|\bX -  f_{t}(\bx^{t}) \|^2,
  \end{equation*}

and

 \begin{equation*}
 \begin{split}
& \mathbb{E}\Big\{\psi\big(X_0^n,  f_{t}(\mu^n_{t} X_0^n + \sqrt{\tau^n_t} Z)\big) \Big\} =  \mathbb{E}\Big\{\big(X_0^n - f_t\big(\mu^n_{t}  X_0^n - \sqrt{\tau^n_t} Z\big)\big)^2 \Big\} \\

 &=  \mathbb{E}\Big\{\big(X_0^n\big)^2 \Big\} + \mathbb{E}\Big\{\big( f_t\big(\mu^n_{t}  X_0^n - \sqrt{\tau^n_t} Z)\big)^2 \Big\} - 2 \mathbb{E}\Big\{ X_0^n f_t\big(\mu^n_{t}  X_0^n - \sqrt{\tau^n_t} Z\big) \Big\} = \rho_n -  \tau^n_{t+1},
 \end{split}
  \end{equation*}

where the final uses that $ \mathbb{E}\{(X_0^n)^2\} = \rho_n$ when $P_{X,n}$ is ${\rm Ber}(\rho_n)$ or Bernoulli-Rademacher, the Law of Total Expectation to give $ \mathbb{E}\{X_0^n f_t(\sqrt{\lambda_n} \tau^n_{t} X_0^n + \sqrt{\tau^n_t} Z)\} = \mathbb{E}\{[f_t(\sqrt{\lambda_n} \tau^n_{t}X_0^n + \sqrt{\tau^n_t} Z)]^2\}$ in the case of the conditional expectation denoiser as in \eqref{eq:denoiser}, and the state evolution definition in \eqref{eq:state_evolution2}.

Now we will prove Theorem~\ref{AMP-theorem_app} result \eqref{eq:finite_sample_vector}.

First we introduce a few useful lemmas about concentration of sums of squares, the proof of which can be found in \cite[Appendix A]{RushVenkataramanan}.

\begin{lemma}[Concentration of Sums]
\label{sums}
If random variables $X_1, \ldots, X_M$ satisfy $P(\abs{X_i} \geq \ep) \leq e^{-n\kappa_i \ep^2}$ for $1 \leq i \leq M$, then

 \begin{equation*}
P\Big(  \lvert \sum_{i=1}^M X_i  \lvert \geq \ep\Big) \leq \sum_{i=1}^M P\left(|X_i| \geq \frac{\ep}{M}\right) \leq M e^{-n (\min_i \kappa_i) \ep^2/M^2}.
  \end{equation*}

\end{lemma}

\begin{lemma}[Concentration of Powers]
\label{powers}
Assume $c > 0$ and $0 < \ep \leq 1$.  Then, if
$
P( \lvert X_n - c \lvert \geq \epsilon ) \leq e^{-\kappa n \epsilon^2},
$
it follows that
$
P(\lvert X_n^2 - c^2  \lvert \geq \epsilon) \leq e^{ {-\kappa n \ep^2}/[1+2c]^2}  \leq e^{-\kappa n \ep^2}.
$
\end{lemma}

Now considering the concentration result in \eqref{eq:finite_sample_vector}, notice that

 \begin{equation*}
 \frac{1}{n^2}\|\bX \bX^T - f_t(\bx^t) [f_t(\bx^t)]^T\|_F^2  =  \frac{1}{n^2}\|\bX\|^4 + \frac{1}{n^2}\|f_t(\bx^t)\|^4 - \frac{2}{n^2} \langle \bX, f_t(\bx^t) \rangle^2.
  \end{equation*}

Then we will prove the following three results:

 \begin{align}
\mathbb{P} \Big(\Big|  \frac{1}{n^2}\|\bX\|^4 -  \rho_n^2 \Big| \geq \epsilon \Big) &\leq 2e^{ -2 n \e^2},  \label{eq:finite_sample_matrix1} \\
\mathbb{P} \Big(\Big|  \frac{1}{n^2}\|f_t(\bx^t)\|^4 - (\tau^n_{t})^2 \Big| \geq \epsilon \Big) &\leq C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon^2}{\lambda_n^{2t}}\Big\},  \label{eq:finite_sample_matrix2} \\
\mathbb{P} \Big(\Big|  \frac{1}{n^2} \langle \bX, f_t(\bx^t) \rangle^2 -  ( \tau^n_{t})^2 \Big| \geq \epsilon \Big) &\leq C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon^2}{\lambda_n^{2t}}\Big\}.\label{eq:finite_sample_matrix3}
 \end{align}

Then the final concentration result in \eqref{eq:finite_sample_vector} follows from Lemma~\ref{sums} as follows:

 \begin{align*}
&\mathbb{P} \Big(\Big| \frac{1}{n^2}\|\bX \bX^T - f_t(\bx^t) [f_t(\bx^t)]^T\|_F^2 - ( \rho_n^2 -  (  \tau^n_{t+1})^2)  \Big| \geq \epsilon \Big) \\

&= \mathbb{P} \Big(\Big|  \Big(\frac{1}{n^2}\|\bX\|^4 -  \rho_n^2 \Big) + \Big( \frac{1}{n^2}\|f_t(\bx^t)\|^4 - (\tau^n_{t+1})^2   \Big)-  \Big(\frac{2}{n^2} \langle \bX, f_t(\bx^t) \rangle^2  - 2 (   \tau^n_{t+1})^2\Big) \Big| \geq \epsilon \Big) \\

&\leq \mathbb{P} \Big(\Big|  \frac{1}{n^2}\|\bX\|^4 -  \rho_n^2 \Big| \geq \frac{\epsilon}{3} \Big) +  \mathbb{P} \Big(\Big|  \frac{1}{n^2}\|f_t(\bx^t)\|^4 - (\tau^n_{t+1})^2  \Big| \geq  \frac{\epsilon}{3} \Big) +  \mathbb{P} \Big(\Big|  \frac{2}{n^2} \langle \bX,f_t(\bx^t) \rangle^2  - 2 (  \tau^n_{t+1})^2 \Big| \geq  \frac{\epsilon}{3} \Big).
 \end{align*}

As a final step, notice that the bounds in  \eqref{eq:finite_sample_matrix1} - \eqref{eq:finite_sample_matrix3} applied to the above give the result in \eqref{eq:finite_sample_vector}.

Now we prove  \eqref{eq:finite_sample_matrix1} - \eqref{eq:finite_sample_matrix3}. First we prove \eqref{eq:finite_sample_matrix1}.  Recall Hoeffding's inequality.
\begin{lemma}[Hoeffding's inequality]
\label{lem:hoeff_lem}
If $X_1, \ldots, X_n$ are bounded random variables such that $a_i \leq X_i \leq b_i$, then for $\nu = 2[\sum_{i} (b_i -a_i)^2]^{-1}$, we have
$P(  \lvert \frac{1}{n}\sum_{i=1}^n (X_i -\mathbb{E}\{X_i\})  \lvert \geq \ep ) \leq 2e^{ -\nu n^2 \ep^2}.$
\end{lemma}
\begin{lemma}[Chernoff's bounds for Bernoulli's]
\label{lem:chernoff}
If $X_1, \ldots, X_n$ be i.i.d.\ ${\rm Ber}(\rho_n)$, then for $\ep \in [0,1]$ we have
$P(  \lvert \frac{1}{n}\sum_{i=1}^n (X_i -\rho_n)  \lvert \geq \ep ) \leq 2\exp\left\{ - \frac{n \ep^2}{3 \rho_n}\right\}.$
\end{lemma}

 \begin{align*}
\mathbb{P} \Big(\Big|  \frac{1}{n}\|\bX\|^2 -  \rho_n \Big| \geq \epsilon \Big)  = \mathbb{P} \Big(\Big|  \frac{1}{n} \sum_{i=1}^n(X_i^2 -  \mathbb{E}\{X_i^2\}) \Big| \geq \epsilon \Big)  &\leq 2e^{ -2 n \ep^2}.
 \end{align*}

Then the result in  \eqref{eq:finite_sample_matrix1} then follows from the above by Lemma~\ref{powers}.

 Next, for \eqref{eq:finite_sample_matrix2} we apply \eqref{eq:finite_sample_app} using the function $ \psi(X_i, f_t(x^t_i)) = [f_t(x^t_i)]^2$, which is pseudo-Lipschitz with constant $L_{\psi} = 2$ by Lemma~\ref{lem:PL}), to find

 \begin{equation}
 \mathbb{P} \Big(\Big|  \frac{1}{n}\|f_t(\bx^t)\|^2 - \tau^n_{t+1} \Big| \geq \epsilon \Big) = \mathbb{P} \Big(\Big| \frac{1}{n} \sum_{i=1}^n [f_t(x^t_i)]^2 -\tau^n_{t+1} \Big| \geq \epsilon \Big) \leq C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon^2}{\lambda_n^{2t}}\Big\},
 \label{eq:finite_sample_conc2}
 \end{equation}

 where we have used the definition of the state evolution in \eqref{eq:state_evolution2} to give
 \begin{equation*}
 \begin{split}
  \mathbb{E}\Big\{\psi\big( X_0^n, f_t\big(\mu^n_{t} X_0^n + \sqrt{\tau^n_{t}} Z\big)\big) \Big\} &=   \mathbb{E}\Big\{\big[f_{t}\big(\mu^n_{t} X_0^n + \sqrt{\tau^n_{t}} Z\big)\big]^2 \Big\} = \tau^n_{t+1}.
  \end{split}
 \end{equation*}

   Then the result in  \eqref{eq:finite_sample_matrix2} follows from the above by Lemma~\ref{powers}.

Finally we prove result \eqref{eq:finite_sample_matrix3} by applying \eqref{eq:finite_sample_app} using the function $ \psi(X_i, f_t(x^t_i)) = X_i f_t(x^t_i)$, which is pseudo-Lipschitz with constant $L_{\psi} = 2$ by Lemma~\ref{lem:PL}), to find

 \begin{equation}
 \mathbb{P} \Big(\Big|  \frac{1}{n} \langle \bX, f_t(\bx^t) \rangle -    \tau^n_{t+1} \Big| \geq \epsilon \Big) = \mathbb{P} \Big(\Big| \frac{1}{n} \sum_{i=1}^n  X_i f_t(x^t_i) -    \tau^n_{t+1} \Big| \geq \epsilon \Big) \leq C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon^2}{\lambda_n^{2t}}\Big\},
 \label{eq:finite_sample_conc2}
 \end{equation}

where
 \begin{equation*}
 \begin{split}
  \mathbb{E}\Big\{\psi\big( X_0^n, f_t\big(\mu^n_{t} X_0^n + \sqrt{\tau^n_{t}} Z\big)\big) \Big\} =  \mathbb{E}\Big\{ X_0^n f_{t}\big(\mu^n_{t} X_0^n + \sqrt{\tau^n_{t}} Z\big) \Big\} &=   \tau^n_{t+1},
  \end{split}
 \end{equation*}

where the final step uses the Law of Total Expectation to give $ \mathbb{E}\{X_0^n f_{t}(\mu^n_{t} X_0^n + \sqrt{\tau^n_{t}} Z)\} = \mathbb{E}\{[f_{t}(\mu_{t}X_0^n + \sqrt{\tau^n_{t}} Z)]^2\}$ in the case of the conditional expectation denoiser as in \eqref{eq:denoiser} and the state evolution definition in \eqref{eq:state_evolution2}.
   Then the result in  \eqref{eq:finite_sample_matrix3} follows  from the above  by Lemma~\ref{powers}.

 We wrap up the proof of Theorem~\ref{AMP-theorem} with the following Lemma which proves that the functions we used when applying result \eqref{eq:finite_sample_app} are indeed pseudo-Lipschitz with the stated constants.

 \begin{lemma}  \label{lem:PL}
 Recall the definition of pseudo-Lipschitz functions of order $2$ given in Definition~\ref{def:PL}.  The following functions $\psi: \mathbb{R}^2 \rightarrow \mathbb{R}$ are all pseudo-Lipschitz of order $2$ with  pseudo-Lipschitz constant $2$.
 \begin{equation}
 \begin{split}
 \psi_1(a, b)  &= (a - b)^2, \qquad  \qquad \psi_2(a, b)  = b^2, \qquad  \qquad \psi_3(a, b)  = a b.
 \label{eq:the_phis}
 \end{split}
 \end{equation}
 Moreover, the conditional expectation denoiser in \eqref{eq:denoiser} is Lipschitz with constant $L_f = \sqrt{\lambda_n}$ when $X_0^n \sim P_{X,n}$ and $P_{X,n}$ is either ${\rm Ber}(\rho_n)$ or Bernoulli-Rademacher and $\frac{\partial}{\partial x} f_t(x)  = \sqrt{\lambda_n} f_t(x)(1- f_t(x))$.
  \end{lemma}

 \begin{proof}
 Verifying the pseudo-Lipschitz property for the functions in \eqref{eq:the_phis} is straightforward, so we omit the details.
 First, recall that $f_t(\cdot)$ is the conditional expectation denoiser given in \eqref{eq:denoiser},

\begin{equation*}
 f_t(x) = \mathbb{E}\big \{X_0^n  \mid  \sqrt{\lambda_n} \tau^n_{t}  X_0^n + \sqrt{\tau^n_t} Z = x\big\}.
\end{equation*}

Notice that for either the Bernoulli or Bernoulli-Rademacher case, we have that $|f_t(x)| \leq 1$ for all $x \in \mathbb{R}$ since $X_0^n  \in \{- 1, 0, 1\}$.

 First consider $ P_{X,n} \sim {\rm Ber}(\rho_n)$ and we show that $f_t(\cdot)$ is Lipschitz continuous with Lipschitz constant $\sqrt{\lambda_n}$.
Let $\phi(x)$ denote the standard Gaussian density evaluated at $x$. First, by Bayes' Rule,

\begin{equation*}
\begin{split}
 f_t(x) &=\mathbb{E}\big \{X_0^n  \mid \sqrt{\lambda_n} \tau^n_{t}  X_0^n + \sqrt{\tau^n_t} Z = x\big\}  \\

&=P\big (X_0^n =1 \mid \sqrt{\lambda_n} \tau^n_{t} X_0^n + \sqrt{\tau^n_t} Z = x\big) = \frac{\rho_n \phi \big(    \frac{x-\sqrt{\lambda_n} \tau^n_{t} }{\sqrt{\tau^n_t}}\big)   }{(1-\rho_n) \phi \big(   \frac{x}{\sqrt{\tau^n_t}}\big)  + \rho_n \phi \big(  \frac{x-\sqrt{\lambda_n} \tau^n_{t} }{\sqrt{\tau^n_t}}\big)  }.

\end{split}
\end{equation*}

Now notice that $\frac{\partial}{\partial x} \phi (\frac{x-a }{b}) = - \frac{(x-a) }{b^2}\phi (\frac{x-a }{b}) $.  Using this and the representation above,

\begin{equation}
\begin{split}
\label{eq:deriv}

\frac{\partial}{\partial x} f_t(x) &= \frac{\partial}{\partial x}  \left[\frac{\rho_n \phi \big(    \frac{x-\sqrt{\lambda_n} \tau^n_{t} }{\sqrt{\tau^n_t}}\big)   }{(1-\rho_n) \phi \big(   \frac{x}{\sqrt{\tau^n_t}}\big)  + \rho_n \phi \big(  \frac{x-\sqrt{\lambda_n} \tau^n_{t} }{\sqrt{\tau^n_t}}\big)  } \right] \\

&=   \frac{-f_t(x)}{\tau^n_{t}}  \left[ (x-\sqrt{\lambda_n} \tau^n_{t})  - \frac{x (1-\rho_n) \phi \big(   \frac{x}{\sqrt{\tau^n_t}}\big)  + \rho_n  (x-\sqrt{\lambda_n} \tau^n_{t})  \phi \big(  \frac{x-\sqrt{\lambda_n} \tau^n_{t} }{\sqrt{\tau^n_t}}\big)   }{(1-\rho_n) \phi \big(   \frac{x}{\sqrt{\tau^n_t}}\big)  + \rho_n \phi \big(  \frac{x-\sqrt{\lambda_n} \tau^n_{t} }{\sqrt{\tau^n_t}}\big)  } \right] \\

&=   \frac{-f_t(x)(x-\sqrt{\lambda_n} \tau^n_{t}) }{\tau^n_{t}}  \left[  \frac {(1-\rho_n) \phi \big(   \frac{x}{\sqrt{\tau^n_t}}\big) \Big[1  -\frac{x}{(x-\sqrt{\lambda_n} \tau^n_{t}) } \Big]   }{(1-\rho_n) \phi \big(   \frac{x}{\sqrt{\tau^n_t}}\big)  + \rho_n \phi \big(  \frac{x-\sqrt{\lambda_n} \tau^n_{t} }{\sqrt{\tau^n_t}}\big)  } \right] \\

&=  \sqrt{\lambda_n} f_t(x)(1- f_t(x)).

\end{split}
\end{equation}

Therefore, using \eqref{eq:deriv}, we see that $\Big \lvert \frac{\partial}{\partial x} f_t(x) \Big \lvert \leq    \sqrt{\lambda_n} $ and it follows that $f_t(\cdot)$ is Lipschitz continuous with Lipschitz constant $  \sqrt{\lambda_n} $.

The fact  that $f_t(\cdot)$ is Lipschitz continuous with Lipschitz constant $\sqrt{\lambda_n}$ can be shown similarly for the case where $P_{X,n}$ is Bernoulli-Rademacher.

\end{proof}

\subsection{Finite sample guarantees}  \label{eq:appsec:finitesample}

Now we would like to discuss the proof of the result \eqref{eq:finite_sample_app}, namely,  for all order $2$ pseudo-Lipschitz functions denoted $\psi: \mathbb{R} \rightarrow \mathbb{R}$ with constant $L_{\psi}>0$ defined in Def.~\ref{def:PL}, for $\epsilon \in (0,1)$ and $t \geq 0$,

 \begin{equation}
 \begin{split}
 \mathbb{P} \Big(\Big| \frac{1}{n} \sum_{i=1}^n \psi(X_i, f_{t}(x^{t}_i)) -  \mathbb{E}\Big\{\psi\big(X_0^n,  f_{t}(\mu^n_{t} X_0^n + \sqrt{\tau^n_t} Z)\big) \Big\} \Big| \geq \epsilon \Big) \leq C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon^2}{\lambda_n^{2 t} L_{\psi}^{2t}}\Big\},
 \label{eq:finite_sample_app_2}
 \end{split}
 \end{equation}

 where $\bX = (X_1, \ldots, X_n)$ is the true signal and $C, C_t, c, c_t$ are universal constants not depending on $n$ or $\epsilon$, but with $C_t, c_t$ depending on the iteration $t$, whose exact value is given in Theorem~\ref{AMP-theorem}.

To prove the above, we will analyze a `symmetric'  AMP algorithm that we describe now, which is similar to the AMP algorithm in \eqref{eq:AMP}. Assume the matrix $\bZ \sim \textsf{GOE}(n)$ is an $n \times n$ matrix form the Gaussian Orthogonal Ensemble, i.e.\ $\bZ$ is a symmetric matrix with $\{Z_{ij}\}_{1 \leq i \leq j \leq n}$ are i.i.d.\ $\mathcal{N}(0,1/n)$, and $\{Z_{ii}\}_{1 \leq i  \leq n}$ are i.i.d.\ $\mathcal{N}(0,2/n)$.  Starting with an initial condition $\bh^0 \in \mathbb{R}^m$ independent of $\bZ$, let $\bh^{1} = \bZ g_0(\bh^0, \bX^n)$ and calculate for $t \geq 1$,
\begin{equation}
\bh^{t+1} = \bZ g_t(\bh^t, \bX^n) - \textsf{c}_t g_{t-1}(\bh^{t-1}, \bX^n).
\label{eq:sym_AMP}
\end{equation}
In the above, $g_t: \mathbb{R}^2 \to \mathbb{R}$ is Lipschitz and separable (act component-wise when applied to vectors) and may depend on $n$ through its Lipschitz constant $L_g^n$. The function $g_t$ takes
as its second argument  a random vector $\bX^n \in \mathbb{R}^n$ assumed to have entries that are i.i.d.\ according to $p_{X,n}$, a sub-Gaussian distribution, $\textsf{c}_t =  \frac{1}{n} \sum_{i=1}^n g'_t(h^{t}_i, X^n_i),$ with the derivative taken with respect to the first argument, and all terms with negative indices take the value $0$. Then the key result of AMP, stated in Theorem~\ref{thm:sym} below, is that for each $t \geq 1$, the empirical distribution of the components of iterates $\bh^t$ are approximately equal in distribution to a Gaussian $\mathcal{N}(0,\sigma^n_t)$ where the variances $\{\sigma^n_t\}_{t \geq 0}$ are defined via the state evolution: initializing with $\sigma^n_1 = \|g_0(\bh^0, \bX^n)\|^2/n$:
\begin{equation}
\sigma^n_{t+1} = \mathbb{E}\left[\left(g_{t}(\sqrt{\sigma^n_{t}}Z, X_0^n) \right)^2\right],
\label{eq:symm_SE}
\end{equation}
where the expectation is with respect to standard Gaussian $Z$ independent of $X_0^n \sim p_{X,n}$.

\begin{thm} \label{thm:sym}
Consider the AMP algorithm in \eqref{eq:sym_AMP} for $\bh^0 \in \mathbb{R}^m$ independent of $\bA$ and Lipschitz, separable $g_t(\cdot, \cdot)$ with Lipschitz constant $L_g^n>0$.   Then the following holds for any (order-$2$) pseudo-Lipschitz function $\phi: \mathbb{R}^2 \rightarrow \mathbb{R}$,  $\ep \in (0,1)$ and  $t \geq 0$.

 \begin{equation}
 \mathbb{P} \Big(\Big| \frac{1}{n} \sum_{i=1}^n \phi(h^{t}_i, X^n_i) -  \mathbb{E}\Big\{\phi\big(\sqrt{\sigma^n_t} Z, X^n_0\big) \Big\} \Big| \geq \epsilon \Big) \leq C C_t \exp\Big\{- \frac{c c_t n \epsilon^2}{L_{\phi}^2 L_{g}^{4(t-1)}  \gamma_n^{t}}\Big\},
 \end{equation}

where the expectation is with respect to standard Gaussian $Z$ independent of $X_0^n \sim p_{X,n}$ and $\sigma^n_t$ is defined in \eqref{eq:symm_SE} and

\begin{equation}
\gamma_n^{t} := (\nu^n +  \sigma^n_{1})  (\nu^n +  \sigma^n_{1} +  \sigma^n_{2})  \cdots  (\nu^n + \sum_{i=1}^{t} \sigma^n_{i}) \times \max\{1, \hat{\textsf{c}}_1\}  \max\{1, \hat{\textsf{c}}_2\} \cdots  \max\{1, \hat{\textsf{c}}_{t-1}\},
\end{equation}

where $\hat{\textsf{c}}_t = \mathbb{E}[ g'_t(\sqrt{\sigma^n_t} Z, X)]$ and $\nu$ is the variance factor of sub-Gaussian $X^n \sim p_{X,n}$ which equals $3 \rho_n$ for $p_{X, n}$ Bernoulli.

\end{thm}

In what follows we give the proof of Theorem~\ref{thm:sym}, which relies heavily on the proof of the finite sample guarantees for various `non-symmetric' AMP algorithms given in \cite{RushVenkataramanan}. Before we get to the proof of Theorem~\ref{thm:sym}, we discuss how we apply the result to our problem, leading to the concentration result in \eqref{eq:finite_sample_app_2}.

\paragraph{Proving \eqref{eq:finite_sample_app_2} with Theorem~\ref{thm:sym}.}
Recall that in our model~\eqref{WSM},

\begin{equation}\label{WSM_app}
\frac{1}{\sqrt{n}}\bW = \frac{\sqrt{\lambda_n}}{n} \bX\otimes \bX +  \bZ\,,
\end{equation}

where $\lambda_n >0$ controls the strength of the signal and the noise is i.i.d.\ gaussian $Z_{ij}\sim{\cal N}(0,1/n)$ for $i<j$ and symmetric $Z_{ij}=Z_{ji}$. Then the AMP algorithm for recovering $\bX$ from the data $\bW$ is given in \eqref{eq:AMP} and restated now.   Let $\bA = \bW/\sqrt{n}$ and initialize  with $\bx^0$ independent of $\bW$, such that $\langle \bx^0, \bX \rangle > 0$.  Then let $\bx^{1} = \bA  f_0(\bx^{0})$, and for $t \geq 1$, compute

\begin{equation}
\bx^{t+1} = \bA  f_t(\bx^{t}) - \mathsf{b}_t  f_{t-1}(\bx^{t-1}), \qquad \mathsf{b}_t  = \frac{1}{n} \sum_{i=1}^n f'_t(x^{t}_i),
\label{eq:AMP2}
\end{equation}

Notice that this AMP algorithm in \eqref{eq:AMP2} is similar to that in \eqref{eq:sym_AMP}, the only difference being that now the matrix $\bA$ is our data matrix (as opposed to it being $\textsf{GOE}(n)$ as is assumed in \eqref{eq:sym_AMP}). If we plug into \eqref{eq:AMP2} the value of $\bW$ from \eqref{WSM_app}, we find that $\bx^{1} = \frac{\sqrt{\lambda_n}}{n}  \bX \langle \bX, f_0(\bx^{0}) \rangle  +  \bZ  f_0(\bx^{0})$, and for $t \geq 1$,

\begin{equation}
\bx^{t+1} = \frac{\sqrt{\lambda_n}}{n}  \bX \langle \bX, f_t(\bx^{t}) \rangle  +  \bZ  f_t(\bx^{t}) - \mathsf{b}_t  f_{t-1}(\bx^{t-1}).
\label{eq:AMP3}
\end{equation}

Now  we define a related iteration to \eqref{eq:AMP3} as follows. Initialize with $\bh^0 = \bx^0$ with denoiser $g_{0}(\bh^{0}, \bX) := f_0(\bx^0)$ and $\bh^{1} =  \mu_{1}^n \bX^n + \bZ g_{0}(\bh^{0}, \bX) $.  Then calculate for $t \geq 1$,

\begin{equation}
\bh^{t+1} =   \bZ  g_t(\bh^{t}, \bX^n) - \mathsf{c}_t  g_{t-1}(\bh^{t-1}, \bX^n), \qquad \mathsf{c}_t  = \frac{1}{n} \sum_{i=1}^n g'_t(h^{t}_i, X^n_i)
\label{eq:AMP_correct}
\end{equation}

where $g_t(h, X) = f_t(h + \mu_{t}^n X^n)$ for $f_t(\cdot)$ the conditional expectation denoiser used in \eqref{eq:AMP3} and $ \mu_{t+1}^n$ calculated from the state evolution in \eqref{eq:state_evolution} for our original iteration (i.e., the algorithm in \eqref{eq:AMP2}).  In the above, $\bX^n$ is the signal in \eqref{WSM_app} and we drop the $n$ superscript in what follows.  Then we notice that the iteration in \eqref{eq:AMP_correct} takes the exact form of the symmetric AMP in \eqref{eq:sym_AMP} with state evolution given by \eqref{eq:symm_SE}.  In particular, the state evolution associated with \eqref{eq:AMP_correct} takes the form $\sigma^n_1 = \|g_0(\bh^0, \bX)\|^2/n$ and for $t \geq 1,$

\begin{equation}
\sigma^n_{t+1} = \mathbb{E}\left[\left(g_{t}(\sqrt{\sigma^n_{t}}Z, X) \right)^2\right]= \mathbb{E}\left[\left(f_{t}(\sqrt{\sigma^n_{t}}Z + \mu^n_t X) \right)^2\right].
\label{eq:symm_SE_new}
\end{equation}

We notice that in the above, the state evolution has the same form as the state evolution for the AMP algorithm in \eqref{eq:AMP3} defined  in \eqref{eq:state_evolution2} as in $\sigma^n_1 = \tau^n_1$ and $\sigma^n_{t+1} = \tau^n_{t+1}$ for all $t \geq 1$ and for this reason we use the $\tau$ notation in what follows.
As the AMP algorithm in \eqref{eq:AMP_correct} takes the exact form of the symmetric AMP in \eqref{eq:sym_AMP}, we can apply Theorem~\ref{thm:sym}.  The relevant pseudo-Lipschitz function for which to apply Theorem~\ref{thm:sym} is $\phi(h^{t}_i, X^n_i) =  \psi(f_{t}(h^{t}_i+ \mu_{t}^n X^n_i), X^n_i)$ for $\psi$ the pseudo-Lipschitz function in \eqref{eq:finite_sample_app_2}, and using this Theorem~\ref{thm:sym} implies

 \begin{equation}
 \begin{split}
& \mathbb{P} \Big(\Big| \frac{1}{n} \sum_{i=1}^n \psi(f_{t}(h^{t}_i+ \mu_{t}^n X_i), X_i) -  \mathbb{E}\Big\{\psi\big(f_{t}(\sqrt{\tau^n_t} Z+ \mu_{t}^n X), X\big) \Big\} \Big| \geq \epsilon \Big) \\

&\hspace{5mm} \leq C C_{t} \exp\Big\{- \frac{c c_{t} n \epsilon^2}{L_{\phi}^2 L_{g}^{4(t-1)}  \gamma_n^{t}}\Big\} = C C_{t} \exp\Big\{- \frac{c c_{t} n \epsilon^2}{L_{\psi}^2 \max\{1,  \lambda_n (\tau_{t}^n)^2\} \lambda_n^{2t-1}  \gamma_n^{t}}\Big\},
  \label{eq:sym_result}
  \end{split}
 \end{equation}

with $\tau^n_t = \sigma^n_t$ defined in \eqref{eq:symm_SE_new} and

\begin{equation}
\gamma_n^{t} := (\nu^n +  \tau^n_{1})  (\nu^n +  \tau^n_{1} +  \tau^n_{2})  \cdots  (\nu^n + \sum_{i=1}^{t} \tau^n_{i}) \times \max\{1, \hat{\textsf{c}}_1\}  \max\{1, \hat{\textsf{c}}_2\} \cdots  \max\{1, \hat{\textsf{c}}_{t-1}\},
\label{eq:gamma}
\end{equation}

where $\hat{\textsf{c}}_t = \mathbb{E}[ g'_t(\sqrt{\tau^n_t} Z, X)] =  \mathbb{E}[ f'_t(\sqrt{\tau^n_t} Z + \mu^n_t X)]$ and $\nu$ is the variance factor of sub-Gaussian $X^n \sim p_{X,n}$ which equals $3 \rho_n$ for $p_{X, n}$ Bernoulli.  We note that the final equality in \eqref{eq:sym_result} follows since $L_g = L_f = \sqrt{\lambda_n}$ in this case and $L_{\phi} = L_{\psi} \max\{\sqrt{\lambda_n},  \lambda_n \tau_{t}^n\}$ which can be seen as follows

 \begin{equation*}
 \begin{split}
\lvert  \phi(h,X) -   \phi(\tilde{h},\tilde{X}) \lvert &= \lvert   \psi(f_{t}(h+ \mu_{t}^n X), X) -     \psi(f_{t}(\tilde{h}+ \mu_{t}^n \tilde{X}),\tilde{X})  \lvert \\
&\leq L_{\psi}  \| (f_{t}(h+ \mu_{t}^n X), X) -    (f_{t}(\tilde{h}+ \mu_{t}^n \tilde{X}),\tilde{X})  \|\\
&\leq L_{\psi} ( | f_{t}(h+ \mu_{t}^n X) - f_{t}(\tilde{h}+ \mu_{t}^n \tilde{X})|+ | X  - \tilde{X}|) \\
&\leq L_{\psi}  L_f | h- \tilde{h}| + L_{\psi}  L_f \mu_{t}^n |X- \tilde{X}|+ L_{\psi} | X  - \tilde{X}|.
\end{split}
 \end{equation*}

 Then result \eqref{eq:finite_sample_app_2} is proved with the following lemma.
 \begin{lemma}
 Define $\textsf{bound}_t : =  C C_{t} \exp\Big\{- \frac{c c_{t} n \epsilon^2}{L_{\psi}^2 \max\{1,  \lambda_n (\tau_{t}^n)^2\} \lambda_n^{2t-1}  \gamma_n^{t}}\Big\}$ for $ \gamma_n^{t}$ in \eqref{eq:gamma}.  Then the following are true

 \begin{align}

  \mathbb{P} \Big(\Big| \frac{1}{n} \sum_{i=1}^n \psi(f_{t}(x^{t}_i), X_i) -  \mathbb{E}\Big\{\psi\big(f_{t}(\mu^n_{t} X_0 + \sqrt{\tau^n_t} Z), X_0\big) \Big\} \Big| \geq \epsilon \Big)  &\leq \textsf{bound}_t, \label{eq:lemmabound1} \\
   \mathbb{P} \Big(\Big| \frac{1}{n} \sum_{i=1}^n \psi(f_{t}(x^{t}_i), X_i)  - \psi(f_{t}(h^{t}_i+ \mu_{t}^n X_i), X_i) \Big| \geq \epsilon \Big)&\leq \textsf{bound}_t,  \label{eq:lemmabound2}\\
   \mathbb{P} \Big( \frac{1}{\sqrt{n \rho_n}}   \Big\| \bx^{t} - \bh^{t} - \mu_{t}^n \bX  \Big\| \geq \frac{\kappa \epsilon}{ L_{\psi}  L_f \sqrt{\rho_n}} \Big)&\leq \textsf{bound}_t. \label{eq:lemmabound3}

   \end{align}

 \end{lemma}

 \begin{proof}
 We first note that \eqref{eq:lemmabound1} follows directly from \eqref{eq:lemmabound2} by Lemma~\ref{sums} and the bound in \eqref{eq:sym_result}.
  Next notice that \eqref{eq:lemmabound2} follows directly from \eqref{eq:lemmabound3} by the following upper bound.

 \begin{equation*}
 \begin{split}
&\Big| \frac{1}{n} \sum_{i=1}^n \psi(f_{t}(x^{t}_i), X_i)  - \psi(f_{t}(h^{t}_i+ \mu_{t}^n X_i), X_i) \Big|  \leq \frac{1}{n} \sum_{i=1}^n \Big| \psi(f_{t}(x^{t}_i), X_i) -\psi(f_{t}(h^{t}_i+ \mu_{t}^n X_i), X_i) \Big| \\

 & \leq \frac{1}{n} \sum_{i=1}^n L_{\psi} \Big(1 + \|(f_{t}(x^{t}_i), X_i)\| + \|(f_{t}(h^{t}_i+ \mu_{t}^n X_i), X_i)\| \Big)  \Big| f_{t}(x^{t}_i) - f_{t}(h^{t}_i+ \mu_{t}^n X_i)  \Big|\\

 & \leq \frac{ \kappa L_{\psi} }{n} \sum_{i=1}^n  \Big| f_{t}(x^{t}_i) - f_{t}(h^{t}_i+ \mu_{t}^n X_i)  \Big|  \leq \frac{ \kappa L_{\psi}  L_f }{n} \sum_{i=1}^n  \Big| x^{t}_i - h^{t}_i- \mu_{t}^n X_i  \Big| \leq \frac{ \kappa L_{\psi}  L_f \sqrt{\rho_n}}{\sqrt{n}}   \Big\| \frac{1}{\rho_n}(\bx^{t} - \bh^{t}- \mu_{t}^n \bX)  \Big\|.
\end{split}
 \end{equation*}

 by the above bound,

 \begin{equation*}
 \mathbb{P} \Big(\Big| \frac{1}{n} \sum_{i=1}^n \psi(f_{t}(x^{t}_i), X_i)  - \psi(f_{t}(h^{t}_i+ \mu_{t}^n X_i), X_i) \Big| \geq \epsilon \Big) \leq \mathbb{P} \Big( \frac{1}{\sqrt{n \rho_n}}   \Big\| \bx^{t} - \bh^{t} - \mu_{t}^n \bX  \Big\| \geq \frac{\kappa \epsilon}{ L_{\psi}  L_f \sqrt{\rho_n}} \Big),
 \end{equation*}

 thus, our goal is to prove \eqref{eq:lemmabound3}.
This is done inductively. First notice that the case $t=0$ is trivially true since $ \bx^{0} = \bh^{0}$ and $ \mu_{0}^n = 0$.  Thus we assume \eqref{eq:lemmabound3} is true up through iteration $t-1$ and prove it for iteration $t$.

\end{proof}

Considering result \eqref{eq:to_show_delta}, and using the definitions of $\bx^{t+1}$ and $\bh^{t+1}$ from \eqref{eq:AMP3} and \eqref{eq:AMP_correct} along with Cauchy-Schwarz inequality, we have that

 \begin{equation}
 \begin{split}
  \label{eq:bound2}
& \frac{1}{n \rho_n} \sum_{i=1}^n  \Big| x^{t}_i - h^{t}_i- \mu_{t}^n X_i  \Big|^2\\

 &\leq   \frac{3}{n\rho_n}\Big\lvert  \frac{\sqrt{\lambda_n}}{n}  \langle \bX, f_{t-1}(\bx^{t-1}) \rangle  - \mu_{t}^n\Big \lvert^2 \sum_{i=1}^n  X_i^2 +   \frac{1}{n\rho_n} \sum_{i=1}^n  \Big|   [\bZ  f_{t-1}(\bx^{t-1})]_i -   [\bZ g_{t-1}(\widetilde{\bx}^{t-1}, \bX)]_i \Big|^2 \\%
 & +  \frac{1}{n\rho_n} \sum_{i=1}^n  \Big|  \mathsf{b}_{t-1}  f_{t-2}(x^{t-2}_i) - \mathsf{c}_{t-1} g_{t-2}(h^{t-2}_i, X_i)  \Big|^2 \\

  &=3  \Big \lvert \frac{\sqrt{\lambda_n}}{n}  \langle \bX, f_{t-1}(\bx^{t-1}) \rangle  - \mu_{t}^n \Big\lvert^2  \frac{1}{n \rho_n}  \sum_{i=1}^n  X_i^2  +   \frac{3}{n \rho_n}  \Big \|  \bZ \big( f_{t-1}(\bx^{t-1}) -   g_{t-1}(\bh^{t-1}, \bX) \big) \Big\|^2 \\%
 & +  \frac{3}{n \rho_n}   \Big\|  \mathsf{b}_{t-1}  f_{t-2}(\bx^{t-2}) - \mathsf{c}_{t-1} g_{t-2}(\bh^{t-2}, \bX)  \Big \|^2.
\end{split}
 \end{equation}

Now we use the upper bounds in  \eqref{eq:bound2} along with Lemma~\ref{sums} to give the following upper bound on the probability on the LHS of \eqref{eq:to_show_delta}:

 \begin{equation}
 \begin{split}
\mathbb{P} \Big( \frac{1}{n}   \Big\| \bx^{t} - \bh^{t} - \mu_{t}^n \bX  \Big\|^2 \geq \frac{\kappa \epsilon^2}{ L_{\psi}^2  L_f^2} \Big)  &\leq \mathbb{P} \Big( \Big \lvert \frac{\sqrt{\lambda_n}}{n}  \langle \bX, f_{t-1}(\bx^{t-1}) \rangle  - \mu_{t}^n \Big\lvert^2 \frac{1}{n}  \sum_{i=1}^n   X_i^2  \geq \frac{\kappa \epsilon}{ L_{\psi}^2  L_f^2} \Big) \\

 &+ \mathbb{P} \Big(\frac{1}{n}  \Big \|  \bZ \big( f_{t-1}(\bx^{t-1}) -   g_{t-1}(\bh^{t-1}, \bX) \big) \Big\|^2  \geq \frac{\kappa \epsilon}{L_{\psi}^2  L_f^2} \Big) \\

 &+ \mathbb{P} \Big( \frac{1}{n}   \Big\|  \mathsf{b}_{t-1}  f_{t-2}(\bx^{t-2}) - \mathsf{c}_{t-1} g_{t-2}(\bh^{t-2}, \bX)  \Big \|^2 \geq \frac{\kappa \epsilon}{L_{\psi}^2  L_f^2} \Big).

 \label{eq:three_terms}
 \end{split}
 \end{equation}

We label the three terms in the above $T_1-T_3$ and provide an upper bound for each.

First consider term $T_1$ of \eqref{eq:three_terms}.

\begin{equation}
  \begin{split}

&T_1 \leq  \mathbb{P} \Big(  \Big|   \frac{\sqrt{\lambda_n}}{n} \langle \bX, f_t(\bx^{t}) \rangle  -  \mu^n_{t}  \Big|^2  \Big( \Big \lvert\frac{ 1}{n} \sum_{i=1}^nX_i^2  \Big) \geq \frac{\kappa \epsilon}{ L^2_{\psi} L^2_f}  \Big) \\

&\leq  \mathbb{P} \Big(  \Big|   \frac{\sqrt{\lambda_n}}{n} \langle \bX, f_t(\bx^{t}) \rangle  -  \mu^n_{t}  \Big| \geq \frac{\kappa \sqrt{\epsilon}}{ \sqrt{\rho_n} L_{\psi} L_f}  \Big)  +  \mathbb{P} \Big(   \frac{ 1}{n} \sum_{i=1}^nX_i^2  \geq2 \rho_n \Big)  \\

&\leq  C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon^2}{\rho_n \lambda_n^{2t} L_{\psi}^{2t} }\Big\} + 2 \exp\Big\{- \frac{ n \rho_n}{2 }\Big\}

\label{eq:T1_bound}
 \end{split}
 \end{equation}

  where the final inequality follows by the induction hypothesis for the first term,
  using the pseudo-Lipschitz function $\psi(a, b) = a b$, and Chernoff's bounds (Lemma~\ref{lem:chernoff}) for the second term.

Now consider term $T_2$ of \eqref{eq:three_terms} and first notice that

\begin{equation*}
\begin{split}

&\frac{1}{\sqrt{n}}  \Big \|  \bZ \big( f_{t-1}(\bx^{t-1}) -   g_{t-1}(\bh^{t-1}, \bX) \big) \Big\| \leq \frac{1}{\sqrt{n}}   \|  \bZ \|_{op} \Big\| f_{t-1}(\bx^{t-1}) -   g_{t-1}(\bh^{t-1}, \bX) \Big\| \\

&\leq\big( \big \lvert  \|  \bZ \|_{op} - 4 \big \lvert + 4 \big)  \frac{1}{\sqrt{n}} \Big\| f_{t-1}(\bx^{t-1}) -   f_{t-1}(\bh^{t-1} + \mu_{t-1}^n \bX) \Big\| \\

&\leq\big( \big \lvert  \|  \bZ \|_{op} - 4 \big \lvert + 4 \big)  \frac{1}{\sqrt{n}} L_f \Big\| \bx^{t-1} -   \bh^{t-1} + \mu_{t-1}^n \bX \Big\|,

\end{split}
\end{equation*}

where the final inequality uses the Lipschitz property of $f_t$.
Therefore, using the same strategy as in \eqref{eq:T1_bound}, we have

\begin{equation*}
  \begin{split}

&T_2 \leq   \mathbb{P} \Big(\big( \big \lvert  \|  \bZ \|_{op} - 4 \big \lvert + 4 \big)  \frac{1}{\sqrt{n}} L_f \Big\| \bx^{t-1} -   \bh^{t-1} + \mu_{t-1}^n \bX \Big\| \geq \frac{\kappa \epsilon}{L_{\psi}  L_f} \Big)  \\

&\leq  \mathbb{P} \Big(   \frac{1}{\sqrt{n}} \Big\| \bx^{t-1} -   \bh^{t-1} + \mu_{t-1}^n \bX \Big\| \geq \frac{\kappa \sqrt{\ep}}{L_{\psi}  L_f^2} \Big) + \mathbb{P} \Big(  \big \lvert  \|  \bZ \|_{op} - 4 \big \lvert   \geq \sqrt{ \ep}  \Big) \\

&\leq  C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon}{\rho_n \lambda_n^{2(t+1)} L_{\psi}^{2t} }\Big\} + 2 \exp\Big\{- \frac{ n \rho_n \ep}{2 }\Big\}

 \end{split}
 \end{equation*}
 where the final inequality follows from the inductive hypothesis for \eqref{eq:to_show_delta} and \textcolor{red}{a result about operator norms of Gaussian matrices.}

 Finally consider term $T_3$ of \eqref{eq:three_terms}. We first give an upper bound using  the definition of $g_t$ and the Lipschitz property of $f_t$ as follows:
\begin{equation}
\begin{split}
\label{eq:termT3_1}
 & \Big\|  \mathsf{b}_{t-1}  f_{t-2}(\bx^{t-2}) - \mathsf{c}_{t-1} g_{t-2}(\bh^{t-2}, \bX)  \Big \| \\

 & \leq  |\mathsf{b}_{t-1}| \Big\|   f_{t-2}(\bx^{t-2}) -  g_{t-2}(\bh^{t-2}, \bX)  \Big \| +  | \mathsf{b}_{t-1}   - \mathsf{c}_{t-1} |  \Big \| g_{t-2}(\bh^{t-2}, \bX)  \Big \| \\

 & \leq  |\mathsf{b}_{t-1}| \Big\|   f_{t-2}(\bx^{t-2}) -  f_{t-2}(\bh^{t-2} - \mu_{t-2}^n \bX)  \Big \| +  | \mathsf{b}_{t-1}   - \mathsf{c}_{t-1} |  \Big \|  f_{t-2}(\bh^{t-2} - \mu_{t-2}^n \bX)  \Big \| \\

 & \leq   \sqrt{\lambda_n} L_f \Big\|  \bx^{t-2} -  \bh^{t-2} + \mu_{t-2}^n \bX \Big \| +  | \mathsf{b}_{t-1}   - \mathsf{c}_{t-1} | \sqrt{n}.
  \end{split}
  \end{equation}

In the final step we use that

 \begin{equation*}
 | \mathsf{b}_{t-1}   | \leq  \frac{1}{n} \sum_{i=1}^n \big| f'_{t-1}(x^{t-1}_i)  \big | \leq  \sqrt{\lambda_n}, \qquad \text{ and } \qquad \Big \|  f_{t-2}(\bh^{t-2} - \mu_{t-2}^n \bX)  \Big \|^2 \leq n.
 \end{equation*}

 We investigate the term $| \mathsf{b}_{t-1}   - \mathsf{c}_{t-1} |$ and recall from their definitions in \eqref{eq:AMP2} and \eqref{eq:AMP_correct},

 \begin{equation}
 \begin{split}
& | \mathsf{b}_{t-1}   - \mathsf{c}_{t-1} | \leq  \frac{1}{n} \sum_{i=1}^n \big| f'_{t-1}(x^{t-1}_i) -  g'_{t-1}(h^{t-1}_i, X_i) \big |=\frac{1}{n} \sum_{i=1}^n \big|  f'_{t-1}(x^{t-1}_i) -    f'_{t-1}(h^{t-1}_i - \mu_{t-1}^n X_i ) \big | \\
&\overset{(a)}{=}   \frac{\sqrt{\lambda_n}}{n} \sum_{i=1}^n   \Big|f_{t-1}(x^{t-1}_i)(1- f_{t-1}(x^{t-1}_i)) -  f_{t-1}(h^{t-1}_i - \mu_{t-1}^n X_i)(1- f_{t-1}(h^{t-1}_i - \mu_{t-1}^n X_i) )\Big | \\
&\overset{(b)}{\leq} \frac{\sqrt{\lambda_n}}{n} \sum_{i=1}^n \Big|   f_{t-1}(x^{t-1}_i) -  f_{t-1}(h^{t-1}_i - \mu_{t-1}^n X_i)  \Big | \overset{(c)}{\leq} \frac{L_f \sqrt{\lambda_n}}{n} \sum_{i=1}^n \Big|   x^{t-1}_i -  h^{t-1}_i + \mu_{t-1}^n X_i  \Big |.
\label{eq:sfterms}
 \end{split}
 \end{equation}

In the above, step $(a)$ uses Lemma~\ref{lem:PL} for computing the derivative $f_t$ and step $(b)$ uses the bound
  \begin{equation}
 \begin{split}
 \big| f_{t-1}(a)(1- f_{t-1}(a)) -  f_{t-1}(b)(1- f_{t-1}(b) \big | &\leq  \big| f_{t-1}(a) -  f_{t-1}(b)\big |   + \big |  [f_{t-1}(a)]^2 -  [f_{t-1}(b)]^2 \big | \\

& \leq  \kappa \big| f_{t-1}(a) -  f_{t-1}(b)\big |.
 \end{split}
 \end{equation}
 Finally, step $(c)$ in \eqref{eq:sfterms} uses the Lipschitz property of $f_{t}$.
Plugging the above bounds in \eqref{eq:sfterms} into \eqref{eq:termT3_1}, we have

 \begin{equation}
\begin{split}
\label{eq:termT3_2}
 & \Big\|  \mathsf{b}_{t-1}  f_{t-2}(\bx^{t-2}) - \mathsf{c}_{t-1} g_{t-2}(\bh^{t-2}, \bX)  \Big \| \\

  & \leq   \sqrt{\lambda_n} L_f \Big\|  \bx^{t-2} -  \bh^{t-2} + \mu_{t-2}^n \bX \Big \| + \sqrt{\lambda_n}   L_f    \Big\|   \bx^{t-1} - \bh^{t-1} + \mu_{t-1}^n \bX  \Big \|.

  \end{split}
  \end{equation}

 Now we have from Lemma~\ref{sums} that

 \begin{equation}
\begin{split}
\label{eq:termT3_2}
T_3 &\leq 2 \mathbb{P} \Big(\frac{1}{\sqrt{n}}  \Big\|   \bx^{t-1} - \bh^{t-1} + \mu_{t-1}^n \bX  \Big \| \geq \frac{\kappa \sqrt{\epsilon}}{L_{\psi} L^2_f \sqrt{\lambda_n}} \Big)\leq  C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon}{ \lambda_n^{2(t+2)} L_{\psi}^{2t} }\Big\} .
  \end{split}
  \end{equation}

The final bound  follows from the inductive hypothesis for \eqref{eq:to_show_delta}.

\paragraph{Proving Theorem~\ref{thm:sym}.}
 Now we we discuss the proof of Theorem~\ref{thm:sym}.
 In doing so, we rely heavily on the proof of the finite sample guarantees for various `non-symmetric' AMP algorithms given in \cite{RushVenkataramanan}. So to begin with, we review the results in \cite{RushVenkataramanan}.
The main concentration result of \cite{RushVenkataramanan}, restated in Theorem \ref{thm:main_amp_perf} below, analyzes the following general AMP recursion. Let $\bA \in \mathbb{R}^{m \times n}$ be a matrix with i.i.d.\ standard Gaussian entries $A_{ij} \sim \mathcal{N}(0,\frac{1}{n})$ for $1 \leq i \leq m$ and $1 \leq j \leq n$.
Set an initial condition $\bv^{0} \in \mathbb{R}^n$ independent of $\bA$ then for $t \geq 0$, calculate
 \begin{equation}
\begin{split}
\bu^t & = \bA f_t(\bv^t, \bV^n) - \lambda_t g_{t-1}(\bu^{t-1}, \bU^m), \\
\bv^{t+1} & = \bA^* g_{t}(\bu^{t}, \bU^m) - \xi_t  f_t(\bv^t, \bV^n).
\end{split}
\label{eq:gen_rec0}
 \end{equation}
In the above, the vectors $\bu^t \in \mathbb{R}^m$, $\bv^{t+1} \in \mathbb{R}^n$  describe the state of the algorithm, the functions $f_t, g_t: \mathbb{R}^2 \to \mathbb{R}$ are Lipschitz functions with constants $L^n_f, L^m_g > 0$ that are also separable, taking as input random vectors $\bU^m \in \mathbb{R}^m$ and $\bV^n \in \mathbb{R}^n$ whose entries are i.i.d.\ according to a sub-Gaussian distributions $p_{U,m}$ and $p_{V,n}$, and the scalars $\lambda_t$ and $ \xi_t$ are computed from the state of the algorithm as
\begin{equation*}
\lambda_t =  \frac{1}{m} \sum_{i=1}^n f'_t(v^{t}_i, V^n_i), \qquad  \xi_t  = \frac{1}{n} \sum_{i=1}^n g'_t(u^{t}_i, U^m_i),
\end{equation*}
where the derivatives are taken with respect to the first argument.
The state evolution is then defined as follows: setting $\sigma^m_1 = \|f_0^2(\bv^0, \bV^n)\|^2/m$ and calculate for $t \geq 0$,
\begin{equation}
\label{eq:nonsym_AMP}
\tau^n_{t+1} = \mathbb{E}\left[\left(g_{t}(\sqrt{\sigma^m_{t}}Z, U^m) \right)^2\right], \qquad \sigma^m_{t+1} = \frac{n}{m}\mathbb{E}\left[\left(f_{t+1}(\sqrt{\tau^n_{t+1}}Z, V^n) \right)^2\right],
\end{equation}
where $Z$ is a standard Gaussian random variable independent of $U^m \sim p_{U, m}$ and $V \sim p_{V,n}$.

The AMP algorithm given in \eqref{eq:sym_AMP} is a symmetric version of the one in \eqref{eq:gen_rec0} where the state of the algorithm is represented by a single vector $\bx^{t+1}  \in \mathbb{R}^{n}$, the function $f_t: \mathbb{R}^2 \to \mathbb{R}$ in \eqref{eq:AMP} is Lipschitz and separable with Lipschitz constant $L_f^n > 0$ possibly depending on $n$, and $\mathsf{b}_t$ is a constant computed from the state of the algorithm. We present here the rigorous non-asymptotic analysis given in \cite{RushVenkataramanan} for the recursion in \eqref{eq:gen_rec0}.  We show that this result can be easily extended to obtain an analogous non-asymptotic result for the symmetric recursion in \eqref{eq:AMP}.

Before stating Theorem \ref{thm:main_amp_perf} below, we give the assumptions on the model and the functions used to define the AMP.  In what follows, $K, \kappa > 0$ are generic positive constants whose values are not exactly specified but do not depend on $n$. \\

 \textbf{Random Vectors:} Random vectors $\bU^m \in \mathbb{R}^m$ and $\bV^n \in \mathbb{R}^n$ are used for the denoising functions. The entries of the vectors are i.i.d.\ according to a sub-Gaussian distributions $p_{U,m}$ and $p_{V,n}$.  We recall that a zero-mean random variable $X$ is sub-Gaussian if there exist positive constants $K, \kappa$ such that $P(\abs{X - \mathbb{E}X} > \ep) \leq K e^{-\kappa \ep^2}$, for all $\ep >0$. \\

\textbf{The Functions $f_t, g_t$}: The denoising functions, $f_t: \mathbb{R}^2 \rightarrow \mathbb{R}$ and $g_t: \mathbb{R}^2 \rightarrow \mathbb{R}$, in \eqref{eq:gen_rec0} are Lipschitz continuous for each $t \geq 0$, with Lipschitz constants denoted $L^n_f, L^n_g >0$, may depend on $n$. By the Lipschitz property, $f_t, g_t$ are weakly differentiable. The weak derivatives, denoted by $f'_t, g'_t$, is assumed to be differentiable.

In addition, the result \cite[Theorem 1]{RushVenkataramanan} uses a stopping criterion similar to the one discussed for the symmetric AMP above. The details can be found in \cite[Section 2.1]{RushVenkataramanan} and we do not elaborate here.
Under the above assumptions, the main result in \cite[Theorem 1]{RushVenkataramanan} is restated below in Theorem \ref{thm:main_amp_perf}.
\begin{thm}{\cite[Theorem 1]{RushVenkataramanan}} \label{thm:main_amp_perf}
Under the assumptions above, the following holds for any (order-$2$) pseudo-Lipschitz function $\phi: \mathbb{R}^2 \rightarrow \mathbb{R}$ with constant $L_{\phi}$,  $\ep \in (0,1)$ and  $0 \leq t < T^*$, where $T^*$ is the first iteration for which the stopping criterion is satisfied.
 \begin{equation}
 \begin{split}
P\left(\left \lvert \frac{1}{n} \sum_{i=1}^n \phi(v^{t+1}_i, V^n_i) - \mathbb{E}\left[\phi\left( \tau_{t+1} Z, V^n \right) \right]\right \lvert \geq \ep\right) \leq  C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon^2}{L_f^{2t}  L_g^{2t} L_{\phi}^2}\Big\} \\
P\left(\left \lvert \frac{1}{m} \sum_{i=1}^m \phi(u^{t}_i, U^m_i) - \mathbb{E}\left[\phi\left( \sigma_{t} Z, U^m \right) \right]\right \lvert \geq \ep\right) \leq  C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon^2}{L_f^{2t} L_g^{2t}  L_{\phi}^2}\Big\}
\label{eq:PL_conc_result}
 \end{split}
 \end{equation}
In the expectation above,  $Z \sim \mathcal{N}(0,1)$ independent of $U^m \sim p_{U,m}$ and $V^n \sim p_{V,n}$ and  $\tau^n_t, \sigma^m_t$ is given by \eqref{eq:nonsym_AMP}.  The constants $C_t, C_t$ are given by
$C_t =C_1^{t} (t!)^{C_2},  c_t = [c_1^{t} (t!)^{c_2}]^{-1}$  and $C, C_1, C_2, c, c_1, c_2$ are universal constants not depending on $n$ or $\epsilon$.
\end{thm}

In what follows we discuss the proof of Theorem~\ref{thm:main_amp_perf} originally given in \cite{RushVenkataramanan} and show how it is adapted for the symmetric version, in particular focusing on the dependence of the Lipschitz constants in the bound.

\paragraph{Spectral Initialization.}
As mentioned previously in Section~\ref{sec:matrixWalgo}, we will assume that the AMP iteration in \eqref{eq:gen_rec0} was initialized with $\bv^{0} \in \mathbb{R}^n$ independent of $\bA$. For estimation with a Bernoulli-Rademacher signal prior, one needs to instead use a spectral initialization that will not be independent of the matrix $\bA$. Theoretically, as introduced in \cite{montanari2017estimation}, one deals with this dependency by analyzing the AMP iteration with a matrix $\widetilde{\bA}$ that is an \emph{approximate} representation of the conditional distribution of $\bA$ given the initialization, and then showing that with high probability the two algorithms are close each other.  We do not give the details of this rather technical argument here, and instead analyze the simpler case using an independent initialization, though the generalize is likely straightforward.

\paragraph{Conditional Distribution Step.}
The proof of \cite[Theorem 1]{RushVenkataramanan} proceeds in two steps.  In the first step, one studies the conditional distribution of $\bA$ given the  output of the algorithm up until iteration $t$, treating $\bA$ as random and the output as deterministic.  In the non-symmetric AMP, $\bA$ is an i.i.d.\ Gaussian measurement matrix and this conditional distribution was  originally studied in \cite{bayati2011dynamics} and the result is concisely stated in \cite[ Lemma 4.2]{RushVenkataramanan}. For the symmetric AMP in \eqref{eq:sym_AMP}, the matrix $\bZ$ is $\textsf{GOE}(n)$ and so this conditioning argument needs to take into account the symmetry of the matrix entries.  This has been studied in other works that give asymptotic characterizations of the performance of symmetric AMP, for example in \cite[Lemma 3]{Montanari-Javanmard}, and these results apply directly to our case since this distributional characterization is already non-asymptotic and does not change in our setting.

\newcommand{\norm}[1]{\lVert#1\rVert}
\newcommand{\mscrs}{\mathscr{S}}
\newcommand{\bH}{\mathbf{H}}
\newcommand{\bDel}{\boldsymbol{\Delta}}
\newcommand{\bigM}{\mathbf{M}}

Using \cite[Lemma 3]{Montanari-Javanmard} to characterize the distribution of $\bZ$ conditioned on the sigma algebra $\mathscr{S}_{t}$, we are able to specify the conditional distributions of $\bh^{t+1}$ given $\mathscr{S}_{t}$ where we define $\mathscr{S}_{t}$ for $ t\geq 0$ to be the sigma-algebra generated by
\begin{equation*}
\bh^0, \bh^1, ..., \bh^{t}, \mathbf{m}^0 := g_0(\bh^0, \bX^n), ...,  \mathbf{m}^t := g_t(\bh^t, \bX^n),\text{ and }  \bX^n.
\end{equation*}
Notice we have introduced the notation $\mathbf{m}^0 := g_0(\bh^0, \bX^n), ..., \mathbf{m}^t := g_t(\bh^t, \bX^n)$.
Observe that conditioning on $\mscrs_{t}$ is equivalent to conditioning on the linear constraint\footnote{While conditioning on the linear constraints, we emphasize that only $\bA$ is treated as random.}
\begin{equation*}
\bZ \bigM_{t} = \bY_{t},
\end{equation*}
where $\bigM_t \in \mathbb{R}^{n \times (t+1)}$ and $\bH_t \in \mathbb{R}^{n \times (t+1)}$ are the matrices
\begin{equation*}
\bigM_{t} = [\mathbf{m}^0 | \mathbf{m}^1 | ... |\mathbf{m}^t] \text { and } \bH_{t} = [\bh^0 | \bh^1 | ... | \bh^{t}],
\end{equation*}
and $\bY_t \in \mathbb{R}^{n \times (t+1)}$ is the matrix $\bY_{t} = \bH_t + [\mathbf{0} |\bigM_{t-1}] \boldsymbol{\textsf{C}_t}$ where
$ \boldsymbol{\textsf{C}_t} =  \text{diag}(\textsf{c}_0, \ldots, \textsf{c}_{t-1})$.
Note that the notation $[\bc_1 \mid \bc_2 \mid \ldots \mid \bc_k]$ is used to denote a matrix with columns $\bc_1, \ldots, \bc_k$.
\textcolor{red}{Check dimensions.}
Thus, we find the following result for the symmetric AMP in \eqref{eq:sym_AMP}.

We use the notation $\mathbf{m}^{t+1}_{\|}$ to denote the projection of $\mathbf{m}^{t+1}$ onto the column space of $\bigM_t$. Let
 \begin{equation}
 \boldsymbol{\alpha}^t := (\alpha^t_0, \ldots, \alpha^t_{t-1})^*
 \label{eq:vec_alph_gam_conc}
\end{equation}
 be the coefficient vectors of these projections, i.e.,

$\mathbf{m}^{t+1}_{\|} := \sum_{i=0}^{t} \alpha^t_i \mathbf{m}^i$,

meaning $ \boldsymbol{\alpha}^t = (\bigM_t^T \bigM_t)^{-1}\bigM_t^T \mathbf{m}^{t+1}.$
 The projections of $\mathbf{m}^{t+1}$onto the orthogonal complement of $\bigM_t$, is denoted by

$\mathbf{m}^{t+1}_{\perp} := \mathbf{m}^{t+1} - \mathbf{m}^{t+1}_{\|}.$

 Lemma \ref{lem:main_lem}  shows that for large $n$, the entries of $\boldsymbol{\alpha}$  are concentrated around constants. In what follows we show that the vector $ \boldsymbol{\alpha}^t$ in \eqref{eq:vec_alph_gam_conc} concentrates to
 \begin{equation}
\hat{\boldsymbol{\alpha}}^t := \left [ 0 | \ldots | 0 | \frac{\sigma_t}{\sigma_{t-1}}\right],
 \label{eq:hatalph_hatgam_def}
\end{equation}
for the state evolution values given in \eqref{eq:symm_SE}.

\begin{lemma}[Conditional Distribution Lemma]
For the vectors $\bh^{t+1}$ defined in \eqref{eq:sym_AMP}, the following hold for $t \geq 1$, provided $n >t$ and $\bigM_{t}^T \bigM_t$ has full column rank.

 \begin{equation}
 \begin{split}
 \bh^{1} \lvert_{\mscrs_{0}}   \stackrel{d}{=} \sqrt{\sigma^n_1} \bU_0, \qquad \text{ and } \qquad  \bh^{t+1} \lvert_{\mscrs_{t}} &  \stackrel{d}{=} \sum_{r=0}^{t-1} \hat{\alpha}^t_r \bh^{r+1} + \sqrt{\sigma^{\perp}_t} \bU_t + \bDel_{t}, \label{eq:Ha_dist}
 \end{split}
\end{equation}

where $\bU_0, \bU_t \in \mathbb{R}^n$ are random vectors with elements that are marginally standard Gaussian random variables that are independent of the corresponding conditioning sigma-algebras. The terms $\hat{\alpha}^t_{i}$ for $i \in [t-1]$ are defined in \eqref{eq:hatalph_hatgam_def} \textcolor{red}{where} and the terms $\sigma_{t}^{\perp}$ in \eqref{eq:sigperp_defs} \textcolor{red}{where} .  The deviation terms are for $t >0$,
\begin{align}
&\Delta_{t} =   \sum_{i=0}^{t-1} (\alpha^t_i - \hat{\alpha}^t_i)\bh^i   +   \Big[ \Big( \frac{\| \mathbf{m}^t_{\perp} \|}{\sqrt{n}} - \sqrt{\sigma_{t}^{\perp}}\Big)\mathsf{I}  -  \frac{\| \mathbf{m}^t_{\perp} \|}{\sqrt{n}}\mathsf{P}^{\parallel}_{\bigM_{t}} \Big]\bU_t  \nonumber  \\
&+     \bigM_{t-1} (\bigM_{t-1}^T\bigM_{t-1})^{-1} \Big[\bH_{t-1}^T   \mathbf{m}^t_{\perp} -  \bigM_{t-1}^*\Big(\textsf{c}_{t} \mathbf{m}^{t-1} - \sum_{i=1}^{t-1} \textsf{c}_{i} \alpha^t_{i} \mathbf{m}^{i-1} \Big)\Big].\label{eq:Dt1t}
\end{align}
\label{lem:hb_cond}
\end{lemma}

\paragraph{Inductive Step.}
The second step of the proof is inductive on the iteration $t$, essentially showing that if the result in \eqref{eq:PL_conc_result} holds up to iteration $t-1$  then it will hold at iteration $t$ as well. This is done by showing that the standardized $\ell_2$ norms of the terms in the AMP algorithm in \eqref{eq:gen_rec0}, like $\frac{1}{n}\|\bv^t\|^2, \frac{1}{n}\|f_t(\bv^t, \bV^n)\|^2$  and $\frac{1}{m}\|\bu^t\|^2,  \frac{1}{m}\|g_t(\bu^t, \bU^m)\|^2$, concentrate on deterministic values predicted by the state evolution. This is done by relating these iteration $t$ values to the iteration $t-1$ values through the equation in \eqref{eq:gen_rec0} and appealing to the conditional distribution from step $(a)$ and your inductive hypothesis.  While the proof for the symmetric AMP is largely similar to that for the non-symmetric version, there are additional challenges due to the dependencies created by the symmetry of the $\textsf{GOE}(n)$ matrix.  The details of the inductive proof are quite technical and long and are therefore not included here but we state the result for the symmetric AMP in \eqref{eq:sym_AMP}.

For $t \geq 0$, let $\kappa_{-1} = K_{-1} = 1$, and
\begin{equation}
\begin{split}

K_t = C (t+1)^5K_{t-1},  &\quad  \kappa_t  = \frac{\kappa_{t-1}}{  c(t+1)^{11}},
\end{split}
\label{eq:Kkappa_def}
\end{equation}
where $C, c > 0$ are universal constants (not depending on $t$, $n$, or $\e$).  To keep the notation compact,  we  use $K, \kappa, \kappa'$ to denote generic positive universal constants whose values may change through  the  lemma statement.

Let $\{ \tilde{Z}_t \}_{t \geq 0}$ be a sequence of of zero-mean jointly Gaussian random variables whose covariance is defined recursively as follows. For $r,t \geq 0$,
\begin{equation}
\mathbb{E}[\tilde{Z}_r \tilde{Z}_t] = \frac{\tilde{E}^n_{r,t}}{\sqrt{\sigma^n_r \sigma^n_t}}, \quad \text{ where } \quad
\tilde{E}^n_{r,t} := \mathbb{E}[g_{r}(\sqrt{\sigma^n_{r}} \tilde{Z}_{r}, X^n) g_{t}(\sqrt{\sigma^n_{t}} \tilde{Z}_{t}, X^n)],
\label{eq:Edef}
\end{equation}
where $X^n \sim p_{X, n}$ is an independent random variable.  In the above, we take $g_0(\cdot, \bX^n) := g_0(\bh^0,\bX^n)$, the initial condition.  Note that $\tilde{E}_{t,t} = \sigma^n_t$, thus $\mathbb{E}[\tilde{Z}^2_t] =1$.

\begin{lemma}
The following statements hold for $1 \leq t < T^*$ and $\e \in (0,1)$. Define
\begin{equation}
\gamma_n^{t+1} := (\nu^n +  \sigma^n_{1})  (\nu^n +  \sigma^n_{1} +  \sigma^n_{2})  \cdots  (\nu^n + \sum_{i=1}^{t+1} \sigma^n_{i}) \times \max\{1, \hat{\textsf{c}}_1\}  \max\{1, \hat{\textsf{c}}_2\} \cdots  \max\{1, \hat{\textsf{c}}_t\},
\end{equation}
where $\nu$ is the variance factor of sub-Gaussian $\bX^n$ which equals $3 \rho_n$ for $p_{X, n}$ Bernoulli.
\begin{enumerate}
\item
\begin{equation}
P\Big(\frac{1}{n}\norm{\bDel_{{t}}}^2 \geq \epsilon\Big) \leq  K t^2 K_{t-1} \exp\Big\{-\frac{\kappa \kappa_{t-1} n \epsilon}{ t^4 \gamma_n^{t} \max\{1, \hat{\textsf{c}}_t\} }\Big\}. \label{eq:Ba}
\end{equation}

\item
Denote $\mathbb{E}_{\phi} :=  \mathbb{E}\, \phi_h(\sqrt{\sigma^n_{1}} \tilde{Z}_{1}, \ldots ,\sqrt{\sigma^n_{t+1}} \tilde{Z}_{t+1}, X^n)$.  Then for pseudo-Lipschitz function $\phi: \mathbb{R}^{t+1} \rightarrow \mathbb{R}$ with constant $L_{\phi}$ we have that
\begin{equation*}
P\Big(\Big \lvert \frac{1}{n}\sum_{i=1}^n \phi(h^1_i, \ldots,  h^{t+1}_i, X^n_{i}) - \mathbb{E}_{\phi} \Big \lvert \geq \ep\Big) \leq K t^3 K_{t-1} \exp\Big\{-\frac{ \kappa \kappa_{t-1} n \epsilon^2}{t^7 L_{\phi}^{2} L_{g}^{4t}  \gamma_n^{t+1} }\Big\}.

\end{equation*}
The random variables $\tilde{Z}_{0}, \ldots, \tilde{Z}_t$ are jointly Gaussian with zero mean and covariance given by \eqref{eq:Edef}, and are independent of $\bX^n \sim p_{X, n}$. In the above

\item Let $L_g > 0$ be the pseudo-Lipschitz constant for the denoiser functions $\{g_t\}_{ t\geq 0}$ and let $X_n \overset{\mathbf{. .}}{=} c$ be shorthand for $$P(\abs{X_n -c} \geq \e) \leq K t^3 K_{t-1} \exp\Big\{-\frac{ \kappa \kappa_{t-1} n \epsilon^2}{t^7 L_{g}^{2(t+1)} \gamma_n^{t+1} }\Big\}.$$
For all $0 \leq r \leq t$,
\begin{align*}
&P\Big(\Big \lvert \frac{1}{n}(\bh^{r+1})^* \bh^{t+1}- \tilde{E}^n_{r,t}\Big \lvert \geq \ep\Big) \leq K t^3 K_{t-1} \exp\Big\{-\frac{ \kappa \kappa_{t-1} n \epsilon^2}{t^7\gamma_n^{t+1} }\Big\}. \\
& \frac{1}{n}(\mathbf{m}^{0})^* \mathbf{m}^{t+1} \overset{\mathbf{. .}}{=} \tilde{E}^n_{0,t+1}  \quad

\frac{1}{n}(\mathbf{m}^{r+1})^*\mathbf{m}^{t+1}  \overset{\mathbf{. .}}{=} \tilde{E}^n_{r+1,t+1}. \\
&P\Big(\Big \lvert \textsf{c}_{t+1} - \hat{\textsf{c}}_{t+1} \Big \lvert \geq \ep\Big) \leq K t^3 K_{t-1} \exp\Big\{-\frac{ \kappa \kappa_{t-1} n \epsilon^2}{t^7 L_{g}^{4(t+1)} \gamma_n^{t+1} }\Big\}. \\%  \label{eq:Hf1}  \\
& \frac{1}{n}(\bh^{t+1})^*\mathbf{m}^{r+1}  \overset{\mathbf{. .}}{=} \hat{\textsf{c}}_{r+1} \tilde{E}^n_{r,t} , \qquad

 \frac{1}{n}(\bh^{r+1})^*\mathbf{m}^{t+1} \overset{\mathbf{. .}}{=}  \hat{\textsf{c}}_{t+1} \tilde{E}^n_{r,t}.
\end{align*}

\item
\begin{equation}

 P\left( \frac{1}{n} \bigM_{t}^* \bigM_{t} \text{  is singular}\right) \leq t K_{t-1} \exp\Big\{-\frac{\kappa_{t-1} \kappa n}{{t^7 L_{g}^{2(t+1)}\gamma_n^{t+1} }}\Big\}. \label{eq:Msing}
\end{equation}
For $\hat{\alpha}^{t}$ defined in \eqref{eq:hatalph_hatgam_def}, when the inverse of $\frac{1}{n} \bigM_{t}^* \bigM_{t} $ exists, for $1\leq i, j \leq t+1$,
\begin{equation}
\begin{split}
& P\Big( \Big \lvert [(\frac{1}{n} \bigM_{t}^* \bigM_{t})^{-1} - (\breve{C}^t)^{-1} ]_{i,j} \Big \lvert \geq \e\Big) \leq K  K_{t-1} \exp\Big\{-\frac{\kappa \kappa_{t-1}n\e^2}{L_{g}^{2(t+1)} \gamma_n^{t+1} } \Big\},  \\
&  P\Big( \lvert\alpha^{t}_{i-1} - \hat{\alpha}^{t}_{i-1} \lvert \geq \e \Big) \leq K t^4 K_{t-1}   \exp\Big\{-\frac{\kappa \kappa_{t-1}n\e^2}{ t^9 L_{g}^{2(t+1)} \gamma_n^{t+1} } \Big\}.
\end{split}
\label{eq:Hg}
\end{equation}

\item With $\tau_{t}^{\perp}$ defined in \eqref{eq:sigperp_defs},
\begin{equation}
P\Big( \Big \lvert\frac{1}{n}\norm{\mathbf{m}^{t+1}_{\perp}}^2 - (\tau_{t+1}^{\perp})^2 \Big \lvert \geq \e \Big) \leq K t^5 K_{t-1}   \exp\Big\{-\frac{\kappa \kappa_{t-1}n\e^2}{ t^{11} L_{g}^{2(t+1)} \gamma_n^{t+1} } \Big\}. \label{eq:Hh}
\end{equation}

\end{enumerate}
\label{lem:main_lem}
\end{lemma}

\paragraph{Rate of the  Concentration.}
We finally note that the $\lambda_n$ in the rates of concentration in Theorem~\ref{thm:main_amp_perf} were  not stated explicitly in the original concentration bound given in \cite[Theorem 1]{RushVenkataramanan} as the authors assume that these values do not change with $n$ and, thus, can be absorbed into the universal constants. The presence of these terms comes from the inductive portion of the proof where one must show that  $\|f_t(\bv^t, \bV^n)\|^2/n$ and $\|g_t(\bu^t, \bU^m)\|^2/m$ concentrate to known constants. This will add a $L_f^2$ and $L_g^2$ in the rate at each step of the induction.  To see this, we point the reader to three facts. First notice that the approximate distributions of $v^t_i$ and $u^t_i$ are Gaussian. Second, it is easy to see that a function $[f(x)]^2$ has the same pseudo-Lipschitz constant as $f(\cdot)$ if $|f(\cdot)|$ is bounded (as $n$ grows) which is the case when $f_t$ and $g_t$ are the conditional expectation denoiser, as in our setting. (More generally, the Lipschitz constant of $[f(x)]^2$ will be no more than the square of the Lipschitz constant of $L_f$ giving instead $L_f^4$ and $L_g^4$ in the rate.) Finally, we highlight that pseudo-Lipschitz functions taking Gaussian and sub-Gaussian input concentrate as in \cite[Lemma B.4]{RushVenkataramanan} with $1/L^2$ in the rate when $L$ is the associated pseudo-Lipschitz constant.
The result is restated here

\begin{lemma}{\cite[Lemma B.4]{RushVenkataramanan}}
\label{lem:PLsubgaussconc}
Let $Z \in \mathbb{R}^n$ be an i.i.d.\ standard Gaussian vector and let $G \in  \mathbb{R}^n$ be a random vector with entries  $G_1, \ldots, G_n$  i.i.d.\   $\sim p_{G}$, where $p_G$ is sub-Gaussian with variance factor $\nu^n$.   Then for any pseudo-Lipschitz function $f: \mathbb{R}^{2} \to \mathbb{R}$ with constant $L_f^n$, non-negative values $\sigma^n$, and  $0< \e \leq 1$, we have
\begin{align*}
& P\Big(\Big\lvert \frac{1}{n}\sum_{i=1}^n f(\sqrt{\sigma^n} Z_{i}, G_i)  - \mathbb{E}[f(\sqrt{\sigma^n} Z, G)] \Big \lvert \geq \e \Big)  \leq 2 \exp \Big\{ \frac{ - \kappa n \e^2}{(L_f^n)^2(  \nu^n + 4 (\nu^n)^2 + \sigma^n +  4  (\sigma^n)^{2}) }  \Big\}.
\end{align*}
\end{lemma}
Hence, in our setting our case, $L = L_f$ or $L= L_g$ to give $L_f^2$ and $L_g^2$ in each inductive step.  The $L^2_{\phi}$ term comes from the final step where one proves the results in \eqref{eq:PL_conc_result} using the result of the inductive argument.  In the case of the symmetric AMP that we study, there is no corresponding $g_t$ step of the induction and therefore our concentration result only has the $L_f^{2t} L_{\psi}^2$ dependence.

Additionally, we note that the proof of \cite[Theorem 1]{RushVenkataramanan}  assumes that the weak derivatives of the denoisers, $f'_t, g'_t$, have bounded derivative everywhere they exist. In the case of interest in this paper, the derivative of the conditional expectation denoiser is given in Lemma~\ref{lem:PL}, and in particular, $f_t'(x) = \sqrt{\lambda_n} f_t(x) (1-f_t(x))$.  It is not hard to show that $f_t'(x)$ is also Lipschitz with constant $L_f^2 = \lambda_n$. We use this to get around the boundedness assumption originally in \cite[Theorem 1]{RushVenkataramanan} and it does not add additional $L_f$ constants in the rate.

config: arxiv


text:
\begin{document}
\title[Hyers-Ulam stability ]{Hyers-Ulam stability of
Jensen functional  equation on amenable semigroups}
\author[ B. Bouikhalene and  E. Elqorachi  ]{Bouikhalene Belaid and Elqorachi Elhoucien  }

\begin{abstract}
In this paper, we give a  proof of the  Hyers-Ulam stability of
the Jensen functional equation
$$f(xy)+f(x\sigma(y))=2f(x),\phantom{+} x,y\in{G},$$ where $G$ is an amenable semigroup and $\sigma$ is an involution of $G.$
\end{abstract}
\maketitle

\section{Introduction}
In 1940,  Ulam \cite{43} gave a wide ranging talk before the
Mathematics Club of the University of wisconsin in which he
discussed a number of important unsolved problems. Among those was
the question concerning the stability of group homomorphisms:
Given a group $G_{1}$, a metric group $(G_{2},d)$, a number
$\epsilon>0$ and a mapping $f$: $G_{1}\longrightarrow G_{2}$ which
satisfies $d(f(xy),f(x)f(y))<\epsilon$ for all $x,y\in{G_{1}}$,
does there exist an homomorphism $g$: $G_{1}\longrightarrow G_{2}$
and a constant $k>0$, depending only on $G_{1}$ and $G_{2}$ such
that $d(f(x),g(x))<k\epsilon$ for all $x\in{G_{1}}$?\\ In 1941,
Hyers \cite{H} considered the case of approximately additive
mappings under the assumption that $G_{1}$ and $G_{2}$ are Banach
spaces.\\    Rassias \cite{19} provided a generalization of the
Hyers' Theorem for linear mappings, by allowing the Cauchy
difference to be unbounded.
\\Beginning around the year 1980, several results for the
Hyers-Ulam-Rassias stability of very many functional equations
have been proved by several researchers.
For more detailed, we can refer for example  to \cite{4c}, \cite{Ga}, \cite{Gav}, \cite{H2}, \cite{Jung}, \cite{12f}, \cite{Yang}. \\
Let $G$ be a semigroup with neutral element $e$. Let $\sigma$ be
an involution of $G$, which means that
$\sigma(xy)=\sigma(y)\sigma(x)$ and $\sigma(\sigma(x))=x$ for all
$x,y\in G$.\\We say that $f$: $G\longrightarrow \mathbb{C}$
satisfies the Jensen functional equation if
\begin{equation}\label{eq1}
    f(xy)+f(x\sigma(y))=2f(x)
\end{equation} for all $x,y\in G$. \\The Jensen functional equation (\ref{eq1}) takes the form \begin{equation}\label{eq2}
    f(xy)+f(xy^{-1})=2f(x)
\end{equation} for all $x,y\in G$, when $\sigma(x)=x^{-1}$ and $G$
is a group.
\\The stability in the sens of Hyers-Ulam of the Jensen equations (\ref{eq1}) and (\ref{eq2})  has been studied
by various authors when $G$ is an abelian group or a vector space.
 The interested reader can be referred  to   Jung \cite{3},
  Kim \cite{4} and   Bouikhalene et al. \cite{a,b}. \\
 Recently,  Faiziev and  Sahoo \cite{1} have proved the
 Hyers-Ulam stability of equation (\ref{eq2}) on some noncommutative groups such as metabelian groups and $T(2,K)$, where
 $K$ is an arbitrary commutative field with characteristic different from two.\\ In this paper, motivated by the ideas of
  Forti,  Sikorska \cite{2} and  Yang \cite{5}, we give a
 proof of the Hyers-Ulam stability of the Jensen functional
 equation (\ref{eq1}), under the condition that $G$ is an amenable
 semigroup.
\section{Hyers-Ulam stability of  equation (\ref{eq1})
on amenable semigroups} In this section we investigate the
Hyers-Ulam stability of equation (\ref{eq1}) on an amenable
semigroup $G$. \\We recall that a semigroupe $G$ is said to be
amenable if there exists an invariant mean on the space of the
bounded complex functions defined on $G$. We refer to \cite{7} for
the definition and properties of invariant means.\\The main result
of the present paper is the following.
\begin{thm}Let $G$ be an amenable semigroup with neutral element $e$.
Let $f$: $G\longrightarrow \mathbb{C}$ be a function satisfying the following inequality
\begin{equation}\label{eq21}
\mid f(xy)+f(x\sigma(y))-2f(x)\mid\leq \delta
\end{equation} for all $x,y\in G$ and for some nonnegative $\delta$.
Then there exists a unique solution $g$ of the Jensen equation (\ref{eq1}) such that
\begin{equation}\label{eq22}
    \mid f(x)-g(x)-f(e)\mid\leq 3\delta
\end{equation}for all $x\in G.$\end{thm}
First, we recall the following lemma which is a generalization of
the useful lemma obtained by  Forti and  Sikorska in \cite{2}. The
proof was given by the authors in \cite{E}.
\begin{lem}\label{lem21} Let $G$ be a semigroup and $B$ be
a Banach space. Let $f:G\rightarrow B$ be a function for which
there exists a solution $g$ of the Drygas functional equation
\begin{equation}\label{eq23}g(yx)+g(\sigma(y)x)=2g(x)+g(y)+g(\sigma(y)),\;\;\;x,y\in
G
\end{equation} such that  $\|f(x)-g(x)\|\leq M$, for all
$x\in{G}$ and for some $M\geq0$. Then
\begin{equation}\label{eq24}
g(x)=\lim_{n\rightarrow+\infty}2^{-2n}\{f^{e}(x^{2^{n}})+\frac{1}{2}\sum^{n}_{k=1}2^{k-1}
[f^{e}((x^{2^{n-k}}\sigma(x)^{2^{n-k}})^{2^{k-1}})
+f^{e}((\sigma(x)^{2^{n-k}}x^{2^{n-k}})^{2^{k-1}})]\}\end{equation}$$+2^{-n}\{f^{o}(x^{2^{n}})
 +\frac{1}{2}\sum^{n}_{k=1}
[f^{e}((x^{2^{k-1}}\sigma(x)^{2^{k-1}})^{2^{n-k}})-f^{e}((\sigma(x)^{2^{k-1}}x^{2^{k-1}})^{2^{n-k}})]\},$$
where
$f^{e}(x)=\frac{f(x)+f(\sigma(x))}{2},f^{o}(x)=\frac{f(x)-f(\sigma(x))}{2}$
are the even and odd part of $f$.
\end{lem}
\begin{lem} Let $G$ be semigroup with neutral element $e$ and $B$ a complex Banach space.
Assume that $f$: $G\longrightarrow B$ satisfies the inequality
\begin{equation}\label{eq25} \mid
f(xy)+f(x\sigma(y))-2f(x)\mid\leq \delta
\end{equation} for all $x,y\in G$ and for  some  $\delta\geq 0$.
Then the limit \begin{equation}\label{eq26}
    g(x)=\lim_{n\longrightarrow \infty}2^{-n}f(x^{2^{n}})
\end{equation}   exists for all $x\in G$  and satisfies
\begin{equation}\label{eq27}
    \mid f(x)-g(x)-f(e)\mid\leq\frac{3\delta}{2}\;\;\text{and}\;\;
    g(x^{2})=2g(x)
\end{equation}for all $x\in G.$\\The function $g$ with the
condition (\ref{eq27}) is unique.
\end{lem}\begin{proof}We define a function $h$: $G\longrightarrow \mathbb{C}$ by $h(x)=f(x)-f(e)$. First, by using
the inequality (\ref{eq25})  we obtain
\begin{equation}\label{eq28} \mid
h(xy)+h(x\sigma(y))-2h(x)\mid\leq \delta
\end{equation} for all $x,y\in G$. Letting $x=e$ in (\ref{eq28}), we get \begin{equation}\label{eq29}
    \mid h^{e}(y)\mid\leq\frac{\delta}{2}
\end{equation} for all $y\in G.$ Similarly, we can put $y=x$ in (\ref{eq28}) to obtain
\begin{equation}\label{eq210}
    \mid h(x^{2})+h(x\sigma(x))-2h(x)\mid\leq\delta
\end{equation} for all $x\in G$. Since $h(x\sigma(x))=h^{e}(x\sigma(x))$, so from (\ref{eq29}) and  (\ref{eq210}), we have
\begin{equation}\label{211}
    \mid h(x^{2})-2h(x)\mid\leq\frac{3\delta}{2}
\end{equation}for all $x\in G.$ Now, by applying some approach used  in \cite{1}, we get the rest of the proof.
\end{proof}
\textbf{Proof of Theorem 2.1.} In the proof we use some ideas from
Yang \cite{5} and Forti, Sikorska \cite{2}.\\ Setting $x=e$ in
(\ref{eq21})   we have
\begin{equation}\label{eq212}
    \mid f^{e}(y)-f(e)\mid\leq\frac{\delta}{2}
\end{equation}for all $y\in G.$ \\ The inequalities (\ref{eq21}), (\ref{eq212}) and the triangle inequality gives
\begin{equation}\label{eq213}
    \mid f(xy)+f(yx)-2f(x)-2f(y)+2f(e)\mid\end{equation}$$\leq\mid
    f(xy)+f(x\sigma(y))-2f(x)\mid+\mid f(yx)+f(y\sigma(x))-2f(y)\mid$$$$+\mid
    2f(e)-f(x\sigma(y))-f(y\sigma(x))\mid$$$$\leq3\delta.
$$Hence, from (\ref{eq21}) (\ref{eq212}) and (\ref{eq213}) we get \begin{equation}\label{eq214}
    \mid f(yx)+f(\sigma(y)x)-2f(x)\mid\leq\mid
    f(yx)+f(xy)-2f(y)-2f(x)+2f(e)\mid\end{equation}$$+\mid
    f(\sigma(y)x)+f(x\sigma(y))-2f(\sigma(y))-2f(x)+2f(e)\mid$$
$$+\mid -f(xy)-f(x\sigma(y))+2f(x)\mid+\mid
2f(y)+2f(\sigma(y))-4f(e)\mid\leq9\delta$$   Now, from
(\ref{eq21}) and (\ref{eq214}) we obtain
\begin{equation}\label{eq215}
\mid
f(yx)-f(\sigma(x)\sigma(y))+f(y\sigma(x))-f(x\sigma(y))-2(f(y)-f(\sigma(y)))\mid
\end{equation}
$$\leq \mid f(yx)+f(y\sigma(x))-2f(y)\mid +\mid f(x\sigma(y))+f(\sigma(x)\sigma(y))-2f(\sigma(y))\mid$$
$$\leq 10\delta.$$
Consequently, we get
\begin{equation}\label{eq216}
\mid f^{o}(yx)+f^{o}(y\sigma(x))-2f^{o}(y)\mid\leq5\delta
\end{equation}for all $x,y\in G.$
So, for fixed $y\in G$, the functions $x\longmapsto
f^{o}(yx)-f^{o}(x\sigma(y))$ and $x\longmapsto
f^{o}(xy)+f^{o}(x\sigma(y))-2f^{o}(x)$ are bounded on $G$.
Furthermore, \begin{equation}\label{eq217}
m\{f^{o}_{\sigma(y)\sigma(z)}+f^{o}_{\sigma(y)z}-2f^{o}_{\sigma(y)}\}=m\{(f^{o}_{\sigma(z)}+f^{o}_{z}-2f^{o})_{\sigma(y)}\}
\end{equation}
$$=m\{f^{o}_{\sigma(z)}+f^{o}_{z}-2f^{o}\},$$ where $m$ is an invariant mean on $G$.\\
 By using some computation  as the one of  (\ref{eq214})
we get,  for every fixed $y\in G$ the function $x\longmapsto
f^{o}(yx)+f^{o}(\sigma(y)x)-2f^{o}(x)$ is bounded and
\begin{equation}\label{eq218}
m\{_{zy}f^{o}+_{\sigma(z)y}f^{o}-2_{y}f^{o}\}=m\{_{y}(_{z}f^{o}+_{\sigma(z)}f^{o}-2f^{o})\}
\end{equation}
$$=m\{_{z}f^{o}+_{\sigma(z)}f^{o}-2f^{o}\}$$Now, define \begin{equation}\label{eq219}
    \phi(y):=m\{_{y}f^{o}-f^{o}_{\sigma(y)}\},\;\;\;y\in G.
\end{equation} By using the definition of $\phi$ and $m$ the equalities (\ref{eq217}) and
(\ref{eq218}), we get \begin{equation}\label{eq220}
\phi(zy)+\phi(\sigma(z)y)=m\{_{zy}f^{o}-f^{o}_{\sigma(y)\sigma(z)}\}+m\{_{\sigma(z)y}f^{o}-f^{o}_{\sigma(y)z}\}
\end{equation}
$$=m\{_{zy}f^{o}+_{\sigma(z)y}f^{o}-2_{y}f^{o}\}-m\{f_{\sigma(y)\sigma(z)}^{o}+f_{\sigma(y)z}^{o}-2f_{\sigma(y)}^{o}\}$$
$$+2m\{_{y}f^{o}-f^{o}_{\sigma(y)}\}$$
$$=m\{_{z}f^{o}+_{\sigma(z)}f^{o}-2f^{o}\}-m\{f_{\sigma(z)}^{o}+f_{z}^{o}-2f^{o}\}$$
$$+2m\{_{y}f^{o}-f^{o}_{\sigma(y)}\}$$
$$=m\{_{z}f^{o}-f^{o}_{\sigma(z)}\}+m\{_{\sigma(z)}f^{o}-f^{o}_{z}\}+2m\{_{y}f^{o}-f^{o}_{\sigma(y)}\}$$
$$=2\phi(y)+\phi(z)+\phi(\sigma(z)),$$
which implies that $\phi$ is a solution of the Drygas functional
equation (\ref{eq23}). Furthermore, we have
\begin{equation}\label{221}
    \mid
    \frac{\phi}{2}(y)-f^{o}(y)\mid=\frac{1}{2}\mid\phi(y)-2f^{o}(y)\mid=\frac{1}{2}\mid
    m\{_{y}f^{o}-f^{o}_{\sigma(y)}-2f^{o}(y)\}\mid
\end{equation}$$\leq\frac{1}{2}\mid m\mid \text{sup}_{x\in G}\mid f^{o}(yx)-f^{o}(x\sigma(y))-2f^{o}(y)\mid=\frac{1}{2} \text{sup}_{x\in G}\mid
f^{o}(yx)+f^{o}(y\sigma(x))-2f^{o}(y)\mid$$$$\leq\frac{5}{2}\delta.$$
Now, by using Lemma 2.2: the mapping $\frac{\phi}{2}$ is a
solution of Drygas functional equation (\ref{eq23}) and
$\frac{\phi}{2}-f^{o}$ is a bounded mapping, so we have
\begin{equation}\label{}
    \frac{\phi}{2}=\lim_{n\rightarrow+\infty}2^{-n}
    f^{o}(x^{2^{n}}),
\end{equation}which implies that $\frac{\phi}{2}$ is odd, so
$\frac{\phi}{2}$ is a solution of Jensen functional equation
(\ref{eq1}). Consequently, we have
\begin{equation}\label{}
    \mid f(x)-\frac{\phi}{2}-f(e)\mid=\mid f^{e}(x)+f^{o}(x)-\frac{\phi}{2}-f(e)\mid\end{equation}$$\leq\mid
    f^{e}(x)-f(e)\mid+\mid f^{o}(x)-\frac{\phi}{2} \mid$$
    $$\leq\frac{\delta}{2}+\frac{5\delta}{2}=\frac{\delta}{2}=3\delta.$$
For proving the uniqueness of the obtained solution, we use the
following: if $g$ is a solution of equation (\ref{eq1}), then
\begin{equation}\label{eqj}
g(e)=g^{e}(x)=g(x\sigma(x));\;\;g(x^{2^{n}})+(2^{n}-1)g(e)=2^{n}g(x)
\end{equation}for all $n\in \mathbb{N}$ and for all $x\in G.$\\
By using (\ref{eqj}) and the proof of [Propostion 3,  \cite{5}] we
get the following result.
\begin{cor} Let $G$ be an amenable semigroup with neutral
element $e$ and $B$ a Banach space Let $f$: $G\longrightarrow B$
be a function satisfying the following inequality
\begin{equation}\label{eq222}
\parallel f(xy)+f(x\sigma(y))-2f(x)\parallel\leq \delta
\end{equation} for all $x,y\in G$ and for some nonnegative $\delta$.
Then there exists a unique solution $g$ of the Jensen equation
(\ref{eq1}) such that
\begin{equation}\label{eq223}
    \parallel f(x)-g(x)-f(e)\parallel\leq3\delta
\end{equation}for all $x\in G.$\end{cor}
\begin{cor} Let $G$ be an amenable semigroup with neutral element
$e$ and $B$ a Banach space Let $f$: $G\longrightarrow B$ be a
function satisfying the following inequality
\begin{equation}\label{eq224}
\parallel f(xy)+f(xy^{-1})-2f(x)\parallel\leq \delta
\end{equation} for all $x,y\in G$ and for some nonnegative $\delta$.
Then there exists a unique solution $g$ of the Jensen equation
(\ref{eq2}) such that
\begin{equation}\label{eq225}
    \parallel f(x)-g(x)-f(e)\parallel\leq3\delta
\end{equation}for all $x\in G.$\end{cor}


text:
\section{Evaluation} \label{s:eval}

We evaluate the performance of \namens, and compare it against the baseline algorithms of \S\ref{s:baseline}. Our experiments are based on a Python simulator we built following the network model of \S\ref{sec:model}.\footnote{Source code and datasets are available at \url{https://github.com/mori94/perigee}.}
We describe the experimental setting in \S\ref{s:expt setup}.
Following this, we evaluate \name on a variety of different network conditions (\S\ref{s:hashpower}--\S\ref{s:fastdistnet}).

\subsection{Experimental Setup}
\label{s:expt setup}

\begin{figure*}[!tbp]
  \centering
  \subfigure[]{\includegraphics[width=0.54\textwidth]{fig/NodeDelay.png}\label{fig:NodeDelay}}

    \subfigure[]{\includegraphics[width=0.21\textwidth]{fig/LowLatencySubgraph.png}\label{fig:LowLatencySubgraph}}
  \subfigure[]{\includegraphics[width=0.21\textwidth]{fig/LowLatencyTree.png}\label{fig:LowLatencyTree}}
  \caption{(a) Delay distributions for \name with 0.1$\times$, 0.5$\times$, 5$\times$ and 10$\times$ the default node delay. (b) Setting with a small number (10\%) of high hash power miners. (c) Performance in the presence of a low-latency block distribution network such as bloXroute.}
  \label{fig:NodeDelay}
   \vspace{-3mm}
\end{figure*}

\noindent
{\bf Network setting.}

We retrieved a publicly available list of 9408 Bitcoin nodes~\cite{bitnodescom}, and use a randomly sampled subset of 1000 nodes from it, for all our experiments.
The ``default'' setting for hash power of nodes, block validation times, link propagation delay, and block size in our experiments are described below.
In \S\ref{s:hashpower}, \S\ref{s:procdelay},
we consider a broader range of settings for each of hash power, block validation times
respectively; in each case, while we explore different settings for one attribute, we fix the other attributes to their ``default'' setting unless specified otherwise.
The default settings are as follows. \\
(1) {\em Hash power.} We assume hash power is distributed uniformly across all the nodes. \\
(2) {\em Propagation delay.} The dataset of Bitcoin nodes~\cite{bitnodescom} includes information about the geographical location of each node.

Nodes are spread across seven geographic regions: North America, South America, Europe, Asia, Africa, China, and Oceania.
We set the propagation latency between any two nodes according to their geographical locations, using the iPlane latency measurement dataset~\cite{madhyastha2006iplane, rohrer2019kadcast}.
\\
(3) {\em Block size.} We assume block sizes are small, relative to the bandwidth available at the nodes. Hence the overall block broadcasting delay is dominated by the link propagation delays, and block validation delays, in the default setting.  \\
(4) {\em Block validation time.} Each node has a mean block processing time of 50 ms. \\

In addition, in \S\ref{s:fastdistnet} we consider a scenario where nodes have access to a high-speed block distribution network such as BloXroute~\cite{klarman2018bloxroute}.

Each node creates 8 outgoing connections, and accepts up to 20 incoming connections.
If a node already has 20 incoming connections, any additional connection request is declined by the node.

\noindent
{\bf Algorithms compared.}
We implement \name under the scoring methods discussed in \S\ref{s:vanillascore}, \S\ref{sec:ucb}, \S\ref{s:groupscoring}, and name them \namens-Vanilla, \namens-UCB and \namens-Subset respectively.
For \namens-Vanilla and \namens-Subset, we define a round such that $|B| = 100$ blocks are mined during each round; for \namens-UCB we use shorter rounds in which only one block ($|B| = 1$) is mined each round.
In all of the \name variants, a node selects two neighbors randomly for exploration every round (\S\ref{s:design}).

As baseline algorithms, we consider the random connection algorithm (\S\ref{s:alg:random}), geography-based connection algorithm (\S\ref{s:geography}) and a structured p2p topology based on Kademlia~\cite{rohrer2019kadcast}.
For these baselines, we do not change the topology with each round.

We also consider a topology in which each node is connected to all other nodes, to obtain a theoretical lower bound on block propagation times.

\noindent
{\bf Performance metric.}

For each node, we compute the time it takes for a block broadcast by the node to reach 50\% and 90\% of the hash power in the network.
We repeat each experiment three times using independently sampled link latencies, and plot the mean propagation times for different nodes in ascending order; we also show error bars at the 100th, 300th, 500th, 700th and 900th node.

Note that the nodes corresponding to the same $x$-coordinate value may not be the same node in the network.

\subsection{Hash Power}
\label{s:hashpower}

We first consider the setting where all the attributes---hash power, link propagation latencies, block validation times, block size---take their default setting (\S\ref{s:expt setup}) and plot the results in Figure~\ref{fig:UniformHash}.

The \namens-Subset and -UCB algorithm achieve around 33\% and 11\% lower delay respectively compared to random neighbor selection, indicating that switching neighbors based on their scores helps reduce the block propagation delays.
Connecting based on node geography does help lower delay compared to random selection, however it is still 40\% worse than \namens-Subset at the 500th node.
The Kademlia topology is slightly worse than even the geographic topology.

While the 90-percentile delays in \name converge as the number of rounds increases, we observe the 50-percentile delays do not exhibit a similar monotonicity.
This is because \name chooses neighbors only to optimize nodes' 90-percentile delays.

Since \namens-Subset is slightly better than \namens-UCB or -Vanilla, for the reminder we have used \namens-Subset as the preferred scoring method.
Next, we consider the same setting as above but where the hash power of the nodes are sampled from an exponential distribution (of mean 1), and normalized to 1 (Figure~\ref{fig:ExpDistributedHash}).

The results show a similar performance pattern as in Figure~\ref{fig:UniformHash} with \namens-Subset being 33\% better than random.

\subsection{Processing Delay}
\label{s:procdelay}

In Figure~\ref{fig:NodeDelay}, we vary the block validation time to 0.1$\times$, 0.5$\times$, 5$\times$ and 10$\times$ its default value.

As shown in the Figure, for small values of node delay (0.1$\times$), \name finds a topology with delays at least 62\% better than random.
However, as the node delay increases, \name approaches the random protocol's performance.
This is expected, since with large processing delays the 90th percentile delay is dictated by the number of nodes on the shortest paths to nodes (\ie the diameter of the network).

With node degree bounded by a constant, the diameter is lower-bounded by the logarithm in number of nodes, which is achieved by the random topology.

\subsection{Fast Distribution Networks}
\label{s:fastdistnet}

The Bitcoin network is known to have a small number of mining pools that contribute to most of the hash power in the network.

To simulate such a network, we randomly select 10\% of the nodes and assign them 90\% of the network's total hash power; we also set the link propagation latencies between the high-power miners to be much smaller than their default values.

In this network, it is desirable for peers to be directly connected to at least one of the high-power miners.

As shown by the results in Figure~\ref{fig:LowLatencySubgraph}, \name can exploit and explore the network to get much closer to the ideal delay in a fully-connected network compared to baselines.

We also simulate fast block relay networks, by considering 100 nodes organized as a tree topology with low-propagation-latency links.
The block validation delays for these 100 nodes are also set to be 10\% of their default value.

Even here, as before, our results in Figure~\ref{fig:LowLatencyTree} show that \name can approach the fully-connected network baseline closely.

\subsection{What does \name ~learn?}
\label{s:interpret}

\begin{figure}[!tbp]
  \centering

    \includegraphics[width=0.47\textwidth]{fig/EdgeLatencyHistgram.png}
  \caption{

  Histograms of the edge latencies in the \pp graph obtained after the execution of various algorithms under uniform hash power.}
  \label{fig:f2}
     \vspace{-3mm}
\end{figure}

In Figure~\ref{fig:f2} we observe that the distribution of edge latencies of the \pp network obtained in all the four algorithms are bimodal.

The lower mode is mostly populated by intra-continental edges with smaller edge latencies whereas the upper mode is mostly populated by inter-continental edges with larger edge latencies. For \namens-subset, the latencies of bulk of the edges are populated around the lower mode. On the other hand, this is not the case in random and geometric. This implies that over the course of execution of \namens-subset algorithm, nodes learn to select those outgoing neighbors with which they have smaller edge latency.


TITLE: Which metric is not complete?
QUESTION [1 upvotes]: Problem
Which one of the following metric is not complete on $\mathbb R$:

$|x-y|$
$|arctan(x) - arctan(y)|$
$|x^3 - y^3|$
$|x^{1/3} - y^{1/3}|$

1 is complete. I am not sure about the 2, 3 and 4.
For 2, I do not know the definition of $arc$ function
For $3. 4$, they can be viewed as the special case of $|f(x) - f(y)|$, note that
$$
|f(x) - f(y)| = |f'(\theta)||x-y|
$$
where $x< \theta < y$.
it seems that 3&4 are complete with respect to the intervals, but what about $\mathbb R$

REPLY [1 votes]: You know 1 is complete. Denote this distance by $d$.
For 2 (presumably $\arctan$), the sequence $x_n = n$ is Cauchy but
clearly does not converge.
For 3 & 4, suppose $f$ is odd, continuous, strictly increasing, unbounded
and $f(0) = 0$ (the latter follows since $f$ is odd). Then I claim that $\rho(x,y) = |f(x)-f(y)|$ is a complete
metric.
Note that $f$ has an inverse $g$ such that $g(f(x)) = x$.
It is straightforward to show that $g$ is continuous.
Suppose $x_n$ is $\rho$-Cauchy. It follows that $f(x_n)$ is bounded. Since $g$ is uniformly continuous on bounded sets, it follows that
for any $\epsilon>0$, there is some $\delta>0$ such that if
$\rho(x_n,x_m)=|f(x_n)-f(x_m)| < \delta$, then $|g(f(x_n))-g(f(x_m))| = |x_n-x_m| < \epsilon$. It follows that $x_n$ is Cauchy with respect to the
standard distance, and hence there is some $x$ such that $x_n \to x$ with respect to $d$. It follows from continuity that $\rho(x_n,x) \to 0$
as well and hence $\rho$ is a complete metric.
Now check that $x \mapsto x^3, x \mapsto \sqrt[3]{x}$ satisfy the
conditions above.


TITLE: How fast does gravity propagate?
QUESTION [136 upvotes]: A thought experiment: Imagine the Sun is suddenly removed. We wouldn't notice a difference for 8 minutes, because that's how long light takes to get from the Sun's surface to Earth.
However, what about the Sun's gravitational effect? If gravity propagates at the speed of light, for 8 minutes the Earth will continue to follow an orbit around nothing. If however, gravity is due to a distortion of spacetime, this distortion will cease to exist as soon as the mass is removed, thus the Earth will leave through the orbit tangent, so we could observe the Sun's disappearance more quickly.
What is the state of the research around such a thought experiment? Can this be inferred from observation?

REPLY [1 votes]: Here's a recent science update to this question: Gravity propagates at the speed of light at least to a precision of one part in $10^{15}$. This has been measured directly in 2017 when a Binary Neutron Star Merger happened that was both seen in gravitational waves (GW170817) and in gamma rays (GRB 170817A). In particular, here is Figure 2 from that paper:

While the neutron star merger happened across a cosmological distance of some 100 million light years, the light and gravitational wave signal were seen within a couple seconds. The ratio of these two numbers thus directly gives an upper limit on the difference of the speed of light and gravitational waves. See also this viewpoint for some context of why this measurement is really qualitatively different from anything done before, and in short, pretty cool.


TITLE: Can we say that an element is not a subset of a set?
QUESTION [7 upvotes]: I am creating a multiple choices question for students that should be as follows:
Which of the following is true?
1) $8\in \mathbb{Z^{+}}$
2) $8\notin \mathbb{Z^{+}}$
3) $8\subset \mathbb{Z^{+}}$
4) $8 \not\subset \mathbb{Z^{+}}$
Should choices Number (1) and (4) be considered as valid answers?
My understanding is that we can't deal with an element with either $\subset$ or $\not\subset$.
Please give me references supporting your answer if there.

REPLY [8 votes]: If you want to initiate a class discussion on what "8" might mean to a mathematician and whether $A \not \subset B$ means the same as $\neg (A \subset B)$ when A or B is not even a set (or is everything in mathematics built from a set anyway ?), then this is a great way to start.
If you wish to leave those topics until another occasion then I suggest you change the question !


TITLE: Evaluate $\sum_{i=0}^{20} \frac{i}{10}(\frac{1}{i} + \frac{1}{1+i} + ...+ \frac{1}{20})$
QUESTION [0 upvotes]: Would the answer be 11.5? I simplified the above expression to $\frac{1}{10}\{1(1) + \frac{1}{2}(1+2) +. .. + \frac{1}{20}(1+2+...+20)\}$ =$\frac{1}{10}\sum_{k=1}^{20} \frac{k+1}{2}$ and thus got 11.5

REPLY [1 votes]: I'll put $n$ for $20$
and start the sum at $i=1$
since the inner sum is not well defined
at $i=0$.
The sum is
$\begin{array}\\
s(n)
&=\sum_{i=1}^n \dfrac{i}{n/2}\sum_{j=i}^n \dfrac1{j}\\
&=\dfrac{2}{n}\sum_{i=1}^n i\sum_{j=i}^n \dfrac1{j}\\
&=\dfrac{2}{n} \sum_{j=1}^n \sum_{i=1}^ji \dfrac1{j}
\qquad\text{since } j \ge i, i \le j\\
&=\dfrac{2}{n} \sum_{j=1}^n\dfrac1{j} \sum_{i=1}^ji \\
&=\dfrac{2}{n} \sum_{j=1}^n\dfrac1{j}\dfrac{j(j+1)}{2} \\
&=\dfrac{1}{n} \sum_{j=1}^n (j+1)\\
&=\dfrac{1}{n} (\dfrac{n(n+1)}{2}+n)\\
&=\dfrac{1}{n} \dfrac{n(n+3)}{2}\\
&=\dfrac{n+3}{2}\\
\end{array}
$
For $n=20$ this is
$\dfrac{23}{2}
=11.5
$.


TITLE: There are infinity many numbers when added to Three distinct integers making them pair-wise relatively prime
QUESTION [4 upvotes]: Given $0<a<b<c$ three distinct integers, prove that there exists infinity many numbers $n$ such that $a+n,b+n,c+n$ are relatively prime to each other.
For the case when $(a,b)=(b,c)=(a,c)=1$ which means they are already relatively prime the answer is easy, i found that $n= (c-b)(c-a)(b-a)k $ for $k \in \mathbb{N} $  works, for instance $gcd((c-b)(c-a)(b-a)k + a, (c-b)(c-a)(b-a)k +b) = (b-a,(c-b)(c-a)(b-a)k +a)=  (b-a,a) = (b,a) = 1$
And so for the rest.
But what to do when one or more are not relatively prime ?
How to solve it in  more general way?

REPLY [3 votes]: Note:  this does not work with $4$ numbers.  For example, if you start with $(2,3,4,5)$ then whatever you add to each term, two of the set will be even. Whatever argument one constructs must fail if you try to extend it to $4$ terms.
Your remark shows that it would suffice to find a single such $n$.
Without loss of generality, suppose that $a>b>c$.
Note:  if a prime $p$ divides $\gcd (a+n,b+n)$ then $p\,|\,a-b$.
Use the Chinese Remainder Theorem to solve the system of congruences $n\equiv 1-a\pmod {p_i}$ for each of the primes $p_i$ which divide $a-b$ or $a-c$, and $n\equiv 1-c\pmod {q_j}$ for each of the primes $q_j$ which divide $b-c$.  Note that if $p_i=q_j$ for some pair $(i,j)$ then the congruences are consistent. (N.B. This is the bit that fails if you extend to $4$ terms).
We claim that $n$ works.
Indeed, If a prime $\psi$ divides $\gcd(a+n,b+n)$  then $\psi\,|\,a-b$ but in that case $a+n\equiv 1 \pmod {\psi}$, a contradiction.


TITLE: Need hint to solve the following integral
QUESTION [1 upvotes]: We are fixed and need some hint to solve the problem
 $$\int\frac{(ax+b)^m}{(cx+d)^n}dx$$ where $m,n\in \mathbb{N}$.

REPLY [1 votes]: Let $u=cx+d$.
$$\int\frac{(ax+b)^m}{(cx+d)^n}dx=\frac{1}{c}\int\frac{\left(\frac{au}{c}+\frac{d(c-a)}{c}\right)^m}{u^n}du=\frac{1}{c^{m+1}}\sum_{k=0}^m\binom{m}{k}a^{k}d^{m-k}(c-a)^{m-k}\int u^{k-n}du$$

REPLY [1 votes]: Hint. By the change of variable
$$
X=cx+d
$$ one is led to evaluate
$$
\int\frac{\left(X+\beta\right)^m}{X^n}
$$ which, by a binomial expansion, amounts to evaluate
$$
\int\frac{dX}{X^k}.
$$


TITLE: How to check analytically that the following integral equations has this solution?
QUESTION [1 upvotes]: Consider the following integral equation
$$
\chi(s)= \frac{12}{\pi} \frac{s(1-s^2)}{(1+s^2)^4} + \frac{1}{i\pi} \int_0^\infty \chi(t) \ln \left| \frac{s+t}{s-t} \right| \, \mathrm{d} t \, , \quad\quad (s\ge 0) \, ,
$$
which has a solution of the form
$$
\chi(s) = -\frac{1}{2\pi} \int_0^\infty \frac{i q^4}{1-iq} e^{-q} \sin (qs) \, \mathrm{d}q \, .
$$
This solution has been obtained by solving the initial problem differently and can be checked numerically to be correct.
I was wondering whether analytical treatment is possible in order to confirm that the solution verifies the above integral equation.
Your helps welcome.
Thanks
RF

REPLY [1 votes]: We can also show the solution directly, after some manipulation. First, the function $\chi(s)$ is extended to the whole real axis as an odd function by $\chi(-s)=-\chi(s)$ if $s<0$. Then the logarithmic integral can be written as
$$
-\frac{1}{\pi i}\int_{-\infty}^\infty \chi(t)\ln|s-t|dt
$$
by using the fact that
$$
\frac{1}{\pi i}\int_0^\infty \chi(t)\ln|s+t|dt =
\frac{1}{\pi i}\int_{-\infty}^0 \chi(-t)\ln|s-t|dt
=-\frac{1}{\pi i}\int_{-\infty}^0 \chi(t)\ln|s-t|dt.
$$
The original integral becomes
$$
\chi(s)= \frac{12}{\pi} \frac{s(1-s^2)}{(1+s^2)^4}
-\frac{1}{\pi i}\int_{-\infty}^\infty \chi(t)\ln|s-t|dt.
$$
Taking derivative w.r.t $s$ on both sides
$$
\chi'(s) = \frac{12}{\pi}\frac{5s^4-10s^2+1}{(1+s^2)^5}+iP.V\frac{1}{\pi}\int_{-\infty}^\infty \frac{\chi(t)}{s-t}dt.
$$
The principal integral $P.V\frac{1}{\pi}\int_{-\infty}^\infty \frac{\chi(t)}{s-t}dt$ on the right hand is exactly the Hilbert transform of $\chi$. Now take the Fourier transform ($\hat{f}(k)=\int_{-\infty}^\infty f(x)e^{-ikx}dx$) of both sides, we get
$$
ik\hat{\chi}(k)=\frac{1}{2}k^4e^{-|k|}+\mbox{sign}(k)\hat{\chi}(k)
$$
or
$$
\hat{\chi}(k) = \frac{1}{ik-\mbox{sign}(k)}\frac{1}{2}k^4e^{-|k|}.
$$
Then $\chi$ is given by the inverse Fourier transform
$$
\chi(s) = \frac{1}{2\pi}\int_{-\infty}^\infty \hat{\chi}(k)e^{iks}dk
=\frac{1}{2\pi}\int_0^\infty
\frac{1}{ik-1}\frac{1}{2}k^4e^{-k}e^{iks}dk
+\frac{1}{2\pi}\int_{-\infty}^0
\frac{1}{ik+1}\frac{1}{2}k^4e^{k}e^{iks}dk.
$$
Finally, convert the variable in the second integral on $(0,\infty)$
$$
\frac{1}{2\pi}\int_{-\infty}^0
\frac{1}{ik+1}\frac{1}{2}k^4e^{k}e^{iks}dk
=\frac{1}{2\pi}\int_0^\infty \frac{1}{-ik+1}\frac{1}{2}k^4e^{-k}e^{-iks}dk,
$$
and we get
$$
\chi(s) = \frac{1}{2\pi}\int_0^\infty
\frac{1}{ik-1}\frac{1}{2}k^4e^{-k}(e^{iks}-e^{-iks})dk
=-\frac{1}{2\pi}\int_0^\infty \frac{ik^4}{1-ik}e^{-k}\sin (ks)dk.
$$


TITLE: Dice rolling / Smallest value probability
QUESTION [2 upvotes]: If $X$ is the smallest number when rolling a die $n$ times. Then how can we obtain the PDF/CDF? I thought as for $1\leq{i}\leq6$ how to find $P(X=i)$.

Example: Throws$=(3,2,4,4,5)\implies X=2$. If we want to generalize this into a PDF/CDF, I was trying to use the formula $X=\min{(X_1,X_2,\dots,X_n)}$.
I don't know how to apply the whole formula and get to the general PDF/CDF.
 Any tips would be welcome.

REPLY [1 votes]: Here is a verification of the results in the very nice Answer of @NicholasFRANCOIS,
for the case $n = 8$, based on simulating the 8-roll experiment a million times
and finding the minimum face number $Y$ for each experiment.
m = 10^6;  n = 8;  die=1:6
x = sample(die, m*n, rep=T)
DTA = matrix(x, nrow=m)      # m x n matrix; each row has results of one n-roll expt
y = apply(DTA, 1, min)
table(y)/m
#     y
#        1        2        3        4        5        6  # simulated dist'n
# 0.767262 0.193576 0.035219 0.003779 0.000163 0.000001

hist(y, prob=T, br=(0:6)+.5, col="wheat")
   pdf=numeric(6)
   i = 1:5;  pdf[1:5] = ((7-i)/6)^n - ((7-i-1)/6)^n
   pdf[6] = (1/6)^n
points(1:6, pdf, col="blue", pch=19)

round(pdf, 6)
# 0.767432 0.193550 0.035112 0.003754 0.000152 0.000001  # exact dist'n

The histogram shows simulated results, and the blue dots atop histogram
bars show exact results. The resolution of the graph shows only about
two decimal places, simulated results are accurate to about three places.

Note: I started by simulating the case $n = 10,$ but then minimums are
almost entirely 1's and 2's.