STFT Phase Retrieval: Uniqueness Guarantees and Recovery Algorithms

I Introduction

In many physical measurement systems, the measurable quantity is the magnitude-square of the Fourier transform of the underlying signal. The problem of reconstructing a signal from its Fourier magnitude is known as phase retrieval . This reconstruction problem is one with a rich history and occurs in many areas of engineering and applied physics such as optics , X-ray crystallography , astronomical imaging , speech recognition , computational biology , blind channel estimation and more. We refer the readers to for a comprehensive survey of classical approaches. Recent reviews can be found in .

It is well known that phase retrieval is an ill-posed problem . In order to be able to uniquely identify the underlying signal, various methods have been explored, which can be broadly classified into two categories: (i) Additional prior information: common approaches include bounds on the support of the signal and sparsity constraints . (ii) Additional magnitude-only measurements: popular examples include the use of structured illuminations and masks , and Short-Time Fourier Transform (STFT) magnitude measurements .

We consider STFT phase retrieval, which is the problem of reconstructing a signal from its STFT magnitude. In some applications of phase retrieval, it is easy to obtain such measurements. One example is Frequency Resolved Optical Gating (FROG), which is a general method for measuring ultrashort laser pulses . Fourier ptychography , a technology which has enabled X-ray, optical and electron microscopy with increased spatial resolution without the need for advanced lenses, is another popular example. In applications such as speech processing, it is natural to work with the STFT instead of the Fourier transform as the spectral content of speech changes over time . The key idea, when using STFT measurements, is to introduce redundancy in the magnitude-only measurements by maintaining a substantial overlap between adjacent short-time sections. This mitigates the uniqueness and algorithmic issues of phase retrieval.

In this work, our contribution is two-fold:

(i) Uniqueness guarantees: Researchers have previously developed conditions under which the STFT magnitude uniquely identifies signals (up to a global phase). However, either prior information on the signal is assumed in order to provide the guarantees, or the guarantees are limited. For instance, the results provided in require exact knowledge of a small portion of the underlying signal. In , the guarantees developed are for the setup in which adjacent short-time sections differ in only one index. These limitations are primarily due to a small number of adversarial signals which cannot be uniquely identified from their STFT magnitude. Here, in contrast, we develop conditions under which the STFT magnitude is an almost surely unique signal representation. In particular, we show that, with the exception of a set of signals of measure zero, non-vanishing signals can be uniquely identified (up to a global phase) from their STFT magnitude if adjacent short-time sections overlap (Theorem III.1). We then extend this result to incorporate sparse signals which have a limited number of consecutive zeros (Corollary III.1).

(ii) Recovery algorithms: Researchers have previously developed efficient iterative algorithms based on classic optimization frameworks to solve the STFT phase retrieval problem. Examples include the Griffin-Lim (GL) algorithm and STFT-GESPAR for sparse signals . While these techniques work well in practice, they do not have theoretical guarantees. In and , a semidefinite relaxation-based STFT phase retrieval algorithm, called STliFT (see Algorithm 1 below), was proposed. In this work, we conduct extensive numerical simulations and provide theoretical guarantees for STliFT. In particular, we conjecture that STliFT can recover most non-vanishing signals (up to a global phase) from their STFT magnitude if adjacent short-time sections differ in at most half the indices (Conjecture IV.1). When this condition is satisfied, we argue that one can super-resolve (i.e., discard high frequency measurements) and reduce the number of measurements to $(4+{o}(1))N$, where $N$ is the length of the complex signal. Therefore, STliFT recovers most non-vanishing signals uniquely, efficiently and robustly, using an order-wise optimal number of phaseless measurements.

We prove this conjecture for the setup in which the exact knowledge of a small portion of the underlying signal is available (Theorem IV.1). For particular choices of STFT parameters, this portion vanishes asymptotically, due to which this setup is asymptotically reasonable. We also prove this conjecture for the case in which adjacent short-time sections differ in only one index (Theorem IV.2). We then extend these results to incorporate sparse signals which have a limited number of consecutive zeros (Corollary IV.1).

The rest of the paper is organized as follows. In Section 2, we mathematically formulate STFT phase retrieval and establish our notation. We present uniqueness guarantees in Section 3. Section 4 considers the STliFT algorithm and provides recovery guarantees. Numerical simulations are presented in Section 5. Section 6 concludes the paper.

II Problem Setup

Let $\mathbf{x}=(x,x,\ldots,x[N-1])^{T}$ be a signal of length $N$ and $\mathbf{w}=(w,w,\ldots,w[W-1])^{T}$ be a window of length $W$. The STFT of $\mathbf{x}$ with respect to $\mathbf{w}$, denoted by $\mathbf{Y}_{w}$, is defined as:

for $0\leq m\leq N-1$ and $0\leq r\leq R-1$, where the parameter $L$ denotes the separation in time between adjacent short-time sections and the parameter R=\big{\lceil}\frac{N+W-1}{L}\big{\rceil} denotes the number of short-time sections considered.

The STFT can be interpreted as follows: Suppose $\mathbf{w}_{r}$ denotes the signal obtained by shifting the flipped window $\mathbf{w}$ by $rL$ time units (i.e., $w_{r}[n]=w[rL-n]$) and $\circ$ is the Hadamard (element-wise) product operator. The $r$th column of $\mathbf{Y}_{w}$, for $0\leq r\leq R-1$, corresponds to the $N$ point DFT of $\mathbf{x}\circ\mathbf{w}_{r}$. In essence, the window is flipped and slid across the signal (see Figure 1 for a pictorial representation), and $\mathbf{Y}_{w}$ corresponds to the Fourier transform of the windowed signal recorded at regular intervals. This interpretation is known as the sliding window interpretation.

Let $\mathbf{Z}_{w}$ be the $N\times R$ measurements corresponding to the magnitude-square of the STFT of $\mathbf{x}$ with respect to $\mathbf{w}$ so that $Z_{w}[m,r]=\mathinner{\!\left\lvert Y_{w}[m,r]\right\rvert}^{2}$. Let $\mathbf{W}_{r}$, for $0\leq r\leq R-1$, be the $N\times N$ diagonal matrix with diagonal elements $(w_{r},w_{r},\ldots,w_{r}[N-1])$. STFT phase retrieval can be mathematically stated as:

for $0\leq m\leq N-1$ and $0\leq r\leq R-1$, where $\mathbf{f}_{m}$ is the conjugate of the $m$th column of the $N$ point DFT matrix and $\left<.,.\right>$ is the inner product operator. In fact, STFT phase retrieval can be equivalently stated by only considering the measurements corresponding to $0\leq r\leq R-1$ and $1\leq m\leq M$, for any parameter $M$ satisfying $2W\leq M\leq N$ (see Section VII for details). This equivalence significantly reduces the number of measurements when $W\ll N$, which is typically the case in practical methods. In Section 4, we further reduce the number of measurements per short-time section through super-resolution. In particular, we consider the setup with $2L\leq W\leq\frac{N}{2}$ and $4L\leq M\leq N$.

We use the following definitions: A signal $\mathbf{x}$ is said to be non-vanishing if $x[n]\neq 0$ for all $0\leq n\leq N-1$. Similarly, a window $\mathbf{w}$ is said to be non-vanishing if $w[n]\neq 0$ for all $0\leq n\leq W-1$. Further, a signal $\mathbf{x}$ is said to be sparse if it is not non-vanishing, i.e., $x[n]=0$ for at least one $0\leq n\leq N-1$.

III Uniqueness Guarantees

In this section, we review existing results regarding the uniqueness of STFT phase retrieval and present our uniqueness guarantees. The results are summarized in Table I.

In STFT phase retrieval, the global phase of the signal cannot be determined due to the fact that signals $\mathbf{x}$ and $e^{i\phi}\mathbf{x}$, for any $\phi$, always have the same STFT magnitude regardless of the choice of $\{\mathbf{w},L\}$. In contrast, in classic phase retrieval, signals which differ from each other by a global phase, time-shift and/ or conjugate-flip (together called trivial ambiguities) cannot be distinguished from each other as they have the same Fourier magnitude .

Observe that $L<W$ is a necessary condition in order to be able to uniquely identify most signals. If $L>W$, then the STFT magnitude does not contain any information from some locations of the signal. When $L=W$, adjacent short-time sections do not overlap and hence STFT phase retrieval is equivalent to a series of non-overlapping instances of classic phase retrieval. Since there is no way of determining the relative phase, time-shift or conjugate-flip between the windowed signals corresponding to the various short-time sections, most signals cannot be uniquely identified. For example, suppose $\{\mathbf{w},L\}$ is chosen such that $L=W=2$ and $w[n]=1$ for all $0\leq n\leq W-1$. Consider the signal $\mathbf{x}_{1}=(1,2,3)^{T}$ of length $N=3$. Signals $\mathbf{x}_{1}$ and $\mathbf{x}_{2}=(1,-2,-3)^{T}$ have the same STFT magnitude. In fact, more generally, signals $\mathbf{x}_{1}$ and $(1,e^{{i}\phi}2,e^{{i}\phi}3)^{T}$, for any $\phi$, have the same STFT magnitude.

For some specific choices of $\{\mathbf{w},L\}$, it has been shown that all non-vanishing signals can be uniquely identified from their STFT magnitude up to a global phase. In , it is proven that the STFT magnitude uniquely identifies non-vanishing signals up to a global phase for $L=1$ if the window $\mathbf{w}$ is chosen such that the $N$ point DFT of $(|w|^{2},|w|^{2},\ldots,|w[N-1]|^{2})$ is non-vanishing, $2\leq W\leq\frac{N+1}{2}$ and $W-1$ is coprime with $N$. In , the authors prove that if the first $L$ samples are known a priori, then the STFT magnitude can uniquely identify non-vanishing signals for any $L$ if the window $\mathbf{w}$ is chosen such that it is non-vanishing and $2L\leq W\leq\frac{N}{2}$.

In this work, we prove the following result for non-vanishing signals:

Almost all non-vanishing signals can be uniquely identified (up to a global phase) from their STFT magnitude if $\{\mathbf{w},L,M\}$ satisfy

The proof is based on a technique commonly known as dimension counting. The outline is as follows (see Section VIII for details):

Consider the short-time sections $r$ and $r+1$. Since adjacent short-time sections overlap (due to $L<W$), there exists at least one index, say $n_{0}$, where both $\mathbf{x}\circ\mathbf{w}_{r}$ and $\mathbf{x}\circ\mathbf{w}_{r+1}$ have non-zero values.

Since $W\leq\frac{N}{2}$, there can be at most $2^{W}$ distinct windowed signals $\mathbf{x}\circ\mathbf{w}_{r}$ (up to a phase) that have the same Fourier magnitude . Consequently, $\mathinner{\!\left\lvert x[n_{0}]\right\rvert}$ is restricted to $2^{W}$ values by the $r$th column of the STFT magnitude (let $\mathcal{S}_{r}$ denote the set of these values). Similarly, $\mathinner{\!\left\lvert x[n_{0}]\right\rvert}$ is restricted to $2^{W}$ values by the $r+1$th column of the STFT magnitude (denote the set of these values by $\mathcal{S}_{r+1}$).

By construction, $\mathcal{S}_{r}\cap\mathcal{S}_{r+1}\neq\phi$ as the STFT magnitude is generated by an underlying signal $\mathbf{x}_{0}$, i.e., $\mathinner{\!\left\lvert x_{0}[n_{0}]\right\rvert}\in\mathcal{S}_{r}\cap\mathcal{S}_{r+1}$. Using Lemma VIII.1 and Theorem VIII.1, we show that, for almost all non-vanishing signals, $\mathcal{S}_{r}\cap\mathcal{S}_{r+1}$ has cardinality one. In other words, $\mathbf{x}\circ\mathbf{w}_{r}$ is uniquely identified (up to a phase) almost surely.

Since adjacent short-time sections overlap, non-vanishing signals are uniquely identified up to a global phase from the knowledge of $\mathbf{x}\circ\mathbf{w}_{r}$ (up to a phase) for $0\leq r\leq R-1$ if $\mathbf{w}$ is non-vanishing. ∎

III-B Sparse signals

While the aforementioned results provide guarantees for non-vanishing signals, they do not say anything about sparse signals. Reconstruction of sparse signals involves certain challenges which are not encountered in the reconstruction of non-vanishing signals.

The following example is provided in to show that the time-shift ambiguity cannot be resolved for some classes of sparse signals and some choices of $\{\mathbf{w},L\}$: Suppose $\{\mathbf{w},L\}$ is chosen such that $L\geq 2$, $W$ is a multiple of $L$ and $w[n]=1$ for all $0\leq n\leq W-1$. Consider a signal $\mathbf{x}_{1}$ of length $N\geq L+1$ such that it has non-zero values only within an interval of the form $[(t-1)L+1,(t-1)L+L-p]\subset[0,N-1]$ for some integers $1\leq p\leq L-1$ and $t\geq 1$. The signal $\mathbf{x}_{2}$ obtained by time-shifting $\mathbf{x}_{1}$ by $q\leq p$ units (i.e., $x_{2}[i]=x_{1}[i-q]$) has the same STFT magnitude. The issue with this class of sparse signals is that the STFT magnitude is identical to the Fourier magnitude because of which the time-shift and conjugate-flip ambiguities cannot be resolved.

It is also shown that some sparse signals cannot be uniquely recovered even up to the trivial ambiguities for some choices of $\{\mathbf{w},L\}$ using the following example: Consider two non-overlapping intervals $[u_{1},v_{1}],[u_{2},v_{2}]\subset[0,N-1]$ such that $u_{2}-v_{1}>W$, and take a signal $\mathbf{x}_{1}$ supported on $[u_{1},v_{1}]$ and $\mathbf{x}_{2}$ supported on $[u_{2},v_{2}]$. The magnitude-square of the STFT of $\mathbf{x}_{1}+\mathbf{x}_{2}$ and of $\mathbf{x}_{1}-\mathbf{x}_{2}$ are equal for any choice of $L$. The difficulty with this class of sparse signals is that the two intervals with non-zero values are separated by a distance greater than $W$ because of which there is no way of establishing relative phase using a window of length $W$.

These examples demonstrate the fact that sparse signals are harder to recover than non-vanishing signals in this setup. Since the aforementioned issues are primarily due to a large number of consecutive zeros, the uniqueness guarantees for non-vanishing signals have been extended to incorporate sparse signals with limits on the number of consecutive zeros. In , it was shown that if $L$ consecutive samples, starting from the first non-zero sample, are known a priori, then the STFT magnitude can uniquely identify signals with less than $W-2L$ consecutive zeros for any $L$ if the window $\mathbf{w}$ is chosen such that it is non-vanishing and $2L\leq W\leq\frac{N}{2}$.

Below, we extend Theorem III.1 to prove the following result for sparse signals:

Almost all sparse signals with less than $\min\{W-L,L\}$ consecutive zeros can be uniquely identified (up to a global phase and time-shift) from their STFT magnitude if $\{\mathbf{w},L,M\}$ satisfy

The $\min\{W-L,L\}$ bound on consecutive zeros ensures the following: For sufficient pairs of adjacent short-time sections, there is at least one index among the overlapping and non-overlapping indices respectively, where the underlying signal has a non-zero value. We refer the readers to Section IX for details. ∎

IV Recovery Algorithms

The classic alternating projection algorithm to solve phase retrieval has been adapted to solve STFT phase retrieval by Griffin and Lim . To this end, STFT phase retrieval is reformulated as the following least-squares problem:

The Griffin-Lim (GL) algorithm attempts to minimize this objective by starting with a random initialization and imposing the time domain and STFT magnitude constraints alternately using projections. The objective is shown to be monotonically decreasing as the iterations progress. An important feature of the GL algorithm is its empirical ability to converge to the global minimum when there is substantial overlap between adjacent short-time sections. However, no theoretical recovery guarantees are available. To establish such guarantees, we rely on a semidefinite relaxation approach.

Semidefinite relaxation has enjoyed considerable success in provably and stably solving several quadratic-constrained problems . The steps to formulate such problems as a semidefinite program (SDP) are as follows: (i) Embed the problem in a higher dimensional space using the transformation $\mathbf{X}=\mathbf{x}\mathbf{x}^{\star}$, a process which converts the problem of recovering a signal with quadratic constraints into a problem of recovering a rank-one matrix with affine constraints. (ii) Relax the rank-one constraint to obtain a convex program.

If the convex program has a unique solution $\mathbf{X}_{0}=\mathbf{x}_{0}\mathbf{x}_{0}^{\star}$, then $\mathbf{x}_{0}$ is the unique solution to the quadratic-constrained problem (up to a global phase). Many recent results in related problems like generalized phase retrieval and phase retrieval using random masks suggest that one can provide conditions, which when satisfied, ensure that the convex program has a unique solution $\mathbf{X}_{0}=\mathbf{x}_{0}\mathbf{x}_{0}^{\star}$.

A semidefinite relaxation-based STFT phase retrieval algorithm, called STliFT, was explored in and . The details of the algorithm are provided in Algorithm 1. In the following, we develop conditions on $\{\mathbf{x}_{0},\mathbf{w},L\}$ which ensure that the convex program (4) has $\mathbf{X}_{0}=\mathbf{x}_{0}\mathbf{x}_{0}^{\star}$ as the unique solution. Consequently, under these conditions, STliFT uniquely recovers the underlying signal up to a global phase.

Based on extensive numerical simulations, we conjecture the following:

The convex program (4) has a unique solution $\mathbf{X}_{0}=\mathbf{x}_{0}\mathbf{x}_{0}^{\star}$, for most non-vanishing signals $\mathbf{x}_{0}$, if

The number of phaseless measurements considered can be calculated as follows: The total number of short-time sections is $\lceil{\frac{N+W-1}{L}}\rceil$. For each short-time section, $M=4L$ phaseless measurements are sufficient. Hence, the total number of phaseless measurements is $\lceil{\frac{N+W-1}{L}}\rceil\times 4L\leq 4\left({N+W}\right)+2W$. Consequently, when $W=o(N)$, this number is $(4+o(1))N$, which is order-wise optimal. In fact, in generalized phase retrieval, it is conjectured that $(4-o(1))N$ phaseless measurements are necessary .

The proof techniques used in and are not applicable in the STFT setup. In and , the measurement vectors are chosen from a random distribution such that they satisfy the restricted isometry property. Furthermore, the randomness in the measurement vectors is used to construct approximate dual certificates based on concentration inequalities. In the STFT setup, testing whether the given measurement vectors satisfy the restricted isometry property is difficult. Also, due to the lack of randomness in the measurement vectors, a different approach is required to construct dual certificates.

In the following, we develop a proof technique for the STFT setup, and use it to prove Conjecture IV.1, with additional assumptions.

The convex program (4) has a unique feasible matrix $\mathbf{X}_{0}=\mathbf{x}_{0}\mathbf{x}_{0}^{\star}$, for almost all non-vanishing signals $\mathbf{x}_{0}$, if

$x_{0}[n]$ for 0\leq n\leq\big{\lfloor}{\frac{L}{2}\big{\rfloor}} is known a priori.

While it is sufficient to show that (4) has a unique solution $\mathbf{X}_{0}=\mathbf{x}_{0}\mathbf{x}_{0}^{\star}$, observe that Theorem IV.1 ensures that (4) has a unique feasible matrix. This is a stronger condition, and as a consequence, the choice of the objective function does not matter in the noiseless setting. While this might suggest that the requirements of the setup are strong, we argue that it is not the case. In fact, this phenomenon is also observed in generalized phase retrieval (Section $1.3$ in ) and phase retrieval using random masks (Theorem $1.1$ in ).

Theorem IV.1 assumes prior knowledge of the first $\lceil{\frac{L}{2}}\rceil$ samples, i.e., half of the second short-time section is required to be known a priori. This is not a lot of prior information if $W\ll N$, which is typically the case. When $W=o(N)$, the fraction of the signal that is required to be known a priori is less than $\frac{W}{N}$, which tends to as $N\rightarrow\infty$.

The convex program (4) has a unique feasible matrix $\mathbf{X}_{0}=\mathbf{x}_{0}\mathbf{x}_{0}^{\star}$, for almost all non-vanishing signals $\mathbf{x}_{0}$, if

This is a direct consequence of Theorem IV.1. The value of $\mathinner{\!\left\lvert x_{0}\right\rvert}$ (and hence $x_{0}$, without loss of generality) can be inferred from the STFT magnitude if $L=1$. ∎

When $L=1$, the number of phaseless measurements is $4(N+W)$, which is again order-wise optimal. For example, when $W=2$, at most $4N+8$ phaseless measurements are considered. Unlike Theorem IV.1, no prior information is necessary.

Theorems IV.1 and IV.2 can be seamlessly extended to incorporate sparse signals:

The convex program (4) has a unique feasible matrix $\mathbf{X}_{0}=\mathbf{x}_{0}\mathbf{x}_{0}^{\star}$, for almost all sparse signals $\mathbf{x}_{0}$ which have at most $W-2L$ consecutive zeros, if

Either $L=1$ or $x_{0}[n]$ for $i_{0}\leq n<i_{0}+L$ is known a priori, where $i_{0}$ is the smallest index such that $x_{0}[i_{0}]\neq 0$.

IV-B Noisy Setting

In practice, the measurements are contaminated by additive noise, i.e., the measurements are of the form

for $1\leq m\leq M$ and $0\leq r\leq R-1$, where $\mathbf{z}_{r}=(z[0,r],z[1,r],\ldots,z[M-1,r])^{T}$ is the additive noise corresponding to the $r$th short-time section and $4L\leq M\leq N$. STliFT, in the noisy setting, can be implemented as follows: Suppose $\|\mathbf{z}_{r}\|_{2}\leq\eta$ for all $0\leq r\leq R-1$. The constraints in the convex program (4) can be replaced by

for $0\leq r\leq R-1$. We recommend the use of trace minimization as the objective function. Numerical simulations strongly suggest that STliFT can recover most non-vanishing signals stably in the noisy setting under certain conditions. The details of the simulations are provided in the following section.

V Numerical Simulations

In this section, we demonstrate the empirical abilities of STliFT using numerical simulations.

In the first set of simulations, we evaluate the performance of STliFT as a function of window and shift lengths. We choose $N=32$, and vary $\{L,W\}$. For each choice of $\{L,W\}$, we consider $M=4L$ phaseless measurements and perform $100$ trials. In every trial, we choose a random signal such that the values in each location are drawn from an i.i.d. standard complex normal distribution. We select the window $\mathbf{w}$ such that $w[n]=1$ for all $0\leq n\leq W-1$. The probability of successful recovery as a function of $\{L,W\}$ is plotted in Fig. 2a.

Observe that STliFT successfully recovers the underlying signal with very high probability when $2L\leq W\leq\frac{N}{2}$ and fails with very high probability when $2L>W$. The choice of $\{L,W\}=\{\frac{N}{4},\frac{N}{2}\}$ uses only six short-time sections and STliFT recovers the underlying signal with very high probability, which, given the limited success of semidefinite relaxation-based algorithms in the Fourier phase retrieval setup, is very encouraging.

In the second set of simulations, we evaluate the performance of STliFT as a function of shift length and measurements per short-time section. We choose $N=32$ and $W=16$, and vary $\{L,M\}$. For each choice of $\{L,M\}$, we perform $100$ trials as before. The probability of successful recovery as a function of $\{L,M\}$ is plotted in Fig. 2b. Observe that recovery is successful even in the $4L\leq M<2W$ regime.

In the third set of simulations, we evaluate the performance of STliFT in the noisy setting. We choose $M=2W$, the rest of the parameters are the same as the first set of simulations. The normalized mean-squared error, given by

is plotted as a function of SNR in Fig. 3. The linear relationship between them shows that STliFT stably recovers the underlying signal in the presence of noise. Also, it can be observed that the choices of $\{W,L\}$ which correspond to significant overlap between adjacent short-time sections tend to recover signals more stably compared to values of $\{W,L\}$ which correspond to less overlap, which is not surprising.

VI Conclusions and Future Directions

In this work, we considered the STFT phase retrieval problem. We showed that, if $L<W\leq\frac{N}{2}$, then almost all non-vanishing signals can be uniquely identified from their STFT magnitude (up to a global phase), and extended this result to incorporate sparse signals which have less than $\min\{W-L,L\}$ consecutive zeros.

For $2L\leq W\leq\frac{N}{2}$, we conjectured that most non-vanishing signals can be recovered (up to a global phase) by a semidefinite relaxation-based algorithm (STliFT). When $W=o(N)$, through super-resolution, we reduced the number of phaseless measurements to $(4+o(1))N$. We proved this conjecture for the setup in which the first \big{\lfloor}\frac{L}{2}+1\big{\rfloor} samples are known, and for the case in which $L=1$. We argued that the additional assumptions are asymptotically reasonable when $W\ll N$, which is typically the case in practical methods. We then extended these results to incorporate sparse signals which have at most $W-2L$ consecutive zeros.

Natural directions for future study include a proof of this conjecture without the additional assumptions, and a stability analysis in the noisy setting. Also, a thorough analysis of the phase transition at $2L=W$ will provide a more complete characterization of STliFT.

Acknowledgements: We would like to thank Mordechai Segev and Oren Cohen for introducing us to the STFT phase retrieval problem, and for many insightful discussions.

References

Appendix

VII Equivalent definition of stft phase retrieval

Since we consider $N$ point DFT and $W$ satisfies $W\leq\frac{N}{2}$, STFT phase retrieval can be equivalently stated in terms of the short-time autocorrelation $\mathbf{a}_{w}$ :

for $0\leq m\leq N-1$ and $0\leq r\leq R-1$.

The knowledge of the short-time autocorrelation is sufficient for all the guarantees provided in this paper. Note that the $r$th column of $\mathbf{Z}_{w}$ and the $r$th column of $\mathbf{a}_{w}$ are Fourier pairs. Hence, for a particular $r$, if $Z_{w}[m,r]$ for $0\leq m\leq N-1$ is available, then $a_{w}[m,r]$ for $0\leq m\leq N-1$ can be calculated by taking an inverse Fourier transform. The following lemma shows that $2W$ phaseless measurements per short-time section are sufficient to infer the short-time autocorrelation.

$Z_{w}[m,r]$ for $1\leq m\leq 2W-1$ is sufficient to calculate $a_{w}[m,r]$ for $0\leq m\leq N-1$.

If the window length is $W$, then $\mathbf{a}_{w}$ has non-zero values only in the interval $0\leq m\leq W-1$ and $N-W+1\leq m\leq N-1$. Let $\mathbf{b}_{w}$ be the signal obtained by circularly shifting $\mathbf{a}_{w}$ by $W-1$ rows, so that $\mathbf{b}_{w}$ has non-zero values only in the interval $0\leq m\leq 2W-2$. Since the submatrix of the $N$ point DFT matrix obtained by considering the first $2W-1$ columns and any $2W-1$ rows is invertible (the Vandermonde structure is retained), $Z_{w}[m,r]$ for $1\leq m\leq 2W-1$ and $b_{w}[m,r]$ for $0\leq m\leq 2W-2$ are related by an invertible matrix. Note that $a_{w}[m,r]$ for $0\leq m\leq N-1$ can be trivially calculated from $b_{w}[m,r]$ for $0\leq m\leq 2W-2$. ∎

Consequently, if the $N$ point DFT is used and $2W\leq M\leq N$ is satisfied, the affine constraints in (4) can be rewritten in terms of $\mathbf{a}_{w}$ and $\mathbf{X}$ as:

VIII Proof of Theorem III.1

The symbol $\equiv$ is used to denote equality up to a global phase and time-shiftFor non-vanishing signals, there is no ambiguity due to time-shift.. We say that two signals $\mathbf{x}_{1}$ and $\mathbf{x}_{2}$ are distinct if $\mathbf{x}_{1}\not\equiv\mathbf{x}_{2}$, and equivalent if $\mathbf{x}_{1}\equiv\mathbf{x}_{2}$.

Let $\mathcal{P}_{c}\subset\mathcal{P}$ be the set of distinct non-vanishing complex signals which cannot be uniquely identified from their STFT magnitude if $\mathbf{w}$ is chosen such that it is non-vanishing and $W\leq\frac{N}{2}$. We show that $\mathcal{P}_{c}$ has measure zero in $\mathcal{P}$. In order to do so, our strategy is as follows:

Consider two signals $\mathbf{x}_{1}\not\equiv\mathbf{x}_{2}$ of length $N$ which have the same STFT magnitude. If the window $\mathbf{w}$ is chosen such that it is non-vanishing and $W\leq\frac{N}{2}$, then, for each $r$, there exists signals $\mathbf{g}_{r}$ and $\mathbf{h}_{r}$, of lengths $l_{gr}$ and $l_{hr}$ respectively, such that

$g_{r}[l_{gr}-1]=1$ and $\{g_{r},h_{r},h_{r}[l_{hr}-1]\}\neq 0$

where $\star$ is the convolution operator. Further, there exists at least one $r$ such that

$l_{hr}\geq 2$, $h_{r}$ is real and positive.

The conditions (ii) and (iii) are properties of convolution (see Lemma $7.1$ of for details), and therefore hold for every $r$.

Furthermore, if $l_{hr}=1$ for all $0\leq r\leq R-1$, then $\mathbf{x}_{1}\equiv\mathbf{x}_{2}$. Hence, $l_{hr}\geq 2$ for at least one $r$. For this $r$, since $e^{i\phi_{1}}\mathbf{x}_{1}$ and $e^{i\phi_{2}}\mathbf{x}_{2}$ have the same STFT magnitude, $h_{r}$ can be assumed to be real and positive without loss of generality. Hence, (iv) holds for at least one $r$. ∎

We first show the arguments for the $L=W-1$ case as the expressions are simple and provide intuition for the technique. Then, we show the arguments for the $L<W-1$ case.

${(i)~{}L=W-1\mathrel{\mathop{\mathchar 58\relax}}}$

The set $\mathcal{Q}_{c}^{rl_{r}l_{r+1}}$ is constructed as follows: Consider the variables $\{\mathbf{g}_{r},\mathbf{h}_{r},\mathbf{g}_{r+1},\mathbf{h}_{r+1}\}$ satisfying $l_{hr}=l_{r}\geq 2$ and $l_{h,r+1}=l_{r+1}$, and $x[n]$ for $n\in[0,u_{r})\cup(v_{r+1},N-1]$. The map $f=(f_{0},f_{1},\ldots,f_{N-1})^{T}$ from these variables to $\mathcal{P}$ is the following:

Since the short-time sections $r$ and $r+1$ overlap in the index $v_{r}$, $\mathbf{g}_{r}\star\mathbf{h}_{r}$ and $\mathbf{g}_{r+1}\star\mathbf{h}_{r+1}$ must be consistent in this index, i.e., $\{\mathbf{g}_{r},\mathbf{h}_{r}\}$ must satisfy:

Observe that $\equiv$ is used in (10), due to the fact that the equality is only up to a phase. However, $h_{r}$ is real and positive (see Lemma VIII.1), due to which (10) fixes $h_{r}$.

${(ii)~{}L<W-1\mathrel{\mathop{\mathchar 58\relax}}}$

The short-time sections $r$ and $r+1$ overlap in the interval $[u_{r+1},v_{r}]$. Let $v_{r}-u_{r+1}+1=T$ (the number of indices in the overlapping interval). Due to $2L\geq W$, we have $T=W-L\leq\lfloor{\frac{W}{2}\rfloor}$. Hence, for each choice of $\{\mathbf{g}_{r+1},\mathbf{h}_{r+1}\}$, $\{\mathbf{g}_{r},\mathbf{h}_{r}\}$ must satisfy:

for $0\leq n\leq T-1$. In addition, $\{\mathbf{g}_{r},\mathbf{h}_{r}\}$ must also satisfy:

If $l_{gr}\geq\lfloor{\frac{W}{2}\rfloor}+1$ instead, then the bilinear equations (11) can be equivalently written as $\mathbf{H}\mathbf{g}_{r}=\mathbf{c}$, the same arguments may be applied to draw the same conclusion. For the setup with $2L>W$, the same arguments hold for the short-time sections $r$ and $r+t$, where $t$ is the largest integer such that the short-time sections $r$ and $r+t$ overlap (this ensures $T\leq\lfloor{\frac{W}{2}\rfloor}$).

IX Proof of Corollary III.1

We now extend Theorem III.1 to incorporate sparse signals. Let $\mathcal{P}^{S}$ denote the set of all distinct complex signals of length $N$ with a support $S$. Here, $S$ is a binary vector of length $N$, such that $x[n]\neq 0$ whenever $S[n]=1$ and $x[n]=0$ whenever $S[n]=0$. Further, $S$ has less than $\min\{L,W-L\}$ consecutive zeros.

Let $\mathcal{P}_{c}^{S}\subset\mathcal{P}^{S}$ denote the set of signals which cannot be uniquely identified from their STFT magnitude if $\mathbf{w}$ is chosen such that it is non-vanishing and $W\leq\frac{N}{2}$. We show that $\mathcal{P}_{c}^{S}$ has measure zero in $\mathcal{P}^{S}$.

In the proof of Theorem III.1, in order to show dimension reduction, we used the fact that for sufficient pairs of adjacent short-time sections $r$ and $r+1$, the following holds:

(i) There is at least one index in the non-overlapping indices $[u_{r},u_{r+1}-1]$ or $[v_{r}+1,v_{r+1}]$ where the signals $\mathbf{x}_{1}$ and $\mathbf{x}_{2}$ have a non-zero value. This ensures that $h_{r}$ is not constrained by $\{\mathbf{g}_{r+1},\mathbf{h}_{r+1}\}$ in general. This condition can be ensured by imposing the constraint that the sparse signal cannot have $L$ consecutive zeros.

(ii) There is at least one index in the overlapping indices $[u_{r+1},v_{r}]$ where the signals $\mathbf{x}_{1}$ and $\mathbf{x}_{2}$ have a non-zero value. This ensures that $h_{r}$ is constrained by $\{\mathbf{g}_{r+1},\mathbf{h}_{r+1}\}$ (10) for signals which cannot be uniquely identified by their STFT magnitude. This condition can be ensured by imposing the constraint that the sparse signal cannot have $W-L$ consecutive zeros.

The only difference in the proof is the following: Unlike in the case of non-vanishing signals, there is time-shift ambiguity. Hence, the constraint (12) is replaced by:

for some $0\leq n\leq T-1$. This fixes the value of $h_{r}$ to one of at most $T$ values, due to which there is a dimension reduction.

X Proof of Theorem IV.1

We first show the arguments for the case $2W\leq M\leq N$ (short-time autocorrelation known) as the expressions are simple and provide intuition. Then, we show the arguments for the case $4L\leq M<2W$ (super-resolution).

${(i)~{}2W\leq M\leq N\mathrel{\mathop{\mathchar 58\relax}}}$

The affine constraints in (4) can be rewritten as (see Section VII):

The proof strategy is as follows: We begin by focusing our attention on short-time section $r=1$. We show that the prior information available, along with the affine autocorrelation measurements corresponding to $r=1$ and the positive semidefinite constraint, will ensure that every feasible matrix of (4) satisfies $X[n,m]=x_{0}[n]x_{0}^{\star}[m]$ for $0\leq n,m\leq L$. We then apply this argument incrementally, i.e., we show that the affine measurements corresponding to short-time section $r$, along with the entries of $\mathbf{X}$ uniquely determined and the positive semidefinite constraint, will ensure that $X[n,m]=x_{0}[n]x_{0}^{\star}[m]$ for $u_{r}\leq n,m\leq v_{r}$, where $u_{r}$ and $v_{r}$ denote the smallest and largest index where $\mathbf{w}_{r}$ has a non-zero value respectively. Consequently, the entries along the diagonal and the first $W-L$ off-diagonals of every feasible matrix of (4) match the entries along the diagonal and the first $W-L$ off-diagonals of the matrix $\mathbf{x}_{0}\mathbf{x}_{0}^{\star}$. Since the entries are sampled from a rank one matrix with non-zero diagonal entries (i.e., $\mathbf{x}_{0}\mathbf{x}_{0}^{\star}$), there is exactly one positive semidefinite completion, which is the rank one completion $\mathbf{x}_{0}\mathbf{x}_{0}^{\star}$ .

Let $\mathbf{s}_{0}=(x_{0},x_{0},\ldots,x_{0}[L])^{T}$ be a length $L+1$ subsignal of $\mathbf{x}_{0}$, and $\mathbf{S}$ be the $(L+1)\times(L+1)$ submatrix of $\mathbf{X}$ corresponding to the first $L+1$ rows and columns. We now show that $\mathbf{S}=\mathbf{s}_{0}\mathbf{s}_{0}^{\star}$ is the only feasible matrix under the constraints of (4).

Since $x_{0}[n]$ for 0\leq n\leq\big{\lfloor}{\frac{L}{2}\big{\rfloor}} is known a priori, we have $S[n,m]=x_{0}[n]x_{0}^{\star}[m]$ for 0\leq n,m\leq\big{\lfloor}{\frac{L}{2}\big{\rfloor}}. Let $\mathcal{A}(\mathbf{S})=\mathbf{c}$ denote these constraints due to prior information, along with the affine constraints corresponding to $r=1$. In particular, $\mathcal{A}(\mathbf{S})=\mathbf{c}$ denotes the following set of constraints:

For each feasible matrix $\mathbf{S}$, these set of measurements fix (i) the \big{\lfloor}{\frac{L}{2}+1\big{\rfloor}\times\big{\lfloor}\frac{L}{2}+1\big{\rfloor}} submatrix, corresponding to the first \big{\lfloor}{\frac{L}{2}+1\big{\rfloor}} rows and columns, of $\mathbf{S}$ (ii) the appropriately weighted sum along the diagonal and each off-diagonal of $\mathbf{S}$ ($2L\leq W$ is implicitly used here).

If $\mathbf{S}_{0}=\mathbf{s}_{0}\mathbf{s}_{0}^{\star}$ satisfies $\mathcal{A}(\mathbf{S})=\mathbf{c}$, then it is the only positive semidefinite matrix which satisfies $\mathcal{A}(\mathbf{S})=\mathbf{c}$.

Let $T$ be the set of Hermitian matrices of the form

and $T^{\perp}$ be its orthogonal complement. The set $T$ may be interpreted as the tangent space at $\mathbf{s}_{0}\mathbf{s}_{0}^{\star}$ to the manifold of Hermitian matrices of rank one. Influenced by , we use $\mathbf{S}_{T}$ and $\mathbf{S}_{T^{\perp}}$ to denote the projection of a matrix $\mathbf{S}$ onto the subspaces $T$ and $T^{\perp}$ respectively.

Standard duality arguments in semidefinite programming show that the following are sufficient conditions for $\mathbf{S}_{0}=\mathbf{s}_{0}\mathbf{s}_{0}^{\star}$ to be the unique optimizer of (4):

Condition 1: $\mathbf{S}\in T\quad\textrm{and}\quad\mathcal{A}(\mathbf{S})=0\Rightarrow\mathbf{S}=0$.

Condition 2: There exists a dual certificate $\mathbf{D}$ in the range space of $\mathcal{A}^{\star}$ obeying:

The proof of this result is based on KKT conditions, and can be found in any standard reference on semidefinite programming (for example, see ).

We first show that Condition 1 is satisfied. The set of constraints in $\mathcal{A}(\mathbf{S})=0$ due to prior information fix the entries of the first \big{\lfloor}{\frac{L}{2}+1\big{\rfloor}} rows and columns of $\mathbf{S}$ to . Since $\mathbf{S}=\mathbf{s}_{0}\mathbf{v}^{\star}+\mathbf{v}\mathbf{s}_{0}^{\star}$ for some $\mathbf{v}=(v,v,\ldots,v[L])^{T}$ (due to $\mathbf{S}\in T$), we infer that $v[n]=icx_{0}[n]$ for 0\leq n\leq\big{\lfloor}{\frac{L}{2}\big{\rfloor}}, for some real constant $c$. Indeed, the equations of the form $s_{0}[n]v^{\star}[n]+v[n]s_{0}^{\star}[n]=0$ imply $v[n]=ic_{n}x_{0}[n]$, for some real constant $c_{n}$. The equations $s_{0}[n]v^{\star}[m]+v[n]s_{0}^{\star}[m]=0$ imply $c_{n}=c_{m}$.

The set of constraints in $\mathcal{A}(\mathbf{S})=0$ due to the measurements corresponding to $r=1$, along with $v[n]=icx_{0}[n]$ for 0\leq n\leq\big{\lfloor}{\frac{L}{2}\big{\rfloor}}, imply $v[n]=icx_{0}[n]$ for \big{\lfloor}{\frac{L}{2}+1\big{\rfloor}}\leq n\leq L. Hence, for $\mathbf{S}\in T$, $\mathcal{A}(\mathbf{S})=0$ implies $\mathbf{v}=ic\mathbf{s}_{0}$, which in turn implies $\mathbf{S}=-ic\mathbf{s}_{0}\mathbf{s}_{0}^{\star}+ic\mathbf{s}_{0}\mathbf{s}_{0}^{\star}=0$.

We next establish Condition 2. For simplicity of notation, we consider the case where $w[n]=1$ for $0\leq n\leq W-1$. For a general non-vanishing $\mathbf{w}$, the same arguments hold (the Toeplitz matrix considered is appropriately redefined with weights).

The range space of $\mathcal{A}^{\star}$ is the set of all $L+1\times L+1$ matrices which are a sum of the following two matrices: The first matrix can have any value in the \big{\lfloor}{\frac{L}{2}+1\big{\rfloor}\times\big{\lfloor}\frac{L}{2}+1\big{\rfloor}} submatrix corresponding to the first \big{\lfloor}{\frac{L}{2}+1\big{\rfloor}} rows and columns, and has a value zero outside this submatrix (dual of the set of constraints due to prior information). The second matrix has a Toeplitz structure (dual of the measurements corresponding to $r=1$).

Suppose $\mathbf{s}_{1}$ is the vector containing the first \big{\lfloor}{\frac{L}{2}+1\big{\rfloor}} entries of $\mathbf{s}_{0}$ and $\mathbf{s}_{2}$ is the vector containing the remaining entries of $\mathbf{s}_{0}$. Here, $\mathbf{s}_{1}$ corresponds to the locations where we have knowledge of the entries and $\mathbf{s}_{2}$ corresponds to the locations where the entries are not determined. Let $\mathbf{L}$ be a lower triangular \big{\lceil}{\frac{L}{2}\big{\rceil}}\times\big{\lfloor}{\frac{L}{2}+1\big{\rfloor}} Toeplitz matrix satisfying $\mathbf{L}\mathbf{s}_{1}+\mathbf{s}_{2}=0$. Such an $\mathbf{L}$ always exists if $s_{1}$ is non-zero and the length of $\mathbf{s}_{1}$ is greater than or equal to the length of $\mathbf{s}_{2}$. Let $\Lambda$ be any \big{\lfloor}{\frac{L}{2}+1\big{\rfloor}}\times\big{\lfloor}{\frac{L}{2}+1\big{\rfloor}} positive semidefinite matrix with rank \big{\lfloor}{\frac{L}{2}\big{\rfloor}} satisfying $\Lambda\mathbf{s}_{1}=0$. Again, such a $\Lambda$ always exists (any positive semidefinite matrix with eigenvectors perpendicular to $\mathbf{s}_{1}$). Consider the following dual certificate:

Clearly, $\mathbf{D}$ is in the range space of $\mathcal{A}^{\star}$. Also, $\mathbf{D}\mathbf{s}_{0}=0$ by construction. From the Schur complement, it is straightforward to see that $rank(\mathbf{D})=L$ and $\mathbf{D}\succcurlyeq 0$. ∎

We have shown that $\mathbf{S}_{0}=\mathbf{s}_{0}\mathbf{s}_{0}^{\star}$ is the only positive semidefinite matrix which satisfies the prior information and the measurements corresponding to $r=1$. Redefine $\mathbf{s}_{0}$ and $\mathbf{S}$ such that $\mathbf{s}_{0}=(x_{0},x_{0},\ldots,x_{0}[2L])^{T}$ is the $2L+1$ length subsignal of $\mathbf{x}$ and $\mathbf{S}$ is the $(2L+1)\times(2L+1)$ submatrix of $\mathbf{X}$ corresponding to the first $2L+1$ rows and columns.

We already have $S[n,m]=x_{0}[n]x_{0}^{\star}[m]$ for $0\leq n,m\leq L$ from above. Let $\mathcal{A}(\mathbf{S})=\mathbf{c}$ denote these constraints, along with the affine constraints corresponding to $r=2$. Due to $2L\leq W$, Lemma X.1 proves that $\mathbf{S}_{0}=\mathbf{s}_{0}\mathbf{s}_{0}^{\star}$ is the only psd matrix which satisfies the prior information and the measurements corresponding to $r=1,2$. Applying this argument incrementally, the entries along the diagonal and the first $W-L$ off-diagonals of every feasible matrix of (4) match the entries along the diagonal and the first $W-L$ off-diagonals of the matrix $\mathbf{x}_{0}\mathbf{x}_{0}^{\star}$.

Sparse signals: The arguments can be seamlessly extended to incorporate sparse signals.

(i) The fact that there exists a unique positive semidefinite completion once the diagonal and the first $W-L$ off-diagonal entries are sampled from $\mathbf{x}_{0}\mathbf{x}_{0}^{\star}$ holds when $\mathbf{x}_{0}$ has less than $W-L$ consecutive zeros.

(ii) Note that the length of $\mathbf{s}_{2}$ is at most $L$, as it corresponds to the locations in the window where the entries are not determined. Since we know $x_{0}[n]$ for $i_{0}\leq n<i_{0}+L$ a priori, where $i_{0}$ is the smallest index such that $x_{0}[i_{0}]\neq 0$, the length of $\mathbf{s}_{1}$ is $W-L$. Redefine $\mathbf{s}_{1}$ so that it corresponds to the locations in the window where the entries are determined, starting from the smallest index which has a non-zero value in order to ensure $s_{1}\neq 0$. If $\mathbf{x}_{0}$ has at most $W-2L$ consecutive zeros, then the length of $\mathbf{s}_{1}$ is at least $(W-L)-(W-2L)=L$. Hence, a lower triangular Toeplitz matrix $\mathbf{L}$, satisfying $\mathbf{L}\mathbf{s}_{1}+\mathbf{s}_{2}=0$, always exists.

The range space of the dual certificate is the set of all $L+1\times L+1$ matrices which are a sum of the following two matrices: The first matrix can have any value in the \big{\lfloor}{\frac{L}{2}+1\big{\rfloor}\times\big{\lfloor}\frac{L}{2}+1\big{\rfloor}} submatrix corresponding to the first \big{\lfloor}{\frac{L}{2}+1\big{\rfloor}} rows and columns, and has a value zero outside this submatrix (dual of the set of constraints due to prior information). The second matrix has the form $\sum_{m=1}^{M}\alpha_{m}\mathbf{W}_{r}^{\star}\mathbf{f}_{m}\mathbf{f}_{m}^{\star}\mathbf{W}_{r}$, where $\alpha_{m}$ is real-valued for each $m$ (dual of the measurements corresponding to $r=1$).

Let ${\mathbf{l}}=(l,l,\ldots,l[N-1])^{T}$ be a vector that satisfies:

$l=1$, $l[n]=l[N-n]=0\quad\textrm{for}\quad 1\leq n\leq\left\lceil\frac{L}{2}\right\rceil-1$

$\sum_{n=0}^{m}x_{0}[n]l[m-n]=\sum_{n=0}^{m}x_{0}^{\star}[n]l[N-m+n]=0$ for \big{\lfloor}\frac{L}{2}+1\big{\rfloor}\leq m\leq L

$\mathbf{f}_{m}^{\star}{\mathbf{l}}=0\quad\textrm{for}\quad M+1\leq m\leq N$.

These constraints together can be written as $\mathbf{A}{\mathbf{l}}=\mathbf{b}$. When $M\geq 4\lceil\frac{L}{2}\rceil$, the matrix $\mathbf{A}$ is square or wide, and almost always (pseudo) invertible. This can be seen as follows: the determinant of $\mathbf{A}$ is a polynomial function of the entries of $\mathbf{x}_{0}$, due to which it is either always zero or almost surely non-zero. By substituting $x_{0}=1$ and $x_{0}[n]=0$ for $n\neq 0$, it is straightforward to check that the determinant is non-zero. Hence, such an ${\mathbf{l}}$ almost always exists.

If the last row in (14) is chosen as $(l[L],l[L-1],\ldots,l)$, then we have: (i) The lower right block is an identity matrix. (ii) $\mathbf{L}\mathbf{s}_{1}+\mathbf{s}_{2}=0$ is satisfied. (iii) Since $\mathbf{b}$ is a real vector, ${\mathbf{l}}$ satisfies $l[n]=l^{\star}[N-n]$. Therefore, ${\mathbf{l}}$ is in the range space of $\sum_{m=1}^{M}\alpha_{m}\mathbf{f}_{m}$ where $\alpha_{m}$ is real-valued, due to which the resulting second matrix is in the range space of $\sum_{m=1}^{M}\alpha_{m}\mathbf{W}_{r}^{\star}\mathbf{f}_{m}\mathbf{f}_{m}^{\star}\mathbf{W}_{r}$.

Therefore, $\mathbf{D}$ satisfies all the requirements. The arguments are applied incrementally as earlier, with $M\geq 4L$ for $r>1$.