Solving Quadratic Equations via PhaseLift when There Are About As Many Equations As Unknowns

Introduction

Suppose we wish to solve quadratic equations of the form

Then approximate this combinatorially hard problem by using a convex surrogate for the nonconvex rank functional: PhaseLift is the relaxation

The main result in states that if the equations are sufficiently randomized and their number $m$ is at least on the order of $n\log n$, then the solution to the convex relaxation (1.3) is exact.

where $c_{0}$ is a sufficiently large constant. Then in all models introduced below, PhaseLift is exact with probability at least $1-3e^{-\gamma\frac{m}{n}}$ ($\gamma$ is a positive numerical constant) in the sense that (1.3) has a unique solution equal to $\bm{x}_{0}\bm{x}_{0}^{*}$.Upon retrieving $\hat{\bm{X}}=\bm{x}_{0}\bm{x}_{0}^{*}$, a simple factorization recovers $\bm{x}_{0}$ up to global phase, i.e. multiplication by a complex scalar of unit magnitude.

The models above are either complex or real depending upon whether $\bm{x}_{0}$ is complex or real valued. In all cases the $\bm{a}_{i}$’s are independently and identically distributed with the following distributions:

Complex models. The uniform distribution on the complex sphere of radius $\sqrt{n}$, or the complex normal distribution $\mathcal{N}(0,\bm{I_{n}}/2)+i\mathcal{N}(0,\bm{I_{n}}/2)$.

Real models. The uniform distribution on the sphere of radius $\sqrt{n}$, or the normal distribution $\mathcal{N}(0,\bm{I_{n}})$.

Clearly, one needs at least on the order of $n$ equations to have a well posed problem, namely, a unique solution to (1.1).The work in shows that with probability one, $m=4n-2$ randomized equations as in Theorem 1.1 are sufficient for the intractable phase retrieval problem (1.1) to have a unique solution. This raises natural questions:

Does the convex relaxation (1.3) with a number of equations on the order of the number of unknowns succeed? Or is the lower bound (1.3) sharp?

Is it possible to improve the guaranteed probability of success?

Can we hope for a universal result stating that once the vectors $\bm{a}_{i}$ have been selected, all input signals $\bm{x}_{0}$ can be recovered?

where $c_{0}$ is a sufficiently large constant. Thus, exact recovery holds simultaneously over all input signals.

In words, (1) the solution to most systems of quadratic equations can be obtained by semidefinite programming as long as the number of equations is at least a constant times the number of unknowns; (2) the probability of failure is exponentially small in the number of measurements, a significant sharpening of Theorem 1.1; (3) these properties hold universally as explained above.

In most applications of interest, we do not have noiseless data but rather observations of the form

where $w_{i}$ is a noise term. Here, we suggest recovering the signal by solving

for some numerical constant $C_{0}$. For the Gaussian models, this holds with the same probability as in the noiseless case whereas the probability of failure is exponentially small in $n$ in the uniform model. By finding the largest eigenvector with largest eigenvalue of $\hat{\bm{X}}$, one can also construct an estimate obeying

In contrast, since $\|\bm{w}\|_{1}\leq\sqrt{m}\|\bm{w}\|_{2}\leq\sqrt{m}\varepsilon$, the new Theorem 1.3 gives

this represents a substantial improvement.

Proofs

We prove Theorems 1.2 and 1.3 in the real-valued case, the complex case being similar, see for details. Next, the Gaussian and uniform models are nearly equivalent: indeed, suppose $\bm{a}_{i}$ is uniformly sampled on the sphere; if $n\rho_{i}^{2}\sim\chi^{2}_{n}$ and is independent of $\bm{a}_{i}$, then $\bm{z}_{i}=\rho_{i}\bm{a}_{i}$ is normally distributed. Hence,

In the noiseless case, we have full equivalence. In the noisy case, we can transfer a bound for Gaussian measurements into the same bound for uniform measurements by changing the probability of success ever so slightly—as noted in Theorem 1.3. Thus, it suffices to study the real-valued Gaussian case.

We begin by specializing Lemmas 3.1 and 3.2 from .

There is an event $E$ of probability at least $1-5e^{-\gamma_{0}m}$ such that on $E$, any positive symmetric matrix obeys

The following intermediate result is novel, although we became aware of a similar argument in as we finished this paper.

Suppose there is a matrix $\bm{Y}$ in the range of $\mathcal{A}^{*}$ obeying $\bm{Y}_{T^{\perp}}\preceq-\bm{I}_{T^{\perp}}$ and $\|\bm{Y}_{T}\|_{F}\leq{1\over{2}}$. Then on the event $E$ from Lemma 2.1, $\bm{X}_{0}=\bm{x}_{0}\bm{x}_{0}^{*}$ is PhaseLift’s unique feasible point.

Proof Suppose $\bm{x}_{0}\bm{x}_{0}^{*}+\bm{H}$ is feasible, which implies that (1) $\bm{H}_{T^{\perp}}\succeq\bm{0}$ and (2) $\bm{H}$ is in the null space of $\mathcal{A}$ so that $\langle\bm{H},\bm{Y}\rangle=0=\langle\bm{H}_{T},\bm{Y}_{T}\rangle+\langle\bm{H}_{T^{\perp}},\bm{Y}_{T^{\perp}}\rangle$. On the one hand,

Lemma 2.1 asserts that $m^{-1}\|\mathcal{A}(\bm{H}_{T^{\perp}})\|_{1}\leq(1+1/8)\operatorname{tr}(\bm{H}_{T^{\perp}})$ and $m^{-1}\|\mathcal{A}(\bm{H}_{T})\|_{1}\geq 0.94(1-1/8)\|\bm{H}_{T}\|$. Since $\mathcal{A}(\bm{H}_{T})=-\mathcal{A}(\bm{H}_{T^{\perp}})$, this gives

where the last inequality is a consequence of the fact that $\bm{H}_{T}$ has rank at most 2. On the other hand,

Since $0.73/\sqrt{2}>1/2$, (2.1) and (2.2) give that $\bm{H}_{T}=0$, which in turns implies that $\bm{H}_{T^{\perp}}=\bm{0}$. This completes the proof.

Proof We assume that $\|\bm{x}_{0}\|_{2}=1$ without loss of generality. Our strategy is to show that

We begin by checking the condition $\bm{Y}_{T^{\perp}}\preceq-\bm{I}_{T^{\perp}}$. First, the matrix $\bm{Y}^{(1)}$ is Wishart and standard results in random matrix theory—e.g. Corollary 5.35 in —assert that

with probability at least $1-2e^{-\gamma m}$ provided that $m\geq cn$, where $c$ is sufficiently large. In particular, we have

Second, letting $\bm{x}^{\prime}$ be the projection of $\bm{x}$ onto the orthogonal complement of $\operatorname{span}{(}\bm{x}_{0})$, we have

It is immediate to check that the $\bm{\xi}_{i}$’s are iid copies of a zero-mean, isotropic and sub-Gaussian random vector $\bm{\xi}$. In particular, with $z\sim\mathcal{N}(0,1)$,

Again, standard results about random matrix with sub-gaussian rows—e.g. Theorem 5.39 in —give

with probability at least $1-2e^{-\gamma m}$ provided that $m\geq cn$, where $c$ is sufficiently large. Clearly, (2.4) together with (2.5) yield the first condition $\|\bm{Y}_{T^{\perp}}+{{17}\over{10}}\bm{I}_{T^{\perp}}\|\leq{1\over{10}}$ .

We now establish $\|\bm{Y}_{T}\|_{F}\leq 3/20$. To begin with, set $\bm{y}=\bm{Y}\bm{x}_{0}$ and observe that since $\|\bm{Y}_{T}\|^{2}_{F}=|\langle\bm{y},\bm{x}_{0}\rangle|^{2}+2\|\bm{y}^{\prime}\|^{2}_{2}$, it suffices to verify that

for some numerical constant $\gamma$. Finally, write $\bm{y}^{\prime}$ as

Note that $\bm{Z}^{\prime}$ and $\bm{c}$ are independent. On the one hand, the $c_{i}^{2}$’s are iid sub-exponential variables and Corollary 5.17 in —gives

for some numerical constant $\gamma>0$. This shows that

with probability at least $1-2e^{-\gamma m}$. On the other hand, for a fixed $\bm{x}$ obeying $\|\bm{x}\|_{2}=1$, $\|\bm{Z^{\prime}}\bm{x}\|_{2}^{2}$ is distributed as a $\chi^{2}$-random variable with $n-1$ degrees of freedom and it follows that

for some numerical constant $\gamma>0$ with the proviso that $m\geq cn$ and $c$ is sufficiently large. We omit the details. To conclude, (2.6) and (2.7) give that with probability at least $1-3e^{-\gamma m}$,

2 Proof of Theorem 1.2

The proof of Theorem 1.2 is now a consequence of the corollary below.

The reason why this corollary holds is straightforward: Lemma 2.3 holds true for exponentially points and a sort of continuity argument allows to extend it to all points. Again it suffices to establish the property for unit-normed vectors.

Proof Let $\mathcal{N}_{\epsilon}$ be an $\epsilon$-net for the unit sphere with cardinality obeying $|\mathcal{N}_{\epsilon}|\leq(1+2/\epsilon)^{n}$ by Lemma 2 in .For any unit-normed vector $\bm{x}$, there is $\bm{x}_{0}\in\mathcal{N}_{\epsilon}$ with $\|\bm{x}_{0}\|_{2}=1$ and $\|\bm{x}-\bm{x}_{0}\|_{2}\leq\epsilon$, where $\epsilon>0$. If $c_{0}$ is sufficiently large, Lemma 2.3 implies that with probability at least $1-O(e^{-\gamma m}(1+2/\epsilon)^{n})\geq 1-O(e^{-\gamma^{\prime}m})$, for all $\bm{x}_{0}\in\mathcal{N}_{\epsilon}$, there exists $\bm{Y}=\mathcal{A}^{*}(\bm{\lambda})$ obeying

and $\|\bm{\lambda}\|_{\infty}\leq 7/m$ (we wrote $T_{0}$ in place of $T$ for convenience). Note that this gives

Consider now an arbitrary unit-normed vector $\bm{x}$ and let $\bm{x}_{0}\in\mathcal{N}_{\epsilon}$ be any element such that $\|\bm{x}-\bm{x}_{0}\|_{2}\leq\epsilon$. Set $\bm{\Delta}=\bm{x}\bm{x}^{T}-\bm{x}_{0}\bm{x}_{0}^{T}$, which obeys

we see that the first condition of Lemma 2.2 holds whenever $\epsilon$ is small enough. For the first condition,

Since $\bm{\Delta}$ has rank at most 2, $\operatorname{rank}(\bm{R})\leq 2$, and

Choosing $\epsilon$ sufficiently small concludes the proof of the corollary.

3 Stability

To see why the stability result (1.7) is optimal, suppose without loss of generality that $\|\bm{x}_{0}\|_{2}=1$. Further, imagine that we are informed that $\|\bm{w}\|_{1}\leq\delta m$ for some known $\delta$. Since $\|\mathcal{A}(\bm{x}_{0}\bm{x}_{0}^{*})\|_{1}\approx m$, it would not be possible to distinguish between solutions of the form $(1+\lambda)\bm{x}_{0}\bm{x}_{0}^{*}$ for $\max(0,1-\delta)\lesssim 1+\lambda\lesssim 1+\delta$. Hence, the error in the Frobenius norm may be as large as $\delta\|\bm{x}_{0}\bm{x}_{0}^{*}\|_{F}=\delta$, which is what the theorem gives.

We now turn to the proof of Theorem 1.3. We do not need to show the second part as the perturbation argument is exactly the same as in [3, Theorem 1.2]. The argument for the first part follows that of the earlier Lemma 2.2, and makes use of the existence of a dual certificate $\bm{Y}=\mathcal{A}^{*}(\bm{\lambda})$ obeying the conditions of this lemma.

Set $\hat{\bm{X}}=\bm{x}_{0}\bm{x}_{0}^{*}+\bm{H}$. Since $\hat{\bm{X}}$ is feasible, $\bm{H}_{T^{\perp}}\succeq\bm{0}$ and $\langle\bm{H},\bm{Y}\rangle=\langle\mathcal{A}(\bm{H}),\bm{\lambda}\rangle$. First,

which by the same argument as before, yields

Since $|\langle\bm{H}_{T},\bm{Y}_{T}\rangle|\leq\frac{1}{2}\|\bm{H}_{T}\|_{F}$, we have established thatThe careful reader will note that we can get a far better constant by observing that the proof of Theorem 1.2 also yields $\|\bm{Y}_{T}\|_{F}\leq 1/4$. Hence, we have $\|\bm{H}_{T}\|_{F}\leq 4(8/9+7){\|\mathcal{A}(\bm{H})\|_{1}}/{m}$.

Also, since $\bm{H}_{T^{\perp}}$ is positive semidefinite

To see why the second inequality is true, observe that

which gives $\|\mathcal{A}(\bm{H})\|_{1}\leq 2\|\bm{w}\|_{1}$ by the triangle inequality. The proof is complete.

Acknowledgements

E. C. is partially supported by AFOSR under grant FA9550-09-1-0643 and by ONR under grant N00014-09-1-0258. This work was partially presented at the University of California at Berkeley in January 2012, and at the University of British Columbia in February 2012.

References