Keywords

1 Introduction

Time-frequency inpainting is an inverse problem where the goal is to estimate a subset of masked coefficients in a time-frequency complex-valued matrix from the observation of the remaining coefficients. A natural strategy consists in performing a spectrogram inpainting stage, where the amplitude of the missing coefficients are estimated, followed by a phase inpainting stage, where the missing phases are estimated. While spectrogram inpainting has been addressed in several works [11, 13, 18], phase inpainting has not been addressed by advanced methods and thus remains a challenge. Indeed, phase reconstruction is known to be a difficult task generally posed as a non-convex problem. Many works have been proposed to reconstruct the phase of all the time-frequency coefficients from their amplitude and may be extended to the phase inpainting problem. A first set of phase reconstruction methods relies on alternate projections [7,8,9,10] among which the Griffin and Lim (GL) algorithm [10] is widely used in audio processing. Its success may be due to the simplicity of its implementation and the low computational cost of its iterations. However, its performance is limited by a slow convergene towards a local minimum. Higher reconstruction performance has been reached by semidefinite programming (SDP) approaches, at the cost of much higher time and space complexities. In particular, PhaseLift [4] and PhaseCut [19] methods have been proposed for any linear operator and further studies [3, 12] have established their good performance in the case of the short-time Fourier transform (STFT). While yet other phase reconstruction algorithms have been recently proposed [1, 5, 6, 14,15,16,17], we focus on extending original GL and SDP approaches to phase inpainting.

The organization of the paper is as follows. In Sect. 2, the phase inpainting problem is formalized and we propose three dedicated algorithms: Griffin and Lim for phase inpainting (GLI), PhaseLift for phase inpainting (PLI) and PhaseCut for phase inpainting (PCI). These three algorithms are the extensions of existing algorithms, in which we add the knowledge of the partially observed phases. While the algorithms are introduced in the general case of any linear operator, Sect. 3 is dedicated to their specific implementation with the STFT operator. In Sect. 4, some experiments in small dimensions with various ratios of missing data and several mask shapes illustrate their performance and their limitations. Finally, conclusions and perspectives are drawn in Sect. 5.

2 Proposed Phase Inpainting Algorithms

2.1 Phase Inpainting Problem

For a signal \(\mathbf {x}\in \mathbb {C}^N\), we consider \(K\) complex linear measurements \(\mathbf {A}\mathbf {x}=\left[ \left\langle \mathbf {a}_k, \mathbf {x} \right\rangle \right] _{k=1}^K\in \mathbb {C}^K\) where \(\mathbf {a}_1, \ldots , \mathbf {a}_K\in \mathbb {C}^{N}\) and \(\mathbf {A}=\left[ \mathbf {a}_1, \ldots , \mathbf {a}_K\right] ^H\). While the specific case of the STFT operator is used in Sects. 3 and 4, the general case of any linear operator is addressed throughout Sect. 2. We assume that we observe both the magnitude and the phase of a subset of measurements while only the magnitude of the remaining measurements is available. The location of these subsets is given by a binary mask \(\varvec{m}\in \left\{ 0, 1\right\} ^K\): \(\varvec{m}\left[ k\right] = 1\) if both the magnitude and the phase of measurement k are known and \(\varvec{m}\left[ k\right] = 0\) if only its magnitude is known.

Throughout the document we will adopt the following notations: for \(\mathbf {b}\in \mathbb {C}^K\) \(\angle {\mathbf {b}}\) denotes its phase, \(\bar{\mathbf {b}}\) its conjugate. For \(\varvec{m}\in \left\{ 0, 1\right\} ^K\), \(\lnot \) denotes the negation. Denoting by \(\mathrm {supp}\left( \varvec{m}\right) \) the support of \(\varvec{m}\), let \(\mathbf {b}\in \mathbb {C}^K\) be the vector containing the fully known coefficients \(\mathbf {b}[k]\) for \(k \in \mathrm {supp}\left( \varvec{m}\right) \), and the known amplitudes \(\mathbf {b}[k]\) for \(k \in \mathrm {supp}\left( \lnot \varvec{m}\right) \). Then the phase inpainting problem is given by

$$\begin{aligned} \text {Find } \mathbf {x}\in \mathbb {C}^N\text { s.t. } {\left\{ \begin{array}{ll} \left\langle \mathbf {a}_k, \mathbf {x} \right\rangle &{} = \mathbf {b}[k], \forall k \in \mathrm {supp}\left( \varvec{m}\right) \\ \left| \left\langle \mathbf {a}_k, \mathbf {x} \right\rangle \right| &{} =\mathbf {b}[k], \forall k \ \mathrm {supp}\left( \lnot \varvec{m}\right) \end{array}\right. } \end{aligned}$$
(1)

2.2 Griffin and Lim Algorithm for Phase Inpainting (GLI)

We propose an extension of the Griffin and Lim algorithm [10] to solve approximately problem (1) by taking into account the known phases. The algorithm is described in Algorithm 1, \(\circ \) denoting the Hadamard product. It mainly relies on alternating a projection onto the span of the linear operator using projector \(\varvec{\varPi }_\mathbf {a}\) and a projection onto the known magnitude and phase constraints. The initialization of this algorithm may be done with random phases for coefficients with unknown phase.

figure a

2.3 PhaseLift for Phase Inpainting (PLI)

The second proposed approach is based on lifting and SDP. The quadratic constraints in problem (1) become linear by means of a projection in a large dimensional space where the variable is a semidefinite positive matrix \(\mathbf {X}\succeq 0\). The PhaseLift method [4] is adapted in order to address phase inpainting, which results in Proposition 1.

Proposition 1

With notations of problem (1), let \(\mathbf {A}_{lk}=\mathbf {a}_{l}\mathbf {a}_{k}^{H}\) for l, k \( \in \lbrace 1, \ldots , K\rbrace \). Using the lifting \(\mathbf {X}= \mathbf {x}\mathbf {x}^{H}\), problem (1) is equivalent to:

$$\begin{aligned} {\min _{\mathbf {X}\in \mathbb {C}^{N\times N}}} {\mathrm {Rank}( \mathbf {X})} \text { s.t. } {\left\{ \begin{array}{ll} \mathrm {Trace}( \mathbf {A}_{lk}\mathbf {X}) = \mathbf {b}[k] \bar{ \mathbf {b}}[l], &{} \forall l , k \in \mathrm {supp}\left( \varvec{m}\right) \\ \mathrm {Trace}( \mathbf {A}_{kk}\mathbf {X}) =\mathbf {b}^2[k], &{} \forall k \in \mathrm {supp}\left( \lnot \varvec{m}\right) \\ \mathbf {X}\succeq 0 \end{array}\right. } \end{aligned}$$
(2)

and can be relaxed as :

$$\begin{aligned} {\min _{\mathbf {X}\in \mathbb {C}^{N\times N}}} {\mathrm {Trace}( \mathbf {X})} \text { s.t. } {\left\{ \begin{array}{ll} \mathrm {Trace}( \mathbf {A}_{lk}\mathbf {X}) = \mathbf {b}[k] \bar{ \mathbf {b}}[l], &{} \forall l , k \in \mathrm {supp}\left( \varvec{m}\right) \\ \mathrm {Trace}( \mathbf {A}_{kk}\mathbf {X}) = \mathbf {b}^2[k], &{} \forall k \in \mathrm {supp}\left( \lnot \varvec{m}\right) \\ \mathbf {X}\succeq 0 \end{array}\right. } \end{aligned}$$
(3)

Proof

The proof can be conducted in three steps:

  1. 1.

    Assume that \(\mathbf {x}\) satisfies (1). For \(k, l \in \mathrm {supp}\left( \varvec{m}\right) \), the phase constraint is obtained by considering that

    $$\begin{aligned} \mathbf {b}[k]\bar{ \mathbf {b}}[l] = \mathrm {Trace}(\mathbf {a}_{k}^{H}\mathbf {x}\mathbf {x}^{H}\mathbf {a}_{l}) = \mathrm {Trace}(\mathbf {a}_{l}\mathbf {a}_{k}^{H}\mathbf {x}\mathbf {x}^{H}) = \mathrm {Trace}(\mathbf {A}_{lk}X) \end{aligned}$$

    For \( k \in \mathrm {supp}\left( \lnot \varvec{m}\right) \), the magnitude constraint is obtained similarly.

  2. 2.

    Problem (1) can then be reformulated as

    $$\begin{aligned} \text {Find }\mathbf {X}\in \mathbb {C}^{N\times N} \quad \text { s.t. } {\left\{ \begin{array}{ll} {\mathrm {Trace}} ( \mathbf {A}_{lk} \mathbf {X}) = \mathbf {b}[k]\bar{ \mathbf {b}}[l], &{} \forall l , k \in \mathrm {supp}\left( \varvec{m}\right) \\ {\mathrm {Trace}} ( \mathbf {A}_{kk} \mathbf {X}) =\mathbf {b}^2[k], &{}\forall k \in \mathrm {supp}\left( \lnot \varvec{m}\right) \\ \mathrm {Rank}(\mathbf {X})=1 \\ \mathbf {X}\succeq 0 \end{array}\right. } \end{aligned}$$

    which is equivalent to problem (2).

  3. 3.

    Since the rank is not convex, one may finally relax the rank by the nuclear norm to obtain Problem (3). \(\square \)

Formulation (3) is called PhaseLift for phase inpainting (PLI). The objective function and equality constraints are linear and the domain \(\mathbf {X}\succeq 0\) is a convex cone. One may notice that only phase differences appear, in the first contraint, to exploit the known phases. In the particular case \(\mathrm {supp}\left( \varvec{m}\right) = \emptyset \), the original PhaseLift problem [4] is obtained.

Finally, from the solution \(\mathbf {X}\) of problem (3), \(\mathbf {x}\) can be estimated as \(\sqrt{\lambda _\text {max}}\mathbf {z}_\text {max}\) where \(\mathbf {z}_\text {max}\) is the eigenvector associated with the largest eigenvalue \(\lambda _\text {max}\) of \(\mathbf {X}\).

In order to solve the PLI problem (3), we use Matlab toolbox TFOCS [2]. Two solvers may be used: solver_sSDP that performs trace minimization under linear constraints as in (3), or solver_TraceLS that solves unconstrained problems of the form \(\min _{\mathbf {X}\succeq 0} \lambda \, \mathrm {Trace}( \mathbf {X}) + \frac{1}{2} {\Vert \mathcal {A}(\mathbf {X})-\beta \Vert }^{2}\) with

$$\begin{aligned} \mathcal {A} : \mathbf {X}\mapsto \begin{bmatrix} vec \left( \left[ \mathrm {Trace}(\mathbf {A}_{lk}\mathbf {X})\right] _{l,k \in \mathrm {supp}\left( \varvec{m}\right) } \right) \\ \left[ \mathrm {Trace}(\mathbf {A}_{kk}\mathbf {X})\right] _{k \in \mathrm {supp}\left( \lnot \varvec{m}\right) } \end{bmatrix}, \beta = \begin{bmatrix} vec \left( \left[ \mathbf {b}[k]\bar{ \mathbf {b}}[l]\right] _{l,k\in \mathrm {supp}\left( \varvec{m}\right) } \right) \\ \left[ \mathbf {b}[k]\right] _{k \in \mathrm {supp}\left( \lnot \varvec{m}\right) } \end{bmatrix}. \end{aligned}$$
(4)

2.4 PhaseCut for Phase Inpainting (PCI)

The third and last proposed algorithm is also an SDP optimization algorithm, namely PhaseCut for phase inpainting (PCI), which is an extension of the original PhaseCut designed for phase retrieval [19].

As in [19], problem (1) is reformulated by explicitly splitting the amplitude and phase variables, so that one may optimize only on the phase vector \(\mathbf {u}\in \mathbb {C}^K\) such that \(\forall k, \vert \mathbf {u}\left[ k\right] \vert = 1 \). We use the lifting \(\mathbf {U}= \mathbf {u}\mathbf {u}^H\) to obtain Proposition 2.

Proposition 2

Using notations of problem (1), let \( \varvec{\varGamma }=\mathrm {Diag}(\mathbf {c}^{H})(I- \mathbf {A}\mathbf {A}^{\dagger } )\mathrm {Diag}(\mathbf {c})\) with \( \mathbf {c}\in \mathbb {C}^K\) is defined by \(\mathbf {c} [k] = \left| \mathbf {b}[k] \right| , \forall k\). Then problem (1) is equivalent to

$$\begin{aligned} \min _{ \mathbf {U}\in \mathbb {C}^{K\times K}} \mathrm {Trace}(\mathbf {U}\varvec{\varGamma }) \text { s.t. } {\left\{ \begin{array}{ll} \mathrm {Diag}(\mathbf {U}) =\mathbbm {1}\\ \mathbf {U}[k_1,k_2]= \frac{\mathbf {b}[k_1]}{\vert \mathbf {b}[k_1]\vert } \frac{\bar{\mathbf {b}}[k_2]}{\vert \mathbf {b}[k_2]\vert }, \forall k_1, k_2 \in \mathrm {supp}\left( \varvec{m}\right) \\ \mathrm {Rank}\left( \mathbf {U}\right) = 1\\ \mathbf {U}\succeq 0 \end{array}\right. } \end{aligned}$$
(5)

and may be relaxed into a convex problem by dropping the rank constraint as

$$\begin{aligned} \min _{ \mathbf {U}\in \mathbb {C}^{K\times K}} \mathrm {Trace}(\mathbf {U}\varvec{\varGamma }) \text { s.t. } {\left\{ \begin{array}{ll} \mathrm {Diag}(\mathbf {U}) =\mathbbm {1}\\ \mathbf {U}[k_1,k_2]= \frac{\mathbf {b}[k_1]}{\vert \mathbf {b}[k_1]\vert } \frac{\bar{\mathbf {b}}[k_2]}{\vert \mathbf {b}[k_2]\vert }, \forall k_1, k_2 \in \mathrm {supp}\left( \varvec{m}\right) \\ \mathbf {U}\succeq 0 \end{array}\right. } \end{aligned}$$
(6)

Proof

Using the amplitude vector \(\mathbf {c}\) and the phase vector \(\mathbf {u}\), problem (1) becomes

$$\begin{aligned} \text {Find } \mathbf {x}\in \mathbb {C}^{N},\mathbf {u}\in \mathbb {C}^{K} \text { s.t. } {\left\{ \begin{array}{ll} \mathbf {A}{\mathbf {x}} &{} =\mathrm {Diag}(\mathbf {c})\mathbf {u}\\ \mathbf {u}\left[ k\right] &{}= e^{\imath \angle \mathbf {b}[k]\, } \forall k \in \mathrm {supp}\left( \varvec{m}\right) \\ \vert \mathbf {u}\left[ k\right] \vert &{}= 1 \; \forall k \end{array}\right. } \end{aligned}$$
(7)

which is equivalent to

$$\begin{aligned} \begin{aligned}&\mathop {\hbox {min}}\limits _{\mathbf {x}\in \mathbb {C}^{N}, \mathbf {u}\in \left[ 0, 2\pi \right. \left[ \right. ^K} \Vert \mathbf {A}{\mathbf {x}} -{\mathrm {Diag}}(\mathbf {c})\mathbf {u}\Vert _{2}^{2} \text { s.t. } {\left\{ \begin{array}{ll} \mathbf {u}\left[ k\right] &{}= e^{\imath \angle \mathbf {b}[k]} \forall k \in \mathrm {supp}\left( \varvec{m}\right) \\ \vert \mathbf {u}\left[ k\right] \vert &{}= 1 \; \forall k \end{array}\right. } \end{aligned} \end{aligned}$$
(8)

Given that \(\mathbf {A}{\mathbf {x}} =\mathrm {Diag}(\mathbf {c})\mathbf {u}\) implies \(\mathbf {x}= \mathbf {A}^{\dagger }\mathrm {Diag}(\mathbf {c})\mathbf {u}\), then \({ \Vert \mathbf {A}{\mathbf {x}} -\mathrm {Diag}(\mathbf {c})\mathbf {u}}\) \( { \Vert }_{2}^{2} = \mathbf {u}^{H}\varvec{\varGamma } \mathbf {u}\), thus (8) is equivalent to (5) which can be relaxed into (6).             \( \square \)

Formulation (6) is called PhaseCut for phase inpainting (PCI). As for PLI, phase differences appear in the constraints that involve known phases. In the particular case where all phases are unknown (\(\mathrm {supp}\left( \varvec{m}\right) = \emptyset \)), contraints \(\mathbf {U}[k_1,k_2]= \frac{\mathbf {b}[k_1]}{\vert \mathbf {b}[k_1]\vert } \frac{\bar{\mathbf {b}}[k_2]}{\vert \mathbf {b}[k_2]\vert }\) disappear and the original PhaseCut problem [19] is obtained \(\mathbf {x}\).

Finally, from the solution \(\mathbf {U}\) of problem (6), signal \(\mathbf {x}\) is estimated as \(\mathbf {x}= \mathbf {A}^{\dagger }\mathrm {Diag}(\mathbf {c})e^{\imath \angle \mathbf {u}_\text {max}}\) where \(\mathbf {u}_\text {max}\) is an eigenvector associated to the largest eigenvalue of \(\mathbf {U}\).

In order to solve PCI problem (6), we adapt the block coordinate descent algorithm proposed in [19] from [20], as given in Algorithm 2. By picking coordinates i in \(\mathrm {supp}\left( \varvec{m}\right) \) instead of \(\left\{ 1, \ldots , K\right\} \), all unknown coefficients in \(\mathbf {U}\), and only them, are updated.

figure b

3 Implementation Issues Specific to the STFT

Phase Inpainting Problem with STFT Measurements. The STFT of a signal \(\mathbf {x}\in \mathbb {C}^N\) is defined for frame index \(t \in \{0, \ldots , T-1\}\) and frequency index \(\nu \in \{0, \ldots , F-1\}\) as \({\text {STFT}}[t,\nu ]=\left\langle \mathbf {x}, \mathbf {a}_{t, \nu } \right\rangle =\mathbf {a}_{t, \nu }^H\mathbf {x}\) where \(\mathbf {a}_{t, \nu }=\left[ \mathbf {w}[n-t h] e^{2\imath \pi \frac{\nu }{F} n}\right] _{n=0}^{N-1} \) \( \in \mathbb {C}^K\), \(\mathbf {w}\) being the analysis window and h the so-called hop size between two successive frames. Hence the \(K=FT\) measurements are indexed by \(k=\left( t, \nu \right) \): measurements may be seen equivalently either as a doubly-indexed vector or as a matrix. A simple reshaping operation can be used to switch between representations, and with a small abuse of notations, both of them are used without explicit distinction in this paper. The STFT phase inpainting problem in time-frequency is thus given by

$$\begin{aligned} \text {Find } \mathbf {x}\in \mathbb {C}^{N}\text { s.t. } {\left\{ \begin{array}{ll} \left\langle \mathbf {x}, \mathbf {a}_{t, \nu } \right\rangle =\mathbf {b}[t,\nu ], &{} \forall \left( t, \nu \right) \in \mathrm {supp}\left( \varvec{m}\right) \\ \left| \left\langle \mathbf {x}, \mathbf {a}_{t, \nu } \right\rangle \right| =\mathbf {b}[t,\nu ], &{} \forall \left( t, \nu \right) \in \mathrm {supp}\left( \lnot \varvec{m}\right) \\ \end{array}\right. } \end{aligned}$$
(9)

GLI Implementation. The GLI algorithm is obtained by setting \(\varvec{\varPi }_\mathbf {a}:\mathbf {y} \mapsto {\text {STFT}}\left( {\text {STFT}}^{-1}\left( \mathbf {y}\right) \right) \) where \({\text {STFT}}^{-1}\) is the (pseudo-)inverse operator for the STFT computed from the canonical dual window of \(\mathbf {w}\).

PLI Implementation. We used solver_TraceLS of TFOCS library, which happened to be faster than solver_sSDP. The implementation of the direct operator \(\mathcal {A}\) defined in (4) and of its adjoint can be more efficient using fast Fourier transforms (FFT) as follows. We have \({\mathrm {Trace}}(\mathbf {A}_{lk}\mathbf {X})=\left( {{\text {STFT}}}_{row}\left( \overline{{\text {STFT}}_{col}(\mathbf {X})} \right) \!\right) ^{H}\![k, l] \) for \(k,l \in \lbrace 1,\ldots , K\rbrace \), where \({{\text {STFT}}}_{row}(\mathbf {X})\) denotes the \({\text {STFT}}\) on the columns of \(\mathbf {X}\) and \( {\text {STFT}}_{col}(\mathbf {X})\) the \( {\text {STFT}}\) on the rows of \(\mathbf {X}\). Hence one may compute \(\mathcal {A}\left( \mathbf {X}\right) \) from only \(2N\) STFT’s. By denoting by \(k_0= \# \mathrm {supp}\left( \varvec{m}\right) \) the number of known phases, the adjoint operator \(\mathcal {A}^* : \mathbb {C}^{k_0^{2}+K-k_0} \rightarrow \mathbb {C}^{N\times N}\) is such that \(\mathcal {A}^* (\mathbf {y}) = \left( {\text {STFT}}^*_{row}\left( \overline{ {\text {STFT}}^*_{col}(\mathbf {Y})} \right) \right) ^{H}\) where \( {\text {STFT}}^*\) is the adjoint of the STFT operator and \(\mathbf {Y}\in \mathbb {C}^{K\times K}\) is defined by \(\mathbf {Y}(\varvec{m},\varvec{m}) = reshape(\mathbf {y}( 1:k_0^{2}),k_0,k_0)\) and \(\mathbf {Y}(\sim \varvec{m},\sim \varvec{m}) = \mathrm {Diag}(\mathbf {y}( k_0^{2}+1:K))\). It thus requires \(2K\) calls to \({\text {STFT}}^*\).

PCI Implementation. Each iteration of Algorithm 2 for PCI requires \(K\) calls to one direct STFT and one inverse STFT, using FFT’s.

4 Experiments

All experiences are available on mad.lis-lab.fr. Experiments in small dimensions are conducted on a signal with length \(N=128\) composed of the sum of two linear chirps with normalized frequency ranges (0, 0.8) and (0.8, 0.6), a dirac located at sample 64 and white Gaussian noise at a signal-to-noise ratio of 10 dB. The STFT is generated with a Hann window with length 16, a hop size of 8 samples (i.e., \(T= 16\) frames) and \(F=32\) frequency bins, resulting in \(K=512\) measurement in a \(32 \times 16\) time-frequency matrix. In a first experiment, masks for missing phases are generated randomly and uniformly among the measures, with various ratios of missing phases. In a second experiment, the ratio of missing phases is fixed at \(30\%\) and missing phases are grouped in holes of a given width, with randomly distributed centers, the widths varying between 1 and 9 coefficients. Figure 1 illustrates the STFT of the signal and of one generated mask.

Fig. 1.
figure 1

Spectrogram of the signal (left, smoothed with \(T= F=128\); middle, with \(T= 16\) and \(F=32\) as set in the experiment) and example of a mask with random holes of width 5 in black (right).

Full size image

Algorithms are used with the following settings. For GLI, \(n_\text {iter}=6000\). For PLI, \(\lambda =10^{-30}\) and TFOCS is used with a maximum of 5000 iterations, no restart, \(tol =10^{-10}\). For PCI, \(\nu =10^{-14}\) and \(n_\text {iter}= 10^{5}\). A baseline approach is also used, denoted as Random Phase Inpainting (RPI) and consisting in filling the missing phases by drawing random values independently and uniformely in \(\left[ 0, 2\pi \right. \left[ \right. \).

Performance is assessed in terms of relative reconstruction error up to a global phase shift, defined by \( E_{dB}(\mathbf {x},\mathbf {\hat{x}}) = 20\log _{10} \min _\theta \frac{{\Vert \mathbf {x}- e^{\imath \theta }\mathbf {\hat{x}}\Vert }_{2}}{{\Vert \mathbf {x}\Vert _{2}}}\) where \( \mathbf {x}\) denotes the original signal and \( \mathbf {\hat{x}}\) the reconstructed one.

Results are shown in Fig. 2, where the reconstruction errors from all methods can be compared, as a function of the ratio of missing phases, for each experiment. The known phases clearly contribute to improve the signal reconstruction. For isolated missing phases (left figure), one can see that below \(40\%\) missing phases, GLI and PCI achieves perfect reconstruction while PLI performs very good but not perfect. Beyond \(40\%\) missing phases, SDP methods PLI and PCI perform better than GLI, with a much better performance for PLI. For holes with a larger width at \(30\%\) missing phases (right figure), one can see that GLI may achieve poor reconstruction due to local minima. SDP methods offer very good performance, with a reconstruction error generally below \(-50\) dB.

Fig. 2.
figure 2

Reconstruction error as a function of the ratio of missing phases randomly distributed (left) or, for \(30\%\) missing phases, as a function of the width of randomly distributed holes (right).

Full size image

The convergence and running time of each method have been checked as follows. For GLI, it was checked visually and manually that the algorithm converges before the maximum number of iterations, with a running time lower than one second for each call. For PLI, similarly, it has been checked that the algorithm stops before the maximum number of iterations is reached, with a running time up to 6 h for one call when the number of missing phases is large. For PCI, convergence may be observed in Fig. 3 by representing the reconstruction error as a function of the iterations. As for PLI, the running time until convergence is all the more reduced as many phases are known, lasting about 4 h for \(10^{5}\) iterations.

Fig. 3.
figure 3

Illustration of the convergence of PCI by representing the reconstruction error as a function of the iterations in the same two settings as in Fig. 2.

Full size image

5 Conclusion and Perspectives

We have considered the phase inpainting problem in which a subset of measurements have missing phases that must be recovered. We have proposed three dedicated algorithms, which are extensions of existing algorithms, namely Griffin and Lim, PhaseLift and PhaseCut, adapted to the phase inpainting problem by incorporating the partial phase information as constraints in the optimization process. Those algorithms have been implemented using fast transforms in the case of the STFT. Experiments in small dimensions confirm that SDP methods perform better than Griffin and Lim algorithm, in particular when the problem is difficult (more unknown phases, larger holes). Even if those methods are very time consuming, it also appears that the knowledge of a subset of phases result in a faster convergence.

Experiments may be extended to the noisy case where only approximate values are available known phases and amplitudes. Time and space complexity of SDP approaches being very large, they cannot be applied to typical audio signals for which dimensions are higher than those used in the proposed experiments. In order to benefit from SDP results, one may investigate the adaptation of SDP algorithms to process only a local time-frequency region instead of the whole STFT matrix. Other algorithms may be designed for phase inpainting. In particular, some recent contributions to phase retrieval [1, 5, 6, 14,15,16,17] may be adapted and may give good performance without the computational limits of SDP methods.