Phase retrieval with random Gaussian sensing vectors by alternating projections

Introduction

The problem of reconstructing a low-rank matrix from linear observations appears under many forms in the fields of inverse problems and machine learning. An important amount of work has thus been devoted to the design of reconstruction algorithms coming with provable reconstruction guarantees. The first algorithms of this kind relied mostly on convexification techniques. They tended to have a high recovery rate, but a possibly prohibitive computational complexity. As a result, a need has emerged to prove similar guarantees for algorithms based on non-convex formulations, which are generally much faster.

so reconstructing $x_{0}$ is equivalent to:

The vector $x_{0}$ is uniquely determined by the $m$ phaseless measurements as soon as $m\gtrsim 4n$ [Balan, Casazza, and Edidin, 2006]; however, reconstructing it is a priori NP-hard [Fickus, Mixon, Nelson, and Wang, 2014]. The oldest reconstruction algorithms [Gerchberg and Saxton, 1972; Fienup, 1982] were iterative: they started from a random initial guess of $x_{0}$, and tried to iteratively refine it by various heuristics. Although these algorithms are empirically seen to succeed in a number of cases, they can also get stuck in stagnation points, whose existence is due to the non-convexity of the problem.

To overcome these convergence problems, convexification methods have been introduced [Chai, Moscoso, and Papanicolaou, 2011; Candès, Strohmer, and Voroninski, 2013]. These methods consider the matricial formulation (1), but replace the non-convex rank constraint by a more favorable convex constraint. They provably reconstruct the unknown vector $x_{0}$ with high probability if the sensing vectors $a_{k}$ are “random enough” [Candès and Li, 2014; Candès, Li, and Soltanolkotabi, 2015; Gross, Krahmer, and Kueng, 2015]. Numerical experiments show that they also perform well on more structured, non-random phase retrieval problems [Waldspurger, d’Aspremont, and Mallat, 2015; Sun and Smith, 2012].

Unfortunately, this good precision comes at a high computational cost: optimizing the $n\times n$ matrix $X_{0}$ is much slower that directly reconstructing the $n$-dimensional vector $x_{0}$. Consequently, convexification techniques are impractical when the dimension of $x_{0}$ exceeds a few hundred. Authors have thus recently begun to design fast non-convex algorithms, for which it is possible to establish similar reconstruction guarantees as for convexified algorithms. The methods that have been developed rely on the following two-step scheme:

an initialization step, that returns a point close to the solution;

a gradient descent (possibly with additional refinements) over a well-chosen non-convex cost function.

The intuitive reason why this scheme works is that the cost function, although globally non-convex, enjoys some good geometrical property in a neighborhood of the solution (like convexity or a weak form of it [White, Sanghavi, and Ward, 2015]). So, if the point returned by the initialization step belongs to this neighborhood, gradient descent converges to the true solution.

A preliminary form of this scheme appears in [Netrapalli, Jain, and Sanghavi, 2013], with an alternating minimization in step (2) instead of a gradient descent. Then, considering the cost function

[Candès, Li, and Soltanolkotabi, 2015] proved the correctness of the two-step scheme, with high probability, in the regime $m=O(n\log n)$, for random independent Gaussian sensing vectors. In [Chen and Candès, 2015; Kolte and Özgür, 2016], the same result was shown in the regime $m=O(n)$ for a slightly different cost function, with additional truncation steps. In [Zhang and Liang, 2016], it was extended to the following non-smooth cost function:

Additionally, Sun, Qu, and Wright have shown that, in the regime $m=O(n\log^{3}n)$, the cost function (2) actually has no “bad critical point”, and the initialization step is not necessary: the gradient descent in step (2) converges to the global minimum of $L_{1}$, almost whatever initial point it starts from. These authors have also numerically observed that, in the regime $m=O(n)$, despite the potential presence of bad critical points, the gradient descent succeeds, with at least constant probability, starting from a random initialization.

In the case of phase retrieval, the most recently introduced non-convex algorithms are optimal in terms of both statistical and computational complexity, up to multiplicative constants. However, there is still a need to understand whether their theoretical reconstruction guarantees can be extended to more general classes of algorithms, that would not exactly follow the above two-step scheme, but would be closer to the algorithms that are actually used in applications. This in particular implies to answer the following two questions:

In Step (2), can we replace the explicit minimization of a cost function by a “less local” search, like alternating projections [Gerchberg and Saxton, 1972] or Douglas-Rachford [Bauschke, Combettes, and Luke, 2002]?

Is the initialization step (1) necessary, or can Step (2) converge to the global optimum even starting from a random initialization, at least in certain cases?

In this article, we answer the first question: we show that, in the optimal regime of $m=O(n)$ random independent Gaussian sensing vectors, replacing gradient descent with alternating projections yields exact recovery with high probability, and convergence occurs at a linear rate.

provided that alternating projections are correctly initialized, for example with the method described in [Chen and Candès, 2015].

Alternating projections, introduced by Gerchberg and Saxton , is the most ancient algorithm for phase retrieval. It is an intuitive method, whose implementation is extremely simple, and with no parameter to choose or tune; it is thus widely used. In terms of complexity, it is slower, for general measurements, than the best non-convex methods by only a logarithmic factor in the precision. For more “structured” measurements (as in all applications that we know of), it is as fast (see Paragraph 3.3).

We believe that the second question, about the necessity of the initialization step, is also important. In addition to being a natural theoretical question, it has practical consequences: the initialization procedure depends on the probability distribution of the sensing vectors, and, for some families of sensing vectors appearing in applications, we do not (yet) have a valid initialization procedure. We partially answer it in the case where the sensing vectors are independent and Gaussian, and reconstruction is done with alternating projections. We propose a description of when this method globally converges to the true solution, depending on the number of measurements and the initialization procedure. This description is summarized in Figure 1.

As shown in the figure, there is a regime in which the stagnation points of the alternating projections routine disappear (except possibly on a “small” set that we define), and, with high probability, alternating projections converge starting from any initialization outside the small set. This regime is $m=O(n^{2})$. Our numerical experiments clearly indicate that, below this regime, there are stagnation points. It is however possible that the attraction basin of the stagnation points is small: even in the regime $m=O(n)$, we numerically see that alternating projections, starting from a random isotropic initializationBy “isotropic”, we mean that the law of the initial vector is invariant under linear unitary transformations., succeed with probability close to $1$ despite the presence of stagnation points. We leave this assertion as a conjecture.

There exist $C_{1},C_{2},\gamma,M>0$, $\delta\in]0;1[$ such that, if $m\geq Mn^{2}$ and the sensing vectors are independently chosen according to complex normal distributions, with probability at least

starting from any initial point that does not belong to a small “bad set”.

Let any $\epsilon>0$ be fixed. When $m\geq Cn$, for $C>0$ large enough, alternating projections, starting from a random isotropic initialization, converge to the true solution with probability at least $1-\epsilon$.

These theorem and conjecture are the parallels for alternating projections of the results and numerical observations obtained by Sun, Qu, and Wright for gradient descent over the cost function (2). The “no stagnation point” regime is much less favorable in the case of alternating projections than in the case of gradient descent: $m=O(n^{2})\gg O(n\log^{3}n)$. It could be due to the discontinuity of the alternating projections operator, but we have no evidence to support this fact.

On the side of proof techniques, there has been a lot of work on the convergence of alternating projections in non-convex settings. Transversality arguments can be shown to prove, in certain cases, local convergence guarantees (“if the initial point is sufficiently close to the correct solution, alternating projections converge to this solution”). See for example [Lewis, Luke, and Malick, 2009; Drusvyatskiy, Ioffe, and Lewis, 2015]. These arguments can be used in phase retrieval, and yield local convergence results for relatively general families of sensing vectors (not necessarily random) [Noll and Rondepierre, 2016; Chen, Fannjiang, and Liu, 2016]. Unfortunately, they give no control on the convergence radius of the algorithm, so the obtained results have a mainly theoretical interest.

Bounding the convergence radius requires using the statistical properties of the sensing vectors. This was first attempted in [Netrapalli, Jain, and Sanghavi, 2013], where the authors proved the global convergence of a resampled version of the alternating projections algorithm. For a non resampled version, a preliminary result was given in [Soltanolkotabi, 2014]. However, the bound on the convergence radius that underlies this result is small. As a consequence, global convergence is only proven for a suboptimal number of measurements ($m=O(n\log^{2}n)$), and with a complex initialization procedure.

A difficulty that we encounter is the fact that the alternating projections operator is not continuous. This difficulty also appears in the two recent articles [Zhang and Liang, 2016; Wang, Giannakis, and Eldar, 2016], where the authors consider a gradient descent over a function whose gradient is not continuous. The proof that we give for our Theorem 4.1 follows a different path as theirs (it does not use a regularity condition); the statistical tools are however similar.

The article is organized as follows. Section 2 precisely defines phase retrieval problems and the alternating projections algorithm. Section 3 states and proves the first main result: the global convergence of alternating projections, with proper initialization, for $m=O(n)$ independent Gaussian measurements. Section 4 proves the second main result: stagnation points disappear in the regime $m=O(n^{2})$, making the initialization step useless. Finally, Section 5 presents numerical results, and conjectures that the alternating projections algorithm can succeed without special initialization in the regime $m=O(n)$, despite the presence of stagnation points. All technical lemmas are deferred to the appendices.

We denote by $A^{\dagger}$ its Moore-Penrose pseudo-inverse. We note that $AA^{\dagger}$ is the orthogonal projection onto $\operatorname{Range}(A)$.

Problem setup

This matrix is called the measurement matrix. The associated phase retrieval problem is:

As the modulus is invariant to multiplication by unitary complex numbers, we can never hope to reconstruct $x_{0}$ better than up to multiplication by a global phase. So, instead of exactly reconstructing $x_{0}$, we want to reconstruct $x_{1}$ such that

In all this article, we assume the sensing vectors to be independent realizations of centered Gaussian variables with identity covariance:

The measurement matrix is in particular independent from $x_{0}$.

Balan, Casazza, and Edidin and Conca, Edidin, Hering, and Vinzant have proved that, for generic measurement matrices $A$, Problem (3) always has a unique solution, up to a global phase, provided that $m\geq 4n-4$. In particular, with our measurement model (4), the reconstruction is guaranteed to be unique, with probability $1$, when $m\geq 4n-4$.

2 Alternating projections

The alternating projections method has been introduced for phase retrieval problems by Gerchberg and Saxton . It focuses on the reconstruction of $Ax_{0}$; if $A$ is injective, this then allows to recover $x_{0}$.

The two sets defining constraints (1) and (2) admit projections with simple analytical expressions, which leads to the following formulas:

If we define $z_{k}$ as the unique vector such that $y_{k}=Az_{k}$, an equivalent form of these equations is:

In particular, if $y_{\infty}$ has no zero entry,

Despite the relative simplicity of this characteristic property, it is extremely difficult to exactly compute the stagnation points, determine their attraction basin or avoid them when the algorithm happens to run into them.

The goal of this article is to show that, in certain settings, there are no stagnation points, or they can be avoided with a careful initialization procedure of the alternating projection routine.

Alternating projections with good initialization

In this section, we prove the first of our two main results: in the regime $m=O(n)$, the method of alternating projections converges to the correct solution with high probability, if it is carefully initialized.

This paragraph proves the key result that we will need to establish our statement. This result is a local contraction property of the alternating projections operator $x\to A^{\dagger}(b\odot\operatorname{phase}(Ax))$.

There exist $\epsilon,C_{1},C_{2},M>0$, and $\delta\in]0;1[$ such that, if $m\geq Mn$, then, with probability at least

The following lemma is proven in Paragraph B.1.

Two technical lemmas allow us to upper bound the terms of this sum. The first one is proved in Paragraph B.2, the second one in Paragraph B.3.

For any $\eta>0$, there exists $C_{1},C_{2},M,\gamma>0$ such that the inequality

holds for any $v\in\operatorname{Range}(A)$ such that $||v||<\gamma||Ax_{0}||$, with probability at least

For $M,C_{1}>0$ large enough, and $C_{2}>0$ small enough, when $m\geq Mn$, the property

holds for any $v\in\operatorname{Range}(A)\cap\{Ax_{0}\}^{\perp}$, with probability at least

We define $\gamma>0$ as in Lemma 3.3. The events described in Lemmas 3.3 and 3.4 hold with probability at least

the terms in Equation (8) can be bounded as in the lemmas, because

and $\frac{\mu_{x}}{\lambda_{x}}v^{x}\in\operatorname{Range}(A)\cap\{Ax_{0}\}^{\perp}$. So the following inequality holds:

Equation (10) implies in particular that, if Condition (11) holds,

To conclude, it is enough to control the norms of $A$ and $A^{\dagger}$ with the following classical result.

If $A$ is chosen according to Equation (4), then, for any $t$, with probability at least

From this proposition, if we choose $\delta,M,t$ such that

we have, for $m\geq Mn$, with probability at least $1-2e^{-mt^{2}}$, as soon as $\epsilon^{x}\leq\epsilon$,

We now combine this with Equation (12): with probability at least

2 Global convergence

In the last paragraph, we have seen that the alternating projections operator is contractive, with high probability, in an $\epsilon||x_{0}||$-neighborhood of the solution $x_{0}$. This implies that, if the starting point of alternating projections is at distance at most $\epsilon||x_{0}||$ from $x_{0}$, alternating projections converge to $x_{0}$. So if we have a way to find such an initial point, we obtain a globally convergent algorithm.

Several initialization methods have been proposed that achieve the precision we need with an optimal number of measurements, that is $m=O(n)$. Let us mention the truncated spectral initialization by Chen and Candès (improving upon the slightly suboptimal spectral initializations introduced by Netrapalli, Jain, and Sanghavi and Candès, Li, and Soltanolkotabi ), the null initialization by Chen, Fannjiang, and Liu and the method described by Gao and Xu . All these methods consist in computing the largest or smallest eigenvector of

where the $\alpha_{1},\dots,\alpha_{m}$ are carefully chosen coefficients, that depend only on $b$.

The method of [Chen and Candès, 2015], for example, has the following guarantees.

There exist $C_{1},C_{2},M>0$ such that, with probability at least

Combining this initialization procedure with alternating projections, we get Algorithm 1. As shown by the following corollary, it converges towards the correct solution, at a linear rate, with high probability, for $m=O(n)$.

There exist $C_{1},C_{2},M>0,\delta\in]0;1[$ such that, with probability at least

Let us fix $\epsilon,\delta\in]0;1[$ as in Theorem 3.1. Let us assume that the properties described in Theorems 3.1 and 3.6 hold; it happens on an event of probability at least

provided that $m\geq Mn$, for some constants $C_{1},C_{2},M>0$.

Let us prove that, on this event, Equation (14) also holds.

So, from Theorem 3.1, applied to $x=\lambda z_{0}$,

The same reasoning can be reapplied to also prove the equation for $t=2,3,\dots$. ∎

3 Complexity

Let $\eta>0$ be the relative precision that we want to achieve:

Let us compute the number of operations that Algorithm 1 requires to reach this precision.

Then, at each step of the for loop, the most costly operation is the multiplication by $A^{\dagger}$. When performed with the conjugate gradient method, it requires $O(mn\log(1/\eta))$ operations. To reach a precision equal to $\eta$, we need to perform $O(\log(1/\eta))$ iterations of the loop. So the total complexity of Algorithm 1 is

Let us mention that, when $A$ has a special structure, there may exist fast algorithms for the multiplication by $A$ and the orthogonal projection onto $\operatorname{Range}(A)$. In the case of masked Fourier measurements considered in [Candès, Li, and Soltanolkotabi, 2015], for example, assuming that our convergence theorem still holds, despite the non-Gaussianity of the measurements, the complexity of each of these operations reduces to $O(m\log n)$, yielding a global complexity of

The complexity is then almost linear in the number of measurements.

As a comparison, Truncated Wirtinger flow, which is currently the most efficient known method for phase retrieval from Gaussian measurements, has an identical complexity, up to a $\log(1/\eta)$ factor in the unstructured case (see Figure 2).

Alternating projections without good initialization

In this section, we assume that the number of measurements is quadratic in $n$ instead of linear (that is $m\geq Mn^{2}$, for $M$ large enough). In this setting, we show that any initialization vector $x$, unless it is almost orthogonal to the ground truth $x_{0}$, yields perfect recovery when provided to the alternating projection routine. This in particular proves that, in this regime, there is no stagnation point (unless possibly among the vectors almost orthogonal to $x_{0}$).

The convergence rate is almost as good as in the case where a good initialization is provided: after $O(\log n)$ iterations, it becomes linear.

for some fixed constant $\mu>0$. In what follows, we assume $\mu=1$, but it is only to simplify the notations; the same result would hold for any value of $\mu$.

To prove global convergence, we first need to understand what happens when we apply one iteration of the alternating projections routine to some vector $x$. We only consider vectors $x$ that are not almost orthogonal to $x_{0}$. We also do not consider vectors that are very close to $x_{0}$: these vectors are already taken care of by Theorem 3.1.

For any $\epsilon>0$, there exist $C_{1},C_{2},M,\delta>0$ such that, if $m\geq Mn^{2}$, then, with probability at least

Before proving this theorem, let us establish its main consequence : the global convergence of alternating projections starting from any initial point that is not almost orthogonal to $x_{0}$. The algorithm is summarized in Algorithm 2 and global convergence is proven in Corollary 4.2.

There exist $C_{1},C_{2},\gamma,M>0,\Delta\in]0;1[$ such that, with probability at least

From Theorem 3.1, there exist $C_{1}^{(1)},C_{2}^{(1)},\epsilon^{(1)},M^{(1)}>0$ such that, if $m\geq M^{(1)}n$, then, with probability at least

for some absolute constant $\delta^{(1)}\in]0;1[$. In the following, we assume that this event is realized.

We now use Theorem 4.1, for $\epsilon={\epsilon^{(1)}}^{2}/2$. Let $C_{1},C_{2},M,\delta>0$ be defined as in this theorem. We assume that the event described in the theorem is realized, which happens with probability at least $1-C_{1}\exp(-C_{2}n)$.

We consider the sequence $(z_{t})_{t\geq 0}$ defined in Algorithm 2, and distinguish two cases.

First, if the initial point $z_{0}=x$ is such that

then, setting $x^{\prime}=\frac{||x_{0}||}{||x||}x$,

We can thus proceed by recursion, as in the proof of Corollary 3.7, to show that:

So Equation (17) is satisfied, provided that we have chosen $\Delta\geq\delta^{(1)}$.

Second, we consider the case where the initial point $z_{0}=x$ is such that

Let then $\mathcal{T}$ be the smallest index $t$ such that the following inequality is not satisfied:

As $z_{0}=x$ is not almost orthogonal to $x_{0}$, we must have $\mathcal{T}\geq 1$. For any $t=0,\dots,\mathcal{T}-1$, Equation (16) of Theorem 4.1 ensures that

As Equation (20) is not satisfied, it means that

We can now apply the same reasoning as the one that led to Equation (19), and get

This implies Equation (17), provided that $\mathcal{T}\leq\gamma\log n$ for some absolute constant $\gamma$. From Equation (21) and the fact that $z_{0}$ is not almost orthogonal to $x_{0}$,

As $\mathcal{T}-1$ satisfies Equation (20), we must have

And this expression can be bounded by $\gamma\log n$, for some $\gamma>0$ independent from $n$.

So we have shown that Equation (17) holds when the events described in Theorems 3.1 and 4.1 happen. When $m\geq\max(M,M^{(1)})n^{2}$, this occurs with probability at least

2 Proof of Theorem 4.1

To prove Theorem 4.1, it is enough to prove that there exist $C_{1},C_{2},M,\delta>0$ such that, if $m\geq Mn^{2}$, then, with probability at least $1-C_{1}\exp(-C_{2}m^{1/8})$, the property

The proof of Equation (22) is in two parts. We first prove (Lemma 4.4) that this equation holds (with high probability) for all $x$ belonging to a net with very small spacing. This part is the most technical: a direct union bound, that does not take advantage of the correlation between the vectors of the net, is not sufficient. We use a chaining argument instead. The detailed proof is in Paragraph C.2.

In a second part (Lemma 4.5), we prove that, with high probability, for any $x$ and $y$ very close, $|\left\langle Ax_{0},b\odot\operatorname{phase}(Ax)\right\rangle-\left\langle Ax_{0},b\odot\operatorname{phase}(y)\right\rangle|$ is small. This allows us to extend the inequality proven for vectors of the net to all vectors. This result is a consequence of two facts: first, the phase is a Lipschitz function outside any neighborhood of zero. Second, with high probability, for any $x$ and $y$, the vectors $Ax$ and $Ay$ have few entries that are close to zero. The detailed proof is in Paragraph C.3.

the following property holds: for any $x\in\mathcal{N}_{n}$,

For any $c>0$, there exist $C_{1},C_{2},C_{3}>0$ such that, with probability at least

To conclude, we apply Lemma 4.4 with $\alpha=7/2$. We define $c,C_{1},C_{2},M,\delta>0$, the set $\mathcal{E}_{n}$ and the $cm^{-7/2}$-net $\mathcal{N}_{n}$ as in the statement of this lemma. With probability at least

By triangular inequality, and using Lemmas 4.4 and 4.5,

As $x^{\prime}$ belongs to $\mathcal{E}_{n}$, if $m\geq Mn^{2}$ and $m$ is large enough,

So we deduce from this and the inequality immediately before:

By Lemma 4.3, this is what we had to prove.

Numerical experiments

In this section, we numerically validate the results obtained in Corollaries 3.7 and 4.2. We formulate a conjecture about the convergence of alternating projections with random initialization, in the regime $m=O(n)$.

The code used to generate Figures 3, 4 and 6 is available at \urlhttp://www-math.mit.edu/ waldspur/code/alternating_projections_code.zip.

Our first experiment consists in a numerical validation of Corollary 3.7: alternating projections succeed with high probability, when they start from a good initial point, in the regime where the number of measurements is linear in the problem dimension ($m=O(n)$).

We use the initialization method described in [Chen and Candès, 2015], as presented in Algorithm 1. We run the algorithm for various choices of $n$ and $m$, $3000$ times for each choice. This allows us to compute an empirical probability of success, for each value of $(n,m)$.

The results are presented in Figure 3. They confirm that, when $m=Cn$, for a sufficiently large constant $C>0$, the success probability can be arbitrarily close to $1$.

2 Alternating projections without good initialization

Next, we investigate Corollary 4.2: if $m\geq Cn^{2}$, for $C>0$ large enough, the method of alternating projections succeeds, with high probability, starting from any initialization (that is not almost orthogonal to the true solution). In particular, there is no stagnation point, unless possibly among vectors that are almost orthogonal to the true solution.

To numerically validate this result, we have generated vectors $x_{0}$ of size $n$ and measurements matrices $A$ of size $m\times n$ for various choices of $n$ and $m$. For each $(x_{0},A)$, we have randomly chosen $10000$ initializations that were not almost orthogonal to $x_{0}$, and we have recorded whether alternating projections, starting from these initializations, always succeeded in reconstructing $x_{0}$ from $|Ax_{0}|$. When at least one of these initializations failed, it proved that there was at least one stagnation point. Otherwise, we have considered it as a sign of absence of stagnation points.

We could thus compute, for each choice of $(n,m)$, the probability of absence of stagnation point. The result is displayed on Figure 4. As foreseen by Corollary 4.2, the probability becomes arbitrarily close to $1$ when $m\geq Cn^{2}$ for $C>0$ large enough.

The same results are presented in Figure 5 under a different form. The graph on the left hand side shows, for each $n$, the number $M_{n}$ of measurements above which the probability that there is at least one stagnation point drops under $0.5$. The curve has a clear quadratic shape.

The plot on the right hand side represents $M_{n}/n^{2}$ as a function of $n$. It is clearly upper bounded by a constant. It also seems to be lower bounded by a positive constant (or possibly by a very slowly decaying function, like $(\log\log)^{-1}$), which indicates that the number of measurements $m=O(n^{2})$ that appears in Corollary 4.2 is probably optimal: when $m\ll n^{2}$, the probability that there are no stagnation points is small.

2.2 Random initialization

Our last experiment consists in measuring the probability that alternating projections succeed, when started from a random initial point (sampled from the unit sphere with uniform probability).

The results are presented in Figure 6. They lead to the following conjecture.

Let any $\epsilon>0$ be fixed. When $m\geq Cn$, for $C>0$ large enough, alternating projections with a random isotropic initialization succeed with probability at least $1-\epsilon$.

As we have seen in Paragraph 5.2.1, in the regime $m=O(n)$, there are (attractive) stagnation points, so there are initializations for which alternating projections fail. However, it seems that these bad initializations occupy a very small volume in the space of all possible initial points. Therefore, a random initialization leads to success with high probability.

Unfortunately, proving this conjecture a priori requires to evaluate in some way the size of the attraction basin of stagnation points, which seems difficult.

Appendix A Proposition 2.1

In particular, if $y_{\infty}$ has no zero entry,

Indeed, because the operators $y\to b\odot\operatorname{phase}(y)$ and $y\to(AA^{\dagger})y$ are projections,

If we pass to the limit the equalities $d(y_{\phi(n)},E_{b})=||y_{\phi(n)}-y^{\prime}_{\phi(n)}||$ and $d(y^{\prime}_{\phi(n)},\operatorname{Range}(A))=||y^{\prime}_{\phi(n)}-y_{\phi(n)+1}||$, we get

As $\operatorname{Range}(A)$ is convex, the projection of $y^{\prime}_{\infty}$ onto it is uniquely defined. This implies

and, because $\forall n,y_{\phi(n)+1}=(AA^{\dagger})y^{\prime}_{\phi(n)}$,

To conclude, we now have to show that $y^{\prime}_{\infty}=b\odot u$ for some $u\in E_{\operatorname{phase}}(y_{\infty})$. We use the fact that, for all $n$, $y^{\prime}_{\phi(n)}=b\odot\operatorname{phase}(y_{\phi(n)})$.

For any $i\in\{1,\dots,m\}$, if $(y_{\infty})_{i}\neq 0$, $\operatorname{phase}$ is continuous around $(y_{\infty})_{i}$, so $(y^{\prime}_{\infty})_{i}=b_{i}\operatorname{phase}((y_{\infty})_{i})$. We then set $u_{i}=\operatorname{phase}((y_{\infty})_{i})$, and we have $(y^{\prime}_{\infty})_{i}=b_{i}u_{i}$.

If $(y_{\infty})_{i}=0$, we set $u_{i}=\operatorname{phase}((y^{\prime}_{\infty})_{i})\in E_{\operatorname{phase}}(0)=E_{\operatorname{phase}}((y_{\infty})_{i})$. We then have $y^{\prime}_{\infty}=|y^{\prime}_{\infty}|u_{i}=b_{i}u_{i}$.

With this definition of $u$, we have, as claimed, $y^{\prime}_{\infty}=b\odot u$ and $u\in E_{\operatorname{phase}}(y_{\infty})$.

Appendix B Technical lemmas for Section 3

The inequality holds if $z_{0}=0$, so we can assume $z_{0}\neq 0$. We remark that, in this case,

It is thus enough to prove the lemma for $z_{0}=1$, so we make this assumption.

When $|z|\geq 1/6$, the inequality is valid. Let us now assume that $|z|<1/6$. Let $\theta\in\left]-\frac{\pi}{2};\frac{\pi}{2}\right[$ be such that

B.2 Proof of Lemma 3.3

For any $\eta>0$, there exists $C_{1},C_{2},M,\gamma>0$ such that the inequality

holds for any $v\in\operatorname{Range}(A)$ such that $||v||<\gamma||Ax_{0}||$, with probability at least

We use the following two lemmas, proven in Paragraphs B.2.1 and B.2.2.

Let $\beta\in]0;1/2[$ be fixed. There exist $C_{1}>0$ such that, with probability at least

the following property holds: for any $S\subset\{1,\dots,m\}$ such that $\operatorname{Card}(S)\geq\beta m$,

Let $\beta\in\left]0;\frac{1}{100}\right]$ be fixed. There exist $M,C_{1},C_{2}>0$ such that, if $m\geq Mn$, then, with probability at least

the following property holds: for any $S\subset\{1,\dots,m\}$ such that $\operatorname{Card}(S)<\beta m$ and for any $y\in\operatorname{Range}(A)$,

Let $\beta>0$ be such that $10\sqrt{\beta\log(1/\beta)}\leq\eta$. Let $M$ be as in Lemma B.2. We set

We assume that Equations (23) and (24) hold; from the lemmas, this occurs with probability at least

for some constants $C_{1}^{\prime},C_{2}^{\prime}>0$, provided that $m\geq Mn$.

On this event, for any $v\in\operatorname{Range}(A)$ such that $||v||<\gamma||Ax_{0}||$, if we set $S_{v}=\{i\mbox{ s.t. }|v_{i}|\geq|Ax_{0}|_{i}\}$, we have that

Indeed, if it was not the case, we would have, by Equation (23),

which is in contradiction with the way we have chosen $v$.

So we can apply Equation (24), and we get

If we choose $C_{1}$ large enough, it is enough to show the property for $m$ larger than some fixed constant.

We first assume $S$ fixed, with cardinality $\operatorname{Card}S\geq\beta m$. We use the following lemma.

From this lemma, for any $t\in]0;1[$, because $Ax_{0}$ has independent Gaussian coordinates,

In particular, for $t=\frac{\beta^{2}}{e}$,

As soon as $m$ is large enough, the number of subsets $S$ of $\{1,\dots,m\}$ with cardinality $\lceil\beta m\rceil$ satisfies

(The first inequality is a classical result regarding binomial coefficients.)

We combine Equations (25) and (26): Property (23) is satisfied for any $S$ of cardinality $\lceil\beta m\rceil$ with probability at least

provided that $m$ is larger that some constant which depends on $\beta$.

If it is satisfied for any $S$ of cardinality $\lceil\beta m\rceil$, then it is satisfied for any $S$ of cardinality larger than $\beta m$, which implies the result. ∎

B.2.2 Proof of Lemma B.2

We first assume $S$ to be fixed, of cardinality exactly $\lceil\beta m\rceil$.

where $A_{S}$, by definition, is the submatrix obtained from $A$ by extracting the rows whose indexes are in $S$.

We apply Proposition 3.5 to $A$ and $A_{S}$, respectively for $t=\frac{1}{2}$ and $t=3\sqrt{\log(1/\beta)}$. It guarantees that the following properties hold:

Assuming $m\geq Mn$ for some $M>0$, we deduce from these inequalities that

If we choose $M$ large enough, we can upper bound Equation (28) by $(\epsilon+2\sqrt{\beta}(1+3\sqrt{\log(1/\beta)}))||Av||\leq(\epsilon+8\sqrt{\beta}\sqrt{\log(1/\beta)})$ for any fixed $\epsilon>0$. So this inequality implies Equation (27).

As in the proof of Lemma B.1, there are at most

so the resulting probability is larger than

for some well-chosen constants $C_{1},C_{2}>0$.

This ends the proof. Indeed, if Equation (27) holds for any set of cardinality $\lceil\beta m\rceil$, it also holds for any set of cardinality $\operatorname{Card}S<\beta m$, because $||A_{S^{\prime}}v||\leq||A_{S}v||$ whenever $S^{\prime}\subset S$. This implies Equation (24). ∎

B.3 Proof of Lemma 3.4

For $M,C_{1}>0$ large enough, and $C_{2}>0$ small enough, when $m\geq Mn$, the property

holds for any $v\in\operatorname{Range}(A)\cap\{Ax_{0}\}^{\perp}$, with probability at least

If we multiply $x_{0}$ by a positive real number, we can assume $||x_{0}||=1$. Moreover, as the law of $A$ is invariant under right multiplication by a unitary matrix, we can assume that

Then, if we write $A_{1}$ the first column of $A$, and $A_{2:n}$ the submatrix of $A$ obtained by removing this first column,

We take $t=\frac{m}{n-1}(0.04)^{2}$ (which is larger than $1$ when $m\geq Mn$ with $M>0$ large enough), and it implies that

for some constant $c_{2}>0$, provided that $m\geq Mn$ with $M$ large enough.

Second, as $A_{2:n}$ is a random matrix of size $m\times(n-1)$, whose entries are independent and distributed according to the law $\mathcal{N}(0,1/2)+\mathcal{N}(0,1/2)i$, we deduce from Proposition 3.5 applied with $t=0.01$ that, with probability at least

When Equations (32) and (33) are simultaneously valid, any $w=A_{2:n}w^{\prime}$ belonging to $\operatorname{Range}(A_{2:n})$ satisfies:

We now conclude. Equations (31), (32) and (33) hold simultaneously with probability at least

for any $C_{1}$ large enough and $C_{2}$ small enough, provided that $m\geq Mn$ with $M$ large enough. Let us show that, on this event, Equation (29) also holds. Any $v\in\operatorname{Range}(A)\cap\{Ax_{0}\}^{\perp}$, from Equality (30), can be written as

for some $w\in\operatorname{Range}(A_{2:n})$. Using Equation (31), then Equation (34), we get:

Appendix C Technical lemmas for Section 4

To prove Theorem 4.1, it is enough to prove that there exist $C_{1},C_{2},M,\delta>0$ such that, if $m\geq Mn^{2}$, then, with probability at least $1-C_{1}\exp(-C_{2}m^{1/8})$, the property

Let us define $\lambda_{1}(A)\geq\dots\geq\lambda_{n}(A)$ to be the $n$ singular values of $A$. From Proposition 3.5, setting $t=\delta^{\prime}/\sqrt{n}$ for $\delta^{\prime}$ small enough, if $M$ is high enough, we have with probability larger than $1-C_{1}\exp(-C_{2}m/n)\geq 1-C_{1}\exp(-C_{2}m^{1/2})$,

In this case, we have in particular, for any $x$ satisfying Equation (15),

So when $x$ satisfies Equations (15) and (22),

So Equation (16) is also satisfied (although for a smaller value of $\delta$). ∎

C.2 Proof of Lemma 4.4

the following property holds: for any $x\in\mathcal{N}_{n}$,

where $\mathcal{V}_{n}^{k}$ is a $2^{-(k+1)}$-net of the unit sphere, and, for any $y$, $P_{\mathcal{E}_{n}}(y)$ is a point in $\mathcal{E}_{n}$ whose distance to $y$ is minimal. From [Vershynin, 2012, Lemma 5.2], this implies that we can choose $\mathcal{M}_{n}^{k}$ such that

(where the expectation denotes the expectation over $A$ with $x_{0}$ and $x$ fixed).

the following property holds: for any $x\in\mathcal{M}_{n}^{k},y\in\mathcal{M}_{n}^{k+1}$ such that $||x-y||\leq 2^{-(k-1)}$,

In the case $k=0$, we additionally have, with the same probability: for all $x\in\mathcal{M}_{n}^{0}$,

Let $\eta,\mathcal{A}>0$ be temporarily fixed. We set $K=\lceil\mathcal{A}\log m-c\rceil$. The event described in the previous lemma holds for all $k\leq K-1$ with probability at least $1-KC_{1}\exp(-C_{2}m^{1/2})$.

For any $x\in\mathcal{M}_{n}^{K}$, there exists a sequence $(y_{0},y_{1},\dots,y_{K-1},y_{K})$ such that

So when the event of Lemma C.1 holds, we have, for any $x\in\mathcal{M}_{n}^{K}$,

To conclude, we only have to evaluate $F$. This is done by the following lemma, proven in Paragraph C.2.2.

There exist $\delta>0$ such that, for any $x\in\mathcal{E}_{n}$,

We combine this lemma and the equation before the lemma: with probability at least $1-KC_{1}\exp(-C_{2}m^{1/2})$, for any $x\in\mathcal{M}_{n}^{K}$,

For the last inequality, we have used the fact that $x\in\mathcal{E}_{n}$, so $|\left\langle x_{0},x\right\rangle|\geq||x_{0}||\,||x||/\sqrt{n}$.

We can choose $\eta>0$ sufficiently small so that $1+\delta-\eta\left(1+\frac{\pi^{2}}{6}\right)>1+\frac{\delta}{2}$. We fix $\mathcal{A}$ to be any real number larger than $\alpha/\log 2$. Then, from the definition of $K$,

As $K\leq\mathcal{A}\log m-c+1$, we can upper bound $1-KC_{1}\exp(-C_{2}m^{1/2})$ by $1-C_{1}^{\prime}\exp(-C_{2}^{\prime}m^{1/2})$, for $C^{\prime}_{1},C^{\prime}_{2}>0$ well-chosen. If we summarize, we get that, with probability at least $1-C_{1}^{\prime}\exp(-C_{2}^{\prime}m^{1/2})$,

and $\mathcal{M}_{n}^{K}$ is a $2^{c}m^{-\alpha}$-net of $\mathcal{E}_{n}$. The lemma is proved. ∎

the following property holds: for any $x\in\mathcal{M}_{n}^{k},y\in\mathcal{M}_{n}^{k+1}$ such that $||x-y||\leq 2^{-(k-1)}$,

In the case $k=0$, we additionally have, with the same probability: for all $x\in\mathcal{M}_{n}^{0}$,

We only prove the first part of the lemma. The proof of the second one follows the same principle.

As our expressions are all homogeneous in $x_{0}$, we can assume that $||x_{0}||=1$.

For any $j=1,\dots,m$, let us denote by $a_{j}^{*}$ the $j$-th line of $A$. We have

As all the $a_{j}^{*}$ are identically distributed,

Were there no terms “$|a_{j}^{*}x_{0}|^{2}$” in Equation (36), we could apply Bennett’s concentration inequality: the random variables $Z_{j}$ are bounded by $2$ in modulus, and, as we are going to see, their variance is small if $x$ and $y$ are close. Bennett’s inequality would then guarantee that the term in Equation (36) is small with high probability. Unfortunately, the $|a_{j}^{*}x_{0}|^{2}$ are not almost surely bounded, so we cannot directly apply Bennett’s inequality.

To overcome this problem, we first condition over $Ax_{0}$. When conditioned over $Ax_{0}$, the random variables $|a_{j}^{*}x_{0}|^{2}Z_{j}$ are almost surely bounded; we will prove that they still have a small variance. We still cannot directly apply Bennett’s inequality, because the bounds depend on $j$, but we can adapt its proof, and get a concentration inequality for the following sum:

After that, we will also need to derive a concentration inequality for

The first step is to control the distribution of the $|a_{j}^{*}x_{0}|$. The idea is that there are a few indexes $j$ for which $|a_{j}^{*}x_{0}|$ is large, but these are sufficiently rare so that the sum $\sum_{j}|a_{j}^{*}x_{0}|^{2}Z_{j}$, when conditioned over $Ax_{0}$, essentially behaves as if all random variables were bounded by the same constant.

The proof of the following lemma is in Paragraph C.2.3.

For some constants $C_{1},C_{2}>0$, the following event happens with probability at least $1-C_{1}e^{-C_{2}\sqrt{m}}$: for any $s\in\{1,\dots,\lfloor m^{1/4}\rfloor\}$,

Let us denote by $\mathcal{E}_{0}$ the event described in the previous lemma:

The second step is to get an upper bound on the variance of the $Z_{j}$, conditioned by $Ax_{0}$. The proof of the following lemma is in Paragraph C.2.4.

There exists a constant $C>0$ depending only on $\epsilon$ such that, for any fixed unit-normed $x,y$ such that

From the previous lemma, we deduce that, if $x\in\mathcal{M}_{n}^{k},y\in\mathcal{M}_{n}^{k+1}$ are fixed and satisfy $||x-y||\leq 2^{-(k-1)}$, we have

where $\gamma$ can be any real number in $]1;2[$, and $C^{\prime}>0$ is a large enough constant (depending on $\gamma$).

To follow the proof of Bennett’s inequality, we now have to upper bound, for suitable values of $\lambda>0$,

We use here the fact that, even when conditioned on $Ax_{0}$, the $Z_{j}$ are independent random variables.

The upper bound relies on the following lemma, proven in Paragraph C.2.5.

From Equation (39) and the previous lemma, for any $\lambda\geq 0$,

On the event $\mathcal{E}_{0}$ defined in Equation (37), we can simplify the sum inside the exponential. Specifically, if we define the function

By a direct computation, we see that, if $C>0$ is properly chosen, we can bound:

We plug this inequality into Equation (40). For any $\lambda\geq 0$, we set

and, on the event $\mathcal{E}_{0}$, we have:

We upper bound the sum of the integrals, using standard analysis techniques. The detailed proof is in Paragraph C.2.6.

With this definition, Conditions (42a) and (42b) are satisfied. Indeed, as $\gamma>1$,

if $m$ is large enough. For the second condition, because of Equation (43),

if $m$ is large enough. (In the second inequality, $c>0$ is a positive constant.)

As the two conditions are satisfied, we can combine Lemma C.6 and Equation (41). We get that, on the event $\mathcal{E}_{0}$,

So, by Markov’s inequality, on the event $\mathcal{E}_{0}$, if $m\geq n^{2}$,

We begin with the following lemma, proven in Paragraph C.2.7.

There exist a constant $C>0$ depending only on $\epsilon$ such that, for any fixed unit-normed $x,y$ such that

To simplify the expressions, we still assume that $||x_{0}||=1$. If $||x-y||\leq 2^{-(k-1)}$, the previous lemma guarantees that, for any $j$,

where $\gamma$ is still our real number in $]1;2[$.

There exist constants $c,C^{\prime}>0$, that depend only on $\gamma$ and $\epsilon$, such that, for any $\lambda\in[-c;c]$,

We are close to the end. The previous equation, combined with Equation (44) yields, by triangular inequality, that for any fixed $x\in\mathcal{M}_{n}^{k},y\in\mathcal{M}_{n}^{k+1}$ such that $||x-y||\leq 2^{-(k-1)}$,

where $\mathcal{C}$ is a constant that depends only on $\eta,\epsilon$ and $\gamma$. We recall that $Z_{j}$ depends on $x$ and $y$, although it does not appear in the notation.

The number of possible pairs $(x,y)\in\mathcal{M}_{n}^{k}\times\mathcal{M}_{n}^{k+1}$ is then bounded by

From Lemma C.3, the probability of $\mathcal{E}_{0}$ is at least $1-C_{1}e^{-C_{2}m^{1/2}}$ for some constants $C_{1},C_{2}>0$, so

When $M>0$ is large enough, this can be lower bounded by $1-C_{1}\exp(-C_{2}m^{1/2})$, where the constants $C_{1},C_{2}>0$ depend on $\eta,\epsilon$ and $\gamma$ but not on $k,m$ or $n$.

We recall Equations (43) and (46): the reasoning holds only for the values of $k$ such that

where, again, $\alpha>0$ is a constant that depends only on $\eta,\epsilon$ and $\gamma$. This means that, if we have chosen $\gamma\in]1;2[$ sufficiently close to $1$, it holds for any $k$ satisfying

C.2.2 Proof of Lemma C.2

There exist $\delta>0$ such that, for any $x\in\mathcal{E}_{n}$,

where $Z_{1}=\frac{(Ax_{0})_{1}}{||x_{0}||}$ and $Z_{2}=\operatorname{phase}(\beta/\alpha)(Ax^{\prime})_{1}$ are independent complex Gaussian variables with variance $1$.

The expectation cannot be analytically computed, but it can be lower bounded by a simple function. The following lemma is proven in Paragraph C.2.9.

The function $f$ is real-valued. For any $\gamma>0$, there exist $\delta>0$ such that

As $x$ belongs to $\mathcal{E}_{n}$, we have:

Consequently, we can apply the lemma with $\gamma=\sqrt{\frac{1}{(1-\epsilon)^{2}}-1}$. It implies that, for some $\delta>0$ that depends only on $\epsilon$,

C.2.3 Proof of Lemma C.3

For some constants $C_{1},C_{2}>0$, the following event happens with probability at least $1-C_{1}e^{-C_{2}\sqrt{m}}$: for any $s\in\{1,\dots,\lfloor m^{1/4}\rfloor\}$,

for some absolute constant $c_{1}>0$. As $s\leq\sqrt{\log m}$, this yields:

Second, we consider the values of $s$ in $\{\left\lfloor\sqrt{\log m}\right\rfloor+1,\dots,\lfloor m^{1/4}+1\rfloor\}$.

as soon as $m$ is large enough. For (a), we have used the inequality $s\geq\sqrt{\log m}$.

for $s=\lfloor m^{1/4}+1\rfloor>m^{1/4}$, we must have

So we see that the desired event holds, for $m$ large enough, with probability at least

which can be bounded by $1-C_{1}e^{-C_{2}\sqrt{m}}$ for $C_{1},C_{2}>0$ well-chosen. ∎

C.2.4 Proof of Lemma C.4

There exists a constant $C>0$ depending only on $\epsilon$ such that, for any fixed unit-normed $x,y$ such that

By the definition of $Z_{j}$, it suffices to prove

As $|Z_{j}|$ is bounded (by $2$), the desired inequality is true for $||x-y||\geq\sqrt{\epsilon}/2$, provided that $C$ is large enough, so we can assume $||x-y||<\sqrt{\epsilon}/2$, which in particular guarantees that $|\beta|>1/2$.

we only need, in order to prove Equation (48), to show that, for some constant $C>0$,

and $\frac{a_{j}^{*}x^{\prime}}{||x^{\prime}||}$ is a complex Gaussian random variable with variance $1$, independent from $Ax_{0}$ and $a_{j}^{*}y^{\prime\prime}$. So

We upper bound this quantity with the following proposition, proven in Paragraph C.2.10.

For some constant $c_{1}>0$, the following inequalities are true:

For $(*)$, we have used the fact that $t\to t^{2}\max(1,\log(1/t))$ is non-decreasing. For the last two lines, we have used this same fact and Equations (49a), (49b) and (49c).

The random variable $a_{j}^{*}y^{\prime\prime}$ is complex and Gaussian, has variance $||y^{\prime\prime}||^{2}$ and is independent from $Ax_{0}$, so, taking the expectation over $a_{j}^{*}y^{\prime\prime}$ then using Equation (49d), we get:

As $||x-y||\leq 2$ (because $x$ and $y$ are unit-normed), this implies Equation (50) and concludes. ∎

C.2.5 Proof of Lemma C.5

C.2.6 Proof of Lemma C.6

As we only consider the function $f_{\lambda}$ on $]1;+\infty[$, we can upper bound it by the slightly simpler expression

Let $X_{0}$ be the (unique) positive number such that

and if $X_{0}>2m^{1/4}$, from the definition of $X_{0}$, we see that

We separately study each of the three right-side terms.

For Term (53), we can do an exact computation, taking into account the fact that $\lambda\leq 1/40$:

For Term (54), if $X_{0}<\sqrt{\log m}+1$, then it is zero. Otherwise, $X_{0}\geq\sqrt{\log m}+1$ and

When $\frac{8}{C^{\prime}}\lambda\gamma^{2k}\leq 1$, we check from the definition of $X_{0}$ (Equation (52)) that $\lambda X_{0}^{2}\leq 1$, so $2\sqrt{\lambda}X_{0}\leq 2$ and

From Equation (52) again, we see that, as $\lambda X_{0}^{2}\leq 1$,

From Condition (42a), we know that $\left(\frac{\gamma^{k}}{\lambda}\right)^{4/3}\leq m^{1/2}$, so

On the other hand, when $\frac{8}{C^{\prime}}\lambda\gamma^{2k}>1$, $2\sqrt{\lambda}X_{0}$ is bounded away from zero. We evaluate the integral in Equation (56) by parts:

From Equation (52), we can compute that, when $2\sqrt{\lambda}X_{0}$ is bounded away from zero,

which yields, together with Condition (42b):

Finally, we consider the last term. When $X_{0}\geq m^{1/4}+1$, it is zero, so we only have to consider the case where $X_{0}<m^{1/4}+1$.

The second part of Equation (58) can be upper bounded as desired, thanks to Condition (42b):

For the first part, let us distinguish the cases $\frac{8}{C^{\prime}}\lambda\gamma^{2k}\leq 1$ and $\frac{8}{C^{\prime}}\lambda\gamma^{2k}>1$.

In the case where $\frac{8}{C^{\prime}}\lambda\gamma^{2k}\leq 1$, we see (in a similar way as in Equation (57)) that

For the last equality, we have used Condition (42a).

In the case where $\frac{8}{C^{\prime}}\lambda\gamma^{2k}>1$, as we have already seen, $\sqrt{\lambda}X_{0}$ is bounded away from , so, for some constant $C^{\prime\prime\prime}>0$,

Finally, we combine Equations (59), (60) and (62). With Equation (58), they show that

C.2.7 Proof of Lemma C.7

There exist a constant $C>0$ depending only on $\epsilon$ such that, for any fixed unit-normed $x,y$ such that

As $Z_{j}=\operatorname{phase}(a_{j}^{*}x)\operatorname{phase}(\overline{a_{j}^{*}x_{0}})-\operatorname{phase}(a_{j}^{*}y)\operatorname{phase}(\overline{a_{j}^{*}x_{0}})$,

The variable $Z_{j}$ is bounded in modulus by $2$, so the desired inequality holds for $||x-y||\geq\sqrt{\epsilon}/2$ if we choose $C\geq 4/\sqrt{\epsilon}$. In what follows, we assume that $||x-y||<\sqrt{\epsilon}/2$, which notably guarantees that $|\beta|>1/2$.

The random variables $a_{j}^{*}x_{0},a_{j}^{*}x^{\prime}$ and $a_{j}^{*}y^{\prime\prime}$ are independent complex Gaussians, with respective variances $||x_{0}||^{2},||x^{\prime}||^{2},||y^{\prime\prime}||^{2}$. Thus,

is Lipschitz (as can be seen by derivation under the integral sign). If we denote by $D>0$ the Lipschitz constant, Equations (63) and (64) imply that

For the last two inequalities, we have used Equations (49a) to (49d). We finally take the expectation over $a_{j}^{*}y^{\prime\prime}$; by triangular inequality,

when $C>0$ is large enough. Additionally,

C.2.8 Proof of Lemma C.8

There exist constants $c,C^{\prime}>0$, that depend only on $\gamma$ and $\epsilon$, such that, for any $\lambda\in[-c;c]$,

We only prove the first inequality; the proof of the second one is identical. We assume that $\lambda$ is positive; the same reasoning holds with minor modifications when $\lambda$ is negative.

As a consequence, because $a_{j}^{*}x_{0}$ is a complex Gaussian random variable with variance $||x_{0}||^{2}=1$,

Combining this with Equation (45), we see that there exists a constant $C^{\prime\prime}>0$ such that

We need to show that both components (65) and (66) are upper bounded by $C^{\prime}\lambda^{2}\gamma^{-2k}$ for some constant $C^{\prime}>0$ sufficiently large, provided that $|\lambda|\leq c$ for some constant $c>0$.

For Term (65), we use the fact that, when $r\leq C^{\prime\prime-1/3}\gamma^{k/3}\lambda^{-1/3}$,

For the second term of this sum, if we assume that

For the last inequality, we have used the fact that there exists a constant $D>0$ such that $e^{-x}\leq Dx^{-5/2}$, for all $x>0$.

For Term (66), still under the assumption $\lambda<1/(4C^{\prime\prime})$,

For Inequality $(*)$, we have used the existence of a constant $D$ such that, for all $k$, $\gamma^{3k}e^{-\gamma^{2k}/2}\leq D\gamma^{-2k}$ and, for all $\lambda$ staying in a bounded interval, $\sqrt{\lambda}e^{-1/(4\lambda C^{\prime\prime})}\leq D\lambda^{4}$.

Equations (68) and (69), combined with Equation (66), show that, when $\lambda<1/(4C^{\prime\prime})$,

for some constant $C^{\prime}>0$ that depends only upon $\gamma$. ∎

C.2.9 Proof of Lemma C.9

The function $f$ is real-valued. For any $\gamma>0$, there exist $\delta>0$ such that

As $(\overline{Z}_{1},\overline{Z}_{2})$ has the same distribution as $(Z_{1},Z_{2})$,

so $f(t)$ is a real number, for any $t\geq 0$.