Signal Processing - September 2016 - 159
are known to closely approximate various classes of images and signals.
Another way to obtain a well-posed
problem is to collect additional intensity
measurements. For example, in diffractive
imaging, one may implement multiple
structured illuminations of the form
FD j x 0 2, where each D j is a known
diagonal matrix. In other applications, we
can take redundant measurements via the
short-time Fourier transform. This
approach has been used in speech and
audio processing, in measurements of ultrashort laser pulses via frequency resolved
optical gating, and in ptychographical diffractive imaging, among others.
To account for the apparent multitude
of plausible intensity measurements
(such as structured illuminations or the
short-time Fourier transform), we consider a general phase retrieval setting in
which we receive y = Ax 0 2 for some
known matrix A ! C m # n . We then seek
to solve the following program:
find x subject to Ax 2 = y, x ! S, (1)
where S 3 C n corresponds to the imposed structure. In this lecture note,
we focus on cases where S is either all
of C n or the set of k-sparse vectors.
For both settings, we discuss transformations A that allow for (1) to uniquely determine x 0 and consider
algorithms that were recently designed
to solve (1) for various choices of A.
The results we present throughout are
surveyed in [6], [8], and [10], unless
indicated otherwise.
Uniqueness
For a fixed A, we are interested in
whether (1) has a "unique" solution for
every x 0 ! S (or for most x 0 ! S) . We
focus on the cases where S is either all
of C n or the set of k-sparse vectors.
Note that in both cases, x ! S if and
only if e iz x ! S for every z ! [0, 2r),
which means (1) never has a unique
solution in the literal sense. To account
for this technicality, we say (1) has a
unique solution (up to a global phase
factor) if every solution lies in the set
[x 0]: = " e iz x 0: z ! [0, 2r) , .
Notice that the set [x 0] is determined
by the outer product x 0 x *0 (and vice
versa). Let a *i denote the ith row of A
(here, a i ! C n is a column vector, and a *i
denotes its conjugate transpose). Then
2
y i = a i* x 0 = a i* x 0 ยท a i* x 0 = a i* x 0 x 0* a i .
(2)
Consider the case where S = C n . In
this setting, (2) implies that (1) has a
unique solution for every x 0 ! C n
precisely when the mapping
x 0 x *0 7 {a *i x 0 x *0 a i} mi = 1 is one to one.
Recent research has investigated the
number of measurements m that are
necessary or sufficient for this map
to be one to one. For example, it has
been shown that the inequality
m $ 4n - O (log n) is a necessary condition. Conversely, for almost every
A ! C m # n with m $ 4n - 4, (1) has a
unique solution for every x 0 ! C n .
Whether such A exist when m 1 4n - 4
remains an open problem for general n.
We know this is impossible when n has
the form n = 2 k + 1 and yet possible
when n = 4 [11]. Alternatively, for
almost every A ! C m # n with m $ 2n,
(1) has a unique solution for almost
every x 0 ! C n, and no such A exists
when m 1 2n - 1.
In many real-world applications, A
exhibits some sort of Fourier structure.
For example, in the classical setting in
which x 0 is compactly supported, A
may be viewed as an oversampled Fourier matrix. As mentioned before, 1-D
uniqueness from Fourier measurements
cannot be guaranteed in general. To
achieve uniqueness beyond trivial ambiguities, consider the model in which A
is a kn # n matrix composed of k different n # n blocks of the form FD j,
where F is the n # n discrete Fourier
transform matrix and each D j is some
diagonal matrix. This model is called
the structured illumination model, and
each D j is referred to as a mask. While
four such masks are required to determine every possible x 0 (by the aforementioned discussion), we currently
only know how to do so with O (log n)
masks. On the other hand, we do know
how to determine almost every possible
x 0 with only two masks, which matches
the above theory; in particular, the two
masks may be taken to be the identity
IEEE Signal Processing Magazine
|
September 2016
|
matrix and diag (0, 1, f, 1), as illustrated in the following example.
Example 2
Suppose that x 0 is a vector of length n = 4
and we measure it using the two masks
D 0 = I and D 1 = D = diag (0, 1, 1, 1) .
The resulting structured illumination matrix
has the form
R1
S
S1
S1
S
FI
S1
A =; E=S
0
FD
S
S0
S0
SS
0
T
1
1
~
1
~
2
~
2
~
4
~
3
~
6
1
1
~
1
~
2
~
2
~
4
~
3
~
6
1 VW
3
~ W
6W
~
W
9
~ W
,
1W
W
3
~ W
6
~ W
9W
~ W
X
2r
where ~ = e -i n = - i. The two-mask
structured illumination model measures
the discrete Fourier transform of the
signal and of the signal minus the first
component (or any other desired element). A larger dimensional example of
this idea is given in Figure 1.
Another structured example of A is
the short-time Fourier transform, which
can be thought of as a special case of
the structured illumination model: The
diagonal entries of each D j come from
a different translation of a common
window function of width w, and we
only consider every lth translation of
this window. This particular measurement model finds applications in crosscorrelation frequency-resolved optical
gating (XFROG), in which one measures ultrafast laser pulses by optically
producing a spectrogram; another application is ptychography, a diffractive
imaging method where different overlapping patches of the unknown object
are measured. For the short-time Fourier
transform model, we know that x 0 is
not uniquely determined if it has w
consecutive zeros, but (1) does uniquely
determine most nonvanishing signals
when l % w % n.
Example 3
Consider the short-time Fourier transform of a signal of length n = 6. We
choose the measurement window as a
rectangular function of length w = 3
159
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