Signal Processing - September 2016 - 161
Wirtinger flow
While PhaseLift allows solving the
phase retrieval problem in polynomial
time (say, with an interior-point method), such methods scale poorly with
the problem size due to the lifting operation, leading one to seek alternative
solvers. To this end, we consider a different program:
minimize
m
/ ^ a *i x 2 - y ih2 .
(5)
i=1
Observe that (5) is equivalent to the
phase retrieval problem (1) when
S = C n . Unfortunately, since (5) is not
convex, we expect to encounter local
minima when attempting to solve it. In
addition, this particular objective function has a continuum of global optimizers: The true solution x 0 induces a
circle of global optimizers [x 0] =
{e iz x 0: z ! [0, 2r)} . Perhaps surprisingly, (5) admits a fast initialization of
gradient descent that allows for convergence to this circle provided A is sufficiently random. This gradient descent
iteration is called Wirtinger flow
because the gradient is conveniently
expressed in terms of Wirtinger derivatives [3].
The convergence of Wirtinger flow is
established by first showing that initializations sufficiently close to [x 0] yield
convergence by verifying a local convexity-type property. Next, a good initialization is found. Suppose the rows {a *i } mi = 1
of A are complex Gaussian. Then a simple moment calculation reveals that
m
E ; 1 / y i a i a i*E = I + 2x 0 x 0*,
m i=1
meaning the true solution x 0 is a leading
eigenvector of the expected matrix. Furthermore, 1/m / im= 1 y i a i a *i is typically
spectrally close to its expectation, and so
its leading eigenvector (suitably scaled) is
close to [x 0] . With this initialization, gradient descent converges linearly to [x 0]
when m = X (n log n) and A has complex Gaussian entries; a variant of the
gradient descent iteration exhibits similar
performance when m = X (n log 4 n)
and A is composed of n # n blocks of
the form FD j (again, following the structured illumination model). Figure 2
shows a comparison between the computation time required for PhaseLift and for
Wirtinger flow.
Following the motivation of Wirtinger
flow, we seek a faster alternative to this
semidefinite program. Let us reformulate (1) in the case where S is the set of
k-sparse vectors:
minimize
m
/ ( a *i x 2 - y i) 2
i=1
subject to x
0
(7)
# k.
Here, x 0 denotes the number of
nonzero entries in x; note the similarity
to (5). When {a i} im= 1 are complex Gaussian, the solution to (7) typically
Sparse phase retrieval
Now suppose that the unknown vector
x 0 is known to be k-sparse. If we were
given Ax 0 instead of Ax 0 2, then we
could leverage the now-rich theory of
compressed sensing to reconstruct x 0
provided A is an m # n random matrix
with m = X (k polylog n); see [1] for a
short introduction to this theory. We
aspire to reconstruct [x 0] from Ax 0 2
with similar requirements on A. We
discuss two algorithms along these
lines but note that their perfor mance is strictly worse than the desired
m = X (k polylog n) . Indeed, achieving
this performance with complex Gaussian
or sufficiently random matrices A
remains an open problem.
In compressed sensing, one of the
most popular reconstruction algorithms
given Ax 0 = y minimizes x 1 subject
to Ax = y [4]. In phase retrieval, we
receive linear measurements of x 0 x *0,
and since x 0 x *0 is sparse, it makes sense
to minimize X 1 subject to A (X) = y.
We also want to encourage X to be
rank-1, leading to the following variation
of PhaseLift:
minimize X 1 + mTr [X]
subject to A (X) = y, X * 0.
(6)
If the entries of A are complex
Gaussian, then for an appropriate
choice of m, (6) typically recovers
X = x 0 x *0 provided m = X (k 2 log n) .
Drawing from compressed sensingbased intuition, the k2 here comes from
the fact that x 0 x *0 is k2-sparse, and so
the barrier to improving this sample
complexity is perhaps an artifact of the
lifting approach.
IEEE Signal Processing Magazine
|
September 2016
|
102
101
Runtime (in Seconds)
from a complex Gaussian distribution,
or A may be composed of n # n blocks
of the form FD j, where F is the n # n
discrete Fourier transform matrix and
D j is a diagonal matrix with random diagonal entries from an acceptable distribution (the latter case models the
structured illumination application of
phase retrieval).
100
10-1
10-2
10-3
10-4
10-5
100
101
102
Dimension n
103
Figure 2. The runtime comparison between
PhaseLift (blue), Wirtinger flow (orange), and
least squares (purple) assuming the known
phase. For each dimension n ! {2 1, f, 2 9}, we
perform 20 iterations of the following experiment:
Draw a 4.5 n # n matrix A with independent entries with complex Gaussian distribution
N (0, 1/2) + iN (0, 1/2) and a signal x ! C n,
also with independent and identically distributed
complex Gaussian entries. Compute z = Ax
and y = z 2 . Then reconstruct x from z
by MATLAB's built-in implementation of least
squares, and reconstruct x from y up to global
phase using Wirtinger flow and PhaseLift. (For
PhaseLift, we solve the semidefinite program
using TFOCS v1.3 release 2 [2]; the runtime was
prohibitively long for n 2 2 5 .) After conducting
all 20 iterations, we plot the average runtime along
with error bars that illustrate one standard deviation. As expected, the least-squares solver (which
enjoys a phase "oracle") is faster than the phase
retrieval solvers. For larger dimensions, Wirtinger
flow appears to be about 100 times slower than
least-squares, whereas PhaseLift is even slower.
161
Table of Contents for the Digital Edition of Signal Processing - September 2016
Signal Processing - September 2016 - Cover1
Signal Processing - September 2016 - Cover2
Signal Processing - September 2016 - 1
Signal Processing - September 2016 - 2
Signal Processing - September 2016 - 3
Signal Processing - September 2016 - 4
Signal Processing - September 2016 - 5
Signal Processing - September 2016 - 6
Signal Processing - September 2016 - 7
Signal Processing - September 2016 - 8
Signal Processing - September 2016 - 9
Signal Processing - September 2016 - 10
Signal Processing - September 2016 - 11
Signal Processing - September 2016 - 12
Signal Processing - September 2016 - 13
Signal Processing - September 2016 - 14
Signal Processing - September 2016 - 15
Signal Processing - September 2016 - 16
Signal Processing - September 2016 - 17
Signal Processing - September 2016 - 18
Signal Processing - September 2016 - 19
Signal Processing - September 2016 - 20
Signal Processing - September 2016 - 21
Signal Processing - September 2016 - 22
Signal Processing - September 2016 - 23
Signal Processing - September 2016 - 24
Signal Processing - September 2016 - 25
Signal Processing - September 2016 - 26
Signal Processing - September 2016 - 27
Signal Processing - September 2016 - 28
Signal Processing - September 2016 - 29
Signal Processing - September 2016 - 30
Signal Processing - September 2016 - 31
Signal Processing - September 2016 - 32
Signal Processing - September 2016 - 33
Signal Processing - September 2016 - 34
Signal Processing - September 2016 - 35
Signal Processing - September 2016 - 36
Signal Processing - September 2016 - 37
Signal Processing - September 2016 - 38
Signal Processing - September 2016 - 39
Signal Processing - September 2016 - 40
Signal Processing - September 2016 - 41
Signal Processing - September 2016 - 42
Signal Processing - September 2016 - 43
Signal Processing - September 2016 - 44
Signal Processing - September 2016 - 45
Signal Processing - September 2016 - 46
Signal Processing - September 2016 - 47
Signal Processing - September 2016 - 48
Signal Processing - September 2016 - 49
Signal Processing - September 2016 - 50
Signal Processing - September 2016 - 51
Signal Processing - September 2016 - 52
Signal Processing - September 2016 - 53
Signal Processing - September 2016 - 54
Signal Processing - September 2016 - 55
Signal Processing - September 2016 - 56
Signal Processing - September 2016 - 57
Signal Processing - September 2016 - 58
Signal Processing - September 2016 - 59
Signal Processing - September 2016 - 60
Signal Processing - September 2016 - 61
Signal Processing - September 2016 - 62
Signal Processing - September 2016 - 63
Signal Processing - September 2016 - 64
Signal Processing - September 2016 - 65
Signal Processing - September 2016 - 66
Signal Processing - September 2016 - 67
Signal Processing - September 2016 - 68
Signal Processing - September 2016 - 69
Signal Processing - September 2016 - 70
Signal Processing - September 2016 - 71
Signal Processing - September 2016 - 72
Signal Processing - September 2016 - 73
Signal Processing - September 2016 - 74
Signal Processing - September 2016 - 75
Signal Processing - September 2016 - 76
Signal Processing - September 2016 - 77
Signal Processing - September 2016 - 78
Signal Processing - September 2016 - 79
Signal Processing - September 2016 - 80
Signal Processing - September 2016 - 81
Signal Processing - September 2016 - 82
Signal Processing - September 2016 - 83
Signal Processing - September 2016 - 84
Signal Processing - September 2016 - 85
Signal Processing - September 2016 - 86
Signal Processing - September 2016 - 87
Signal Processing - September 2016 - 88
Signal Processing - September 2016 - 89
Signal Processing - September 2016 - 90
Signal Processing - September 2016 - 91
Signal Processing - September 2016 - 92
Signal Processing - September 2016 - 93
Signal Processing - September 2016 - 94
Signal Processing - September 2016 - 95
Signal Processing - September 2016 - 96
Signal Processing - September 2016 - 97
Signal Processing - September 2016 - 98
Signal Processing - September 2016 - 99
Signal Processing - September 2016 - 100
Signal Processing - September 2016 - 101
Signal Processing - September 2016 - 102
Signal Processing - September 2016 - 103
Signal Processing - September 2016 - 104
Signal Processing - September 2016 - 105
Signal Processing - September 2016 - 106
Signal Processing - September 2016 - 107
Signal Processing - September 2016 - 108
Signal Processing - September 2016 - 109
Signal Processing - September 2016 - 110
Signal Processing - September 2016 - 111
Signal Processing - September 2016 - 112
Signal Processing - September 2016 - 113
Signal Processing - September 2016 - 114
Signal Processing - September 2016 - 115
Signal Processing - September 2016 - 116
Signal Processing - September 2016 - 117
Signal Processing - September 2016 - 118
Signal Processing - September 2016 - 119
Signal Processing - September 2016 - 120
Signal Processing - September 2016 - 121
Signal Processing - September 2016 - 122
Signal Processing - September 2016 - 123
Signal Processing - September 2016 - 124
Signal Processing - September 2016 - 125
Signal Processing - September 2016 - 126
Signal Processing - September 2016 - 127
Signal Processing - September 2016 - 128
Signal Processing - September 2016 - 129
Signal Processing - September 2016 - 130
Signal Processing - September 2016 - 131
Signal Processing - September 2016 - 132
Signal Processing - September 2016 - 133
Signal Processing - September 2016 - 134
Signal Processing - September 2016 - 135
Signal Processing - September 2016 - 136
Signal Processing - September 2016 - 137
Signal Processing - September 2016 - 138
Signal Processing - September 2016 - 139
Signal Processing - September 2016 - 140
Signal Processing - September 2016 - 141
Signal Processing - September 2016 - 142
Signal Processing - September 2016 - 143
Signal Processing - September 2016 - 144
Signal Processing - September 2016 - 145
Signal Processing - September 2016 - 146
Signal Processing - September 2016 - 147
Signal Processing - September 2016 - 148
Signal Processing - September 2016 - 149
Signal Processing - September 2016 - 150
Signal Processing - September 2016 - 151
Signal Processing - September 2016 - 152
Signal Processing - September 2016 - 153
Signal Processing - September 2016 - 154
Signal Processing - September 2016 - 155
Signal Processing - September 2016 - 156
Signal Processing - September 2016 - 157
Signal Processing - September 2016 - 158
Signal Processing - September 2016 - 159
Signal Processing - September 2016 - 160
Signal Processing - September 2016 - 161
Signal Processing - September 2016 - 162
Signal Processing - September 2016 - 163
Signal Processing - September 2016 - 164
Signal Processing - September 2016 - 165
Signal Processing - September 2016 - 166
Signal Processing - September 2016 - 167
Signal Processing - September 2016 - 168
Signal Processing - September 2016 - 169
Signal Processing - September 2016 - 170
Signal Processing - September 2016 - 171
Signal Processing - September 2016 - 172
Signal Processing - September 2016 - 173
Signal Processing - September 2016 - 174
Signal Processing - September 2016 - 175
Signal Processing - September 2016 - 176
Signal Processing - September 2016 - Cover3
Signal Processing - September 2016 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201809
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201807
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201805
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201803
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201801
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1117
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0917
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0717
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0517
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0317
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0117
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1116
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0916
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0716
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0516
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0316
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0116
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1115
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0915
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0715
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0515
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0315
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0115
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1114
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0914
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0714
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0514
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0314
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0114
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1113
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0913
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0713
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0513
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0313
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0113
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1112
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0912
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0712
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0512
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0312
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0112
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1111
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0911
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0711
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0511
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0311
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0111
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1110
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0910
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0710
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0510
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0310
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0110
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1109
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0909
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0709
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0509
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0309
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0109
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1108
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0908
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0708
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0508
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0308
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0108
https://www.nxtbookmedia.com