On the stability of Gabor phase retrieval
Matthias WELLERSHOFF1 ; Rima ALAIFARI2
1 Seminar for Applied Mathematics, ETH Zürich, Switzerland, matthias.wellershoff@sam.math.ethz.ch
2 Seminar for Applied Mathematics, ETH Zürich, Switzerland, rima.alaifari@sam.math.ethz.ch

ABSTRACT
Phase retrieval refers to the problem of recovering a signal from phaseless measurements. Gabor phase retrieval, in particular, is concerned with reconstruction from the absolute value of the Gabor transform and has
applications in the time-frequency analysis of audio signals. From a mathematical point of view, phase retrieval(from frame coefficients) is a challenging problem as it has been shown to be unstable in infinite dimensional
Hilbert spaces and severely ill-conditioned in finite dimensional spaces. However, it has also been shown that
one can relax the classical stability regime to so-called semi-global phase reconstruction and obtain a stability
result for phase retrieval from the continuous Gabor transform in this setting. Recently, we were able to adapt
semi-global phase reconstruction to the discrete case and to prove a promising stability result for the discrete
Gabor transform. In this contribution, we survey selected highlights from recent research on phase retrieval
from frame coefficients with emphasis on phase retrieval from Gabor measurements. In particular, we review
results on semi-global stability of phase retrieval in the infinite dimensional case and present our result in thefinite dimensional setting.

Keywords: Phase retrieval, Time-frequency analysis, Gabor transform

1

INTRODUCTION

In audio processing, among other applications, one sometimes wants to reconstruct an unknown signal x frommeasurements that do not contain phase information. This reconstruction problem is widely known as phaseretrieval. Mathematically, phase retrieval can be modelled with the help of a Hilbert space H and a frameΦ = {φλ }λ ∈Λ of H in such a way that we seek to reconstruct x ∈ H from the measurements {|(x, φλ )|}λ ∈Λ .
In this form, it occurs in applications such as signal noise reduction (1), automatic speech recognition (2) or
the phase vocoder (3, 4).
The most popular algorithms for phase retrieval up to this point are so-called alternating projection methods
originating with the well-known Gerchberg–Saxton algorithm (5) and the further developments in (6). Unfortunately, it is known that the Gerchberg–Saxton algorithm can fail to converge to the desired solution and thesame is true for the methods proposed in (6) in the presence of noise. Of course, various methods exist to
overcome the limitations of the algorithms in (5, 6), but as we do not want to focus on algorithmic methods inthis paper, we will refer the reader to the survey (7). In recent years, a host of other methods have surfaced
which we want to mention, however. Among those are PhaseLift (8), which solves the phase retrieval problem
using semidefinite programming techniques but suffers from immense computational costs, Wirtinger Flow (9),which boils down to performing gradient descent on a non-convex cost function from a suitably chosen initial
guess, and PhaseMax (10, 11), which like PhaseLift uses a convex relaxation but unlike PhaseLift operates on
the natural parameter space and does therefore allow for efficient implementation.
Most of the theoretical guarantees for the success of the aforementioned methods rely on measurement systems{φλ }λ ∈Λ ⊂ CL whose individual elements are chosen independently at random and which contain sufficiently
many measurement vectors (8, 9, 11). In addition, there are a few results based on random measurement systems
which are more closely related to the Gabor transform (12, 13). Notably absent from these results, however,are statements about deterministic measurement systems and in particular frames for Hilbert spaces.
Among the theoretical work for phase retrieval from deterministic measurements, we want to shortly highlight3369

the research on polarisation for phase retrieval in (14, 15) as well as the research on generic frames in (16–19). More theoretical work (and numerical experiments) on deterministic phase retrieval has been carried out in(20–24).
This paper is sructured as follows. Section 2 provides an overview over the classical mathematical theory ofphase retrieval. In particular, the instability of phase retrieval in infinite dimensional spaces and the stability
yet ill-conditionedness of phase retrieval in finite dimensional spaces are discussed. Section 3 contains theintroduction of the concept of semi-global phase reconstruction. In particular, the pioneering work on infinite
dimensional spaces (25) as well as recent work on finite dimensional spaces is described. The paper ends in aconclusion which points out interesting future avenues of research.

2

PHASE RETRIEVAL IN THE CLASSICAL SETTING

Let K be either C or R, H a Hilbert space over K with inner product (·, ·) : H × H → K, Λ some index
set and Φ := {φλ }λ ∈Λ ⊂ H a set of measurement elements. Then, the recovery of x ∈ H from the measurements {|(x, φλ )|}λ ∈Λ is immediately seen to be impossible as all signals in {xeiα }α∈R generate the samemeasurements. It is the canon in the literature to circumvent this problem by recovering signals up to global
phase. Mathematically, this is captured by introducing the quotient spaces PR H := H /{−1, 1} as well as
PC H := H /S 1 and measuring the distance between signals via the metricdH (x, y) := min {kx − τykH | τ ∈ K, |τ| = 1} ,x, y ∈ H .

The phase retrieval problem is formulated as the inversion of the phase retrieval operator AΦ : PK H → RΛ+given byAΦ [x] := {|(x, φλ )|}λ ∈Λ ,x∈H .
In this paper, we are mainly interested in phase retrieval from the discrete and continuous Gabor transform. We
will therefore consider a window function φ ∈ L2 (R) and a signal x ∈ L2 (R) in order to define the (continuous)
Gabor transformZt, ξ ∈ R.
Vφ [x](t, ξ ) := x(s)φ (s − t)e−2πisξ ds,
R

Gabor phase retrieval does then refer to the recovery of x from |Vφ [x]| which is exactly the recovery of x fromAΦ [x], for Φ := {φ(t,ξ ) (s) = φ (s − t)e2πisξ |t, ξ ∈ R}. The discrete case is very similar to the continuous one:
For a window function φ ∈ CL and a signal x ∈ CL , we introduce the discrete Gabor transform`n1 L−1Vφd [x](m, n) := √ · ∑ x(`)φ (` − m)e−2πi L ,L `=0m, n = 0, . . . , L − 1,

where the indexing of φ (and in general all vectors in this paper) is understood to be evaluated modulo L.
Discrete Gabor phase retrieval does then refer to the recovery of x from |Vφd [x]| which is exactly the recovery
of x from AΦd [x], for Φd := {φ (m,n) (`) = φ (` − m)e2πi`n/L | m, n = 0, . . . , L − 1}.
2.1 Injectivity
The injectivity of the phase retrieval operator is an interesting (and vast) topic in its own right. We broach
this subject here as it plays an important role in the stability results we present subsequently. It is well-known(16, 17, 26, 27) that injectivity of the phase retrieval operator in spaces over the real field is equivalent tothe so-called complement property introduced by Balan, Casazza and Edidin (16) in 2006. In spaces over thecomplex field, in contrast, the complement property is merely necessary for injectivity.
For Gabor phase retrieval, one can derive quite palpable uniqueness guarantees based on the relation of theGabor measurements with the ambiguity functions Vx [x] and Vφ [φ ] (22, 23, 28, 29). In particular, the following
simple lemma holds (28).

3370

x+
µ (s)

−µ

µ

s

x−
µ (s)

Figure 1. The most prominent example for instability of phase retrieval with continuous Gabor measurements.
Lemma 2.1. Let x, φ ∈ L2 (R) withVφ [φ ](t, ξ ) 6= 0,t, ξ ∈ R.

Then, x can be uniquely recovered from |Vφ [x]| (up to global phase).
For the discrete Gabor transform, one can derive the same result (see (23)).
2.2 Stability
The stability of phase retrieval in the classical setting can be fully characterised by continuity properties of theinverse of the phase retrieval operator. A first stability result, often called weak stability, is proven in (26, 27).
Lemma 2.2. Let Φ = {φλ }λ ∈Λ be a frame for H and suppose that AΦ is injective. Then, AΦ−1 is continuous.
Mere continuity of AΦ−1 is usually not enough, however, as it does not allow us to quantify the stability constantof the problem, which is the smallest c > 0 such that for all x, y ∈ H ,dH (x, y) ≤ c · kAΦ [x] − AΦ [y]k ,(1)

where k·k is some suitable norm. Using the compactness of the unit ball in finite dimensions, the authors of(26, 27) are able to show that phase retrieval in finite dimensional Hilbert spaces always admits a finite stability
constant. We say that finite dimensional phase retrieval is (strongly) stable.
Theorem 2.3. Let H be finite dimensional, Φ = {φλ }λ ∈Λ a frame for H and suppose that AΦ is injective. Then,the stability constant of phase retrieval satisfies c < ∞.
Unfortunately, the picture looks very different in the infinite dimensional setting and in fact the authors of(26, 27) proved that infinite dimensional phase retrieval is never (strongly) stable.
Theorem 2.4. Let H be infinite dimensional. Then, for every frame Φ = {φλ }λ ∈Λ for H (with finite upper framebound) and every c > 0, there exist x, y ∈ H such that inequality (1) is violated.
2.3 Severe ill-posedness and ill-conditionedness
Finite dimensional phase retrieval is a challenging problem in spite of its stability. This is because the stability
constants of phase retrieval from frame coefficients in finite dimensional Hilbert spaces might increase drastically

3371

10

Frequency [kHz]

8

6

4

2

0
0.0

0.5

1.0

1.5

2.0
Time [sec]

2.5

3.0

3.5

Figure 2. Spectrogram of an audio signal in which one may hear a bird and a bison.
in the dimension of the Hilbert spaces in question. This was first noticed by Cahill, Casazza and Daubechies(26) in 2016 when they constructed a sequence of finite dimensional subspaces (and frames) of an infinite
dimensional space along which the stability constants increased exponentially. A very similar construction that2
is easily understood can be found in (31). The authors consider two signals x±µ ∈ L (R), µ > 0, consisting of
two Gaussian bumps each. More precisely, they use the Gaussian window φ (s) = exp(−πs2 ) and the signalsx+µ (s) := φ (s − µ) + φ (s + µ),x−µ (s) := φ (s − µ) − φ (s + µ)−
3/4 and through some technical calculations one
depicted in figure 1. It is not hard to see that dL2 (R) (x+µ , xµ ) = 2
can establish (see (31)) that there exists a constant c > 0 such that−Vφ [x+µ ] − Vφ [xµ ]2

H 1 (R)≤ ce−µ ,where k·kH 1 (R) denotes the Sobolev norm. In particular, the stability of the recovery of x±µ from Gabormeasurements degrades at a rate that is (at least) exponential in the size of the time gap squared µ 2 andwe say that phase retrieval from continuous Gabor measurements is severely ill-posed. In the discrete case,
one can derive analogousS results. In particular, it is true that if we consider a family of window functions{φL | φ L ∈ CL , L ∈ N} ⊂ L∈N CL which is exponentially decaying in the sense that there exist L0 ∈ N, c > 0,
µ > 0 such that for all `, L ∈ N with L ≥ L0 and L0 ≤ ` + 1 ≤ L, |φL (`)| ≤ ce−µ` , then the stability constants(cL )L∈N of the corresponding discrete Gabor phase retrieval problems are (at least) exponentially increasing. We
say that phase retrieval from discrete Gabor measurements is severely ill-conditioned.

3

SEMI-GLOBAL PHASE RECONSTRUCTION

It was noticed by Alaifari, Daubechies, Grohs and Yin (25) in 2018 that all examples that were designedin the literature to show the severe ill-posedness of phase retrieval in infinite dimensions or the severe illconditionedness of phase retrieval in finite dimensions had one thing in common: The underlying measurementsAΦ [x] = {|(x, φλ )|}λ ∈Λ were disconnected in the sense that one could decompose (x, φ· ) : Λ → K, λ 7→ (x, φλ ),3372

into a sum of functions Fk : Λ → K, k = 1, . . . , K, whose support was essentially disjoint. Examples of thisinclude the functions xλ± ∈ L2 (R) designed in (31) and pictured in figure 1 which lead to a disconnectedness of
the Gabor transform in time or the digital signal x ∈ CL in which birdsong is superimposed on the bellow ofa bison and whose spectrogram (that is the absolute value of the discrete Gabor transform) is shown in figure
2. This insight led the authors of (25) to suggest that one should try to reconstruct signals up to semi-global
phase and not up to global phase as was common in the literature up to then. In particular, they suggested
that instead of reconstructing (x, φ· ) = ∑Kk=1 Fk (up to global phase) from |∑Kk=1 Fk | = AΦ [x], one should try
to reconstruct ∑Kk=1 eiαk Fk , with αk ∈ R, k = 1, . . . , K. Remarkably, this suggestion ties in very nicely with aphysical property of Gabor transform-based time-frequency analysis: The human ear cannot distinguish between
audio signals differing by semi-global phase. For examples of this, the reader is strongly advised to visit (32).
Mathematically, the authors of (25) formulated semi-global phase reconstruction by introducing so-called atoll
functions and were able to prove the following stability result for them1 .
Theorem 3.1 (Theorem 1.5 in (25)). Let φ (s) = exp(−πs2 ), f = ∑Kk=1 fk ∈ L2 (R) and g = ∑Kk=1 gk ∈ L2 (R), withVφ [ fk ] Br (z ) ∈ F ∈ C 1 (Brk (zk )) δk ≤ |F(z)| ≤ ∆k , |∇|F|(z)| ≤ ∆k , z ∈ Brk (zk ) ,kkwhere rk , δk , ∆k > 0 and zk ∈ C, as well as
Z
R2 \B

Z

2

Vφ [ fk ](t, ξ ) dt dξ ≤ εk2

and

rk

2

R2 \BrkVφ [gk ](t, ξ ) dt dξ ≤ εk2 ,where εk > 0, for k = 1, . . . , K. Then, there exist c0 , c1 > 0 such that
K

K

∆2

∑ fk − eiαk gk L2 (R) ≤ c0 · ∑ δ k2 · (1 + c1 rk )α1 ,...,αK
inf

k=1

k=1 k



K
2
· 1 + c1 (rk + 1)eπrk /2 · k|VΦ [ f ]| − |VΦ [g]|kH 1 (Br (zk )) + ∑ εk .
k

k=1

The proof of the above result fundamentally depends on the fact that the Gaussian window generates a Gabortransform with analytic model space (this is due to the intimate relation of the Gabor transform with Gaussian
window and the Bargmann transform which is explained in section 3.4 of (33)). Regrettably, it was shown in(34) that the Gaussian is the only window function for which the Gabor transform has an analytic model space.
Because of this, it remains unknown whether theorem 3.1 may be extended to more general window functionsφ ∈ L2 (R).
It is known, however, that theorem 3.1 may be extended to phase retrieval from discrete Gabor measurements
when one adapts the notion of semi-global phase reconstruction in a suitable (graph theoretic) way (29): Letx, y ∈ CL be two signals, δ0 > 0 and `0 ∈ {0, . . . , bL/2c − 1}. Define the graph G = (V, E) by
V := {` ∈ {0, . . . , L − 1} ||x(`)|, |y(`)| > δ0 }(2)

and placing an edge between two vertices `, `0 ∈ V if
1 ≤ ` − `0 ≤ `0 + 1

mod L.

(3)

In general, the graph G will consist of K ∈ {1, . . . , L − 1} connected components whose vertex sets can be denoted by {Vk }Kk=1 . Then, we say that x agrees with y up to semi-global phase if for every connected component
Vk ∈ {Vk }Kk=1 , there exists an αk ∈ R such that for all ` ∈ Vk ,x(`) = eiαk y(`).
1 Theorem 3.1 is displayed in a drastically simplified version here and the reader is invited to consult (25) for the full result and, in particular,

an in-depth explanation of the terminology ’atoll domains’.

3373

Theorem 3.2 (Theorem 3.5 in (29)). Consider two signals x, y ∈ CL , a window φ ∈ CL , two tolerance parametersδ0 , δ1 > 0 and a maximum time separation parameter `0 ∈ {0, . . . , bL/2c − 1}. Let G = (V, E) be defined by theequations (2) as well as (3) and assume that G has K connected components with vertex sets {Vk }Kk=1 . Then,K

1
inf∑ x − eiαk y `2 (Vk ) ≤ δ0 δ1 ·
α1 ,...,αK ∈R k=1!
1 min{kxk∞ , kyk∞ } K+· ∑ |Vk | ·
2
δ0
k=1
1
+ ·
δ0

2

Vφd [x] − Vφd [y]2F!
1 min{kxk∞ , kyk∞ } K+· ∑ |Vk | · ε
2
δ0
k=1

holds, where k·kF denotes the Frobenius norm and with ε > 0 satisfying
ε 2 `0 +1
= ∑
2
m=0

L−1

∑

|Ad [x](m, n) − Ad [y](m, n)|2 .

n=0|Ad [φ ](m,n)|≤δ1

The main weakness of the above statement is that it only allows for the treatment of signals whose discrete
Gabor transform is disconnected in time. A similar theorem may be deduced for signals with frequency gap but
a unifying result in which general time-frequency disconnectedness is treated is not known.
We want to finish this section by remarking that there exists a numerical method (35) for phase retrieval
from Gabor measurements which does signal reconstruction up to semi-global phase as described in (25).
The method, called phase gradient heap integration, relies on the analyticity of the model space of the Gabor transform with Gaussian window and reconstructs phase locally based on a finite difference version of the
Cauchy–Riemann equations.

4

CONCLUSIONSIn this survey paper, we have summarised selected highlights from recent research on Gabor phase retrieval. In
particular, we have covered classical stability results for phase retrieval from frame coefficients, the notion ofsemi-global phase reconstruction introduced by Alaifari, Daubechies, Grohs and Yin as well as their stability
result for continuous Gabor phase retrieval with Gaussian window. We want to end this survey by presenting
two interesting open research questions:
1. Can one prove stability of continuous Gabor phase retrieval in the semi-global regime for a windowfunction φ ∈ L2 (R) which is not the Gaussian? The difficulty here is that the approach by Alaifari,
Daubechies, Grohs and Yin breaks down for any non Gaussian window as the Gabor transform fails tohave an analytic model space.
2. Can one prove stability (in the sense that the stability constant does not increase too drastically in thespace dimension) of discrete Gabor phase retrieval in a truly semi-global regime? In particular, what
happens for general time-frequency disconnectedness in the discrete Gabor transform?

REFERENCES
1. Deller JR, Proakis JG, Hansen JH. Discrete time processing of speech signals. Englewood Cliffs, New Jersey,
USA: Prentice-Hall; 1993.
2. Becchetti C, Ricotti LP. Speech recognition: Theory and C++ implementation. New York, USA: Wiley; 1999.
3. Flanagan JL, Golden RM. Phase vocoder. Bell Syst Tech J. 1996;45(9):1493–1509.

3374

4. Griffin D, Lim J. Signal estimation from modified short-time Fourier transform. IEEE Trans Acoust.
1984;32(2):236–243.
5. Gerchberg RW, Saxton WO. A practical algorithm for the determination of the phase from image and diffraction plane pictures. Optik. 1972;35(2):237–246.
6. Fienup JR. Phase retrieval algorithms: A comparison. Appl Opt. 1982;21(15):2758–2769.
7. Shechtman Y, Eldar YC, Cohen O, Chapman HN, Miao J, Segev M. Phase retrieval with application to
optical imaging. IEEE Signal Process Mag. 2015;32(3):87–109.
8. Candès EJ, Strohmer T, Voroninski V. PhaseLift: Exact and stable signal recovery from magnitude measurements via convex programming. Commun Pure Appl Math. 2012;66(8):1241–1274.
9. Candès EJ, Li X, Soltanolkotabi M. Phase retrieval via Wirtinger flow: Theory and algorithms. IEEE TransInf Theory. 2015;61(4):1985–2007.
10. Bahmani S, Romberg J. A flexible convex relaxation for phase retrieval. Electron J Stat. 2017;11(2):5254–
5281.
11. Goldstein T, Studer C. PhaseMax: Convex phase retrieval via basis pursuit. IEEE Trans Inf Theory.
2018;64(4):2675–2689.
12. Candès EJ, Li X, Soltanolkotabi M. Phase retrieval from coded diffraction patterns. Appl Comput Harmon
Anal. 2015;39(2):277–299.
13. Gross D, Krahmer F, Kueng R. Improved recovery guarantees for phase retrieval from coded diffraction
patterns. Appl Comput Harmon Anal. 2017;42(1):37–64.
14. Bandeira AS, Chen Y, Mixon DG. Phase retrieval from power spectra of masked signals. Inf Inference.
2014;3(2):83–102.
15. Alexeev B, Bandeira AS, Fickus M, Mixon DG. Phase retrieval with polarisation. SIAM J Imaging Sci.
2017;7(1):35–66.
16. Balan R, Casazza P, Edidin D. On signal reconstruction without phase. Appl Comput Harmon Anal.
2006;20(3):345–356.
17. Bandeira AS, Cahill J, Mixon DG, Nelson A. Saving phase: Injectivity and stability for phase retrieval.
Appl Comput Harmon Anal. 2014;37(1):106–125.
18. Conca A, Edidin D, Hering M, Vinzant C. An algebraic characterisation of injectivity in phase retrieval.
Appl Comput Harmon Anal. 2015;38(2):346–356.
19. Vinzant C. A small frame and a certificate of its injectivity. In: Proceedings of the 11th international
conference on sampling theory and applications [conference proceedings on the Internet]; 2015 May 25–
29; Washington DC, USA. IEEE; 2015 [cited 2019 April 9]. p. 197–200. Available from: IEEE Xplore
https://ieeexplore.ieee.org/Xplore/home.jsp
20. Nawab S, Quatieri T, Lim J. Signal reconstruction from short-time Fourier transform magnitude. IEEE Trans
Acoust. 1983;31(4):986–998.
21. Eldar YC, Sidorenko P, Mixon DG, Barel S, Cohen O. Sparse phase retrieval from short-time Fourier
measurements. IEEE Signal Process Lett. 2015;22(5):638–642.

3375

22. Pfander GE, Zheltov P. Estimation of overspread scattering functions. IEEE Trans Signal Process.
2015;63(10):2451–2463.
23. Bojarovska I, Flinth A. Phase retrieval from Gabor measurements. J Fourier Anal Appl. 2015;22(3):542–
567.
24. Iwen MA, Preskitt B, Saab R, Viswanathan A. Phase retrieval from local measurements: Improved robustness via eigenvector-based angular synchronisation. Appl Comput Harmon Anal [journal on the Internet].
2018 June 18 [cited 2019 April 10]. doi: 10.1016/j.acha.2018.06.004. [Epub ahead of print]
25. Alaifari R, Daubechies I, Grohs P, Yin R. Stable phase retrieval in infinite dimensions. Found Comput
Math [journal on the Internet]. 2018 October 15 [cited 2019 April 10]. doi: 10.1007/s10208-018-9399-7.
[Epub ahead of print]
26. Cahill J, Casazza PG, Daubechies I. Phase retrieval in infinite-dimensional Hilbert spaces. Trans Am Math
Soc B. 2016;3(3):63–76.
27. Alaifari R, Grohs P. Phase retrieval in the general setting of continuous frames for Banach spaces. SIAM J
Math Anal. 2017;49(3):1895–1911.
28. Grohs P, Rathmair M. Stable Gabor phase retrieval and spectral clustering. Commun Pure Appl Math.
2019;72(5):981–1043.
29. Alaifari R, Wellershoff M. Stability estimates for phase retrieval from discrete Gabor measurements [preprint
on the Internet]. 2019 [cited 2019 April 12]. Available from: https://arxiv.org/pdf/1901.05296.pdf.
30. Bendory T, Beinert R, Eldar YC. Fourier phase retrieval: Uniqueness and algorithms. In: Boche H, Claire
G, Calderbank R, März M, Kutyniok G, Mathar R, eds. Compressed sensing and its applications. Cham,
Switzerland: Birkhäuser; 2018. p. 55–91.
31. Alaifari R, Grohs P. Gabor phase retrieval is severely ill-posed [preprint on the Internet]. 2018 [cited 2019
April 12]. Available from: https://arxiv.org/pdf/1805.06716.pdf.
32. Duke University, Department of Mathematics [Internet]. Durham, North Carolina, USA: Duke University,
Department of Mathematics; [cited 2019 April 16]. Yin R. Phase modification of acoustic signals in time domain; [cited 2019 April 16]. Available from: https://services.math.duke.edu/ rachel/research/PhaseRetrieval/acoustic_result/acoustic_result.html
33. Gröchenig K. Foundations of time-frequency analysis. New York, USA: Springer Science+Business Media;
2001.
34. Ascensi G, Bruna J. Model space results for the Gabor and wavelet transforms. IEEE Trans Inf Theory.
2009;55(5):2250–2259.
35. Průša Z, Balazs P, Søndergaard PL. A noniterative method for reconstruction of phase from STFT magnitude. IEEE/ACM Trans Audio, Speech Lang Process. 2017;25(5):1154–1164.

3376