Invertibility and Robustness of Phaseless Reconstruction

Introduction

This paper is concerned with the question of reconstructing a vector $x$ in a finite-dimensional real Hilbert space $H$ of dimension $n$ when only the magnitudes of the coefficients of the vector under a redundant linear map are known.

Specifically our problem is to reconstruct $x\in H$ up to a global phase factor from the magnitudes $\{|{\langle x,f_{k}\rangle}|~{},~{}1\leq k\leq m\}$ where $\mathcal{F}=\{f_{1},\mathinner{\cdotp\cdotp\cdotp},f_{m}\}$ is a frame (complete system) for $H$.

A previous paper described the importance of this problem to signal processing, in particular to the analysis of speech. Of particular interest is the case when the coefficients are obtained from a Windowed Fourier Transform (also known as Short-Time Fourier Transform), or an Undecimated Wavelet Transform (in audio and image signal processing). A similar problem appears in Quantum Information (QI) literature (see e.g. ). However some important differences are notable: first the unknown objects to be reconstructed are quantum states (meaning nonnegative symmetric operators of unit trace); secondly, measurements are performed by taking Hilbert-Schmidt inner products against some (nonnegative) symmetric operators of rank not necessarily one. In QI language our problem is to reconstruct rank one nonnegative symmetric operators from measurements against a set of rank one nonnegative symmetric operators.

While presents some necessary and sufficient conditions for reconstruction, the general problem of finding fast/efficient algorithms is still open. In we describe one solution in the case of STFT coefficients.

For vectors in real Hilbert spaces, the reconstruction problem is easily shown to be equivalent to a combinatorial problem. In this problem is further proved to be equivalent to a (nonconvex) optimization problem.

A different approach (which we called the algebraic approach) was proposed in . While it applies to both real and complex cases, noisless and noisy cases, the approach requires solving a linear system of size exponentially in space dimension. This algebraic approach generalizes the approach in where reconstruction is performed with complexity $O(n^{2})$ (plus computation of the principal eigenvector for a matrix of size $n$). However this method requires $m=O(n^{2})$ frame vectors.

Recently the authors of developed a convex optimization algorithm (a SemiDefinite Program called PhaseLift) and proved its ability to perform exact reconstruction in the absence of noise, as well as its stability under noise conditions. In a separate paper , the authors further developed a similar algorithm in the case of windowed DFT transforms. Inspired by the PhaseLift and MaxCut algorithms, but operating in the coefficients space, the authors of proposed a SemiDefinite Program called PhaseCut. They show the algorithm yields the exact solution in the absence of noise under similar conditions as PhaseLift.

The paper presents an iterative regularized least-square algorithm for inverting the nonlinear map and compares its performance to a Cramer-Rao lower bound for this problem in the real case. The paper also presents some new injectivity results which are incorporated into this paper.

A different approach is proposed in . There the authors use a 4-term polarization identity together with a family of spectral expander graphs to design a frame of bounded redundancy ($\frac{m}{n}\leq 236$) that yields an exact reconstruction algorithm in the absence of noise.

The authors of study several robustness bounds to the phase recovery problem in the real case. However their approach is different than ours in several respects. First they consider a probabilistic setup of this problem, where data $x$ and frame vectors $f_{j}$’s are random vectors with probabilities from a class of subgaussian distributions. Additionally, their focus is on classes of $k$-sparse signals. Their results show that, with high probability, recovery is possible from a number of measurements $m$ that has a similar asymptotic behavior with respect to $n$ and $k$ as in the case of linear measurements (that is with the phase). In our paper we analyze stability bounds of reconstruction for a fixed frame using deterministic analytic tools. After that we present asymptotic behavior of these bounds for random frames.

Finally, the authors of analyze the phaseless reconstruction problem for both the real and complex case. In the real case the authors obtain the exact upper Lipschitz constant for the nonlinear map ${\alpha_{\mathcal{F}}}$, namely $\sqrt{B}$ where $B$ is the upper frame bound. For the lower Lipschitz constant, they give an estimate between two computable singular eienvalues. Our results have overlaps with their results somewhat here. However, in this paper we improve the improve the lower Lipschitz constant by giving its exact value. There are some significant differences between this paper and . In addition to studying of the Lipschitz property of the map ${\alpha_{\mathcal{F}}}$ we focus also on two related but different settings. First we study the robustness of the reconstruction given a fixed error allowance in measurements. Second we also consider the Lipschitz property of the map ${\alpha_{\mathcal{F}}}^{2}$. The authors of point out that the map ${\alpha_{\mathcal{F}}}^{2}$ is not bi-Lipschitz. However in our paper we show ${\alpha_{\mathcal{F}}}^{2}$ becomes bi-Lipschitz for a different metric on the domain. With this metric (the one induced by the nuclear norm on the set of symmetric operators) the nonlinear map ${\alpha_{\mathcal{F}}}^{2}$ is bi-Lipschitz with constants indicated in Theorem 4.5. Furthermore the same conclusion holds true in the complex case, although this will be studied elsewhere.

The organization of the paper is as follows. Section 2 formally defines the problem and reviews existing inversion results in the real case. Section 3 establishes information theoretic performance bounds, namely the Cramer-Rao lower bound. Section 4 contains robustness measures of any reconstruction algorithm. Section 5 presents a stochastic analysis of these bounds, and is followed by references.

Background

When we can choose $A=B$ the frame is said tight. For $A=B=1$ the frame is called Parseval. The frame matrix corresponding to $\mathcal{F}$ is defined as $F=[f_{1},f_{2},\dots,f_{m}]$ with the vectors $f_{j}\in\mathcal{F}$ as its columns. We shall frequently identify $\mathcal{F}$ with its corresponding frame matrix $F$. The largest $A$ and smallest $B$ in (2.1) are called the lower frame bound and upper frame bound of $\mathcal{F}$, and they are given by

Thus the phaseless reconstruction problems aims to reconstruct $\hat{x}\in\hat{H}$ from the map ${\alpha_{\mathcal{F}}}(x)$. We say a frame $\mathcal{F}$ is phase retrievable if one can reconstruct $\hat{x}\in\hat{H}$ for all $\hat{x}$, or in other words, ${\alpha_{\mathcal{F}}}$ is injective on $\hat{H}$. The main objective of this paper is to analyze robustness and stability of the inversion map, and to give performance bounds of any reconstruction algorithm.

If $\mathcal{F}$ is phase retrievable in $\hat{H}$ then $m\geq 2n-1$. Furthermore, for a generic $\mathcal{F}$ with $m\geq 2n-1$ the map ${\alpha_{\mathcal{F}}}$ is phase retrievable in $\hat{H}$.

Let $m=2n-1$. Then $\mathcal{F}$ is phase retrievable in $\hat{H}$ if an only if $\mathcal{F}$ is full spark.

Then $\mathcal{F}$ is phase retrievable in $\hat{H}$ if and only if $a_{0}>0$.

Proof. The results (1)-(3) are in , and (4)-(5) are in .

Information Theoretic Performance Bounds

In this section we derive expressions for the Fisher Information Matrix and obtain performance bounds for reconstruction algorithms in the noisy case.

Consider the following noisy measurement process:

where the noise model is AWGN (additive white Gaussian noise): each random variable $\nu_{k}$ is independent and normally distributed with zero mean and $\sigma^{2}$ variance.

Under these assumptions we compute the Fisher Information matrix (see ). This is given by

where the likelihood function $L(x)$ is given by

Note the matrix $R(x)$ is exactly the same as the matrix introduced in (2.6). Thus we obtain the following results:

This allows to state the following performance bound result (see for details on the Cramer-Rao lower bound).

Furthermore, any efficient estimator (that is, any unbiased estimator ${\omega}$ that achieves the Cramer-Rao Lower Bound (3.6)) has the covariance matrix bounded from above by

Robustness Measures for Reconstruction

In this section we analyze the robustness of deterministic phaseless reconstruction. Additionally we connect the constant $a_{0}$ introduced earlier in Theorem 2.1 to quantities directly computable from the frame $\mathcal{F}$.

The size of $Q_{\varepsilon}(x)$ measures the worst case stability of the reconstruction for the vector $x$, under the assumption that the total noise level is controlled by $\varepsilon$. We also study the global stability by analyzing the measures

Here $\|.\|$ denotes usual Euclidian norm. Note that $Q_{\varepsilon}(x)$ has the scaling property $Q_{\varepsilon}(x)=Q_{|c|\varepsilon}(cx)$ for any real $c\neq 0$. Thus it is natural to focus on unit vectors $x$.

We introduce now some quantities that play key roles in the estimation of these robustness measures. For the frame $\mathcal{F}$ let $F=[f_{1},f_{2},\cdots,f_{m}]$ be its frame matrix. Denote by $\mathcal{F}[S]=\{f_{k}~{},~{}k\in S\}$ the subset of $\mathcal{F}$ indexed by a subset $S\subseteq\{1,2,\mathinner{\cdotp\cdotp\cdotp},m\}$, and by $F_{S}$ the frame matrix corresponding to $\mathcal{F}[S]$ (which is the matrix with vectors in $\mathcal{F}[S]$ as its columns). Set

All of them depend of course on $\mathcal{F}$. However since we fix $\mathcal{F}$ throughout the paper, we shall without confusion not explicitly reference $\mathcal{F}$ in the notation for simplicity as there will not be any confusion. Clearly

Let $\varepsilon>0$. Then the stability measurement function $Q_{\varepsilon}(x)$ is given by

under the constraints $\frac{1}{2}(w_{1}+w_{2})=x$ and

where $S:=S(w_{1},w_{2})=\{j:~{}|\langle f_{j},w_{1}\rangle|\leq|\langle f_{j},w_{2}\rangle|\}$.

Let $F$ be the frame matrix of $\mathcal{F}$. We thus have

Note that $d(x,y)=\min(\|w_{1}\|,\|w_{2}\|)$. The proposition now follows.

The above proposition allows us to establish the following stability result for the worst case scenario.

Assume that the frame $\mathcal{F}$ is phase retrievable. Let $A>0$ be the lower frame bound for the frame $\mathcal{F}$ and let $\tau:=\min\{\sigma_{n}(F_{S}):~{}S\subseteq\{1,\dots,m\},~{}{\rm rank}(F_{S})=n\}$.

If $\varepsilon<\tau$ then $q_{\varepsilon}=\frac{1}{\omega}$. Consequently $q_{0}=\frac{1}{\omega}$.

The upper bound $q_{\infty}$ equals the reciprocal of $\Delta$:

under the constraints $\frac{1}{2}(w_{1}+w_{2})=x$ and

for some $S$. Now assume without loss of generality that $\|w_{1}\|\leq\|w_{2}\|$. Then

Thus $Q_{\varepsilon}(x)\leq\frac{1}{\Delta}$.

Thus ${\|w_{2}\|}\geq{\|w_{1}\|}$. Now let

It follows that $q_{\varepsilon}\geq\min\,\{\frac{1}{\varepsilon},\frac{1}{\omega}\}$. Now by taking $\varepsilon>0$ sufficiently small we have $q_{\varepsilon}\geq\frac{1}{\omega}$.

This is a contradiction. So ${\rm rank}(F_{S})<n$ and hence

Thus $\|w_{2}\|\leq\frac{\varepsilon}{\omega}$. Proposition 4.1 now yields $q_{\varepsilon}=\frac{1}{\omega}$, proving part (B).

Now we prove (C). We go back to the formulation in Proposition 4.1.

under the constraints $\frac{1}{2}(w_{1}+w_{2})=x$ and

where $S:=S(w_{1},w_{2})=\{j:~{}|\langle f_{j},w_{1}\rangle|\leq|\langle f_{j},w_{2}\rangle|\}$. Since ${\alpha_{\mathcal{F}}}$ is injective, either ${\rm rank}(F_{S})=n$ or ${\rm rank}(F_{S^{c}})=n$ by Theorem 2.1 (1). Without loss of generality we assume ${\rm rank}(F_{S})=n$. Thus \varepsilon\geq\|F_{S}^{*}w_{1}\bigr{\|}\geq\tau\|w_{1}\|. So $\|w_{1}\|\leq\varepsilon/\tau$. We show that for any $k\in S^{c}$ we must have $\langle f_{k},x\rangle=0$. Assume otherwise and write $w_{2}=2x-w_{1}$, $L_{x}:=\min\,\{|\langle f_{j},x\rangle|:~{}\langle f_{j},x\rangle\neq 0\}$. Then

This is a contradiction. Thus for $k\in S^{c}$ we have $\langle f_{k},x\rangle=0$ and

Thus $\|w_{1}\|\leq\varepsilon/\sqrt{A}$ and hence $Q_{\varepsilon}(x)\leq\frac{1}{\sqrt{A}}$. Now we show the bound can be achieved. Let $w_{1}$ satisfy $\|F^{*}w_{1}\|=\sqrt{A}\|w_{1}\|=\varepsilon$. Such a $w_{1}$ always exists. Then clearly $w_{1}$ and $w_{2}=2x-w_{1}$ satisfy the required constraints, and it is easy to check that $\min\,(\|w_{1}\|,\|w_{2}\|)=\|w_{1}\|=\varepsilon/\sqrt{A}$.

Finally we prove (D). By the result at part (A), $q_{\infty}\leq\frac{1}{\Delta}$. It is therefore sufficient to shoow that $Q_{\varepsilon}(x)\geq\frac{1}{\Delta}$ for some $x$ and $\varepsilon$. Let $S_{0}$ be the subset that achieves the minimum in (4.4). Let $u,v\in H$ be unit eigenvectors corresponding to the lowest eigenvalues of $F_{S_{0}}F_{S_{0}}^{*}$ and $F_{S_{0}^{c}}F_{S_{0}^{c}}^{*}$ respectively. Thus

Let $x=(u+v)/2$ and $\varepsilon=\Delta$, and set $w_{1}=u$, $w_{2}=v$. Then by Proposition 4.1

Remark. It may seem strange that $Q_{\varepsilon}(x)=\frac{1}{\sqrt{A}}$ for all $x\neq 0$ and sufficiently small $\varepsilon$ while $q_{0}=\frac{1}{\omega}$, where $\omega$ is typically much smaller than $\sqrt{A}$. The reason is that for $Q_{\varepsilon}(x)=\frac{1}{\sqrt{A}}$ to hold, $\varepsilon$ depends on $x$. Thus we cannot exchange the order of $\limsup_{\varepsilon{\rightarrow}0}$ and $\max_{\|x\|=1}$.

We first investigate the bounds for $U(x,y)$. For this the upper bound is relatively straightforward. Let $w_{1}=x-y$ and $w_{2}=x+y$. We have already shown in the proof of Theorem 4.2 using (4.9) that

To study the lower bound $U(x,y)$ we now consider the following quantities:

where again $w_{1}=x-y$ and $w_{2}=x+y$. Now fix $x$ and let $d(x,y)<\varepsilon$. Without loss of generality we may assume $\|y-x\|<\varepsilon$. Thus $\|w_{1}\|<\varepsilon$ and $\|w_{2}-2x\|=\|w_{1}\|<\varepsilon$. Let $S=\{j,~{}\langle f_{j},x\rangle\neq 0\}$ and set

Note for any $w_{1}$ with ${\|w_{1}\|}<\varepsilon_{0}$ and $k\in S$ we have

Hence $\min\,(|\langle f_{j},w_{1}\rangle|^{2},|\langle f_{j},w_{2}\rangle|^{2})=|\langle f_{j},w_{1}\rangle|^{2}$ for all $j$ whenever $\varepsilon<\varepsilon_{0}(x)$. It follows that

Thus $U^{2}(x,y)\geq A$ where $A$ is the lower frame bound for the frame $\mathcal{F}$. Furthermore this lower bound is achieved whenever $w_{1}=x-y$ is an eigenvector corresponding to the smallest eigenvalue of $FF^{*}$. This implies that

whenever $\varepsilon<\varepsilon_{0}(x)$. Consequently $\rho(x)=\sqrt{A}$. We have the following theorem:

Assume that $\varepsilon<\varepsilon_{0}(x)$. Then $\rho_{\varepsilon}(x)=\sqrt{A}$. Consequently $\rho(x)=\rho_{0}=\sqrt{A}$.

$\Delta=\rho_{\infty}\leq\omega\leq\rho_{0}=\rho(x)=\sqrt{A}$.

The map ${\alpha_{\mathcal{F}}}$ is bi-Lipschitz with (optimal) upper Lipschitz bound $\sqrt{B}$ and lower Lipschitz bound $\rho_{\infty}$:

Proof. We have already proved (1) and (2) of the theorem in the discussion. It remains only to prove (3) since (4) is just a restatement of (1) and (3). Note that

For any $w_{1},w_{2}$, assume without loss of generality that $0<\|w_{1}\|\leq\|w_{2}\|$. Let $S=\{j:~{}|{\langle f_{j},w_{1}\rangle}|\leq|{\langle f_{j},w_{2}\rangle}|\}$. Set $v_{1}=w_{1}/\|w_{1}\|$, $v_{2}=w_{2}/\|w_{2}\|$ and $t=\|w_{2}\|/\|w_{1}\|\geq 1$. Then

Let $S$ and $u,v\in H$ be normalized (eigen) vectors that achieve the bound $\Delta$, that is:

Remark. The two quantities, $\rho_{\infty}$ and $q_{\infty}$ satisfy $\rho_{\infty}=\frac{1}{q_{\infty}}$. However there are subtle differences between $q_{\varepsilon}(x)$ and $\rho_{\varepsilon}(x)$ so that the simple relationship $\rho_{\varepsilon}(x)=1/q_{\varepsilon}(x)$ does not usually hold.

Remark. The upper Lipschitz bound $\sqrt{B}$ has been obtained independently in . The lower Lipschitz bound we obtained here strenghtens the estimates given in . Specifically their estimate for $\rho_{\infty}$ reads ${\boldsymbol{\sigma}}\leq\rho_{\infty}\leq\sqrt{2}{\boldsymbol{\sigma}}$ where

Clearly ${\boldsymbol{\sigma}}\leq\Delta\leq\sqrt{2}{\boldsymbol{\sigma}}$.

We conclude this section by turning our attention to the analysis of $V(x,y)$. A motivation for studying it is that in practical problems the noise is often added directly to ${\alpha_{\mathcal{F}}}^{2}$ as in (3.1) rather than to ${\alpha_{\mathcal{F}}}$. Such noise model is used in many studies of phaseless reconstruction, e.g. in the Phaselift algorithm , or in the IRLS algorithm in .

The following lemma will be useful in this analysis

Furthermore, for $X=\frac{1}{2}(w_{1}w_{2}^{T}+w_{2}w_{1}^{T})$ its nuclear norm is $\|X\|_{1}=\|w_{1}\|\|w_{2}\|$.

(B) $\Rightarrow$ (C) is proved directly by setting $w_{1}=x-y$ and $w_{2}=x+y$.

We now prove (C) $\Rightarrow$ (A) by computing the eigenvalues of $X=\frac{1}{2}(w_{1}w_{2}^{T}+w_{2}w_{1}^{T})$. Obviously ${\rm rank}(X)\leq 2$. Let $\lambda_{1},\lambda_{2}$ be the two (possibly) nonzero eigenvalues of $X$. Then

Hence, by Cauchy-Schwartz inequality, $\lambda_{1}\geq 0\geq\lambda_{2}$ which proves $X\in S_{n}^{1,1}$. Furthermore, it also shows that the nuclear norm of $X$ is $\|X\|_{1}=|\lambda_{1}|+|\lambda_{2}|=\|w_{1}\|\|w_{2}\|$.

Now we analyze $V(x,y)$. Parallel to the study of $U(x,y)$ we consider the following quantities:

as well as the upper bound $sup_{d_{1}(x,y)>0}V(x,y)$. By (4.15) we have $|\langle f_{j},x\rangle|^{2}-|\langle f_{j},y\rangle|^{2}={\langle F_{j},X\rangle}$ where $F_{j}=f_{j}f_{j}^{T}$ and $X=xx^{T}-yy^{T}$. Hence

Set $w_{1}=x-y$ and $w_{2}=x+y$ and apply Lemma 4.4 we obtain

We can immediately obtain the upper bound:

where $R(x)$ was defined in (2.6). An immediate bound is ${\Lambda_{\mathcal{F}}}\leq\sqrt{B}\max{\|f_{k}\|}$ with $B$ the upper frame bound of $\mathcal{F}$.

Fix $x\neq 0$ and let $d(x,y){\rightarrow}0$. Then either $y\rightarrow x$ or $y{\rightarrow}-x$. Without loss of generality we assume that $x{\rightarrow}y$. Thus $w_{1}=x-y\rightarrow 0$ and $w_{2}=x+y\rightarrow 2x$. However $w_{1}/{\|w_{1}\|}$ can be any unit vector. Thus

where $R(x)$ was introduced in (2.6). Thus we obtain

where $a_{0}$ was introduced in (2.4). Thus we proved:

Assume the frame $\mathcal{F}$ is phase retrievable. Then

Furthermore ${\alpha_{\mathcal{F}}}^{2}$ is bi-Lipschitz with upper Lipschitz bound ${\Lambda_{\mathcal{F}}}^{2}$ and lower Lipschitz bound $\mu_{0}$:

Remark. Note that the distance $d(.,.)$ is not equivalent to $d_{1}(.,.)$. Theorem 4.5 now also implies that ${\alpha_{\mathcal{F}}}^{2}$ is not bi-Lipschitz with respect to the distance $d(.,.)$ on $\hat{H}$. This fact was pointed out in .

Robustness and Size of Redundancy

Previous sections establish results on the robustness of phaseless reconstruction for the worst case scenario. A natural question is to ask: can “reasonable” robustness be achieved for a given frame, and in particular with small number of samples? We shall examine how $q_{\infty}$ scales as the dimension $n$ increases.

Consider the case where $m=2n-1$. This is the minimal redundancy required for phaseless reconstruction. In this case any frame $\mathcal{F}$ would have $\Delta=\omega$. Hence we have $\min\{1/\omega,1/\varepsilon\}\leq q_{\varepsilon}=1/\omega$. The stability of the reconstruction is thus mostly controlled by the size of $1/\omega$. The question is: how big is $\omega$, especially as $n$ increases?

It follows that $\sigma_{n}(G)\leq\frac{L}{\sqrt{n}}$, and hence

Note that here we have considered only the first $n+1$ vectors of the frame $\mathcal{F}$. The actual value of $\omega$ will likely decay much faster as $n$ increases. In a preliminary work we are able to establish the bound $\omega\leq CL/\sqrt{n^{3}}$ where $C$ is independent of $n$ . But even this estimate is likely far from optimal.

Let $m=2n-1$ and $\|f_{j}\|\leq L$ for all $f_{j}\in\mathcal{F}$. Then there exist constants $C>0$ and $0<\beta<1$ independent of $n$ such that

A related problem is as follows: Consider an $n\times(n+k)$ matrix $F=[g_{1},g_{2},\dots,g_{n+k}]$. Let $\tau=\min\{\sigma_{n}(F_{S}):~{}S\subset\{1,\dots,n+k\},|S|=n\}$. Assume that all $\|g_{j}\|\leq 1$. How large can $\tau$ be? For $k=1$ we have already seen that it is bounded from above by $C/\sqrt{n}$. The preliminary work shows that for $k=1$ it is bounded from above by $C/n^{\frac{3}{2}}$.

There exists a constant $C=C(k)$ such that

Thus in the minimal setting with $m=2n-1$ it is impossible to achieve scale independent stability for phaseless reconstruction. The same arguments can be used to show that even when $m=2n+k_{0}$ for some fixed $k_{0}$ scale independent stability is not possible. A natural question is whether scale independent stability is possible when we increase the redundancy of the frame. As it turns out this is possible via a recent work by Wang . More precisely, the following result follows from the main results in :

Let $r_{0}>2$ and let $F=\frac{1}{\sqrt{n}}G$ where $G$ is an $n\times m$ random matrix whose elements are i.i.d. normal $N(0,1)$ random variables such that $m/n=r_{0}$. Then there exist constants $0<\Delta_{0}\leq\omega_{0}$ dependent only on $r_{0}$ and not on $n$ such that with high probability we have

Proof. Part of the main theorem of proves the following result: Let $\lambda>\delta>1$ be fixed. Assume that $A=\frac{1}{\sqrt{n}}B$ where $B$ is an $n\times N$ random Gaussian matrix with i.i.d $N(0,1)$ entries such that $N/n=\lambda$. Then there exists a constant $c>0$ depending continuously and only on $\lambda$ and $\delta$ such that

The theorem now readily follows. Observe that because $r_{0}>2$, in the expression for $\Delta$ we may choose $\lambda=r_{0}$ $\delta=\frac{r_{0}}{2}>1$ and clearly we have

for some $\Delta_{0}>0$ independent of $n$. For $\omega$ we may choose $\lambda=r_{0}$ and $\delta=r_{0}-1>1$. Again the theorem of implies that

In the theorem the values $\Delta_{0}$ and $\omega_{0}$ can be estimated explicitly. Here with high probability is in the standard sense that the probability is at least $1-c_{0}e^{-\beta n}$ for some $c_{0},\beta>0$. Thus scale independent stable phaseless reconstruction is possible whenever the redundancy is greater than $2+\delta$, $\delta>0$, at least for random Gaussian matrices.

Acknowledgement. The authors would like to thank Matt Fickus, Dustin Mixon and Jeffrey Schenker for very helpful discussions.

References