TITLE: Find the value of $\frac {|B-A| }{|1-\overline AB|}$ where $|B| = 1$.
QUESTION [1 upvotes]: If $A$ and $B$ are two different complex numbers and $|B| = 1$, find the value of
  $$\frac {|B-A| }{|1-\overline AB|}$$
  where, as usual, $\overline A$ denotes the conjugate of $A$.

If possible please don't tell me the entire answer just tell me from where to begin.

REPLY [0 votes]: Hint:)
$$\left(\frac {|B-A| }{|1-\overline AB|}\right)^2=\dfrac{B-A}{1-\overline AB}\dfrac{\overline B-\overline A}{1-A\overline B}$$
now multiply and simplify!


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

In this appendix, we prove theorem~\ref{AMP-theorem}.  To do this, we begin by introducing a general `symmetric' AMP algorithm  in section~\ref{appsec:finitesample} and show it is quite similar to the AMP algorithm in \eqref{eq:AMP}.  For this symmetric AMP algorithm, we provide finite sample guarantees like those given in \cite{RushVenkataramanan} for  various `non-symmetric' AMP algorithms. However, we have an added challenge in that terms like the Lipschitz constant of the denoiser $f_t$ in \eqref{eq:denoiser} and the state evolution values in \eqref{eq:state_evolution2} depend on $n$ and therefore cannot be treated as universal constants in the rate of concentration, as they were in \cite{RushVenkataramanan}.  The main concentration result for the symmetric AMP is given in theorem~\ref{thm:sym} in section~\ref{appsec:finitesample}. Then, in section~\ref{appsec:our_AMP_result}, we use theorem~\ref{thm:sym} to prove result \eqref{eq:finite_sample}, from which we prove theorem~\ref{AMP-theorem}.

\subsection{Symmetric AMP finite sample guarantees}  \label{appsec:finitesample}

We begin by analyzing a `symmetric'  AMP algorithm, described now, that 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}$ i.i.d.\ $\mathcal{N}(0,1/n)$, and $\{Z_{ii}\}_{1 \leq i  \leq n}$ i.i.d.\ $\mathcal{N}(0,2/n)$.  Start with an initial condition $\bh^0 \in \mathbb{R}^n$, independent of $\bZ$, and calculate for $t \geq 0$,
\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 (i.e.\ it acts component-wise when applied to vectors) and may depend on $n$ through its Lipschitz constant, denoted $L_g^n$. The function $g_t$ takes
as its second argument  a random vector $\bX^n \in \mathbb{R}^n$ with entries that are i.i.d.\ $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),$ the derivative taken with respect to the first argument, and all terms with negative indices take the value $0$ (so that, for example, $\bh^{1} = \bZ g_0(\bh^0, \bX^n)$). The key result, stated in theorem~\ref{thm:sym} below, is that for each $t \geq 1$, the empirical distribution of the components of $\bh^t$ is 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: initialize with $\sigma^n_1 = \|g_0(\bh^0, \bX^n)\|^2/n$, calculate for $t\geq 1$,
\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}$.

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

 \textbf{Random Vectors:} The random vector $ \bX^n \in \mathbb{R}^n$ used in the denoising functions, is assumed to have entries that are i.i.d.\ according to a sub-gaussian distribution $p_{X,n}$, in particular, $p_{X,n}$ is ${\rm Ber}(\rho_n)$ or Bernoulli-Rademacher, where sub-gaussian  random variables are defined in lemma~\ref{lem:subgauss}.

\textbf{The function $g_t$}: The denoising function $g_t: \mathbb{R}^2 \rightarrow \mathbb{R}$ in \eqref{eq:sym_AMP} is defined as $g_t(\bh^t, \bX^n) = f_t(\bh^t + \sqrt{\lambda_n} \sigma^n_{t} \bX^n)$ where $f_t$ is the conditional expectation denoiser in \eqref{eq:denoiser}. With this definition, $g_t$ is
separable and Lipschitz continuous for each $t \geq 0$, with Lipschitz constant denoted $L^n_g >0$, that depends on $n$. By the Lipschitz property, $g_t$ are weakly differentiable and the weak derivatives, denoted by $g'_t$, are also differentiable.

\begin{thm} \label{thm:sym}
Consider the AMP algorithm in \eqref{eq:sym_AMP} for $\bh^0 \in \mathbb{R}^m$ independent of $\bA$ under the assumptions above.   Then, for any (order-$2$) pseudo-Lipschitz function $\phi: \mathbb{R}^2 \rightarrow \mathbb{R}$,  $\ep \in (0,1)$, and  $t \geq 1$.

 \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  \widetilde{\gamma}_n^{t}}\Big\},
 \label{eq:sym_bound}
 \end{equation}

where the expectation is with respect to standard gaussian $Z$ independent of $X_0^n \sim p_{X,n}$, the state evolution values $\sigma^n_t$ are defined in \eqref{eq:symm_SE}, the constants $C_t, c_t$ are defined in theorem~\ref{AMP-theorem}, and

\begin{align}
\widetilde{\gamma}_n^{t+1} &:= \lambda_n^{2t}  (\nu^n +  \sigma^n_{1})  (\nu^n +  \sigma^n_{1} +  \sigma^n_{2})  \cdots  (\nu^n + \sum_{i=1}^{t+1} \sigma^n_{i}) \max\{1, \hat{\textsf{c}}_1\}  \max\{1, \hat{\textsf{c}}_2\} \cdots \max\{1, \hat{\textsf{c}}_{t}\},
\label{eq:tilde_gamma}
\end{align}

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 $12 \rho_n$ for $p_{X, n} \sim {\rm Ber}(\rho_n)$ (see lemma~\ref{lem:subgauss}).

\end{thm}

The proof of theorem~\ref{thm:sym} is given in section~\ref{appsec:thmproof}.  The proof relies heavily on the proof of the finite sample guarantees for various `non-symmetric' AMP algorithms given in \cite[theorem 1]{RushVenkataramanan} and we reference this result throughout. We will use theorem~\ref{thm:sym}  to prove theorem~\ref{AMP-theorem}, but before doing so, we make a few remarks about extensions of the result and the major differences between theorem~\ref{thm:sym} and the finite sample guarantees in \cite{RushVenkataramanan}.

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

\textbf{Remark 2: Rate of the concentration.}
The rate of concentration depends on $\lambda_n$, $\rho_n$, and the state evolution values, $\sigma_t^n$, through $\widetilde{\gamma}_n^{t}$ defined in \eqref{eq:tilde_gamma}.  In particular, the term $\lambda_n^{2(t-1)}$ in $\widetilde{\gamma}_n^{t}$, appears through the dependency of the rate on the Lipschitz constant of  $g_t$, where $g_t(\bh^t, \bX^n) = f_t(\bh^t + \sqrt{\lambda_n} \sigma^n_{t} \bX^n)$ and $f_t$ is the conditional expectation denoiser in \eqref{eq:denoiser}. With this definition, $L_g^n = \sqrt{\lambda_n}$.
The dependence on these values was not stated explicitly in the concentration bound of \cite[theorem 1]{RushVenkataramanan} as the authors assume that the Lipschitz constant, sparsity, and state evolution terms do not change with $n$ and, thus, can be absorbed into the universal constants.

The presence of these terms in our rate comes from the inductive portion of the proof where one must show that the values $\|g_t(\bh^t, \bX^n)\|^2/n$ concentrate to known constants. Essentially, this step will add a term $(L_g^n)^2 (\nu^n + \sigma^n_{t})$ in the rate at each step of the induction.  To see this, we point the reader to three facts. First, notice that the approximate distribution of $h^t_i$ is gaussian with variance $\sigma^n_{t}$. 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 for $g_t$ in our setting. (More generally, the Lipschitz constant of $[f(x)]^2$ will be no more than $L_f^2$.) Finally, we highlight that pseudo-Lipschitz functions taking gaussian and sub-gaussian input concentrate as in \cite[Lemma B.4]{RushVenkataramanan} with $L^2(\nu^n +  \sigma^n_{t})$ in the denominator of the rate where $L$ is the associated pseudo-Lipschitz constant, $\nu^n$ is the sub-gaussian variance factor, and $\sigma^n_{t}$ is the gaussian variance. Indeed, we restate \cite[Lemma B.4]{RushVenkataramanan} here for clarity.

\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 $G \in  \mathbb{R}^n$ 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< \ep \leq 1$,
\begin{align*}
& \mathbb{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 \ep \Big)  \hspace{-2pt} \leq \hspace{-2pt} 2 \exp \Big\{ \frac{ - \kappa n \ep^2}{(L_f^n)^2[ \nu^n + 4 (\nu^n)^2 + \sigma^n +  4  (\sigma^n)^{2}] }  \Big\}.
\end{align*}
\end{lemma}

Since $0 \leq \nu^n,  \sigma^n  \leq 1$ we drop the squared terms $(\nu^n)^2, (\sigma^n)^{2}$ from the rate since $\nu^n, \sigma^n$ dominate.

\textbf{Remark 3: Denoisers}
The proof of \cite[theorem 1]{RushVenkataramanan}  assumes that the weak derivative of the denoiser, $g'_t$, has bounded derivative everywhere it exists. Here, $g_t(\bh^t, \bX^n) = f_t(\bh^t + \sqrt{\lambda_n} \sigma^n_{t} \bX^n)$ where $f_t$ is the conditional expectation denoiser in \eqref{eq:denoiser} and  $f'_t$ is given in lemma~\ref{lem:PL}. In particular, $f_t'(x) = \sqrt{\lambda_n} f_t(x) (1-f_t(x))$, which is not bounded (in $n$) since $\lambda_n$ grows with $n$.  However, we can show that $f_t'(x)$ is also Lipschitz, with constant $L_f^2 = \lambda_n$,  and we use this fact directly in the proof to get around the boundedness assumption originally used in \cite[theorem 1]{RushVenkataramanan}.

\subsection{Proving theorem~\ref{AMP-theorem}}  \label{appsec:our_AMP_result}

Before we get to the proof of theorem~\ref{AMP-theorem}, we discuss how we apply the result of theorem~\ref{thm:sym} to our problem. This will lead to the concentration result in \eqref{eq:finite_sample},

which concerns convergence within pseudo-Lipschitz loss functions of the empirical distribution of $x^t_i$, the iterate of the AMP algorithm in \eqref{eq:AMP}, to its approximating distribution with mean and variance determined by the state evolution. 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  $\|\phi(\bx)-\phi(\by)\|\leq L\left(1+ \|\bx\|+ \|\by\|\right) \|\bx-\by\|$ for $\bx, \by \in \mathbb{R}^n$.
 \end{defi}

Now we prove \eqref{eq:finite_sample}. 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}$. The AMP algorithm for recovering $\bX$ from the data $\bW$ is given in \eqref{eq:AMP}.

Notice that the AMP algorithm in \eqref{eq:AMP} is similar to \eqref{eq:sym_AMP}, the only difference being that the matrix $\bA$ in \eqref{eq:AMP} is our data matrix, as opposed to it being $\textsf{GOE}(n)$ as in \eqref{eq:sym_AMP}. If we plug the value of $\bW$ from \eqref{WSM_app} into \eqref{eq:AMP}, we find the following iteration: $\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} = \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:AMP}).  In the above, $\bX^n$ is the signal in \eqref{WSM_app} and we drop the $n$ superscript in what follows.  Then, 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} is $\tau^n_1 = \|g_0(\bh^0, \bX)\|^2/n$ and for $t \geq 1,$

\begin{equation}
\tau^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}

The above state evolution is exactly the state evolution for the AMP algorithm in \eqref{eq:AMP3} defined  in \eqref{eq:state_evolution2}.
For this reason, we used the $\tau$ notation.

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 proof idea is to use theorem~\ref{thm:sym} to give performance guarantees to the algorithm in \eqref{eq:AMP_correct} and then to argue that the algorithm in \eqref{eq:AMP3} is asymptotically equivalent to the algorithm in \eqref{eq:AMP_correct} so the performance guarantees hold for \eqref{eq:AMP3} as well.

We apply theorem~\ref{thm:sym} to \eqref{eq:AMP_correct} using  the pseudo-Lipschitz function  $\phi(h^{t}_i, X^n_i) =  \psi(h^{t}_i+ \mu_{t}^n X^n_i, X^n_i)$, where $\psi$ is the order $2$ pseudo-Lipschitz function in \eqref{eq:finite_sample},  to find  that for $t \geq 1$,

 \begin{equation}
 \begin{split}
& \mathbb{P} \Big(\Big| \frac{1}{n} \sum_{i=1}^n \psi(h^{t}_i+ \mu_{t}^n X_i, X_i) -  \mathbb{E}\Big\{\psi\big(\sqrt{\tau^n_t} Z+ \mu_{t}^n X, X\big) \Big\} \Big| \geq \epsilon \Big) \leq C C_{t} \exp\Big\{\frac{-c c_{t} n \epsilon^2}{L_{\psi}^2   \widetilde{\gamma}_n^{t}}\Big\}.
  \label{eq:sym_result}
  \end{split}
 \end{equation}

We have used that $L_{\phi} = 2L_{\psi} (1+\mu_{t}^n)^2$, which is shown in lemma~\ref{lem:PL_second},
and that  $L_{\phi} =2 L_{\psi} (1+\mu_{t}^n)^2 \leq \kappa L_{\psi}$, which follows from the fact that $ \mu_{t}^n \leq \kappa'$ in the regime of interest, as discussed, for example, in \eqref{eq:mu_bound} in section~\ref{appsec:lemmaproof}.

To show how \eqref{eq:finite_sample} follows from~\eqref{eq:sym_result},  we use the following lemma.

 \begin{lemma} \label{lem:aux}
 Define $\textsf{bound}_t := C C_{t} \exp\Big\{\frac{-c c_{t} n \epsilon^2}{L_{\psi}^2\widetilde{\gamma}_n^{t}}\Big\},$ for $  \widetilde{\gamma}_n^{t}$ in \eqref{eq:tilde_gamma}.  Let $\bh^{t}$ be defined by the algorithm in \eqref{eq:AMP_correct} and $ \bx^{t}$ by \eqref{eq:AMP3} Then for $t \geq 1$, the following are true

 \begin{align}

 & \mathbb{P} \Big( \frac{ 1 }{\sqrt{n}}  \| \bh^{t} + \mu_{t}^n \bX  \| \geq \kappa_h \Big) \leq C C_{t} e^{\frac{-c c_{t} n}{\widetilde{\gamma}_n^{t}}} , \quad   \mathbb{P} \Big(   \frac{1}{n}\sum_{i=1}^n h^{t}_i + \mu_{t}^n X_i\geq \frac{\mu_t^n}{2} \Big) \leq C C_{t} e^{\frac{-c c_{t} n }{\rho_n^{-2} \widetilde{\gamma}_n^{t}}}, \label{eq:lemmaboundh} \\

 &        \mathbb{P} \Big( \frac{1}{n}   \Big\| \bx^{t} - \bh^{t} - \mu_{t}^n \bX  \Big\|^2 \geq \frac{\kappa \epsilon^2}{ L^2_{\psi}} \Big)\leq \textsf{bound}_t,\label{eq:lemmabound3} \\

&    \mathbb{P} \Big( \frac{1}{\sqrt{n}}\| \bx^{t}  \| \geq \kappa_x \Big) \leq C C_{t} e^{\frac{-c c_{t} n}{\widetilde{\gamma}_n^{t}}}, \qquad \mathbb{P} \Big( \frac{1}{n}  \sum_{i=1}^n x^{t}_i \geq \frac{\mu_t^n}{2} \Big) \leq C C_{t} e^{\frac{-c c_{t} n}{ \rho_n^{-2} \widetilde{\gamma}_n^{t}}},\label{eq:lemmaboundx}  \\

&       \mathbb{P} \Big(\Big| \frac{1}{n} \sum_{i=1}^n \psi(X_i, x^{t}_i)  - \psi(X_i, h^{t}_i+ \mu_{t}^n X_i) \Big| \geq \epsilon \Big)\leq \textsf{bound}_t,  \label{eq:lemmabound2}\\

 & \mathbb{P} \Big(\Big| \frac{1}{n} \sum_{i=1}^n \psi(X_i, x^{t}_i) -  \mathbb{E}\Big\{\psi\big(X_0, \mu^n_{t} X_0 + \sqrt{\tau^n_t} Z\big) \Big\} \Big| \geq \epsilon \Big)  \leq \textsf{bound}_t. \label{eq:lemmabound1}

   \end{align}

   In \eqref{eq:lemmaboundh} and \eqref{eq:lemmaboundx} both $\kappa_h$ and $\kappa_x$ are universal constants.
 \end{lemma}

The proof of lemma~\ref{lem:aux} is rather long and technical, so we include it in full detail at the end of the appendix in section~\ref{appsec:lemmaproof} and give a high level sketch here.

The basic idea behind the proof of lemma~\ref{lem:aux} is that the results in \eqref{eq:lemmaboundh} follow from the fact that $h^{t}_i + \mu_{t}^n X_i \approx \sqrt{\tau_t^n} Z + \mu_{t}^n X$ for $X \sim p_{X,n}$ independent of $Z$ standard gaussian by theorem~\ref{thm:sym}.  Thus, $ \frac{1}{n}  \sum_{i=1}^n h^{t}_i  + \mu_{t}^n X_i$ concentrates on $\mu_{t}^n  \rho_n$.  Similarly, $\frac{1}{\sqrt{n}} \| \bh^{t} + \mu_{t}^n \bX  \|$ will concentrate to $\tau_t^n + ( \mu_{t}^n)^2 \rho_n$. Then we use concentration to imply boundedness with high probability.
The result \eqref{eq:lemmaboundx} follows from the same ideas since it can be shown that $x^{t}_i \approx \sqrt{\tau_t^n} Z + \mu_{t}^n X$.

Next,  results  \eqref{eq:lemmabound2} and \eqref{eq:lemmabound1} follow immediately from \eqref{eq:lemmaboundh}--\eqref{eq:lemmabound3}.  To see this, first notice that \eqref{eq:lemmabound1} follows directly from the bound in \eqref{eq:sym_result} and \eqref{eq:lemmabound2} using lemma~\ref{sums}.
Next, \eqref{eq:lemmabound2} follows from results \eqref{eq:lemmaboundh} -- \eqref{eq:lemmabound3}.  This can be seen by using the following upper bound due to Cauchy-Schwarz,

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

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

 & \leq \frac{\kappa L_{\psi}}{\sqrt{n}}  \left\| \bx^{t} - \bh^{t}- \mu_{t}^n \bX  \right\| \sqrt{  \Big(1 + \frac{2}{n} \|\bX\|^2 + \frac{1}{n}\|\bx^{t}\|^2 + \frac{1}{n}\|\bh^{t}+ \mu_{t}^n \bX\|^2 \Big) },

\end{split}
 \end{equation}

 and the boundedness of the term $\|\bX\|^2/n$.
Thus, using $\kappa_B = \sqrt{1  + 4 + \kappa_x^2 + \kappa_h^2} > 0$, a universal constant, by the above bound it follows that

 \begin{equation}
 \begin{split}
 \label{eq:tobebounded}
 \mathbb{P}& \Big(\Big| \frac{1}{n} \sum_{i=1}^n \psi(X_i, x^{t}_i)  - \psi(X_i, h^{t}_i+ \mu_{t}^n X_i) \Big| \geq \epsilon \Big)\\%
 & \leq \mathbb{P} \Big( \frac{1}{\sqrt{n}}   \Big\| \bx^{t} - \bh^{t} - \mu_{t}^n \bX  \Big\|\sqrt{  \Big(1 + \frac{2}{n} \|\bX\|^2 + \frac{1}{n}\|\bx^{t}\|^2 + \frac{1}{n}\|\bh^{t}+ \mu_{t}^n \bX\|^2 \Big) }  \geq \frac{\kappa \epsilon}{ L_{\psi}} \Big) \\
 & \leq \mathbb{P} \Big( \frac{1}{\sqrt{n}}   \Big\| \bx^{t} - \bh^{t} - \mu_{t}^n \bX  \Big\| \geq \frac{\kappa \epsilon}{\kappa_B L_{\psi}} \Big) + \mathbb{P} \Big(\frac{2}{n} \|\bX\|^2  \geq 2(1+ \rho_n) \Big)  \\

 & \hspace{3cm}+  \mathbb{P} \Big(  \frac{1}{n}\|\bx^{t}\|^2   \geq \kappa^2_x \Big) +  \mathbb{P} \Big(  \frac{1}{n}\|\bh^{t}+ \mu_{t}^n \bX\|^2  \geq \kappa^2_h \Big).
 \end{split}
 \end{equation}

Note, we have used $\rho_n \leq 1$ so $\frac{1}{\kappa_B^2}\left(1 + 2(1 + \rho_n) +\kappa_x^2 + \kappa_h^2\right) \leq 1$.
Considering the result in \eqref{eq:tobebounded}, we notice that result \eqref{eq:lemmabound2} follows directly from \eqref{eq:lemmaboundh}--\eqref{eq:lemmabound3}, since by Chernoff's bound (lemma~\ref{lem:chernoff}),

\begin{equation*}
 \mathbb{P} \Big(\frac{2}{n} \|\bX\|^2  \geq 2(1+ \rho_n)  \Big)  \leq  \mathbb{P} \Big(\Big \lvert \frac{1}{n} \|\bX\|^2 - \rho_n  \Big \lvert \geq 1 \Big)  \leq 2\exp\left\{  \frac{-n}{3 \rho_n}\right\}.
\end{equation*}

Thus, \eqref{eq:lemmabound2} (hence, \eqref{eq:lemmabound1},) follows easily from \eqref{eq:lemmaboundh}--\eqref{eq:lemmabound3} and the main technical piece of proving lemma~\ref{lem:aux} is then proving results \eqref{eq:lemmaboundh}--\eqref{eq:lemmabound3} rigorously.  This is done in section~\ref{appsec:lemmaproof}.

Now that we show that \eqref{eq:finite_sample}  follows from lemma~\ref{lem:aux} result \eqref{eq:lemmabound1}, and then we finally prove theorem~\ref{AMP-theorem}. Notice that \eqref{eq:finite_sample} is recovered by applying \eqref{eq:lemmabound1} with pseudo-Lipschitz function $ \widetilde{\psi}(X_i, x^{t}_i) =  \psi(X_i, f_t(x^{t}_i))$,

as the only difference between \eqref{eq:finite_sample} and  \eqref{eq:lemmabound1} is that  $x^t_i$ in \eqref{eq:finite_sample} is replaced with $f_t(x^t_i)$ in \eqref{eq:lemmabound1}. With this choice of pseudo-Lipschitz function, an $L_f^2$ term is added in the denominator of the rate of concentration, since
$L_{\widetilde{\psi}} = 3  L_{\psi}  \max\{1, L_f\}$, which is shown in lemma~\ref{lem:PL_second}.

We note that from \eqref{eq:gamma_def} and \eqref{eq:tilde_gamma} it is easy to see that
$
 \widetilde{\gamma}_n^{t}  L_f^2 = \widetilde{\gamma}_n^{t}  \lambda_n
 = \gamma_n^{t},
$
 noting that $\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)] = \hat{\textsf{b}}_t$.  Moreover, the bound on the RHS of \eqref{eq:finite_sample} equals $\textsf{bound}_t$ defined in theorem~\ref{AMP-theorem} when $L_{\psi}$ is a universal constant.

 Now we prove theorem~\ref{AMP-theorem} using \eqref{eq:finite_sample}.
First, notice that theorem~\ref{AMP-theorem} result \eqref{eq:finite_sample_vector1} follows directly from \eqref{eq:finite_sample} using 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_vector1} 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 prove theorem~\ref{AMP-theorem} result \eqref{eq:finite_sample_matrix1}.
Now considering the concentration result in \eqref{eq:finite_sample_matrix1}, 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: for $\textsf{bound}_t$ defined in the  theorem~\ref{AMP-theorem} statement,

 \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_matrix01} \\
\mathbb{P} \Big(\Big|  \frac{1}{n^2}\|f_t(\bx^t)\|^4 - (\tau^n_{t})^2 \Big| \geq \epsilon \Big) &\leq \textsf{bound}_t,  \label{eq:finite_sample_matrix02} \\
\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 \textsf{bound}_t.\label{eq:finite_sample_matrix03}
 \end{align}

Then the final concentration result in \eqref{eq:finite_sample_matrix1} 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)\\
&\qquad\qquad +  \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_matrix01} - \eqref{eq:finite_sample_matrix03} applied to the above give the result in \eqref{eq:finite_sample_matrix1}.

Now we prove  \eqref{eq:finite_sample_matrix01} - \eqref{eq:finite_sample_matrix03}. First we prove \eqref{eq:finite_sample_matrix01} using Heoffding's Inequality, lemma~\ref{lem:hoeff_lem},

 \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_matrix01} then follows from the above by lemma~\ref{powers}.

 Next, for \eqref{eq:finite_sample_matrix02} we apply \eqref{eq:finite_sample} 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 \textsf{bound}_t,
 \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_matrix02} follows from the above by lemma~\ref{powers} and the fact that $\tau^n_{t} \leq \rho_n$.

Finally we prove result \eqref{eq:finite_sample_matrix03} by applying \eqref{eq:finite_sample} 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 \textsf{bound}_t,
 \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_matrix03} follows  from the above  by lemma~\ref{powers} $\tau^n_{t} \leq \rho_n$.

\input{sections/APP_AMP_symAMP}
\input{sections/APP_AMP_lemmaproof}

\subsection{Useful lemmas} \label{appsec:useful_lemmas}

In this section we introduce a number of technical lemmas that are used to prove our main results. We include proofs only where the proof is non-standard.

 \begin{lemma}
 Recall from \cite{BLMConc},  that a random variable, $X$, is sub-gaussian with variance factor $\nu$ if $\log \mathbb{E}[e^{t (X - \mathbb{E}[X])}] \leq {t^2 \nu}/{2}$ for all $t \in \mathbb{R}$. When $X \sim p_{X}$, we have $\nu = 12 \rho$ for $p_{X} \sim {\rm Ber}(\rho)$.
 \label{lem:subgauss}
 \end{lemma}

 \begin{proof}
 The proof relies on an intermediate result: if for any $t >0$ it is true that

 \begin{equation}
 P(X > t) \leq \exp\left(\frac{-t^2}{2 \sigma^2}\right), \qquad \text{ and } \qquad  P(X < -t) \leq \exp\left(\frac{-t^2}{2 \sigma^2}\right),
 \label{eq:prob_bounds}
 \end{equation}

 then for any $s > 0$ it holds that $\mathbb{E}[e^{s X}] \leq e^{4 \sigma^2 s^2}$. This is easy to prove by showing that \eqref{eq:prob_bounds} implies bounds on the moments $\mathbb{E}[|X|^k]$ for any $k \in \mathbb{N}$, from which we can bound the moment generating function.
 Thus, by  lemma~\ref{lem:chernoff}, we have that $\sigma^2 = (3/2) \rho_n$, giving the desired result: $\mathbb{E}[e^{t (X - \mathbb{E}[X])}] \leq e^{6 \rho_n t^2}$.
 \end{proof}

\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
$\mathbb{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{lemma}[Hoeffding's inequality]
\label{lem:hoeff_lem}
If $X_1, \ldots, X_n$ are independent 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
$\mathbb{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}  \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}
  \end{lemma}

 \begin{proof}
 Verifying the pseudo-Lipschitz property for the functions in \eqref{eq:the_phis} is straightforward, so we omit the details.

\end{proof}

 \begin{lemma}  \label{lem:PL_second}
 Recall the definition of pseudo-Lipschitz functions of order $2$ given in Definition~\ref{def:PL}. Let $f_t$ be the conditional expectation denoiser in \eqref{eq:denoiser} with Lipschitz constant $L_f^n$ and let  $\psi: \mathbb{R}^2 \rightarrow \mathbb{R}$ be a pseudo-Lipschitz of order $2$ function with constant $L_{\psi}$.
 The following functions $\phi: \mathbb{R}^2 \rightarrow \mathbb{R}$ are all pseudo-Lipschitz of order $2$ with  the stated pseudo-Lipschitz constants.
 \begin{align}
 \phi_1(a, b)  &=   \psi(a+ \mu_{t}^n b, b) , \qquad  L_{\phi_1} =  2 L_{\psi} (1+\mu_{t}^n)^2,  \label{eq:phi1}\\
\phi_2(a, b)  &=  \psi(a, f_{t}(b)),  \qquad  L_{\phi_2} =  3  L_{\psi}  \max\{1, L_f\},  \label{eq:phi2} \\
\phi_3(a, b)  &=   (\mu_{t}^n)^{-1}a+b  , \qquad  L_{\phi_3} =  \sqrt{2} \max\{1, (\mu_{t}^n)^{-1}\} ,  \label{eq:phi3} \\
 \phi_4(a, b)  &=   (a + \mu_{t}^n b)^2  , \qquad  L_{\phi_4} =  2\max\{1, (\mu_{t}^n)^2\} .  \label{eq:phi4}
 \end{align}
  \end{lemma}

  \begin{proof}
For function $\phi_1$ in \eqref{eq:phi1}, first notice

 \begin{equation}
 \begin{split}
 \label{eq:Lipschitz1}
&\lvert  \phi_1(a,b) -   \phi_1(\widetilde{a},\widetilde{b}) \lvert = \lvert   \psi(a+ \mu_{t}^n b, b) -     \psi(\widetilde{a}+ \mu_{t}^n \widetilde{b},\widetilde{b})  \lvert  \\

&\qquad \leq L_{\psi} (1 +  \| (a+ \mu_{t}^n b, b) \| +  \|  (\widetilde{a}+ \mu_{t}^n \widetilde{b},\widetilde{b})  \| )  \times \| (a+ \mu_{t}^n b, b) -  (\widetilde{a}+ \mu_{t}^n \widetilde{b},\widetilde{b})   \|.
\end{split}
 \end{equation}

 Next notice

 \begin{equation*}
 \begin{split}
&\| (a+ \mu_{t}^n b, b) - (\widetilde{a}+ \mu_{t}^n \widetilde{b},\widetilde{b})  \| \leq  | a- \widetilde{a}| + (1+\mu_{t}^n)  |b- \widetilde{b}| \leq \sqrt{2} (1+\mu_{t}^n)   \| (a, b) -    (\widetilde{a},\widetilde{b})  \|,
\end{split}
 \end{equation*}

and

$ \| (a+ \mu_{t}^n b, b) \|  \leq  |a+ \mu_{t}^n b| + |b | \leq  |a|+ (1+\mu_{t}^n) |b| \leq \sqrt{2} (1+\mu_{t}^n) \| (a, b) \|. $

Thus, from  \eqref{eq:Lipschitz1}, we have result \eqref{eq:phi1}:

 \begin{equation*}
 \begin{split}
&\lvert  \phi_1(a,b) -   \phi(\widetilde{a},\widetilde{b}) \lvert \leq 2 L_{\psi} (1+\mu_{t}^n)^2 (1 +  \| (a, b) \| + \| (\widetilde{a},\widetilde{b}) \|| )   \times  \| (a, b) -    (\widetilde{a},\widetilde{b})  \|.
\end{split}
 \end{equation*}

 For function $\phi_2$ in \eqref{eq:phi2}, first notice

 \begin{equation}
 \begin{split}
 \label{eq:Lipschitz_func2}
\lvert    \phi_2(a, b) -   \phi_2(\widetilde{a}, \widetilde{b}) \lvert &= \lvert   \psi(a, f_{t}(b)) -     \psi(\widetilde{a}, f_{t}(\widetilde{b}))  \lvert \\

& \leq L_{\psi} (1 +  \| (a, f_{t}(b))  \| +  \|  (\widetilde{a}, f_{t}(\widetilde{b}))  \|) \| (a, f_{t}(b)) -    (\widetilde{a}, f_{t}(\widetilde{b}))  \|.
\end{split}
 \end{equation}

 Next, notice that since $f_t(\cdot)$ is a Lipschitz function with constant $L_f$,

 \begin{equation*}
 \begin{split}
\| (a, f_{t}(b)) -    (\widetilde{a}, f_{t}(\widetilde{b}))  \|^2 &= | f_{t}(b) - f_{t}(\widetilde{b})|^2+ | a  - \widetilde{a}|^2 \\
&\leq   L_f^2 | b- \widetilde{b}|^2 + | a  - \widetilde{a}|^2 \leq \max\{1, L_f^2\} \| (a, b) -    (\widetilde{a}, \widetilde{b})  \|^2,
\end{split}
 \end{equation*}

 and since our denoiser of interest $f_t$ in \eqref{eq:denoiser} is such that $|f_t(x)| \leq 1$,

 \begin{equation*}
 \begin{split}
   \| (a, f_{t}(b))  \| \leq  |a| + |f_{t}(b)| \leq  |a|  + 1 &\leq (1 + |a| +  |b| )  \leq \sqrt{2} (1 + \|(a, b)\|).
\end{split}
 \end{equation*}

 Thus, from \eqref{eq:Lipschitz_func2},

 \begin{equation}
 \begin{split}
 \label{eq:Lipschitz_func2}
\lvert  \widetilde{\psi}(a,b) -   \widetilde{\psi}(\widetilde{a}, \widetilde{b}) \lvert   \leq 3  L_{\psi}  \max\{1, L_f\} (1 + \|(a, b)\| + \|( \widetilde{a},  \widetilde{b})\| )  \| (a, b) -    (\widetilde{a}, \widetilde{b})  \|.
\end{split}
 \end{equation}

Next, the bound for function $\phi_3$ in \eqref{eq:phi3} is straightforward:

 \begin{equation*}
 \begin{split}
\lvert    \phi_3(a, b) -   \phi_3(\widetilde{a}, \widetilde{b}) \lvert &= \Big \lvert    (\mu_{t}^n)^{-1} a +b  -   (\mu_{t}^n)^{-1}  \widetilde{a} - \widetilde{b} \Big  \lvert   \\
&\leq      (\mu_{t}^n)^{-1} \lvert a   -  \widetilde{a}   \lvert + \lvert b - \widetilde{b}  \lvert \leq  \sqrt{2} \max\{1, (\mu_{t}^n)^{-1}\} \| (a,b)   -  (\widetilde{a}, \widetilde{b}) \| .
\end{split}
 \end{equation*}

Finally, for function $\phi_4$ in \eqref{eq:phi4}, first notice

 \begin{equation*}
 \begin{split}
&\lvert    \phi_4(a, b) -   \phi_4(\widetilde{a}, \widetilde{b}) \lvert = \Big \lvert    (a + \mu_{t}^n b)^2  -   (  \widetilde{a} + \mu_{t}^n   \widetilde{b})^2 \Big  \lvert   \\

&\leq \Big \lvert    (a + \mu_{t}^n b)  -   (  \widetilde{a} + \mu_{t}^n   \widetilde{b}) \Big  \lvert  \Big \lvert    (a + \mu_{t}^n b) +  (  \widetilde{a} + \mu_{t}^n   \widetilde{b}) \Big  \lvert  \\

&\leq   2\max\{1, (\mu_{t}^n)^2\} ( \| (a, b)\| + \| (\widetilde{a} , \widetilde{b} )\|)  ( \| (a, b) - (\widetilde{a} , \widetilde{b} )\|),
\end{split}
 \end{equation*}

 where the final inequality uses that $ \lvert    a + \mu_{t}^n b  \lvert  \leq \sqrt{2} \max\{1, \mu_{t}^n\}   \| (a, b)\|$ giving

 $$ \Big \lvert    (a + \mu_{t}^n b) +  (  \widetilde{a} + \mu_{t}^n   \widetilde{b}) \Big  \lvert  \leq  \sqrt{2} \max\{1, \mu_{t}^n\}  ( \| (a, b)\| + \| (\widetilde{a} , \widetilde{b} )\|)$$

 and the fact that

 \begin{align*}
 \Big \lvert    (a + \mu_{t}^n b)  -   (  \widetilde{a} + \mu_{t}^n   \widetilde{b}) \Big  \lvert \leq  \lvert a - \widetilde{a} \lvert + \mu_{t}^n \vert b -   \widetilde{b} \lvert  \leq \sqrt{2} \max\{1,  \mu_{t}^n\} \|(a,b) - (  \widetilde{a} ,   \widetilde{b})\|.
 \end{align*}

 \end{proof}

\begin{lemma}  \label{lem:PL_cond}
 Recall the definition of pseudo-Lipschitz functions of order $2$ given in Definition~\ref{def:PL}.  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))$.  Moreover, the Lipschitz constant can be strengthened to $\sqrt{\lambda_n}  \rho_n$ on $x \in (-\infty, \frac{\mu^n_t}{2})$ and $f_t(0) \leq \rho_n$.
  \end{lemma}

 \begin{proof}
 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}
\label{eq:ft}
 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\}  \\

&=\mathbb{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.

Finally, notice that from \eqref{eq:ft} we have

\begin{equation}
\begin{split}
\label{eq:ft2}
 f_t(x) &= \frac{\rho_n   }{(1-\rho_n)  \exp\big\{ \frac{1}{2}  (\lambda_n \tau^n_{t}  - 2x \sqrt{\lambda_n} ) \big\}   +\rho_n  }.
\end{split}
\end{equation}

Then since $e^{x} \geq 1 + x$ (which can be seen by showing that $f(x) =e^{x} - (1 + x)$ has a minimum at $f(0) =0$),
\begin{equation*}
\begin{split}
 f_t(x) &\leq \frac{\rho_n   }{(1-\rho_n)  (1 +  \frac{1}{2}  (\lambda_n \tau^n_{t}  - 2x \sqrt{\lambda_n} ))   +\rho_n  } =  \frac{\rho_n   }{1  +\frac{1}{2} (1-\rho_n)   (\lambda_n \tau^n_{t}  - 2x \sqrt{\lambda_n} )   }.
\end{split}
\end{equation*}

The above implies that $ f_t(0) \leq \rho_n$, and further, since
\begin{align*}
 (1-\rho_n)   (\lambda_n \tau^n_{t}  - 2x \sqrt{\lambda_n} ) \geq 0 \quad \text{ when } \quad x \leq  \frac{\sqrt{\lambda_n} \tau^n_{t}}{2} ,
\end{align*}
we find the bound $0 \leq  f_t(x) \leq \rho_n$ when $x \leq  \frac{\sqrt{\lambda_n} \tau^n_{t}}{2}$.

Therefore, by \eqref{eq:deriv}, we have $|\frac{\partial}{\partial x} f_t(x)| \leq  \sqrt{\lambda_n} f_t(x) \leq  \sqrt{\lambda_n}  \rho_n$ and it follows that $f_t(\cdot)$ is Lipschitz continuous with Lipschitz constant $  \sqrt{\lambda_n}  \rho_n$ on $x \in (-\infty, \frac{\mu^n_t}{2})$.
\end{proof}

The proof of the following two lemmas 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*}
\mathbb{P}\Big(  \lvert \sum_{i=1}^M X_i  \lvert \geq \ep\Big) \leq \sum_{i=1}^M \mathbb{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\,
$
\mathbb{P}( \lvert X_n - c \lvert \geq \epsilon ) \leq e^{-\kappa n \epsilon^2},
$
it follows that
$
\mathbb{P}(\lvert X_n^2 - c^2  \lvert \geq \epsilon) \leq e^{ {-\kappa n \ep^2}/[1+2c]^2}.
$
\end{lemma}

config: arxiv


TITLE: Factor negative from quadratic equation
QUESTION [0 upvotes]: $-4x^2+20x-25=0$
Then you factor out -1
$-1(4x^2-20x+25)=0$
Then factor again into $(a-b)^2$
$-1(2x-5)^2=0$
In the second equation, can I multiply both sides by -1, why did the author  leave "-1" dangling in the final equation?
i.e.
$-1 * (4x^2-20x+25)=0 *-1$
which will result in
$(4x^2-20x+25) = 0 $
$(2x-5)^2 = 0$

REPLY [1 votes]: Yes you can, multiplying/dividing by a number doesn't really affect the solution as much, but what's not allowed is to divide variable as it will make you lose some answer. In fact eliminating negative number make it easier to solve the equation


TITLE: Consider the linear transformation $L:R^n\to R^n$ defined by $L\left(X\right)=AX$, then $A$ is diagonalizable iff the matrix of $L$ is diagonal.
QUESTION [0 upvotes]: I was asked to study the following corollary
I could only understand up to theorem 3, does anyone know what the name of this corollary is and if there is clearer proof online?

REPLY [0 votes]: I think that this is a pretty straightforward result. You have to first understand what do you mean by Diagonalization. It means that the matrix representing the linear transformation (with a suitable basis) is a diagonal matrix. Note that if you change the basis the matrix representing the transformation will likely change. There is another interpretation of Diagonalization which says that a linear transformation is diagonalize if the eigen spaces corresponding to the eigen vales cumulatively span the range of the transformation. This corollary shows that the two are equivalent.


TITLE: Area of triangle formed by a pair of tangents to a circle, from an external point, with the chord of contact
QUESTION [2 upvotes]: If the length of tangent drawn from an external point P to the circle of radius $r$ is $l$ , then prove that area of triangle form by pair of tangent and its chord of contact is $\displaystyle\frac{rl^3}{r^2+l^2}$

I have the solution of this which states: External point P, centre C and one point of contact is A. Let $\theta$ is the angle formed at P and $\angle APC$.
It is given that area =$\frac{1}{2} 2r\cos\theta \cdot l \cos\theta$
My question how come it is $r\cos\theta$ as the point of intersection of chord and line PC is not equal to $r$ (radius).

REPLY [1 votes]: Let $A'$ be the other point of contact.
The triangle $APC$ is right. $A'A$ and $PC$ are perpendicular. Let $H$ be the intersection of $A'A$ and $PC$. Then the triangles $ACH$, $AHP$ and $APC$ are similar. Thus, the angle $\angle APC$ is equal to $\angle CAH$. Then, the chord $A'A$ is $2r\cos\theta$. Now, use the similarity:
$$\frac{PH}{AH}=\frac{AP}{AC}$$
that is,
$$\frac{PH}{r\cos\theta}=\frac lr$$
and then
$$PH=l\cos\theta$$
Now we can compute the area:
$$[AA'P]=\frac{AA'\cdot HP}2=rl\cos^2\theta$$
but
$$\cos\theta=\frac {AP}{CP}=\frac l{\sqrt{l^2+r^2}}$$


TITLE: How to find partial derivative if given antiderivative
QUESTION [0 upvotes]: In my book exercise I need to find $\frac{მz}{მx}$, if $F(xz,yz)=0$
I try to do it like that
$$ F'_{xz}(d(xz))+F'_{yz}(d(yz))=0 $$
$$ F'_{xz}(z+x\frac{მz}{მx})+F'_{yz}(z\frac{მy}{მx}+y\frac{მz}{მx})=0 $$
express from it $\frac{მz}{მx}$
$$ \frac{მz}{მx}=\frac{-F'_{xz}*z-F'_{yz}*z\frac{მy}{მx}}{F'_{xz}*x+F'_{yz}*y} $$
but answer in the end of the book don't have part with $\frac{მy}{მx}$

REPLY [1 votes]: Write $$\frac {\partial}{\partial u}F(u,v)=F_1(u,v),\frac {\partial}{\partial v}F(u,v)=F_2(u,v).$$ The given equation defines $z$ implicitly as a function of $x$ and $y.$ By the chain rule, $$F_1(xz,yz)(z+x\frac{\partial z}{\partial x})+F_2(xz,yz)(y\frac{\partial z}{\partial x})=0.$$
$$F_1(xz,yz)z+F_1(xz,yz)x\frac{\partial z}{\partial x}+F_2(xz,yz)(y\frac{\partial z}{\partial x})=0.$$ $$(F_1(xz,yz)x+F_2(xz,yz)y)\frac{\partial z}{\partial x}=-F_1(xz,yz)z$$
$$\frac{\partial z}{\partial x}=-\frac{F_1(xz,yz)z}{F_1(xz,yz)x+F_2(xz,yz)y}$$
provided $F_1(xz,yz)x+F_2(xz,yz)y \ne 0.$


TITLE: prove ergodic theorem for finite irreducible, aperiodic Markov Chain
QUESTION [1 upvotes]: State and prove ergodic theorem for finite irreducible, aperiodic Markov Chain with transition probability matrix $P=(p_{ij})$.

I know what irreducible, aperiodic means. But I do not understand about what theorem it is referring. More precisely, what are the things I need to prove.
I know that if a finite markov chain is irreducible, it is called ergodic markov chain. But what to prove here if that is a definition. So what to prove here?
Thanks for any help.

REPLY [0 votes]: Lemma C.1 (page 392) in the book "Markov Chains and Mixing Times (2nd edition)" written by David A.Levin and Yuval Peres contains the proof you want. (The key is to use the strong law of large numbers).


TITLE: Counting ways to distribute 7 apples and 5 pears between 4 children with restriction
QUESTION [6 upvotes]: I was given the following problem:

In how many ways $7$ apples and $5$ pears can be distributed between four kids if each child gets three fruits?

My counting is not the strongest, here is how I approached the problem: first I will distribute the pears then fill the missing spots with apples. We can use stars and bars to count the distribution of pears: $\binom{5+4-1}{4-1}=\binom 8 3=56$. We need to subtract cases when there are more than $3$ pears: $4$ (one basket with $5$ pears) and $\frac{4!}{2!}$ ($4$ pears in one basket and one in some other basket). Thus, the total number is $56-4-12=40$. Is this correct? Is there a better way to explain this problem to students?

REPLY [3 votes]: Using more powerful technique, for much more tough questions :
Lets use generating functions, lets assume that $x's$ mean apples and $y's$ mean pears, then a child can have at most $3$ apples or pears. Hence the generating function of each child is $$(x^3+ x^2y +xy^2 +y^3) = \frac{x^4 -y^4}{x-y}$$
Now , we need to find the coefficient of $x^7y^5$ in the expansion of $$(x^3+ x^2y +xy^2 +y^3)^4=\left( \frac{x^4 -y^4}{x-y} \right)^4$$
The answer is $40$.


TITLE: How to generate a series of points in a convex set?
QUESTION [0 upvotes]: For an arbitrary convex set, may be a polyhedron or an ellipsoid how can I generate N uniformly distributed points inside?

REPLY [1 votes]: Generate points uniformly in a rectangle that contains the set and keep only those that are in the set.


TITLE: Question about finding the dimension of Ker of a matrix!
QUESTION [0 upvotes]: First year student here trying to pass the Linear Algebra exam! Found this in one of the practice quizzes! I tried to find a way to acchive the result but i cant figure it out! Can someone help me?
So the question goes like this!
Let R^(3,2) be the vector space of real matrices with 3 rows and 2 columns and R^(2,2) be the vector space of real matrices with 2 rows and 2 columns. Let us consider the linear map:
f(X)=(1 2 1, 0 0 0)*X where X∈R^(3,2).
Which of the following statements is true?
A) f is sujective;
B)dim(Ker(f))=2
C)dim(Ker(f))=4
D) f is injective
Tee correct one is C but i cant figure it out how to solve it in case something similar comes up in my exam! Can you help me?

REPLY [0 votes]: For any two finite dimensional vector spaces $V$ and $W$ with a linear map $\varphi:V \rightarrow W$ the dimension of the image plus the dimension of the kernel will be the dimension of $V$. We also know that the dimension of the image can be no greater than the dimension of $W$. In this case you have a six dimensional space of $3 \times 2$ matrices mapping to the four dimensional space of $2 \times 2$ matrices. The matrix you're given will have an image of the form $$\pmatrix{x & y  \\ 0 & 0}$$ and since the image is two dimensional. This means the dimension of the kernel is $6 - 2 = 4$.


TITLE: If a morphism of vector bundles is a vector space isomorphism on the fibres, then it it a vector bundle isomorphism.
QUESTION [3 upvotes]: The following is a definition of a vector bundle isomorphism.

Let $E,F$ be vector bundles over a base manifold $M$. A smooth map $u:E\rightarrow F$ is a an isomorphism of vector bundles if

$u$ respects the fibres, that is for all $x\in M$ it follows that $u_x:=u|_{E_x}:E_x\rightarrow F_x$.

for each $x\in M$ the map $u_x$ is a vector space isomorphism.

It is not obvious to me how this implies that there is a smooth inverse $u^{-1}:F\rightarrow E$.It's clear that it has something to do with vector bundles being locally trivial but I am not sure how to complete my arguement.
Let $U$ be a neighborhood on which $E$ and $F$ are trivial. Then there are diffeomorphism $\phi:E_U\rightarrow U\times \mathbb{R}^n$ and $\psi:F_U\rightarrow U\times \mathbb{R}^n$. but since clearly $U\times \mathbb{R}^n \cong U\times \mathbb{R}^n$ it follows that $E_U \cong F_U$. So we have shown that $E$ and $F$ as manifolds are locally diffeomorphic?
I'm not sure if this is correct, and I haven't shown that $u$ has a smooth inverse.

REPLY [3 votes]: This is essentially the same as Showing map is vector bundle isomorphism. The difference is that you work in the smooth category.
$GL(n,\mathbb R)$ is smooth submanifold of $End(\mathbb R^n) \approx \mathbb R^{n^2}$ and it is well-known that for product bundles the assignment $\phi \mapsto \phi''$ given in my answer to the linked question establishes a bijection between smooth bundle maps $\phi$ ansd smooth maps $\phi'' : B \to GL(n,\mathbb R)$ (provided $B$ is a smooth manifold).
Since inversion in $GL(n,\mathbb R)$ is smooth, we see that $\phi^{-1}$ is smooth.
This transfers to smooth bundle maps between trivial bundles.
Thus, if $u :  E \to F$ is a general smooth bundle map, we see that $u^{-1} : F \to E$ is locally smooth. But local smoothness implies global smoothness. This follows from the definition of a smooth map - it is a local property. You can also find it in any good textbook.