State Evolution for Approximate Message Passing with Non-Separable Functions

Introduction

(A slightly different definition, that is more convenient for proofs, will be adopted in Section 3.)

Apart from being broadly applicable, AMP algorithms admit an asymptotically exact characterization in the high-dimensional limit $m,n\to\infty$ with $m/n$ converging to a limit, which is known as state evolution. Informally, for any $t$ fixed, in the high-dimensional limit, ${\boldsymbol{u}}^{t}$ is approximately Gaussian with mean zero and covariance $\tau^{2}_{t}{\boldsymbol{I}}_{n}$, while ${\boldsymbol{v}}^{t}$ is approximately ${\sf N}(0,\sigma^{2}_{t}{\boldsymbol{I}}_{m})$. The variance parameters $\tau^{2}_{t},\sigma^{2}_{t}$ can be computed via a one-dimensional recursion.

State evolution was proved in [BM11] for the recursion (1), (2) under two key assumptions

${\boldsymbol{A}}$ a Gaussian random matrix with with i.i.d. entries $(A_{ij})_{i\leq m,j\leq n}\sim{\sf N}(0,1/m)$.

We introduce a random perturbation of the functions $e_{t}(\,\cdot\,)$, $g_{t}(\,\cdot\,)$. We prove that, with probability one with respect to this random perturbation, the new iteration satisfies the required non-degeneracy assumption.

We prove that both AMP and state evolution are uniformly continuous in the size of the perturbation, and hence we can let the perturbation vanish recovering state evolution for the original unperturbed problem.

Further, we obtain a streamlined proof with respect to the strategy of [BM11], by introducing a different algorithms, that we call LAMP (for Long AMP). State evolution is proved first for LAMP, and then the latter is shown to be closely approximated by the original AMP. We believe that LAMP is potentially of independent interest and will be further investigated in [MN17]

In the rest of this introduction we will briefly describe two applications of AMP with non-separable nonlinearities, and show how state evolution can be used to characterize its behavior. Both of these are examples of generalized compressed sensing, cf. Section 7. We will then review some related work in Section 2, and state our results in Section 3 (for the asymmetric iteration (1) and Section 4 (for the analogue case in which ${\boldsymbol{A}}$ is a random symmetric matrix)). Proofs are presented in Sections 5 and 6. In fact, we will first prove state evolution in the case in which ${\boldsymbol{A}}$ is a symmetric random matrix, and then reduce the asymmetric case to the symmetric one. Finally, Section 7 applies the general theory to compressed sensing reconstruction with a variety of denoisers. In particular, we derive a bound on the convergence rate for denoisers that are projectors onto convex sets. Several technical elements are deferred to the appendices.

For a summary of notations used throughout the paper, the reader is urged to consult Section 5.1.

The following AMP algorithm can be used to reconstruct ${\boldsymbol{X}}_{0}$ from observations ${\boldsymbol{y}}$:

The divergence in Eq. (7) can be computed explicitly using a formula from [CSLT13, DG+14], see Appendix A.1. The sequence of parameters $(\lambda_{t})_{t\geq 0}$ can be chosen to optimize the algorithm performance.

Fixed points of this AMP algorithm are minimum nuclear norm solution of the constraint ${\boldsymbol{y}}={\boldsymbol{A}}({\boldsymbol{X}})$. This algorithm was implemented in [Don13] and partly motivated the predictions of [DGM13]. A recent detailed study (and generalizations) can be found in [RG17], showing that its phase transition matches the one of nuclear norm minimization, predicted in [DGM13] and proved in [OTH13, ALMT14].

With a change of variables, the algorithm (5), (6) can be recast in the general form (1), (2) with one of the functions being non-separable and given by the SVT operator (the change of variables is described in Section 7).

We plot the the normalized mean square error as a function of the iteration number (with $n=n_{1}n_{2}$ the number of unknowns):

State evolution allows to predict the value $\lim_{n\to\infty}{\rm NMSE}(t;n)$. The prediction is already very accurate for $n_{1}=n_{2}=170$.

2 Vignette #​2#2\#2: Compressed sensing with images

A broad class of AMP reconstruction algorithms take the form

Again, the iteration (14), (13) can be put in the form (1), (2) with a change of variables described in Section 7. A non-separable denoiser $\eta_{t}$ translates into non-separable non-linearities $g_{t}$, $e_{t}$.

Here we use Non-Local Means denoising (NLM) [BCM05]. Given a noisy image ${\boldsymbol{z}}$, NLM estimates pixel $(i,j)$ as a weighted average of the pixels of ${\boldsymbol{z}}$:

In words, NLM averages patches that are similar to each other. The recent paper [MMB16] studies this algorithm and demonstrates state-of-the-art performances. Here we carry out similar simulations to demonstrate the accuracy of the state evolution prediction. At each iteration we can choose three parameters: $L_{t}$, $R_{t}$ and $h_{t}$. We fix $L_{t}=7$, $R_{t}=11$ and adapt $h_{t}$ to the noise level. The theory developed in the next sections suggests that $\|{\boldsymbol{r}}^{t}\|_{2}/\sqrt{m}$ is a good measure of the effective noise level after $t$ iterations. We therefore set

where the coefficient $0.9$ was selected empirically.

One difficulty is to compute the divergence of NLM denoisers ${\rm div}\,\eta_{t}$. Rather than computing explicitly the divergence from Eqs. (16) and (17), we use a trick suggested in [MMB16, Section V.B]. The trick is based on the formula

Rather than taking the limit, we fix $\varepsilon$ very small and evaluate the expectation by Monte Carlo. In high dimensions, concentration of measure helps and it is sufficient to use only one or a few samples to approximate the integral.

In Figure 2, we demonstrate the algorithm performance for an image of size $170\times 170$ (i.e. $n_{1}=n_{2}=170$) with $m=0.5\cdot n_{1}n_{2}$ measurements and noise level $\sigma_{w}=0.034\cdot\|{\boldsymbol{x}}_{0}\|_{2}/\sqrt{170}$. For each iteration $t\in\{0,1,2,3,4\}$, we show the estimates ${\boldsymbol{x}}^{t}+{\boldsymbol{A}}^{{\sf T}}{\boldsymbol{r}}^{t}$ (left column) together with the denoised versions ${\boldsymbol{x}}^{t+1}=\eta_{t}({\boldsymbol{x}}^{t}+{\boldsymbol{A}}^{{\sf T}}{\boldsymbol{r}}^{t})$ (right column). In Figure 3, we report the evolution of the normalized square error ${\rm NMSE}(t;n)=\|{\boldsymbol{x}}^{t}-{\boldsymbol{x}}_{0}\|_{2}^{2}/\|{\boldsymbol{x}}_{0}\|_{2}^{2}$, as a function of the number of iteration. State evolution appears to track very closely the simulation results.

Further related work

Approximate Message Passing algorithms are motivated by ideas in spin glass theory, where they correspond to an iterative version of the celebrated TAP equations [TAP77, Bol14]. They can also be derived from graphical models ideas, by viewing them as approximations of belief propagation [KF09, Mon12]. In both of these cases, the AMP nonlinearities turn out to be related to conditional expectation with respect to certain prior distributions. The theorems proved here apply more broadly, as demonstrated by the example in Section 1.2.

A generalization of AMP to right-invariant random matrices was introduced and analyzed in [MP17, RSF16], using the conditioning technique also applied here. This allows to treat classes of matrices with dependent entries and potentially large condition numbers. In the same direction, [OCW16, ÇOWF17] develops iterative algorithms analogous to (1), (2) for unitarily invariant symmetric matrices, and for compressed sensing. The analysis in these works is based on non-rigorous density functional methods from statistical physics.

All results discussed above are asymptotic, and characterize the limit $m,n\to\infty$ with $m/n$ converging to a limit. Nevertheless, the conditioning technique does rely on central-limit-theorem and concentration-of-measure arguments and, as demonstrated in [RV16], it can be sharpened to obtain non-asymptotic results.

Finally, a recent paper by Ma, Rush and Baron [MRB17] states a theorem establishing state evolution for compressed sensing reconstruction via AMP with a non-separable sliding-window denoiser. The result of [MRB17] is not directly comparable with ours, since it concerns a special class of non-separable nonlinearities, but provides non-asymptotic guarantees.

Main results

In this section we state our main result for the asymmetric AMP iteration of Eqs. (1), (2). A similar result for symmetric AMP will be stated in Section 4 (and proven in 5).

For two sequences (in $n$) of random variables $X_{n}$ and $Y_{n}$, we write X_{n}\mathrel{\stackrel{{\scriptstyle{\rm P}}}{{\mathrel{\scalebox{1.8}[1.0]{\simeq}}}}}Y_{n} when their difference converges in probability to , i.e. $X_{n}-Y_{n}\stackrel{{\scriptstyle{\rm P}}}{{\longrightarrow}}0$.

2 State evolution

We next list our assumptions (we refer to Section 5.1 for a summary of notations used in the paper):

${\boldsymbol{A}}$ has entries $(A_{ij})_{i\leq m,j\leq n}\sim_{iid}{\sf N}(0,1/m)$.

$\|{\boldsymbol{u}}^{0}\|_{2}/\sqrt{n}$ converges to a finite constant as $n\to\infty$.

The following limit exists and is finite:

where $Z\sim{\sf N}(0,s{\boldsymbol{I}}_{n})$.

where $({\boldsymbol{Z}}_{1},{\boldsymbol{Z}}_{2})\sim{\sf N}(0,{\boldsymbol{S}}\otimes{\boldsymbol{I}}_{n})$ and $({\boldsymbol{Z}}_{3},{\boldsymbol{Z}}_{4})\sim{\sf N}(0,{\boldsymbol{S}}\otimes{\boldsymbol{I}}_{m})$.

State evolution characterizes the AMP iteration of Eqs. (1), (2), which we copy here for the reader’s convenience:

where the initial condition is given by ${\boldsymbol{u}}^{0}$, and we let $g_{-1}(\,\cdot\,)=0$ by convention. Further we use the following expression for the memory terms (which we shall refer to as ‘Onsager terms,’ following the physics tradition):

We are now in position to state our main result.

The proof of this theorem is presented in Section 6, and is obtained by reduction to the symmetric case, which is treated in the next section.

As mentioned above, we use Eq. (29) to define the coefficients ${\sf b}_{t}$, ${\sf d}_{t}$ because this simplifies the proofs. In practice, this definition is replaced by an empirical estimate, e.g. as in Eq. (3). State evolution follows for these versions of AMP provided such estimates of ${\sf b}_{t}$, ${\sf d}_{t}$ are consistent.

Consider the modified AMP iteration whereby Eqs. (27), (28) are replaced by

with the initialization $\hat{\boldsymbol{u}}^{0}={\boldsymbol{u}}^{0}$, where $\hat{\sf b}_{t}=\hat{\sf b}_{t}(\hat{\boldsymbol{u}}^{0},\hat{\boldsymbol{v}}^{0},\dots,\hat{\boldsymbol{v}}^{t-1},\hat{\boldsymbol{u}}^{t})$ and $\hat{\sf d}_{t}=\hat{\sf d}_{t}(\hat{\boldsymbol{u}}^{0},\hat{\boldsymbol{v}}^{0},\dots,\hat{\boldsymbol{v}}^{t-1},\hat{\boldsymbol{u}}^{t},\hat{\boldsymbol{v}}^{t})$ are two estimators of ${\sf b}_{t}$, ${\sf d}_{t}$. Assume the same conditions as Theorem 1. If, for each $t$, $\hat{\sf b}_{t}(\,\cdot\,)$, $\hat{\sf d}_{t}(\,\cdot\,)$ are such that

then the iterates $(\hat{\boldsymbol{u}}^{t},\hat{\boldsymbol{v}}^{t})_{t\geq 0}$ satisfy state evolution, namely Eq. (32) holds with $({\boldsymbol{u}}^{t},{\boldsymbol{v}}^{t})_{t\geq 0}$ replaced by $(\hat{\boldsymbol{u}}^{t},\hat{\boldsymbol{v}}^{t})_{t\geq 0}$.

The proof of this statement is deferred to Section 6.

Two choices of $\hat{\sf b}_{t},\hat{\sf d}_{t}$ that satisfy the assumptions are:

By Theorem 1, if ${\rm div}\,e_{t}(\,\cdot\,)/m$, ${\rm div}\,g_{t}(\,\cdot\,)/m$ are uniformly pseudo-Lipschitz, then the assumptions of Corollary 2 hold, and hence we can apply state evolution.

Consistency follows (for $e_{t}(\,\cdot\,)$, $g_{t}(\,\cdot\,)$ uniformly Lipschitz) from Theorem 1 and Gaussian integration by parts (in particular, Stein’s lemma; see Lemma 17).

Symmetric AMP

We insist on the fact that ${\boldsymbol{A}}$, $f_{t}$ and ${\boldsymbol{x}}^{0}$ depend on $n$. However, we will drop this dependence most of the time to ease the reading.

$\|{\boldsymbol{x}}^{0}\|_{2}/\sqrt{n}$ converges to a finite constant as $n\to\infty$.

The following limit exists and is finite:

We have can now state the following state evolution characterization of symmetric AMP, which is analogous to Theorem 1.

Under assumptions (A1)-(A6), consider the AMP iteration $\left\{{\boldsymbol{x}}^{t},{\boldsymbol{m}}^{t}\middle|f_{t},{\boldsymbol{x}}^{0}\right\}$. Define for all $n$,

The proof of this theorem is presented in Section 5. We also note that an analogue of Corollary 2 applies to this case as well, and ${\sf b}_{t}$ can be replaced by a consistent estimator $\hat{\sf b}_{t}$.

Proof of Theorem 3 (Symmetric AMP)

In this section we prove Theorem 3 using a sequence of lemmas, whose proofs are postponed to Section 5.5. We will also try to motivate the main steps. Throughout this section and the next, Assumptions (A1)-(A6) hold.

We generally denote scalars by lower case letters, e.g. $a$, $b$, $c$, vectors by lower case boldface, e.g. ${\boldsymbol{a}}$, ${\boldsymbol{b}}$, ${\boldsymbol{c}}$, and matrices by upper case boldface, e.g. ${\boldsymbol{A}}$, ${\boldsymbol{B}}$, ${\boldsymbol{C}}$. We also use the upper case to emphasize that we are referring to a random variable, and –with a slight abuse of the convention– upper case boldface for random vectors.

We use ${\boldsymbol{I}}_{n}$ to denote the $n\times n$ identity matrix. We use $\sigma_{\min}\left({\boldsymbol{Q}}\right)$ and $\sigma_{\max}\left({\boldsymbol{Q}}\right)=\left\|{\boldsymbol{Q}}\right\|_{\mbox{\tiny\rm op}}$ to denote the minimum and maximum singular values of the matrix ${\boldsymbol{Q}}$. For two matrices ${\boldsymbol{Q}}$ and ${\boldsymbol{P}}$ of the same number of rows, $\left[{\boldsymbol{Q}}|{\boldsymbol{P}}\right]$ denotes the matrix by concatenating ${\boldsymbol{Q}}$ and ${\boldsymbol{P}}$ horizontally. For any matrix ${\boldsymbol{M}}$, we denote the orthogonal projection onto its range ${\boldsymbol{P}}_{M}$, and we let ${\boldsymbol{P}}_{M}^{\perp}={\boldsymbol{I}}-{\boldsymbol{P}}_{M}$. When ${\boldsymbol{M}}$ is an empty matrix, ${\boldsymbol{P}}_{M}=0$ and ${\boldsymbol{P}}_{M}^{\perp}={\boldsymbol{I}}$. When ${\boldsymbol{M}}$ has full column rank, ${\boldsymbol{P}}_{M}={\boldsymbol{M}}\left({\boldsymbol{M}}^{{\sf T}}{\boldsymbol{M}}\right)^{-1}{\boldsymbol{M}}^{{\sf T}}$.

where $f_{i}({\boldsymbol{x}})$ is the $i$-th coordinate of $f({\boldsymbol{x}})$.

We say that a sequence of events that depends on $n$, hold with high probability (w.h.p.) if it holds with probability converging to 1 as $n\to\infty$.

We define the Wasserstein distance (of order $2$) between two probability measures $\mu$ and $\nu$ as

where the infimum is taken over all couplings of $\mu$ and $\nu$, i.e. all random variables $(X,Y)$ such that $X\sim\mu$ and $Y\sim\nu$ marginally.

2 Long AMP

The main idea of the proof is to analyze a different recursion than the AMP recursion (38), (39). This new recursion satisfies the conclusion of Theorem 3 and will be a good approximation of the AMP recursion in the asymptotic $n\rightarrow\infty$. It is defined as:

The initialization is ${\boldsymbol{q}}^{0}=f_{0}({\boldsymbol{x}}^{0})$ and ${\boldsymbol{h}}^{1}={\boldsymbol{A}}{\boldsymbol{q}}^{0}$. This recursion will be referred as the Long AMP recursion, or LAMP $\left\{{\boldsymbol{h}}^{t},{\boldsymbol{q}}^{t}\middle|f_{t},{\boldsymbol{x}}^{0}\right\}$.

Note that for the LAMP recursion to be well-defined, the matrices ${\boldsymbol{Q}}_{t-1}^{{\sf T}}{\boldsymbol{Q}}_{t-1}$ must be invertible, that is to say the family ${\boldsymbol{q}}^{0},{\boldsymbol{q}}^{1},\dots,{\boldsymbol{q}}^{t-1}$ must be linearly independent. This has no reason to be true, since ${\boldsymbol{q}}^{s}=f_{s}({\boldsymbol{h}}^{s})$ and $f_{s}$ is a generic sequence of Lipschitz functions (satisfying assumptions (A4)-(A6)). For instance, if all $f_{s}$, $s=0,\dots,t-1$, have images included in a same subspace of dimension lower than $t$, this cannot be true. This difficulty leads to some technicalities in the proof. However, we will start by studying the case where ${\boldsymbol{Q}}_{t-1}^{{\sf T}}{\boldsymbol{Q}}_{t-1}$ is invertible, with $\sigma_{\min}\left({\boldsymbol{Q}}_{t-1}\right)/\sqrt{n}\geq c_{t}>0$, for $n$ large enough, where $c_{t}$ is a constant independent of $n$. More formally, we make the following assumption.

We say that the LAMP iterates satisfy the non-degeneracy assumption if

3 The non-degenerate case

The LAMP recursion is of interest because it behaves well with Gaussian conditioning, so that the sequence of iterates becomes easier to study. The following lemma makes this idea explicit.

Consider the LAMP $\left\{{\boldsymbol{h}}^{t},{\boldsymbol{q}}^{t}\middle|f_{t},{\boldsymbol{x}}^{0}\right\}$ and suppose it satisfies the non-degeneracy assumption. Then:

To conclude that Theorem 3 holds in this case, we only need to show that LAMP is a good approximation of AMP.

Wrapping things together, we have shown the following weaker form of Theorem 3.

4 The general case

To treat the case where the matrix ${\boldsymbol{Q}}_{t-1}$ is ill-conditioned, we add a small perturbation to the functions $f_{s}$ so that the perturbed AMP behaves well. We then make sure that the perturbed AMP approximates well the original one.

A convenient way implement this program is to perturb randomly the functions. We then show that almost surely, the perturbation has the required properties (A4)-(A6). Specifically, consider

where $\epsilon\geq 0$ and ${\boldsymbol{y}}^{0},{\boldsymbol{y}}^{1},{\boldsymbol{y}}^{2},\dots$ are generated as i.i.d. ${\sf N}\left(0,{\boldsymbol{I}}_{n}\right)$, independent of the matrix $A$. The perturbation vectors ${\boldsymbol{y}}^{0},{\boldsymbol{y}}^{1},{\boldsymbol{y}}^{2},\dots$ are called collectively as ${\boldsymbol{y}}$ for brevity.

Denote as ${\boldsymbol{Q}}_{t-1}^{\epsilon y}$ the matrix associated with the LAMP iterates $\left\{{\boldsymbol{h}}^{\epsilon y,t},{\boldsymbol{q}}^{\epsilon y,t}\middle|f_{t}^{\epsilon y},{\boldsymbol{x}}^{0}\right\}$, according to equation (51). Assume $\epsilon>0$. Then as soon as $n\geq t$, almost surely the matrix ${\boldsymbol{Q}}_{t-1}^{\epsilon y}$ is of full column rank. Furthermore, there exists a constant $c_{t,\epsilon}>0$ -independent of $n$- such that almost surely, there exists $n_{0}$ (random) such that for $n\geq n_{0}$, $\sigma_{\min}({\boldsymbol{Q}}_{t-1}^{\epsilon y})/\sqrt{n}\geq c_{t,\epsilon}$.

The last two lemmas imply that almost surely, we can apply Theorem 7 to $\left\{f_{t}^{\epsilon y}\right\}_{t\geq 0}$. The next three lemmas quantify how this result approximates our original one.

and for all $\epsilon\leq 1$, with high probability,

The proof combines three elements that follow from the previous lemmas:

Using that $\phi_{n}$ is uniformly pseudo-Lipschitz of order $k$ and the triangle inequality,

where here $C_{j}(k,t)$ is a constant depending only on $k$ and $t$. Lemma 12 ensures that w.h.p. $\left\|{\boldsymbol{x}}^{\epsilon y,i}-{\boldsymbol{x}}^{i}\right\|_{2}/\sqrt{n}\leq h_{i}(\epsilon)$. We also know by assumption (A3) that $\left\|{\boldsymbol{x}}^{0}\right\|_{2}/\sqrt{n}$ converges to a finite limit. Furthermore, one can use Theorem 7 to bound w.h.p.

Finally, using the triangle inequality, w.h.p.,

As this upper bound goes converges to 0 as $\epsilon\to 0$, we have for any $\eta>0$,

Let us now combine the three elements together. Let $\eta>0$. We have:

Taking $\limsup$ as $n\to\infty$, the second term vanishes because of (69):

Because of (78) and (70), this upper bound converges to 0 as $\epsilon\to 0$. We can then conclude that

5 Proof of the Lemmas

The claim for $t=0$ is immediate from that $\mathfrak{S}_{0}$ is the trivial $\sigma$-algebra and ${\boldsymbol{P}}_{Q_{t-1}}^{\perp}={\boldsymbol{I}}_{n}$. For $t\geq 1$, let us rewrite (49) as

5.2 Proof of Lemma 5

Proof of ${\cal H}_{0}$. Recall that ${\boldsymbol{h}}^{1}={\boldsymbol{A}}{\boldsymbol{q}}^{0}$. Then (a) follows immediately from Lemma 19, and (b) is from Lemmas 19, 21, 23.

We only need to prove the claim for $r=t$.

Consider the case $s<t$. Since ${\boldsymbol{h}}^{s+1}$ and $\left\langle{\boldsymbol{q}}^{s},{\boldsymbol{q}}^{t}\right\rangle$ are $\mathfrak{S}_{t}$-measurable, by Lemma 4,

Note that by ${\cal H}_{t-1}\left(a\right)$, $\frac{1}{n}\left\|{\boldsymbol{H}}_{t-1}^{{\sf T}}{\boldsymbol{h}}^{s+1}-{\boldsymbol{Q}}_{t-1}^{{\sf T}}{\boldsymbol{q}}^{s}\right\|_{2}\xrightarrow[n\to\infty]{{\rm P}}0$ . Hence,

since $\frac{1}{\sqrt{n}}\left\|{\boldsymbol{h}}^{s+1}\right\|_{2}$ and $\frac{1}{\sqrt{n}}\left\|{\boldsymbol{q}}^{t}\right\|_{2}$ concentrate at finite constants by ${\cal H}_{t-1}\left(b\right)$ and Lemma 20, and $\left\|{\boldsymbol{P}}_{Q_{t-1}}^{\perp}{\boldsymbol{h}}^{s+1}\right\|_{2}\leq\left\|{\boldsymbol{h}}^{s+1}\right\|_{2}$, $\left\|{\boldsymbol{q}}_{\perp}^{t}\right\|_{2}\leq\left\|{\boldsymbol{q}}^{t}\right\|_{2}$. It follows that \frac{1}{n}\left\langle{\boldsymbol{h}}^{s+1},{\boldsymbol{h}}^{t+1}\right\rangle\mathrel{\stackrel{{\scriptstyle{\rm P}}}{{\mathrel{\scalebox{1.8}[1.0]{\simeq}}}}}\frac{1}{n}\left\langle{\boldsymbol{q}}^{s},{\boldsymbol{q}}^{t}\right\rangle.

Consider the case $s=t$. Since ${\boldsymbol{q}}^{t}$ is $\mathfrak{S}_{t}$-measurable, by Lemma 4,

Using ${\cal H}_{t-1}\left(a\right)$ and that ${\boldsymbol{\alpha}}^{t}\xrightarrow[n\to\infty]{{\rm P}}{\boldsymbol{\alpha}}^{t,*}$,

Notice that $\left\langle{\boldsymbol{\alpha}}^{t},{\boldsymbol{Q}}_{t-1}^{{\sf T}}{\boldsymbol{Q}}_{t-1}{\boldsymbol{\alpha}}^{t}\right\rangle=\left\|{\boldsymbol{q}}_{\parallel}^{t}\right\|_{2}^{2}$. The claim is proven.

where $C(k,t)$ is a constant depending only on $k$ and $t$. We have:

Notice that $\frac{1}{n}\left\|{\boldsymbol{q}}_{\perp}^{t}\right\|_{2}^{2}=\frac{1}{n}\left\|{\boldsymbol{q}}^{t}\right\|_{2}^{2}-\frac{1}{n}\left\langle{\boldsymbol{\alpha}}^{t},{\boldsymbol{Q}}_{t-1}^{{\sf T}}{\boldsymbol{Q}}_{t-1}{\boldsymbol{\alpha}}^{t}\right\rangle$, which converges to a constant $a^{2}$ due to ${\cal H}_{t-1}\left(b\right)$ and that ${\boldsymbol{\alpha}}^{t}\xrightarrow[n\to\infty]{{\rm P}}{\boldsymbol{\alpha}}^{t,*}$. Then by Lemma 19, there exists ${\boldsymbol{Z}}\sim{\sf N}\left(0,{\boldsymbol{I}}_{n}\right)$ independent of $\mathfrak{S}_{t}$ such that

where we use Lemma 23 in the second step, and ${\cal H}_{t-1}$$\left(b\right)$ and Lemma 22 in the third step. (Here with an abuse of notation, we let ${\boldsymbol{Z}}$ to be on the same joint space as and independent of ${\boldsymbol{Z}}^{1},\dots,{\boldsymbol{Z}}^{t}$.) The thesis follows immediately from that

5.3 Proof of Lemma 6

where we take $\hat{{\boldsymbol{h}}}^{1}={\boldsymbol{A}}{\boldsymbol{q}}^{0}$.

where $\left(a\right)$ holds because ${\boldsymbol{Q}}_{t-1}^{{\sf T}}{\boldsymbol{A}}=\left({\boldsymbol{A}}{\boldsymbol{Q}}_{t-1}\right)^{{\sf T}}=\hat{{\boldsymbol{H}}}_{t-1}^{{\sf T}}+\mathsf{B}_{t-1}\left[0|{\boldsymbol{Q}}_{t-2}\right]^{{\sf T}}$ and ${\boldsymbol{Q}}_{t-2}^{{\sf T}}{\boldsymbol{P}}_{Q_{t-1}}^{\perp}=0$, and

where $\frac{1}{\sqrt{n}}\left\|{\boldsymbol{q}}^{t}\right\|_{2}$ converges in probability to a finite constant by Lemma 5. We claim that $\frac{1}{\sqrt{n}}c_{s}\left\|{\boldsymbol{q}}^{s-1}\right\|_{2}\xrightarrow[n\to\infty]{{\rm P}}0$ for $s=1,\dots,t$. Then the thesis follows from this claim.

To prove the claim, denoting $R=\frac{1}{n}\left({\boldsymbol{Q}}_{t-1}^{{\sf T}}{\boldsymbol{Q}}_{t-1}\right)^{-1}$ for brevity, we note that

since ${\boldsymbol{Z}}^{r}$ has zero mean. By Lemmas 5 and 17, for $j=2,\dots,t-1$,

Identifying $\frac{1}{n}\left\langle{\boldsymbol{q}}^{r-1},{\boldsymbol{q}}^{j-1}\right\rangle=\left(R^{-1}\right)_{r,j}$, we get

i.e. $c_{s}\xrightarrow[n\to\infty]{{\rm P}}0$. Finally, since $\frac{1}{\sqrt{n}}\left\|{\boldsymbol{q}}^{s-1}\right\|_{2}$ converges in probability to a finite constant by Lemma 5, the claim is proven. ∎

Let ${\cal H}_{t}$ be the statement $\frac{1}{\sqrt{n}}\left\|{\boldsymbol{q}}^{t}-{\boldsymbol{m}}^{t}\right\|_{2}\xrightarrow[n\to\infty]{{\rm P}}0$ and $\frac{1}{\sqrt{n}}\left\|{\boldsymbol{h}}^{t+1}-{\boldsymbol{x}}^{t+1}\right\|_{2}\xrightarrow[n\to\infty]{{\rm P}}0$. We prove it by induction. The base case ${\cal H}_{0}$ is trivial because ${\boldsymbol{q}}^{0}={\boldsymbol{m}}^{0}$ and ${\boldsymbol{h}}^{1}={\boldsymbol{x}}^{1}$.

We now assume ${\cal H}_{t-1}$ is true and we show ${\cal H}_{t}$. We have:

using that $f_{t}$ is uniformly Lipschitz and the induction hypothesis ${\cal H}_{t-1}$. Further, we will prove that $\frac{1}{\sqrt{n}}\left\|\hat{{\boldsymbol{h}}}^{t+1}-{\boldsymbol{x}}^{t+1}\right\|_{2}\xrightarrow[n\to\infty]{{\rm P}}0$, which together with Lemma 13 yields ${\cal H}_{t}$. We have:

5.4 Proof of Lemma 8

The second term is Gaussian, with mean zero and variance

which is summable. Using Borel-Cantelli’s lemma, it is then easy to show that

The treatment of the third term is the same as for the second term.

Using the law of large numbers, we get that

Putting things together, we get almost surely

The proof of assumptions (A4), (A5) are very similar, here we only state the resulting expressions: almost surely,

Using equations (144), (145), (146), it is a simple induction that the state evolution for the perturbed setting $\left\{{\boldsymbol{x}}^{0},f_{t}^{\epsilon y}\right\}$ is indeed non-random almost surely.

5.5 Proof of Lemma 9

If we denote $\mathcal{F}_{t}$ as the $\sigma$-algebra generated by ${\boldsymbol{h}}^{\epsilon y,1},\dots,{\boldsymbol{h}}^{\epsilon y,t},{\boldsymbol{y}}^{1},\dots,{\boldsymbol{y}}^{t-1}$, it follows that

When $n>t$, this conditional distribution is almost surely non-zero. Thus when $n\geq t$, the matrix ${\boldsymbol{Q}}_{t-1}$ has full column rank.

To lower bound the minimum singular value of ${\boldsymbol{Q}}_{t-1}$, a more careful treatment is required. Using [BM11, Lemma 8], it is sufficient to check that there exists a constant $c_{\epsilon}$ such that almost surely, for $n$ sufficiently large,

We can choose $c_{\epsilon}$ such that $c_{\epsilon}/\epsilon^{2}=1/4$, and consider only the case $n\geq 2t$, so that $n/(n-t)\leq 2$. We then get:

Using concentration of the chi-squared variable, it is easy to show that $\Pr\left(\frac{\chi_{n-t}}{n-t}\leq\frac{1}{2}\right)$ is summable over $n$. Taking expectation of the last inequality, we get

Then Borel-Cantelli’s lemma concludes the proof.

5.6 Proof of Lemma 10

We then use the two following identities for the Wasserstein distance:

For a proof of the second identity, see [GS84, Proposition 7]. It follows that

Using expressions for moments of chi-square variables, we get:

for a constant $C(k,t)$ that depends only on $k$ and $t$. Back to inequality (159),

5.7 Proof of Lemma 11

The sequence of functions $(z^{s},z^{t})\mapsto\frac{1}{n}\left\langle f_{s}\left(z^{s}\right),f_{t}\left(z^{t}\right)\right\rangle$ is uniformly pseudo-Lipschitz by Lemma 20, thus Lemma 10 and the induction hypothesis jointly ensure that

5.8 Proof of Lemma 12

Indeed, one only needs to use that the functions involved are uniformly Lipschitz and Theorem 16. Note that these inequalities hold for the original AMP iterates by taking $\epsilon=0$.

by the law of large numbers. Thus we choose $h_{0}^{\prime}(\epsilon)=2\epsilon$. Furthermore,

by Theorem 16. Thus we choose $h_{0}(\epsilon)=6\epsilon$.

using that $f_{t}$ is uniformly Lipschitz with Lipschitz constant $L_{t}$. Thus we choose $h_{t}^{\prime}(\epsilon)=L_{t}h_{t-1}(\epsilon)+2\epsilon$, which converges to zero as $\epsilon\to 0$. Furthermore,

Proof of Theorem 1 and Corollary 2 (Asymmetric AMP)

We reduce this case to the asymmetric case, as in [JM13]. Consider

Applying Theorem 3 to the AMP recursion $\left\{{\boldsymbol{x}}^{t},{\boldsymbol{m}}^{t}|f_{t},{\boldsymbol{x}}^{0}\right\}$ shows our theorem. ∎

The proof is by induction over $t$. Let ${\mathcal{H}}_{t}$ be the claim that \|{\boldsymbol{u}}^{s}-\hat{\boldsymbol{u}}^{s}\|_{2}/\sqrt{n}\mathrel{\stackrel{{\scriptstyle{\rm P}}}{{\mathrel{\scalebox{1.8}[1.0]{\simeq}}}}}0 for all $s\leq t$ and \|{\boldsymbol{v}}^{s}-\hat{\boldsymbol{v}}^{s}\|_{2}/\sqrt{n}\mathrel{\stackrel{{\scriptstyle{\rm P}}}{{\mathrel{\scalebox{1.8}[1.0]{\simeq}}}}}0 for all $s\leq t-1$. The initial conditions imply immediately ${\mathcal{H}}_{0}$.

We now prove that ${\mathcal{H}}_{t}$ implies ${\mathcal{H}}_{t+1}$. Taking the difference of Eq. (2) and Eq. (34) and using triangular inequality, we get

where $L$ is the maximum Lipschitz constant of $e_{t}$ and $g_{t-1}$ and the second inequality holds with high probability by the Bai-Yin law [BY88]. Next notice that, with high probability, $\|g_{t-1}({\boldsymbol{v}}^{t-1})\|_{2}/\sqrt{n}\leq C$ for some constant $C$ by Theorem 1 (together with Assumption (B6)) and that $|\hat{\sf b}_{t}|\leq|{\sf b}_{t}|+|\hat{\sf b}_{t}-{\sf b}_{t}|\leq L+1$ with high probability by Assumption (35) and the Lipschitz continuity of $e_{t}$. Hence, for a suitable constant $C_{1}$, the following holds with high probability

We therefore have \|{\boldsymbol{v}}^{t}-\hat{\boldsymbol{v}}^{t}\|_{2}/\sqrt{n}\mathrel{\stackrel{{\scriptstyle{\rm P}}}{{\mathrel{\scalebox{1.8}[1.0]{\simeq}}}}}0 by Eq. (35) and the induction hypothesis.

Taking the difference of Eq. (2) and Eq. (34), we get

and the proof is completed by the same argument as above. ∎

Application to general compressed sensing

where the initialization is given by $\hat{\boldsymbol{\theta}}^{0}=0$ and $\eta_{-1}\left(\,\cdot\,\right)=0$. We assume the Onsager coefficient $\hat{\sf b}_{t}$ to be a function of $\hat{\boldsymbol{\theta}}^{0},\dots,\hat{\boldsymbol{\theta}}^{t}$, and ${\boldsymbol{r}}^{0},\dots,{\boldsymbol{r}}^{t-1}$, but we will discuss concrete choices below.

The sensing matrix ${\boldsymbol{A}}$ is Gaussian with i.i.d. entries, $(A_{ij})_{i\leq m,j\leq n}\sim{\sf N}\left(0,1/m\right)$.

$\|{\boldsymbol{\theta}}_{0}\|_{2}/\sqrt{n}$ converges to a constant as $n\to\infty$.

The limit $\sigma_{w}=\lim_{n\to\infty}\|{\boldsymbol{w}}\|_{2}/\sqrt{m}\in[0,\infty)$ exists.

where $Z\sim{\sf N}\left(0,\sigma^{2}{\boldsymbol{I}}_{n}\right)$.

where $\left({\boldsymbol{Z}},{\boldsymbol{Z}}^{{}^{\prime}}\right)\sim{\sf N}\left(0,{\boldsymbol{\Sigma}}\otimes{\boldsymbol{I}}_{n}\right)$.

The technical assumptions (C5) and (C6) ensure the existence of the limits in the following state evolution recursion:

where ${\boldsymbol{Z}}\sim{\sf N}\left(0,{\boldsymbol{I}}_{n}\right)$.

State evolution predicts the asymptotic behavior of the estimates $\hat{\boldsymbol{\theta}}^{1},\hat{\boldsymbol{\theta}}^{2},\dots$ in terms of an iterative denoising process.

Under assumptions (C1)-(C6), consider the recursion (202)-(203). Assume that $\hat{\sf b}_{t}(\hat{\boldsymbol{\theta}}^{0},{\boldsymbol{r}}^{0},\dots,{\boldsymbol{r}}^{t-1},\hat{\boldsymbol{\theta}}^{t})$ satisfies

where ${\boldsymbol{Z}}\sim{\sf N}\left(0,{\boldsymbol{I}}_{m}\right)$ and ${\boldsymbol{Z}}^{\prime}\sim{\sf N}\left(0,{\boldsymbol{I}}_{n}\right)$.

This is a special case of the asymmetric AMP of Eqs. (1), (2), with

and the initialization ${\boldsymbol{u}}^{0}=-{\boldsymbol{\theta}}_{0}$. Assumptions (B1)-(B6) are satisfied thanks to assumptions (C1)-(C6). The claim follows from Theorem 1 and Corollary 2. ∎

A special case of common interest is $\psi_{n}({\boldsymbol{x}},{\boldsymbol{y}})=\|\eta_{t}({\boldsymbol{x}})-{\boldsymbol{y}}\|_{2}^{2}/n$, for which Theorem 14 yields

Two choices of the coefficient $\hat{\sf b}_{t}$ that satisfy the assumption (208) are:

Using Theorem 14, this satisfies the assumptions by induction, provided ${\boldsymbol{x}}\mapsto\frac{1}{m}{\rm div}\eta_{t}({\boldsymbol{x}})$ is uniformly Lipschitz for each $t$.

If ${\boldsymbol{x}}\mapsto\frac{1}{m}{\rm div}\,\eta_{t}({\boldsymbol{x}})$ is not uniformly Lipschitz, a smoothed version of Eq. (217) achieves the same goal, namely

where the expectation is with respect to ${\boldsymbol{Z}}\sim{\sf N}(0,{\boldsymbol{I}}_{n})$, and $\varepsilon_{n}$ is a deterministic sequence that converges to sufficiently slowly. Adapting the arguments of Section 5.5.8, it is possible to show that this choice satisfies the assumption (208).

We also note that, even if ${\boldsymbol{x}}\mapsto\frac{1}{m}{\rm div}\eta_{t}({\boldsymbol{x}})$ is not uniformly Lipschitz, the choice (217) can still satisfy the assumption (208). For instance, if $\eta_{t}(\,\cdot\,)$ if the soft thresholding denoiser (a case studied in [DMM09, BM11]), then ${\boldsymbol{x}}\mapsto\frac{1}{m}{\rm div}\,\eta_{t}({\boldsymbol{x}})$ is discontinuous but nevertheless a standard weak convergence argument implies Eq. (208).

2 Denoising by convex projection

An important feature of the theory developed in the previous section is that the denoiser $\eta_{t}$ can be fairly general, and not induced by an underlying optimization problem. Nevertheless, it is interesting to specialize the theory developed so far to cases with special additional structure.

Denoting by ${\sf P}_{{\mathcal{K}}}$ the projection onto the set ${\mathcal{K}}$ (which is a $1$- Lipschitz denoiser), the corresponding AMP algorithm reads

The constraint ${\boldsymbol{\theta}}\in{\mathcal{K}}$ is effective if ${\mathcal{K}}$ accurately captures the structure of the signal ${\boldsymbol{\theta}}_{0}$. We denote by ${\mathcal{C}}_{{\mathcal{K}}}({\boldsymbol{\theta}}_{0})$ the tangent cone of ${\mathcal{K}}$ at ${\boldsymbol{\theta}}_{0}$, i.e. the smallest convex cone containing ${\mathcal{K}}-\theta_{0}$. This can also be defined as

with $d({\boldsymbol{x}},S)\equiv\inf\{\|{\boldsymbol{x}}-{\boldsymbol{y}}\|_{2}:{\boldsymbol{y}}\in S\}$ the Euclidean point-set distance. A highly structured signal ${\boldsymbol{\theta}}_{0}$ corresponds to a ‘small’ cone ${\mathcal{C}}_{{\mathcal{K}}}({\boldsymbol{\theta}}_{0})$. This can be quantified via its statistical dimension [CRPW12, ALMT14]

where expectation is with respect to ${\boldsymbol{Z}}\sim{\sf N}(0,{\boldsymbol{I}}_{n})$. It turns out that the statistical dimension also controls the convergence of AMP. As for our general theory, we will consider a sequence of problems indexed by the dimension $n$.

Then for any $t\geq 0$, letting ${\sf R}_{0}\equiv\limsup_{n\to\infty}\|{\boldsymbol{\theta}}_{0}(n)\|_{2}/\sqrt{n}$, we have

The proof of this statement is deferred to Appendix C.

This theorem establishes exponentially fast convergence (in the high-dimensional limit) in all the region $m\geq(1+\eta)\Delta_{n}$, \Delta_{n}=\Delta\big{(}{\mathcal{C}}_{{\mathcal{K}}(n)}({\boldsymbol{\theta}}_{0}(n))\big{)}, i.e. whenever exact reconstruction is possible in absence of noise [ALMT14]. Further, the convergence rate is precisely given by the ratio of the number of necessary measurements to the number of measurements $\Delta_{n}/m$. For instance, it implies that, in order to achieve accuracy $\|\hat{\boldsymbol{\theta}}^{t}-{\boldsymbol{\theta}}_{0}\|_{2}/\|{\boldsymbol{\theta}}_{0}\|_{2}\leq\varepsilon$ in the noiseless case $\sigma_{w}=0$, it is sufficient to run the AMP iteration (221), (222) for approximately $\log(1/\varepsilon)/\log(m/\Delta_{n})$ iterations.

The first result of this type (for separable soft-thresholding denoising) was obtained in [DMM09, DMM11]. The only comparable result is obtained in recent work by Oymak, Recht, and Soltanolkotabi [ORS15], which establishes exponential convergence of of projected gradient descent, in a non-asymptotic sense, although at a slower rateThe same paper also prove convergence at a faster rate, but this requires $m>2\Delta_{n}$, i.e. a number of measurements that is twice as large as the optimal one.. In particular, in the noiseless case, $\varepsilon$ accuracy requires $(n/m)\log(1/\varepsilon)$. It would be interesting to derive a non-asymptotic version of Theorem 15, which might be possible using the approach of [RV16].

Acknowledgements

This work was partially supported by grants NSF CCF-1319979, NSF DMS-1613091, NSF CCF-1714305.

Appendix A Technical aspects of the numerical simulations

the SVT operator with threshold $\lambda$ yields

As proved in [CSLT13], the divergence for this operator can be computed using the formula

This expression should be understood in a weak sense as it is not defined on the negligible set where ${\boldsymbol{Y}}$ has repeated singular values.

A.2 Compressed sensing with images

In our simulation, to compute the state evolution iterates

we approximated them by their non-asymptotic estimates:

Here $n=170\times 170$ is the size of our image. However, we could not compute the expectation in equation (233) exactly. Thus at each iteration we used a Monte Carlo method to approximate the expectation with the mean over 10 samples. Computing each sample amounts to adding gaussian noise of variance $\hat{\tau}_{t}^{2}$ over the Lena image, denoising with NLM, and computing the square error. The resulting state evolution is shown in figure 3.

Appendix B Some useful tools

We reminder the readers of three well-known results. The first concerns with the operator norm of ${\boldsymbol{A}}\in{\rm GOE}\left(n\right)$; see e.g. [BY88] for a more general statement. The second is a simple consequence of Stein’s lemma [Ste72]. The last one is the Gaussian Poincaré inequality.

Consider a sequence of matrices ${\boldsymbol{A}}\sim{\rm GOE}\left(n\right)$. Then $\left\|{\boldsymbol{A}}\right\|_{{\rm op}}\to 2$ almost surely as $n\to\infty$.

We state some properties of the GOE matrices, and provide proofs for completeness.

$\frac{1}{n}\left\langle{\boldsymbol{v}},{\boldsymbol{A}}{\boldsymbol{u}}\right\rangle\stackrel{{\scriptstyle{\rm P}}}{{\longrightarrow}}0$

$\frac{1}{n}\left\|{\boldsymbol{A}}{\boldsymbol{u}}\right\|_{2}^{2}\stackrel{{\scriptstyle{\rm P}}}{{\longrightarrow}}1$.

Recall that ${\boldsymbol{A}}={\boldsymbol{G}}+{\boldsymbol{G}}^{{\sf T}}$ where $G_{i,j}$ are i.i.d. ${\sf N}\left(0,1/(2n)\right)$ random variables, thus

The random variable $\frac{1}{n}\left\langle{\boldsymbol{v}},G{\boldsymbol{u}}\right\rangle$ is centered Gaussian with variance

Thus $\frac{1}{n}\langle{\boldsymbol{v}},{\boldsymbol{G}}{\boldsymbol{u}}\rangle$ converges in probability to 0. We can conclude as similarly, $\frac{1}{n}\langle{\boldsymbol{v}},{\boldsymbol{G}}^{{\sf T}}{\boldsymbol{u}}\rangle$ also converges in probability to 0.

Consider ${\boldsymbol{v}}_{1},\dots,{\boldsymbol{v}}_{k}$ an orthogonal basis of the image of ${\boldsymbol{P}}$, such that $\|{\boldsymbol{v}}_{1}\|=\dots=\|{\boldsymbol{v}}_{k}\|=\sqrt{n}$. Note that $k$ can depend on $n$, but $k$ is uniformly bounded by $t$. Then, by point $(a)$,

This follows immediately from point $(d)$ below.

It is easy to check that ${\boldsymbol{A}}{\boldsymbol{u}}$ is a centered Gaussian vector with covariance matrix ${\boldsymbol{\Sigma}}={\boldsymbol{I}}_{n}+\frac{1}{n}{\boldsymbol{u}}{\boldsymbol{u}}^{{\sf T}}$. Thus there exists a Gaussian vector ${\boldsymbol{z}}\sim{\sf N}\left(0,{\boldsymbol{I}}_{n}\right)$ such that ${\boldsymbol{A}}{\boldsymbol{u}}={\boldsymbol{\Sigma}}^{1/2}{\boldsymbol{z}}={\boldsymbol{z}}+(\sqrt{2}-1)\frac{1}{n}{\boldsymbol{u}}{\boldsymbol{u}}^{{\sf T}}{\boldsymbol{z}}$. Using that $\varphi$ is uniformly pseudo-Lipschitz of order $k$, one has

The law of large numbers gives $\left\|{\boldsymbol{z}}\right\|_{2}/\sqrt{n}\xrightarrow[n\to\infty]{}1$, and we have $\left\|{\boldsymbol{A}}{\boldsymbol{u}}\right\|_{2}/\sqrt{n}\leq\|{\boldsymbol{\Sigma}}^{1/2}\|_{\rm op}\|{\boldsymbol{z}}\|_{2}/\sqrt{n}\leq\sqrt{2}\|{\boldsymbol{z}}\|_{2}/\sqrt{n}\xrightarrow[n\to\infty]{}\sqrt{2}$. Further

where the last convergence follows from the fact that $\frac{1}{n}{\boldsymbol{u}}^{{\sf T}}{\boldsymbol{z}}$ is a centered Gaussian random variable with variance $\|{\boldsymbol{u}}\|_{2}^{2}/n^{2}=1/n$.

We state some useful properties of uniformly pseudo-Lipschitz functions. We omit the proofs, which are easy to verify.

Finally, we have the following result on the Gaussian concentration for uniformly pseudo-Lipschitz functions.

This is a straightforward application of Theorem 18. In particular, by the definition of uniformly pseudo-Lipschitz functions of order $k$,

Since ${\boldsymbol{Z}}\sim{\sf N}\left(0,{\boldsymbol{I}}_{n}\right)$, the right-hand side goes to as $n\to\infty$. The claim is proven. ∎

Appendix C Proof of Theorem 15

Note for all $n\geq n_{0}$, $\|\hat{\boldsymbol{\theta}}^{t}\|_{2},\|{\boldsymbol{\theta}}_{0}\|_{2}\leq{\sf R}_{*}\sqrt{n}$ for all $t$.

where expectation is with respect to $({\boldsymbol{Z}},{\boldsymbol{Z}}^{\prime})\sim{\sf N}(0,{\boldsymbol{\Sigma}}\otimes{\boldsymbol{I}}_{n})$.

Note that the function ({\boldsymbol{Z}},{\boldsymbol{Z}}^{\prime})\mapsto\big{\langle}{\sf P}_{{\mathcal{K}}}({\boldsymbol{\theta}}_{0}+{\boldsymbol{Z}}),{\sf P}_{{\mathcal{K}}}({\boldsymbol{\theta}}_{0}+{\boldsymbol{Z}}^{\prime})\big{\rangle}/n is uniformly pseudo-Lipschitz of order $2$. Hence, using Lemma 10, we have

We can therefore apply Theorem 14 (and Remark 7.1) along this subsequence, to obtain \|\hat{\boldsymbol{\theta}}^{t+1}-{\boldsymbol{\theta}}_{0}\|_{2}^{2}/n\mathrel{\stackrel{{\scriptstyle{\rm P}}}{{\mathrel{\scalebox{1.8}[1.0]{\simeq}}}}}\delta(\tau_{t+1}^{2}-\sigma_{w}^{2}) and hence (since $\|\hat{\boldsymbol{\theta}}^{t+1}-{\boldsymbol{\theta}}_{0}\|_{2}^{2}/n\leq{\sf R}_{*}^{2}$ is bounded uniformly)

Here $\tau_{t+1}$ is given recursively by Eq. (207), namely $\tau^{2}_{0}={\sf R}_{0}^{2}$ and

where the limit exists by the existence of the limit of $F_{n}({\boldsymbol{\Sigma}})$ above. Now, since ${\mathcal{K}}-{\boldsymbol{\theta}}_{0}\subseteq{\mathcal{C}}_{{\mathcal{K}}}({\boldsymbol{\theta}}_{0})$, we have

We therefore get the recursion $\tau_{s+1}^{2}\leq\sigma_{w}^{2}+\rho\tau^{2}_{s}$, which can be summed to yield

which yields the desired contradiction hence proving the theorem.

References