Optimization-based AMP for Phase Retrieval: The Impact of Initialization and $\ell_2$-regularization

Introduction

2 Informal statement of our results

where $x_{*,i}$ is the $i$th component of $\bm{x}_{*}$ and $w_{a}\sim\mathcal{CN}(0,\sigma^{2}_{w})$ a Gaussian noise. The recent surge of interest has led to a better understanding of the theoretical aspects of this problem. Thanks to such research we now have access to several algorithms, inspired by different ideas, that are theoretically guaranteed to recover $\bm{x}_{*}$ exactly in the noiseless setting. Despite all this progress, there is still a gap between the theoretical understanding of the recovery algorithms and what practitioners would like to know. For instance, for many algorithms, including Wirtinger flow and amplitude flow , the exact recovery is guaranteed with either $cn\log n$ or $cn$ measurements, where $c$ is often a fixed but large constant that does not depend on $n$. In both cases, it is often claimed that the large value of $c$ or the existence of $\log n$ is an artifact of the proving technique and the algorithm is expected to work with $cn$ for a reasonably small value of $c$. Such claims have left many users wondering

Which algorithm should we use? Since the theoretical analyses are not sharp, they do not shed any light on the relative performance of different algorithms. Answering this question through simulations is very challenging too, since many factors including the distribution of the noise, the true signal $\bm{x}_{*}$, and the number of measurements may have impact on the answer.

When can we trust the performance of these algorithms in the presence of noise? Suppose for a moment that we know the minimum number of measurements that is required for the exact recovery through simulations. Should we collect the same number of measurements in the noisy settings too?

What is the impact of initialization schemes, such as spectral initialization? Can we trust these initialization schemes in the presence of noise? How should we compare different initialization schemes?

Researchers have developed certain intuition based on a combination of theoretical and empirical results, to give heuristic answers to these questions. However, as demonstrated in a series of papers in the context of compressed sensing, such folklores are sometimes inaccurate . To address Question Q.1, several researchers have adopted the asymptotic framework $m,n\rightarrow\infty$, $m/n\rightarrow\delta$, and provided sharp analyses for the performance of several algorithms . This line of work studies recovery algorithms that are based on convex optimization. In this paper, we adopt the same asymptotic framework and study the following popular non-convex problem, known as amplitude-based optimization :

Since (1.2) is a non-convex problem, the algorithm to solve it matters. In this paper, we study a message passing algorithm that aims to solve (1.2). As a result of our studies we

present sharp characterization of the mean square error (even the constants are sharp) in both noiseless and noisy settings.

present a quantitative characterization of the gain initialization and regularization can offer to our algorithms.

Furthermore, the sharpness of our results enables us to present a quantitative and accurate comparison with convex optimization based recovery algorithms and give partial answers to Question Q.1 mentioned above. Below we introduce our message passing algorithm and informally state some of our main results. The careful and accurate statements of our results are postponed to Section 2.

The first point that we would like to discuss here is the effect of the regularizer on AMP.A. For the moment suppose that the noise $\bm{w}$ is zero. Does including the regularizer in (1.2) benefit AMP.A? Clearly, any regularization may introduce unnecessary bias to the solution. Hence, if the final goal is to obtain $\bm{x}_{*}$ exactly we should set $\mu_{k}=0$. However, the optimization problem in (1.2) is non-convex and iterative algorithms intended to solve it can get stuck at bad local minima. In this regard, regularization can still help AMP.A to escape bad local minima through continuation. Continuation is popular in convex optimization for improving the convergence rate of iterative algorithms , and has been applied to the phase retrieval problem in . In continuation we start with a value of $\mu_{k}$ for which AMP.A is capable of finding the global minimizer of (1.2). Then, once $\rm AMP.A$ converges we will either decrease or increase $\mu_{k}$ a little bit (depending on the final value of $\mu$ for which we want to solve the problem) and use the previous fixed point of AMP.A as the initialization for the new AMP.A. We continue this process until we reach the value of $\mu_{k}$ we are interested in. For instance, if we would like to solve the noiseless phase retrieval problem then $\mu_{k}$ should eventually go to zero so that we do not introduce unnecessary bias. The rationale behind continuation is the following. Let $\mu_{k}$ and $\mu^{\prime}_{k}$ be two different values of the regularization parameter, and they are close to each other. Suppose that the global minimizer of (1.2) with regularization parameter $\mu^{\prime}_{k}$ is $\bm{x}(\mu^{\prime}_{k})$ and is given to the user. Suppose further that the user would like to find the global minimizer of (1.2) with $\mu_{k}$. Then, it is conceivable that the global minimizer of the new problem is close to $\bm{x}(\mu^{\prime}_{k})$.Given the sometimes complex geometry of non-convex problems, this might not always be the case. Hence, the user can initialize AMP.A with $\bm{x}(\mu^{\prime}_{k})$ and hope that the algorithm may converge to the global minimizer of (1.2) for $\mu_{k}$.

A more general version of the continuation idea we discussed above is to let $\mu_{k}$ change at every iteration (denoted as $\mu^{t}_{k}$), and set $\lambda_{t}$ according to $\mu^{t}_{k}$:

Below we informally discuss some of the results we will prove in this paper.

We would like to make the following remarks about these two results:

As is clear from our second informal result, when $\delta<1+\frac{4}{\pi^{2}}$, $\rm AMP.A$ cannot converge to $\bm{x}_{*}$. This value of $\delta$ is different from the information theoretic lower bound $\delta=1$. This discrepancy is in fact due to the type of continuation we used in this paper. Note that this issue does not happen in the complex-valued $\rm AMP.A$. The search for a better continuation strategy for the real-valued $\rm AMP.A$ is left as future research.

Simulation results presented in our forthcoming paper show that for real-valued signals, AMP.A with $\mu_{k}=0$ can only recover when $\delta>2.5$. As mentioned in our second informal result, continuation has improved the threshold of correct recovery to $\delta\approx 1.5$.

Now let us discuss the performance of AMP.A under noisy settings. We assume that the measurement noise is Gaussian and small. Clearly, in this setting exact recovery is impossible, hence we study the asymptotic mean square error defined as the following almost sure limit ($\theta_{t}\overset{\scriptscriptstyle\Delta}{=}\angle\frac{1}{n}\langle\bm{x}_{*},\bm{x}^{t}\rangle$)

3 Related work

Early theoretical results on phase retrieval, such as PhaseLift and PhaseCut , are based on semidefinite relaxations. For random Gaussian measurements, a variant of PhaseLift can recover the signal exactly (up to global phase) in the noiseless setting using $O(n)$ measurements . However, PhaseLift (or PhaseCut) involves solving a semidefinite programming (SDP) and is computationally prohibitive for large-scale applications. A different convex optimization approach for phase retrieval, which has the same $O(n)$ sample complexity, was independently proposed in and . This method is formulated in the natural signal space and does not involve lifting, and is therefore computationally more attractive than SDP-based counterparts. However, both methods require an anchor vector that has non-zero correlation with the true signal, and the quality of the recovery highly depends on the quality of the anchor.

Apart from convex relaxation approaches, non-convex optimization approaches attract considerable recent interests. These algorithms typically consist of a carefully designed initialization step (usually accomplished via a spectral method ) followed by iterations that refine the estimate. An early work in this direction is the alternating minimization algorithm proposed in , which has sub-optimal sample complexity. Another line of work includes the Wirtinger flow algorithm , truncated Wirtinger flow algorithm , and other variants. Other approaches include Kaczmarz method , trust region method , coordinate decent , prox-linear algorithm and Polyak subgradient method .

All the above theoretical results guarantee successful recovery with $m=\delta n$ measurements (or more) where $\delta$ is a fixed often large constant. However, such theories are not capable of providing fair comparison among different algorithms. To resolve this issue researchers have started studying the performance of different algorithms under the asymptotic setting $m/n\to\delta$ and $n\to\infty$. An interesting iterative projection method was proposed in, whose dynamics can be characterized exactly under this asymptotic setting. However, does not analyze the number of measurements required for this algorithm to work. The work in provides sharp characterization of the spectral initialization step (which is a key ingredient to many of the above algorithms). The analysis in reveals a phase transition phenomenon: spectral method produces an estimate not orthogonal to the signal if and only if $\delta$ is larger than a threshold (called “weak threshold” in ). Later, derived the information-theoretically optimal weak threshold (which is $0.5$ for the real-valued model and $1$ for the complex-valued model) and proved that the optimal weak threshold can be achieved by an optimally-tuned spectral method. Using the non-rigorous replica method from statistical physics, analyzes the exact threshold of $\delta$ (for the real-value setting) above which the PhaseMax method in and achieves perfect recovery. The analysis in shows that the performance of PhaseMax highly depends on initialization (see Fig. 1 of ), and the required $\delta$ is lower bounded by $2$ for real-valued models. The analysis in was later rigorously proved in via the Gaussian min-max framework , and a new algorithm called PhaseLamp was proposed. The PhaseLamp method has superior recovery performance over PhaseMax, but again it does not work when $\delta<2$ for real-valued models. A recent paper extends the asymptotic analysis of to the complex-valued setting, and it was shown that PhaseMax cannot work for $\delta<4$. On the other hand, AMP.A proposed in this paper achieves perfect recovery when $\delta>1.5$ and $\delta>2.5$, for the real and complex-valued models respectively. Further, focus on the noiseless scenario, while in this paper we also analyze the noise sensitivity of AMP.A. Finally, a recent paper derived an upper bound of $\delta$ such that PhaseLift achieves perfect recovery. The exact value of this upper bound can be derived by solving a three-variable convex optimization problem and empirically shows that $\delta\approx 3$ for real-valued models.

3.2 Existing work based on AMP

Our work in this paper is based on the approximate message passing (AMP) framework , in particular the generalized approximate message passing (GAMP) algorithm developed and analyzed in . A key property of AMP (including GAMP) is that its asymptotic behavior can be characterized exactly via the state evolution platform .

For phase retrieval, a Bayesian GAMP algorithm has been proposed in . However, did not provide rigorous performance analysis, partly due to the heuristic treatments used in the algorithm (such as damping and restart). Another work related to ours is the recent paper (appeared on Arxiv while we are preparing this paper), which analyzed the phase transitions of the Bayesian GAMP algorithms for a class of nonlinear acquisition models. For the phase retrieval problem, a phase transition diagram was shown in [43, Fig. 1] under a Bernoulli-Gaussian signal prior. The numerical results in indeed achieve state-of-the-art reconstruction results for real-valued models. However, did not provide the analysis of their results and in particular did not mention how they handle a difficulty related to initialization. Further, the algorithm in is based on the Bayesian framework which assumes that the signal and the measurements are generated according to some known distributions. Contrary to and , this paper considers a version of GAMP derived from solving the popular optimization problem (1.2). We provide rigorous performance analysis of our algorithm for both real and complex-valued models. Note that the advantages and disadvantages of Bayesian and optimization-based techniques have been a long debate in the field of Statistics. Hence, we do not repeat those debates here. Given our experience in the fields of compressed sensing and phase retrieval, it seems that the performance of Bayesian algorithms are more sensitive to their assumptions than the optimization-based schemes. Furthermore, performance analyses of Bayesian algorithms are often very challenging under “non-ideal” situations which the algorithms are not designed for.

Here, we emphasize another advantage of our approach. Given the fact that the most popular schemes in practice are iterative algorithms derived for solving non-convex optimization problems, the detailed analyses of $\rm AMP.A$ presented in our paper may also shed light on the performance of these algorithms and suggest new ideas to improve their performances.

3.3 Fundamental limits

It the literature of phase retrieval, it is well known that to make the signal-to-observation mapping injective one needs at least $m=4n$ measurements (or $m=2n$ in the case of real-valued models). On the other hand, the measurement thresholds obtained in this paper are $\delta=\frac{64}{\pi^{2}}-4\approx 2.5$ and $\delta=\frac{\pi^{2}}{4}-1\approx 1.5$ respectively. In fact, our algorithm can in principal recover the signal when $\delta>2$ and $\delta>1+\frac{4}{\pi^{2}}$ (or $\delta>1$ if continuation is not applied) for complex and real-valued models, provided that the algorithm is initialized close enough to the signal (though no known initialization strategy can accomplish this goal). Hence, our threshold are even smaller than the injectivity bounds. We emphasize that this is possible since the injectivity bounds derived in are defined for all $\bm{x}_{*}$ (which can depend on $\bm{A}$ in the worst case scenario). This is different from our assumption that $\bm{x}_{*}$ is independent of $\bm{A}$, which is more relevant in applications where one has some freedom to randomize the sampling mechanism. In fact, several papers have observed that their algorithm can operate at the injectivity thresholds $\delta=2$ for real-valued models . These two different notions of thresholds were discussed in . In the context of phase retrieval, the reader is referred to the recent paper , which showed that by solving a compression-based optimization problem, the required number of observations for recovery is essentially the information dimension of the signal (see for the precise definition). For instance, if the signal is $k$-sparse and complex-valued, then $2k$ measurements suffice.

4 Organization of the paper

The structure of the rest of the paper is as follows: Section 2 mentions the asymptotic framework of the paper, and summarizes our main results on the asymptotic analysis of $\rm AMP.A$. Section 3 discusses the real-valued $\rm AMP.A$ algorithm and its analysis. Section 4 presents the proofs of our main results.

Asymptotic analysis of AMP.Aformulae-sequenceAMPA\rm AMP.A

In this section, we present the asymptotic platform under which $\rm AMP.A$ is studied, and we derive a set of equations, known as state evolution (SE), that capture the performance of $\rm AMP.A$ under the asymptotic analysis.

Our analysis of $\rm AMP.A$ is carried out based on a standard asymptotic framework developed in . In this framework, we let $m,n\rightarrow\infty$, while $m/n\rightarrow\delta$. Within this section, we will write $\bm{x}_{*}$, $\bm{x}^{t}$, $\bm{w}$ and $\bm{A}$ as $\bm{x}_{*}(n)$, $\bm{x}^{t}(n)$, $\bm{w}(n)$ and $\bm{A}(n)$ to make explicit their dependency on the signal dimension $n$. In this section we focus on the complex-valued AMP. We postpone the discussion of the real-valued AMP until Section 3. Following , we introduce the following definition of converging sequences.

The sequence of instances $\{\bm{x}_{*}(n),\bm{A}(n),\bm{w}(n)\}$ is said to be a converging sequence if the following hold:

$\frac{m}{n}\to\delta\in(0,\infty)$, as $n\to\infty$.

$\bm{A}(n)$ has i.i.d. Gaussian entries where $A_{ij}\sim\mathcal{CN}(0,1/m)$.

Under the asymptotic framework introduced above, the behavior of $\rm AMP.A$ can be characterized exactly. Roughly speaking, the estimate produced by $\rm AMP.A$ in each iteration is approximately distributed as the (scaled) true signal $+$ additive Gaussian noise; in other words, ${\bm{x}}^{t}$ can be modeled as $\alpha_{t}\bm{x}_{*}+\sigma_{t}\bm{h}$, where $\bm{h}$ behaves like an iid standard complex normal noise. We will clarify this claim in Theorem 1 below. The scaling constant $\alpha_{t}$ and the noise standard deviation $\sigma_{t}$ evolve according to a known deterministic rule, called the state evolution (SE), defined below.

In the above equations, the expectations are over all random variables involved: $Z\sim\mathcal{CN}(0,1/\delta)$, $P=\alpha Z+\sigma B$ where $B\sim\mathcal{CN}(0,1/\delta)$ is independent of $Z$, and $Y=|Z|+W$ where $W\sim\mathcal{CN}(0,\sigma^{2}_{w})$ is independent of both $Z$ and $B$. Further, the partial Wirtinger derivative $\partial_{z}g(p,|z|+w)$ is defined as:

The functions $\psi_{1}$ and $\psi_{2}$ are well defined except when both $\alpha$ and $\sigma^{2}$ are zero.

Most of the analysis in this paper is concerned with the noiseless case. For brevity, we will often write $\psi_{2}(\alpha,\sigma;\delta,0)$ (where $\sigma^{2}_{w}=0$) as $\psi_{2}(\alpha,\sigma;\delta)$. Further, when our focus is on $\alpha$ and $\sigma^{2}$ rather than $\delta$, we will simply write $\psi_{2}(\alpha,\sigma^{2};\delta)$ as $\psi_{2}(\alpha,\sigma^{2})$.

In Appendix B.2, we simplify the functions $\psi_{1}(\cdot)$ and $\psi_{2}(\cdot)$ into the following expressions (with $\theta_{\alpha}$ being the phase of $\alpha$):

The above expressions for $\psi_{1}$ and $\psi_{2}$ are more convenient for our analysis.

The state evolution framework for generalized AMP (GAMP) algorithms was first introduced and analyzed in and later formally proved in . As we will show later in Theorem 1, SE characterizes the macroscopic behavior of $\rm AMP.A$. To apply the results in to AMP.A, however, we need two generalizations. First, we need to extend the results in to complex-valued models. This is straightforward by applying a complex-valued version of the conditioning lemma introduced in . Second, existing results in require the function $g$ to be smooth. Our simulation results in case of complex-valued $\rm AMP.A$ show that SE predicts the performance of $\rm AMP.A$ despite the fact that $g$ is not smooth. Since our paper is long, we postpone the proof of this claim to another paper. Instead we use the smoothing idea discussed in to connect the SE equations presented in (2.1) with the iterations of $\rm AMP.A$ in (1.6). Let $\epsilon>0$ be a small fixed number. Consider the following smoothed version of $\rm AMP.A$:

Note that as $\epsilon\rightarrow 0$, $g_{t,\epsilon}\rightarrow g_{t}$ and hence we expect the iterations of smoothed-$\rm AMP.A$ converge to the iterations of $\rm AMP.A$.

Let $\{\bm{x}_{*}(n),\bm{A}(n),\bm{w}(n)\}$ be a converging sequence of instances. For each instance, let $\bm{x}^{0}(n)$ be an initial estimate independent of $\bm{A}(n)$. Assume that the following hold almost surely

Let $\bm{x}_{\epsilon}^{t}(n)$ be the estimate produced by the smoothed $\rm AMP.A$ initialized by $\bm{x}^{0}(n)$ (which is independent of $\bm{A}(n)$) and $\bm{p}^{-1}(n)=\mathbf{0}$. Let $\epsilon_{1},\epsilon_{2},\ldots$ denote a sequence of smoothing parameters for which $\epsilon_{i}\rightarrow 0$ as $i\rightarrow\infty$ Then, for any iteration $t\geq 1$, the following holds almost surely

where $\theta_{t}=\angle\alpha_{t}$, $X^{t}=\alpha_{t}X_{*}+\sigma_{t}H$ and $X_{*}\sim p_{X}$ is independent of $H\sim\mathcal{CN}(0,1)$. Further, $\{\alpha\}_{t\geq 1}$ and $\{\sigma_{t}^{2}\}_{t\geq 1}$ are determined by (2.1) with initialization $\alpha_{0}$ and $\sigma_{0}^{2}$.

The proof of Theorem 1 is given in Section 4.2.

2 Convergence of the SE for noiseless model

We now analyze the dynamical behavior of the SE. Before we proceed, we point out that in phase retrieval, one can only hope to recover the signal up to global phase ambiguity , for generic signals without any structure. In light of (2.5), AMP.A is successful if $|\alpha_{t}|\to 1$ and $\sigma_{0}^{2}\to 0$ as $t\to\infty$.

Let us start with the following interesting feature of the state evolution, which can be seen from (2.2).

$\psi_{2}(\alpha,\sigma^{2})=\psi_{2}(|\alpha|,\sigma^{2})$.

Hence, if $\theta_{t}$ denotes the phase of $\alpha_{t}$, then $\theta_{t}=\theta_{0}$.

In light of this lemma, we can focus on real and nonnegative values of $\alpha_{t}$. In particular, we assume that $\alpha_{0}\geq 0$ and we are interested in whether and under what conditions can the SE converge to the fixed point $(\alpha,\sigma^{2})=(1,0)$. The following two values of $\delta$ will play critical roles in the analysis of SE:

Notice that $\alpha_{0}\neq 0$ is essential for the success of AMP.A. This can be seen from the fact that $\alpha=0$ is always a fixed point of $\psi_{1}(\alpha,\sigma^{2})$ for any $\sigma^{2}>0$. From our definition of $\alpha_{0}$ in Theorem 1, $\alpha_{0}=0$ is equivalent to $\frac{1}{n}\langle\bm{x}_{*},\bm{x}^{0}\rangle=0$. This means that the initial estimate $\bm{x}^{0}$ cannot be orthogonal to the true signal vector $\bm{x}_{*}$, otherwise there is no hope to recover the signal no matter how large $\delta$ is.

3 Noise sensitivity

So far we have only discussed the performance of $\rm AMP.A$ in the ideal setting where the noise is not present in the measurements. In general, one can use (2.1) to calculate the asymptotic MSE (AMSE) of $\rm AMP.A$ as a function of the variance of the noise and $\delta$. However, as our next theorem demonstrates it is possible to obtain an explicit and informative expression for AMSE of $\rm AMP.A$ in the high signal-to-noise ratio (SNR) regime.

The proof of this theorem can be found in Appendix E.

Extension to real-valued signals

Until now our focus is on complex-valued signals. In this section, our goal is to extend our results to real-valued signals. Since most of the results are similar to the complex-valued case, we will skip the details and only emphasize on the main differences.

In the real-valued case, $\rm AMP.A$ uses the following iterations:

2 Asymptotic Analysis

Our analysis is based on the same asymptotic framework detailed in Section 2.2. The only difference is that the measurement matrix is now real Gaussian with $A_{ij}\sim\mathcal{N}(0,1/m)$ and $w_{a}\sim\mathcal{N}(0,\sigma^{2}_{w})$. In the real-valued setting, the state evolution (SE) recursion of $\rm AMP.A$ in (3.1) becomes the following.

The expectations are over the following random variables: $Z\sim\mathcal{N}(0,1/\delta)$, $P=\alpha Z+\sigma B$ where $B\sim\mathcal{N}(0,1/\delta)$ is independent of $Z$, and $Y=|Z|+W$ where $W\sim\mathcal{N}(0,\sigma^{2}_{w})$ independent of both $Z$ and $B$.

In Appendix B.3, we derived the following closed-form expressions of $\psi_{1}$ and $\psi_{2}$:

As in the complex-valued case, we would like to study the dynamics of these two equations. The following lemma simplifies the analysis.

$\psi_{1}\left(\alpha,\sigma^{2}\right)$ and $\psi_{2}(\alpha,\sigma^{2})$ in (3.3) and (3.3b) have the following properties:

$\psi_{1}(\alpha,\sigma^{2})=\psi_{1}(|\alpha|,\sigma^{2})\cdot{\rm sign}(\alpha)$.

$\psi_{2}(\alpha,\sigma^{2})=\psi_{2}(|\alpha|,\sigma^{2})$.

Again the following two values of $\delta$ play a critical role in the performance of AMP:

The following two theorems correspond to Theorems 2 and 3 that explain the dynamics of SE for complex-valued signals. The proofs can be found in Section D.1 and Section D.2 respectively.

Note that in Theorem 5 the sequences converge for any $\sigma^{2}_{0}<\infty$. This result is stronger than the complex-valued counterpart, which requires $0<|\alpha_{0}|\leq 1$ and $\sigma^{2}_{0}\leq 1$ (see Theorem 2).

Finally, we discuss the performance of $\rm AMP.A$ in the high SNR regime. See Section E for its proof.

Proofs of our main results

The functions that we have in (2.1) are related to the first and second kinds of elliptic integrals. Below we review some of the properties of these functions that will be used throughout our paper. Elliptic integrals (elliptic integral of the second kind) were originally proposed for the study of the arc length of ellipsoids. Since their appearance, elliptic integrals have appeared in many problems in physics and chemistry, such as characterization of planetary orbits. Three types of elliptic integrals are of particular importance, since a large class of elliptic integrals can be reduced to these three. We introduce two of them that are of particular interest in our work.

The first and second kinds of complete elliptic integrals, denoted by $K(m)$ and $E(m)$ (for $-\infty<m<1$) respectively, are defined as

In the above definitions, we continued to use $m$, to follow the convention in the literature of elliptic integrals. Previously, $m$ was defined to be the number of measurements, but such abuse of notation should not cause confusion as the exact meaning of $m$ is usually clear from the context.

Below, we list some properties of elliptic integrals that will be used in this paper. The proofs of these properties can be found in standard references for elliptic integrals and thus omitted (e.g., ).

The following hold for $K(m)$ and $E(m)$ defined in (4.1):

$K(0)=E(0)=\frac{\pi}{2}$. Further, for $\epsilon\to 0$, $E(1-\epsilon)$ and $K(1-\epsilon)$ behave as

On $m\in(0,1)$, $K(m)$ is strictly increasing, $E(m)$ is strictly decreasing, and $T(m)$ is strictly increasing.

The derivatives of $K(m)$, $E(m)$ and $T(m)$ are given by (for $m<1$)

Furthermore, we will use a few more elliptic integrals in our work. Next lemma and its proof connects these elliptic integrals to Type I and Type II elliptic integrals.

The following equalities hold for any $m\geq 0$:

We will only prove (4.4b). (4.4a) can be proved in the same way. The idea is to express the integrals using elliptic integrals defined in (4.1), and then apply known properties of elliptic integrals (Lemma 3) to simplify the results. The same tricks in proving (4.4b) are used to derive other related integrals in this paper. Below, we will provide the full details for the proof of (4.4b), and will not repeat such calculations elsewhere. The LHS of (4.4b) can be rewritten as:

The equality in (4.5) can be proved by combining the following identities together with straightfroward manipulations:

where $K(m)$ and $E(m)$ denote the complete elliptic integrals of the first and second kinds (see (4.1)). First, consider the identity (i) in (4.6):

where (a) is from the definition of $K(m)$ and $E(m)$ in (4.1), and (b) is from Lemma 3 (iii).

where (a) is due to Lemma 3 (iv) and (b) is from Lemma 3 (iii).

where step (a) follows from the third step of (4.7), and step (b) follows from Lemma 3 (iii).

Identity (iv) can be proved in a similar way:

where (a) is from the third step of (4.8), step (b) is from Lemma 3 (iv) and (c) is from Lemma 3 (iii).

Lastly, identity (v) can be proved as follows:

where step (a) follows from the derivations of the previous two identities and (b) is again due to Lemma 3 (iii). ∎

2 Proof of Theorem 1

Since the proof of the real-valued and complex valued signals look similar, for the sake of notational simplicity we present the proof for the real-valued signals. First note that according to [19, Lemma 13]The proof for a more general result was first presented in . However, we found easier to follow. The reader may also find [26, Claim 1] and related discussions useful, although no formal proof was provided. for the smoothed $\rm AMP.A$ algorithm we know that almost surely

where $X_{\epsilon}^{t}=\alpha_{\epsilon,t}X_{*}+\sigma_{\epsilon,t}H$ and $X_{*}\sim p_{X}$ is independent of $H\sim\mathcal{N}(0,1)$, and $\alpha_{\epsilon,t}$ and $\sigma_{\epsilon,t}$ satisfy the following iterations:

where $Y=|Z|+W$, $P^{t}=\alpha_{\epsilon,t}Z+\sigma_{\epsilon,t}B$, where $B\sim\mathcal{N}(0,1/\delta)$ is independent of $Z\sim\mathcal{N}(0,1/\delta)$ and $W\sim\mathcal{N}(0,1/\delta)$. It is also straightforward to use an induction step similar to the one presented in the proof of Theorem 1 of and show that $(\alpha_{\epsilon,t},\sigma^{2}_{\epsilon,t})\rightarrow(\alpha_{t},\sigma^{2}_{t})$ as $i\rightarrow\infty$, where $(\alpha_{t},\sigma^{2}_{t})$ satisfy

3 Proof of Theorem 2

The goal of this section is to prove Theorem 2. However, since the proof is very long we start with the proof sketch to help the reader navigate through the complete proof.

Our main goal is to study the dynamics of the iterations:

Notice that according to the assumptions of the theorem, we assume that we initialized the dynamical system with $\alpha_{0}>0$. Our first hope is that this dynamical system will not oscillate and will converge to the solutions of the following system of nonlinear equations:

Hence, the first step is to characterize and understand the fixed points of the solutions of (4.10). Toward this goal we should study the properties of $\psi_{1}(\alpha,\sigma^{2})$ and $\psi_{2}(\alpha,\sigma^{2};\delta)$. In particular, we would like to know how the fixed points of $\psi_{1}(\alpha,\sigma^{2})$ behave for a given $\sigma^{2}$ and how the fixed points of $\psi_{2}(\alpha,\sigma^{2};\delta)$ behave for a given value of $\alpha$ and $\delta$. The graphs of these functions are shown in Figure 2.

We list some of the important properties of these two functions. We refer the reader to Section 4.3.2 to see more accurate statement of these claims.

$\psi_{1}\left(\alpha,\sigma^{2}\right)$ is a concave and strictly increasing function of $\alpha>0$, for any $\sigma^{2}>0$: This implies that $\psi_{1}\left(\alpha,\sigma^{2}\right)$ can have two fixed points: one at zero and one at $\alpha>0$. Also, as is clear from the figure, the second fixed point is the stable one.

For the moment assume that the unstable fixed points do not affect the dynamics of $\rm AMP.A$. Let $F_{1}(\sigma^{2})$ denote the non-zero fixed point of $\psi_{1}$ and $F_{2}(\sigma^{2})$ the stable fixed point of $\psi_{2}$.In the literature of dynamical systems, these functions are sometimes called nullclines. Nullclines are useful for qualitatively analyzing local dynamical behavior of two-dimensional maps (which is the case for the SE in this paper). We will prove in Lemma 11 that $F_{1}(\sigma^{2})$ is a decreasing function and hence $F_{1}^{-1}(\alpha)$ is well-defined on $0<\alpha\leq 1$. Moreover, we will show that by choosing $F_{1}^{-1}(0)=\frac{\pi^{2}}{16}$, $F_{1}^{-1}(\alpha)$ is continuous on . $F_{1}^{-1}(\alpha)$ and $F_{2}(\alpha;\delta)$ are shown in Fig. 3. Note that the places these curves intersect correspond to the fixed points of (4.10). Depending on the value of $\delta$ the two curves show the following different behaviors:

You may find the proof of this lemma in Section 4.3.4. Intuitively speaking, in this case we expect the state evolution to converge to the fixed point $(\alpha,\sigma^{2})=(1,0)$, meaning that AMP.A achieves exact recovery.

So far, we have studied the solutions of (4.10). But the ultimate goal of analysis of $\rm AMP.A$ is the analysis of (4.9). In particular, it is important to show that the estimates $(\alpha_{t},\sigma_{t}^{2})$ converge to $(1,0)$ and do not oscillate. Unfortunately, the dynamics of $(\alpha_{t},\sigma_{t}^{2})$ do not monotonically move toward the fixed point $(1,0)$, which makes the analysis of SE complicated.

where $\sigma^{2}_{\max}\overset{\scriptscriptstyle\Delta}{=}\max\left\{1,\frac{4}{\delta}\right\}$.

From the above lemma, we see that to understand the dynamics of the SE, we only focus on the region \mathcal{R}\overset{\scriptscriptstyle\Delta}{=}\left\{(\alpha,\sigma^{2})\big{|}0<\alpha\leq 1,0<\sigma^{2}\leq\sigma^{2}_{\max}\right\}. Since the dynamic of $\rm AMP.A$ is complicated, we divide this region into smaller regions. See Figure 4 for an illustration.

We divide \mathcal{R}\overset{\scriptscriptstyle\Delta}{=}\left\{(\alpha,\sigma^{2})\big{|}0<\alpha\leq 1,0<\sigma^{2}\leq\sigma^{2}_{\max}\right\} into the following three sub-regions:

Our next lemma shows that if $(\alpha_{t},\sigma_{t}^{2})$ is in $\mathcal{R}_{1}$ or $\mathcal{R}_{2}$ for $t\geq 1$, then $(\alpha_{t},\sigma_{t}^{2})$ converges to $(1,0)$. The following lemma demonstrates this claim.

$(\alpha_{t},\sigma^{2}_{t})$ remains in $\mathcal{R}_{1}\cup\mathcal{R}_{2}$ for all $t>t_{0}$;

This claim will be proved in Section 4.3.5. Notice that the condition $t_{0}\geq 1$ is important for part (i) to hold: if $(\alpha_{0},\sigma^{2}_{0})$ is close to the origin (and thus in $\mathcal{R}_{2}$), then $(\alpha_{1},\sigma^{2}_{1})$ can move to $\mathcal{R}_{0}$. However, this cannot happen when $t\geq 1$. In the proof given in Section 4.3.5, we showed that for any $(\alpha_{0},\sigma^{2}_{0})\in\mathcal{R}$ the possible locations of $(\alpha_{1},\sigma^{2}_{1})$ are bounded from below by a curve, and once $(\alpha,\sigma^{2})$ is above this curve and also in region $\mathcal{R}_{1}$ or $\mathcal{R}_{2}$, then we will prove that it cannot go to $\mathcal{R}_{0}$. Finally, we will prove the following Lemma that completes the proof.

The proof of this result is in Section 4.3.6. Combining the above two lemmas, it is straightforward to see that $(\alpha_{t},\sigma_{t}^{2})\rightarrow(1,0)$, and hence the proof is complete.

In this section we derive all the main properties of $\psi_{1}$ and $\psi_{2}$ that are used throughout the paper.

$\psi_{1}\left(\alpha,\sigma^{2}\right)$ has the following properties (for $\alpha\geq 0$):

$\psi_{1}\left(\alpha,\sigma^{2}\right)$ is a concave and strictly increasing function of $\alpha>0$, for any given $\sigma^{2}>0$.

$0<\psi_{1}(\alpha,\sigma^{2})\leq 1$, for $\alpha>0$ and $\sigma^{2}>0$.

If $0<\sigma^{2}<\pi^{2}/16$, then there are two nonnegative solutions to $\alpha=\psi_{1}(\alpha,\sigma^{2})$: $\alpha=0$ and $\alpha=F_{1}(\sigma^{2})>0$. Further, $F_{1}(\sigma^{2})$ is strongly globally attracting, meaning that

On the other hand, if $\sigma^{2}\geq\pi^{2}/16$ then $\alpha=0$ is the unique nonnegative fixed point and it is strongly globally attracting.

Part (i): From (2.2), it is easy to verify that $\psi_{1}(\alpha,\sigma^{2})$ is an increasing function of $\alpha>0$. We now prove its concavity. To this end, we calculate its first and second partial derivatives:

Hence, $\psi_{2}(\alpha,\sigma^{2})$ is a concave function of $\alpha$ for $\alpha>0$.

Part (ii): Positivity of $\psi_{1}$ is obvious. Also, note that

Proof of (iii): The claim is a consequence of the concavity of $\psi_{1}$ (with respect to $\alpha$) and the following condition:

The detailed proof is as follows. First, it is straightforward to verify that $\alpha=0$ is always a solution to $\alpha=\psi_{1}(\alpha,\sigma^{2})$. Define

Since $\Psi_{1}(\alpha,\sigma^{2})$ is a concave function of $\alpha$ (as $\psi_{1}(\alpha,\sigma^{2})$ is concave), $\frac{\partial\Psi_{1}(\alpha,\sigma^{2})}{\partial\alpha}$ is decreasing. Let’s first consider $\sigma^{2}>\pi^{2}/16$. In this case we know that

where the second equality can be calculated from (4.13a). Since $\Psi_{1}(\alpha,\sigma^{2})$ is a decreasing function of $\alpha$ and is equal to zero at zero, and it does not have any other solution. Now, consider case $\sigma^{2}<\pi^{2}/16$. It is straightforward to confirm that

Furthermore, from (4.13a) we have \frac{\partial\psi_{1}(\alpha,\sigma^{2})}{\partial\alpha}\Big{|}_{\alpha\to\infty}=0, and so

Hence, $\Psi_{1}(\alpha,\sigma^{2})=0$ has exactly one more solution for $\alpha>0$. Note that since from part (ii) $\psi_{1}(\alpha,\sigma^{2})<1$, the solution of $\alpha=\psi_{1}(\alpha,\sigma^{2})$ also satisfies $\alpha\leq 1$.

Finally, the strong global attractiveness follows from the fact that $\psi_{1}$ is a strictly increasing function of $\alpha$.

$\psi_{2}\left(\alpha,\sigma^{2};\delta\right)$ has the following properties:

If $\delta<2$, then $\sigma^{2}=0$ is a locally unstable fixed point to $\sigma^{2}=\psi_{2}\left(\alpha,\sigma^{2};\delta\right)$, meaning that

For any $\delta>2$, $\sigma^{2}=\psi_{2}\left(\alpha,\sigma^{2};\delta\right)$ has a unique fixed point in $\sigma^{2}\in$ for any $\alpha\in$. Further, the fixed point is (weakly) globally attracting in $\sigma^{2}\in$:

where $\sigma^{2}_{\max}\overset{\scriptscriptstyle\Delta}{=}\max\{1,4/\delta\}$.

For any $\delta>0$, $\psi_{2}(\alpha,\sigma^{2};\delta)$ is an increasing function of $\sigma^{2}>0$ if

where $s_{\ast}^{2}$ is the unique solution to

First note that the partial derivative of $\psi_{2}$ w.r.t. $\sigma^{2}$ is given by

Part (i): Before we proceed, we first comment on the discontinuity of the partial derivative $\frac{\partial\psi_{2}(\alpha,\sigma^{2};\delta)}{\partial\sigma^{2}}$ at $\sigma^{2}=0$. Note that the formula in (4.18) was derived for non-zero values of $\sigma^{2}$. Naively, one may plug in $\sigma^{2}=0$ in the equation and assume that \frac{\partial\psi_{2}(\alpha,\sigma^{2};\delta)}{\partial\sigma^{2}}\Big{|}_{\alpha=1,\sigma^{2}=0}=\frac{4}{\delta}. This is not the case since the integral $\int_{0}^{\pi/2}\frac{d\theta}{\sin\theta}$ is divergent. It turns out that the derivative $\frac{\partial\psi_{2}(\alpha,\sigma^{2};\delta)}{\partial\sigma^{2}}$ is a continuous function of $\sigma^{2}$. The technical details can be found in Appendix C.

Since $\frac{\partial\psi_{2}(\alpha,\sigma^{2};\delta)}{\partial\sigma^{2}}$ is continuous at $\sigma^{2}=0$, we have

Note that if we set $m=1/\sigma^{2}$, then from (4.6) we have

It is then straightforward to use Lemma 3 to prove that

Hence, \frac{\partial\psi_{2}(\alpha,\sigma^{2};\delta)}{\partial\sigma^{2}}\Big{|}_{\alpha=1,\sigma^{2}=0}>1 for $\delta<2$.

Part (ii): We first prove that the following equation has at least one solution for any $\alpha\in$ and $\delta>2$:

We next prove our claim by proving the following:

We next show that $g(\alpha^{2})$ in (4.21) is a concave function of $\alpha^{2}$, and hence the minimum can only happen at either $\alpha=0$ or $\alpha=1$. The first two derivatives w.r.t. $\alpha^{2}$ are given by:

The concavity of $g(\alpha^{2})$ implies that its minimum happens at either $\alpha=0$ or $\alpha=1$. Hence, to prove (4.21), it suffices to prove that

which holds for $\delta>2$. Hence, (4.21) holds. By combining (4.19) and (4.20) we conclude that $\psi_{2}(\alpha,\sigma^{2};\delta)$ has at least one fixed point between $\sigma^{2}=0$ and $\sigma^{2}=1$. The next step is to prove the uniqueness of this fixed point. For the rest of the proof, we discuss two cases separately: a) $\delta>4$ and b) $2<\delta\leq 4$.

From (4.18), if $\delta>4$, then $\frac{\partial\psi_{2}(\alpha,\sigma^{2};\delta)}{\partial\sigma^{2}}<1$, $\forall\sigma^{2}>0$. This means that $\Psi_{2}(\alpha,\sigma^{2};\delta)$ defined in (4.22) is monotonically decreasing in $\sigma^{2}>0$. Hence, the solution to $\Psi_{2}(\alpha,\sigma^{2};\delta)=0$ is unique. Furthermore, the following property is a direct consequence of the monotonicity of $\Psi_{2}(\alpha,\sigma^{2};\delta)$:

where $F_{2}(\alpha)$ denotes the solution to $\Psi_{2}(\alpha,\sigma^{2};\delta)=0$.

$2<\delta\leq 4$. In this case, we will prove that there exists a threshold on $\sigma^{2}$, denoted as $\sigma^{2}_{\star}(\alpha;\delta)$ below, such that the following hold:

This means that $\Psi_{2}(\alpha,\sigma^{2};\delta)=\psi_{2}(\alpha,\sigma^{2};\delta)-\sigma^{2}$ is strictly decreasing on $\sigma^{2}\in(0,\sigma^{2}_{\star}(\alpha;\delta))$ and increasing on $\sigma^{2}\in(\sigma^{2}_{\star}(\alpha;\delta),\infty)$. Note that since we have proved that $\Psi_{2}(\alpha,\sigma^{2};\delta)=0$ has at least one solution, we conclude that there exist exactly two solutions to $\Psi_{2}(\alpha,\sigma^{2};\delta)=0$, one in $(0,\sigma^{2}_{\star}(\alpha;\delta))$ and the second in $(\sigma^{2}_{\star}(\alpha;\delta),\infty)$, if $\Psi_{2}(\alpha,\sigma^{2};\delta)|_{\sigma^{2}=\sigma^{2}_{\star}(\alpha;\delta)}<0$. This is the case since $\Psi_{2}(\alpha,\sigma^{2};\delta)|_{\sigma^{2}=1}<0$ (see (4.20)), and that $\Psi_{2}(\alpha,\sigma^{2};\delta)|_{\sigma^{2}=1}<\Psi_{2}(\alpha,\sigma^{2};\delta)|_{\sigma^{2}=\sigma^{2}_{\star}(\alpha;\delta)}$ (since the latter is the global minimum of $\Psi_{2}(\alpha,\sigma^{2};\delta)$ in $\sigma^{2}\in(0,\infty)$).

Also, it is easy to prove (4.23). In fact, the following holds:

where $\hat{F}_{2}(\alpha;\delta)>1$ denotes the larger solution to $\Psi_{2}(\alpha,\sigma^{2};\delta)=0$. See Fig. 5 for an illustration.

From the above discussions, it remains to prove (4.24). To this end, it is more convenient to express (4.18) using elliptic integrals discussed in Section 4.1:

where we introduced a new variable $s\overset{\scriptscriptstyle\Delta}{=}\frac{\sigma}{\alpha}$ and the last step is derived using the identities in Lemma 4. Based on (4.25) we can now rewrite (4.24) as

To prove this, we first show that there exists $s^{*}$ such that $f(s)$ is strictly increasing on $(0,s_{\ast})$ and decreasing on $(s_{\ast},\infty)$, namely,

This can be seen from $f^{\prime}(s)$ derived below:

Further noting that $E(\cdot)$ is strictly decreasing in $(0,1)$ while $K(\cdot)$ is increasing, we proved (4.27).

Based on the above discussions, we can finally turn to the proof of (4.26). From (4.25b), it is straightforward to verify that $f(0)=\frac{1}{2}$. Therefore, when $\delta>2$, we have

Hence, the following equation admits a unique solution (denoted as $s_{\star}(\alpha;\delta)$ below):

See Fig. 6 for an illustration. Also, from our above discussions on the monotonicity of $f(s)$ it is straightforward to show that

which proves (4.26) by setting $\sigma_{\star}(\alpha;\delta)\overset{\scriptscriptstyle\Delta}{=}\alpha\cdot s_{\star}(\alpha;\delta)$. This proves (4.24), which completes the proof.

Part (iii): We will prove a stronger result: $\psi_{2}\leq 4/\delta$. From (2.2b), $\psi_{2}(\alpha,\sigma^{2};\delta)\leq 4/\delta$ is equivalent to

For $0\leq\alpha\leq 1$ and $\sigma^{2}\leq\sigma^{2}_{\max}$ we have

which, similar to (4.29), can be proved by

Part (iv): We bound the partial derivative of $\psi_{2}(\alpha,\sigma^{2};\delta)$ for $\sigma^{2}\in[0,\sigma^{2}_{\max}]$ as:

Hence, there exists a unique solution (which we denote as $F_{2}(\alpha)$) to the following equation:

Finally, the property in (4.16) is a direct consequence of the fact that $\Psi_{2}(\alpha,\sigma^{2};\delta)=\psi_{2}(\alpha,\sigma^{2};\delta)-\sigma^{2}$ is a decreasing function of $\sigma^{2}\leq\sigma^{2}_{\max}$.

Part (v): In (4.25), we have derived the following:

where $s\overset{\scriptscriptstyle\Delta}{=}\frac{\sigma}{\alpha}$. From (4.25b), we see that $\psi_{2}(\alpha,\sigma^{2};\delta)$ is an increasing function of $\sigma^{2}$ if the following holds:

Further, (4.27) implies that the maximum of $f(s)$ happens at $s_{*}$, i.e.,

where $s_{\ast}^{2}$ is the unique solution to

Clearly, $\alpha>\alpha_{\ast}$ immediately implies $\alpha>f(s)$, which further guarantees that $\psi_{2}(\alpha,\sigma^{2};\delta)$ is monotonically increasing on $\sigma^{2}>0$. Finally, the strong global attractiveness of $F_{2}(\alpha)$ is a direct consequence of part (iv) of this lemma together with the monotonicity of $\psi_{2}$. ∎

In this section we derive the main properties of the functions $F_{1}$ and $F_{2}$ introduced in Section 4.3.1. These properties play major roles in the results of the paper.

The following hold for $F_{1}(\sigma^{2})$ and $F_{2}(\alpha;\delta)$ (for $\delta>2$):

$F_{1}(0)=1$ and $\lim_{\sigma^{2}\rightarrow\frac{\pi^{2}}{16}^{-}}F_{1}(\sigma^{2})=0$. Further, by choosing $F_{1}(\frac{\pi^{2}}{16})=0$, we have $F_{1}(\sigma^{2})$ is continuous on $\left[0,\frac{\pi^{2}}{16}\right]$ and strictly decreasing in $\left(0,\frac{\pi^{2}}{16}\right)$;

$F_{2}$ is a continuous function of $\alpha\in$ and $\delta\in(2,\infty)$. $F_{2}(1;\delta)=0$, and $F_{2}(0;\delta)=\left(\frac{-\pi+\sqrt{\pi^{2}+4(\delta-4)}}{\delta-4}\right)^{2}$ for $\delta\neq 4$ and $F_{2}(0;4)=4/\pi^{2}$.

Part (i): We first verify $F_{1}(0)=1$ and $\lim_{\sigma^{2}\rightarrow\frac{\pi^{2}}{16}^{-}}F_{1}(\sigma^{2})=0$. First, $F_{1}(0)=1$ can be seen from the following facts: (a) $\psi_{1}(\alpha,0)=1$ for $\alpha>0$, see (2.2a); and (b) By definition, $F_{1}(0)$ is the non-zero solution to $\alpha=\psi_{1}(\alpha,0)$. Then, by Lemma 9 (iii) and continunity of $\psi_{1}$, we know $F_{1}$ is continuous on $[0,\frac{\pi^{2}}{16})$, and further $\lim_{\sigma^{2}\rightarrow\frac{\pi^{2}}{16}^{-}}F_{1}(\sigma^{2})=0$ since $\sigma^{2}=\frac{\pi^{2}}{16}$ corresponds to a case where the non-negative solution to $\psi_{1}(\alpha,\sigma^{2})=\alpha$ decreases to zero. Next, we prove the monotonicity of $F_{1}$. Note that

Differentiation w.r.t. $\sigma^{2}$ yields

where \partial_{2}\psi_{1}(F_{1}(\sigma^{2}),\sigma^{2})\overset{\scriptscriptstyle\Delta}{=}\frac{\partial\psi_{1}(\alpha,\sigma^{2})}{\partial\sigma^{2}}\Big{|}_{\alpha=F_{1}(\sigma^{2})} and \partial_{1}\psi_{1}(F_{1}(\sigma^{2}),\sigma^{2})\overset{\scriptscriptstyle\Delta}{=}\frac{\partial\psi_{1}(\alpha,\sigma^{2})}{\partial\alpha}\Big{|}_{\alpha=F_{1}(\sigma^{2})}. Hence,

We have proved in (4.14) that \frac{\partial\psi_{1}(\alpha,\sigma^{2})}{\partial\alpha}\Big{|}_{\alpha=0}<1 when $\sigma^{2}<\frac{\pi^{2}}{16}$. Together with the concavity of $\psi_{1}$ w.r.t. $\alpha$ (cf. Lemma 9 (i)), we have

Further, from (2.2a), it is straightforward to see that $\psi_{1}$ is a strictly decreasing function of $\sigma^{2}$, and thus

Substituting (4.34) and (4.35) into (4.33), we obtain

Proof of (ii): By Lemma 10 (ii) and continuity of $\psi_{2}$, it is straightforward to check that $F_{2}$ is continuous. Moreover, we have proved that $\sigma^{2}=F_{2}(\alpha;\delta)$ is the unique solution to the following equation (for $\delta>2$):

which has two possible solutions (for $\delta\neq 4$):

(For the special case $\delta=4$, $\sigma_{1}=2/\pi$.) However, $\sigma_{2}$ is invalid due to our constraint $0<\sigma^{2}<1$. This can be seen as follows. First, $\sigma_{2}<0$ for $\delta>4$ and hence invalid. When $2<\delta<4$, we have

Hence, $F_{2}(0;\delta)=\sigma_{1}$. When $\alpha=1$, (4.36) becomes:

It is straightforward to verify that $\sigma^{2}=0$ is a solution. Also, from Lemma 10 (ii), $\sigma^{2}=0$ is a also the unique solution. Hence, $F_{2}(1;\delta)=0$.

3.4 Proof of Lemma 5

In Lemma 10, we have proved that $F_{2}(\alpha;\delta)$ is the unique globally attracting fixed point of $\psi_{2}$ in $\sigma^{2}\in$ (for $\delta>2$), and from (4.15) we have

We now make some variable changes for (4.39). From (2.2a), $\psi_{1}$ in can be rewritten as the following for $\alpha>0$:

By definition, $F_{1}(\sigma^{2})$ is the solution to $\alpha=\psi_{1}(\alpha,\sigma^{2})$, and hence the following holds:

At this point, it is more convenient to make the following variable change:

where the first equality is from (4.40) and the second step from (4.41). Using the relationship in (4.42), we can reformulate the inequality in (4.39) into the following equivalent form:

Substituting (4.41) and (2.2b) into (4.43) and after some manipulations, we can finally write our objective as:

In the next two subsections, we prove (4.44) for $s^{2}>0.07$ and $s^{2}\leq 0.07$ using different techniques.

Using the variable $t$, we can rewrite (4.44) into the following:

Notice that if we could prove (4.46a) for $t<14.3$, we would have proved (4.44) for $s^{2}>0.07$, since $14.3>1/0.07\approx 14.28$. For the ease of later discussions, we define

The following identities related to $\{g_{1}(t),g_{2}(t),g_{3}(t),g_{4}(t)\}$ will be used in our proof:

We now prove (4.46a). First, it is straightforward to verify that equality holds for (4.46a) at $t=0$, i.e.,

Hence, to prove that $G(t)\geq\gamma$ for $t\in[0,14.3)$, it is sufficient to prove that $G(t)$ is an increasing function of $t$ on $t\in[0,14.3)$. To this end, we calculate the derivative of $G(t)$:

where step (a) follows from the identities listed in (4.47). Since $g_{3}(t)>0$, we have

It remains to prove that $G_{1}(t)+G_{2}(t)-2>0$ for $t<14.3$. Our numerical results suggest that $G_{1}(t)+G_{2}(t)$ is a monotonically decreasing function for $t>0$, and $G_{1}(t)+G_{2}(t)\to 2$ as $t\rightarrow\infty.$ However, directly proving the monotonicity of $G_{1}(t)+G_{2}(t)$ seems to be quite complicated. We use a different strategy here. We will prove that (at the end of this section)

As a consequence, the following hold true for any $c_{2}>c_{1}>0$:

Hence, if we verify that $G_{1}(c_{1})+G_{2}(c_{2})-2>0$, we will be proving the following:

To this end, we verify that $G_{1}(c_{1})+G_{2}(c_{2})-2>0$ hold for a sequence of $c_{1}$ and $c_{2}$: $[c_{1},c_{2}]=[0,0.49]$, $[c_{1},c_{2}]=[0.49,1.08]$, $[c_{1},c_{2}]=[1.08,1.78]$, $[c_{1},c_{2}]=[1.78,2.56]$, $[c_{1},c_{2}]=[2.56,3.47]$, $[c_{1},c_{2}]=[3.47,4.47]$, $[c_{1},c_{2}]=[4.47,5.56]$, $[c_{1},c_{2}]=[5.56,6.77]$, $[c_{1},c_{2}]=[6.67,8.08]$, $[c_{1},c_{2}]=[8.08,9.5]$, $[c_{1},c_{2}]=[9.5,11]$, $[c_{1},c_{2}]=[11,12.6]$, $[c_{1},c_{2}]=[12.6,14.3]$. Combining all the above results proves

From the above discussions, it only remains to prove the monotonicity of $G_{1}(t)$ and $G_{2}(t)$. Consider $G_{1}(t)$ first:

Applying the Cauchy-Schwarz inequality yields:

Combining (4.49) and (4.50), we proved that $G^{\prime}_{1}(t)\geq 0$, and therefore $G_{1}(t)$ is monotonically increasing. For $G_{2}(t)$, we have

Combining the previous two equations leads to $G^{\prime}_{2}(t)\geq 0$, which completes our proof.

Case II: We next prove (4.44) for $s^{2}\leq 0.07$, which is based on a different strategy. Some manipulations of the RHS of (4.44) yields:

From our reformulation in (4.51), the inequality in (4.44) for $s^{2}<0.07$ becomes

Note that $0.93<1/(1+0.07)$ and thus proving the above inequality for $x\in[0.93,1)$ is sufficient to prove the original inequality for $s^{2}\leq 0.07$ (note that $x\overset{\scriptscriptstyle\Delta}{=}1/(1+s^{2})$, see (4.51b)).

With some further calculations, (4.52) can be reformulated as

The following inequality is due to [51, Eqn. (1)]

and to prove (4.53) it suffices to prove the following

To this end, we will prove that the LHS of (4.54) is a strictly increasing function of $x\in[0.93,1)$. If this is true, we would have

We next prove the monotonicity of $\frac{E(x)T(x)-x}{1-x}$. From the identities in Lemma 3, we derive the following

Hence, to prove that $\frac{E(x)T(x)-x}{1-x}$ is monotonically increasing, it is sufficient to prove the following inequality:

Now, substituting $T(x)=E(x)-(1-x)K(x)$ into (4.55) and after some manipulations, we finally reformulate the inequality to be proved into the following form:

It can be verified that equality holds at $x=1$. We next prove that $T(x)^{2}+xE(x)^{2}-2x$ is monotonically decreasing on $[0.93,1)$. We differentiate once more:

Our problem boils down to proving $2E(x)^{2}-(1-x)K(x)^{2}-2<0$ for $x\in[0.93,1)$. We can verify that $2E(x)^{2}-(1-x)K(x)^{2}-2=0$ holds at $x=1$. We finish by showing that $2E(x)^{2}-(1-x)K(x)^{2}-2$ is monotonically increasing in $x\in[0.93,1)$. To this end, we differentiate again:

We note that $K(x)-\left(\frac{3}{2}+\frac{1}{\sqrt{2}}\right)E(x)$ is a monotonically increasing function in (0,1) since $K(x)$ is monotonically increasing and $E(x)$ is monotonically decreasing. We verify that $K(x)-\left(\frac{3}{2}+\frac{1}{\sqrt{2}}\right)E(x)>0$ when $x\geq 0.93$. Hence,