Rigorous Dynamics of Expectation-Propagation-Based Signal Recovery from Unitarily Invariant Measurements

I Introduction

The signal vector $\boldsymbol{x}$ has independent and identically distributed (i.i.d.) zero-mean non-Gaussian elements We require no additional assumptions for the prior distribution of each signal to prove the main theorem, whereas it is practically important to postulate some prior distribution indicating the sparsity of $\boldsymbol{x}$. with unit variance and finite fourth moments.

For an i.i.d. Gaussian matrix $\boldsymbol{A}$—satisfying Assumption 2—the approximate message passing (AMP) was proved in to be asymptotically Bayes-optimal when the compression rate $\delta$ is larger than the so-called belief-propagation (BP) threshold . However, it has been recognized that the original AMP fails to converge for non-i.i.d. measurement matrices . To solve this limitation, several message-passing algorithms have been proposed on the basis of expectation propagation (EP) , the expectation-consistent approximation , or of the turbo principle . These algorithms are essentially the same as each other, with the only exception of . In this paper, they are referred to as EP-based algorithms.

The main advantage of EP-based algorithms is that they are asymptotically Bayes-optimal for unitarily invariant measurement matrices. This claim was conjectured in , by proposing state evolution (SE) equations of the EP-based algorithms based on two heuristic assumptions, and by investigating the properties of the SE equations. However, the rigorous justification of the conjecture is still open. A similar result was posted on the arXiv a few months before the first submission of this paper. The main difference between the two papers is that we use a probabilistic approach, while the posted paper considered a deterministic one based on pseudo-Lipschitz continuity. The deterministic approach only provides results averaged over all elements of $\boldsymbol{x}$. On the other hand, the probabilistic one allows us to obtain results for individual elements, while only averaged results are presented due to space limitation. The purpose of this paper is to prove the conjecture by presenting a rigorous derivation of the SE equations.

II Expectation Propagation

due to Assumption 2. As proved in Section IV, $\gamma_{t}$ eliminates dependencies between estimation errors in the two modules.

The following lemma is used to prove that (7) eliminates dependencies between estimation errors in the two modules.

III Main Result

Theorem 1 was originally conjectured in , and implies that the EP-based algorithm predicts the exact dynamics of the extrinsic variances in the large system limit. The fixed-points (FPs) of the SE equations were proved in to correspond to those of an asymptotic energy function that describes the Bayes-optimal performance—derived in via a non-rigorous tool in statistical physics. Thus, the Bayes-optimal performance derived in is achievable when the SE equations have a unique FP, or equivalently when the compression rate $\delta$ is larger than the BP threshold .

We define $\boldsymbol{m}_{t}^{\parallel}=\boldsymbol{P}_{\boldsymbol{M}_{t}}^{\parallel}\boldsymbol{m}_{t}=\boldsymbol{M}_{t}\boldsymbol{\alpha}_{t}$, $\boldsymbol{\alpha}_{t}=\boldsymbol{M}_{t}^{\dagger}\boldsymbol{m}_{t}$, and $\boldsymbol{m}_{t}^{\perp}=\boldsymbol{m}_{t}-\boldsymbol{m}_{t}^{\parallel}$. See the end of Section I for the notations. The vectors $\boldsymbol{q}_{t}^{\parallel}$, $\boldsymbol{q}_{t}^{\perp}$, and $\boldsymbol{\beta}_{t}=\boldsymbol{Q}_{t}^{\dagger}\boldsymbol{q}_{t}$ are defined in the same manner. For notational convenience, we define $\boldsymbol{\alpha}_{0}=\boldsymbol{0}$, $\boldsymbol{\beta}_{0}=\boldsymbol{0}$, $\boldsymbol{Q}_{0}=\boldsymbol{O}$, $\boldsymbol{B}_{0}=\boldsymbol{O}$, $\boldsymbol{M}_{0}=\boldsymbol{O}$, $\boldsymbol{H}_{0}=\boldsymbol{O}$, $\boldsymbol{M}_{0}^{\dagger}=\boldsymbol{O}$, and $\boldsymbol{Q}_{0}^{\dagger}=\boldsymbol{O}$, implying $\boldsymbol{P}_{\boldsymbol{M}_{0}}^{\perp}=\boldsymbol{I}_{N}$ and $\boldsymbol{P}_{\boldsymbol{Q}_{0}}^{\perp}=\boldsymbol{I}_{N}$.

Each element in $\boldsymbol{q}_{\tau+1}$ has finite fourth moments. Furthermore, the following limit exists for all $\tau^{\prime}\leq\tau+1$:

Theorem 1 follows immediately from Theorem 2. A sketch for the proof of Theorem 2 is presented in the next section. See for the detailed proof.

IV Proof of Theorem 2

The proof strategy is based on a conditioning technique used in . A challenging part in the proof is to evaluate the distributions of the estimation errors in each iteration conditioned on the estimation errors in all preceding iterations. Bayati and Montanari evaluated the conditional distributions via the conditional distribution of the measurement matrix $\boldsymbol{A}$. Since the LMMSE filter is used in module A, the conditional distribution of $\boldsymbol{A}$ can be regarded as the posterior distribution of $\boldsymbol{A}$ given linear, noiseless, and compressed observations of $\boldsymbol{A}$, determined by the estimation errors in all preceding iterations. For i.i.d. Gaussian measurement matrices, it is well known that the posterior distribution is also Gaussian. The proof in heavily relies on this well-known fact.

The main contribution of this paper is to extend the argument in to the case of the unitary matrix $\boldsymbol{V}$. Assumption 2 implies that $\boldsymbol{V}$ is independent of $\boldsymbol{U}$ and $\boldsymbol{\Sigma}$, and a Haar matrix —uniformly distributed on the space of all possible $N\times N$ unitary matrices. Under coordinate rotations in the row and column spaces of $\boldsymbol{V}$, it is possible to show that the linear, noiseless, and compressed observation of $\boldsymbol{V}$ is equivalent to observing part of the elements in $\boldsymbol{V}$. Since any Haar matrix is bi-unitarily invariant , the distribution of $\boldsymbol{V}$ after the coordinate rotations is the same as the original one. Thus, evaluating the conditional distribution of $\boldsymbol{V}$ reduces to analyzing the conditional distribution of a Haar matrix given part of its elements. This argument was implicitly used in .

Evaluation of this conditional distribution is a technically challenging part in this paper, while this part is not required for i.i.d. Gaussian measurements. We use further coordinate rotations to reveal the statistical structure of the conditional Haar matrix. We know that a Haar matrix has similar properties to an i.i.d. Gaussian matrix as $N\to\infty$. In particular, a finite number of linear combinations of the elements in a Haar matrix were proved to converge in distribution to jointly Gaussian-distributed random variables as $N\to\infty$ . Note that the classical central limit theorem cannot be used, since the elements of a Haar matrix are not independent. Using this asymptotic similarity between Haar and i.i.d. Gaussian matrices, we arrive at the following two lemmas:

conditioned on $\Theta$ and $\mathcal{X}_{t,t}$ for $t>0$, and for all $\tau<t+1$

conditioned on $\boldsymbol{a}$, $\Theta$, and $\mathcal{X}_{t,t}$ in the large system limit.

conditioned on $\boldsymbol{a}$, $\Theta$, and $\mathcal{X}_{t,t+1}$ in the large system limit.

In order to prove Theorem 2, we need the strong law of large numbers for the elements of a Haar matrix, which are dependent random variables.

IV-B Sketch of Proof by Induction

We are ready to prove Theorem 2. The proof is by induction. We omit the proof for the case $\tau=0$, and only present a sketch of the proof for a general case, because of space limitation.

We assume that Theorem 2 is correct for all $\tau<t$, and prove that Theorem 2 holds for $\tau=t$. Note that we can use Lemma 2, since the induction hypothesis (a) for $\tau<t$ implies that $\boldsymbol{M}_{t}$ and $\boldsymbol{Q}_{t^{\prime}}$ are full rank for $t^{\prime}=t$ and $t^{\prime}=t+1$.

We first prove (18) for $\tau=t$. We use (25), $\boldsymbol{\epsilon}_{1,t}=\boldsymbol{o}(1)$, and Lemma 4 to have

For $\tau^{\prime}=t$, (25) and Lemma 4 imply

To prove (17) for $\tau=t$, we repeat the same proof to obtain

conditioned on $\Theta$ and $\mathcal{X}_{t,t}$, where we have used the induction hypothesis (17) for $\tau<t$.

Let us prove (19) and (20) for $\tau=t$. Using (5), (13), (17), and (18), we obtain

in the large system limit. From (11) and (40), (19) holds.

Similarly, we use (11), (18), and (40) to obtain

in the large system limit. Using (13), (17), (18), and Assumption 2, we find that the second term reduces to (23) for $t^{\prime}=\tau^{\prime}$. Thus, (20) holds for $\tau=t$. ∎

The proof for the convergence of $\boldsymbol{h}_{t}$ is omitted, since it is the same as for the convergence of $\boldsymbol{b}_{t}$ to (15). ∎

The proof of (21) for $\tau=t$ is omitted, since it is the same as the proof for (18) with $\boldsymbol{D}=\boldsymbol{I}_{N}$. ∎

We only prove the existence of (14) for $\tau^{\prime}\leq\tau=t$, since the case $\tau^{\prime}=t+1$ can be proved in the same manner. Using (12) yields

The induction hypothesis (14) $\tau<t$ implies that the first term is convergent in the large system limit.

In order to prove the existence of (14) for $\tau^{\prime}\leq\tau=t$, it is sufficient to confirm

We use the strong law of large numbers [17, Theorem 6] and the property (b) for $\tau=t$ to have

We shall prove (22) for $\tau=t$. From (12) and (26), we find

conditioned on $\Theta$ and $\mathcal{X}_{t,t+1}$ for $\tau^{\prime}\leq t$, which is almost surely equal to zero, because of (19) for $\tau=t$. Thus, (22) holds for $\tau^{\prime}\leq\tau=t$.

We use (12) and (22) for $\tau^{\prime}=0$ and $\tau=t$ to have

for $\tau^{\prime}=t+1$. It is possible to prove

in the large system limit, by repeating the proof of (43).

We use Lemma 1, (8), and (22) to evaluate (14) as

Acknowledgment

The author was in part supported by the Grant-in-Aid for Exploratory Research (JSPS KAKENHI Grant Number 15K13987), Japan.

References