# Accelerated Griffin-Lim algorithm:
A fast and provably converging numerical method for phase retrieval

Rossen Nenov†, Dang-Khoa Nguyen⋆, Peter Balazs† and Radu Ioan Boţ⋆
† Acoustics Research Institute, Vienna, Austria
⋆ University of Vienna, Austria

###### Abstract

The recovery of a signal from the magnitudes of its transformation, like the
Fourier transform, is known as the phase retrieval problem and is of big
relevance in various fields of engineering and applied physics. In this paper,
we present a fast inertial/momentum based algorithm for the phase retrieval
problem and we prove a convergence guarantee for the new algorithm and for the
Fast Griffin-Lim algorithm, whose convergence remained unproven in the past
decade. In the final chapter, we compare the algorithm for the Short Time
Fourier transform phase retrieval with the Griffin-Lim algorithm and FGLA and
to other iterative algorithms typically used for this type of problem.

###### Index Terms:

phase retrieval, inertial algorithm, Griffin-Lim algorithm, Fast Griffin-Lim
algorithm, convergence guarantee.

##  I Introduction

00footnotetext: This work was supported by the Austrian Science Fund FWF-
project NoMASP (“Nonsmooth nonconvex optimization methods for acoustic signal
processing”; P 34922-N). The authors would like to express their gratitude to
Dr. Nicki Holighaus (Austria Academy of Sciences) for his valuable input and
ideas in the numerical experiments section.

Reconstructing the phase of a signal from phaseless measurements of its (Short
Time) Fourier transform is a pervasive challenge, called the phase retrieval
problem. It arises in a great amount of areas of applications, most
prominently in audio processing [1, 2], imaging [3, 4], and electromagnetic
theory [5, 6]. Therefore it is, to this day, an active research topic with
numerous algorithms designed to find satisfactory solutions to the phase
retrieval problem. These algorithms can be divided into two classes: non-
iterative and iterative algorithms. For the _Short Time Fourier transform_
(STFT), it was analysed in [7] that the performance of non-iterative
algorithms strongly depends on the redundancy of the STFT. They perform better
than iterative algorithms in terms of quality and speed for high redundancies,
which are rarely considered in practice. For the lower, more common,
redundancies the iterative methods gave more qualitative results than the non-
iterative ones, which motivates their study.

The _Griffin-Lim algorithm_ (GLA) [8] is a well known and widely used
iterative algorithm based on the method of alternating projections and applied
to the phase retrieval problem in the time-frequency setting. In optics, this
algorithm is also known as the Gerchberg-Saxton algorithm [9]. Inspired by the
_Fast iterative shrinkage threshold algorithm_ (FISTA [10]), the authors of
[11] proposed to introduce an inertial/momentum step to GLA, which formed the
_Fast Griffin-Lim algorithm_ (FGLA). As a result, they obtained a method that
converges faster than GLA in practice and recovers signals with lower
reconstruction error, but the convergence guarantee remained an open question.
Since its introduction, FGLA gained considerable traction for phase retrieval
in audio processing [12, 13] and machine learning [14, 15], but still, a
convergence result for this iterative algorithm was pending, which motivated
this work.

In this work, we will present the _Accelerated Griffin-Lim algorithm_ (AGLA),
a new iterative method, and prove a convergence result for it in a generalized
setting covering a wide range of areas, where the phase retrieval problem
arises, beyond the field of audio processing. This method is an extension of
FGLA, and therefore our results cover FGLA as well.

Furthermore, we will round out the theoretical results with the comparison of
numerical simulations of AGLA against its predecessors and other iterative
algorithms to highlight the improved numerical performance of our algorithm.

##  II The Phase Retrieval Problem

A linear and injective transformation from $\mathbb{C}^{L}\to\mathbb{C}^{M}$
with $M\geq L$ can be written as a transformation matrix $T$ in
$\mathbb{C}^{M\times L}$ with full column rank, for example, the discrete
Fourier transform or the analysis operator of a finite frame [16]. The vector
$s\in[0,+\infty)^{M}$ will denote the measured magnitudes of the coefficients
of the transform. The phase retrieval problem can be expressed mathematically
as finding the signal $x^{*}\in\mathbb{C}^{L}$, whose transform coefficients
match the magnitudes $s$, that is $\left|Tx^{*}\right|=s$, where
$\left|\cdot\right|$ is understood as the absolute value applied
componentwise. The feasibility, uniqueness, and stability of the phase
retrieval problem have been studied in many works, most notably in [17, 18].
The results in the present paper are actually independent of the solvability
of the phase retrieval problem.

In practice, measurements can include some noise and inaccuracies and
therefore we are usually looking for solutions $x^{*}$ of the following
minimization problem

$\displaystyle\min_{x\in\mathbb{C}^{L}}\left\|\left|Tx\right|-s\right\|,$ (1)

where $\left\|\cdot\right\|$ denotes the norm of $\mathbb{C}^{M}$. In [11] it
was proposed to consider this problem, as the task in finding a vector $c^{*}$
in the set of coefficients admitted by the transformation matrix $T$, namely
its range, which is as close as possible to the set of coefficients, whose
magnitude match with $s$. The range of the transformation matrix $T$ will be
denoted as

$\displaystyle C_{1}=\\{c\in\mathbb{C}^{M}\mid\exists
x\in\mathbb{C}^{L}:c=Tx\\}.$ (2)

This set is a linear subspace of $\mathbb{C}^{L}$. Let $C_{2}$ be the set of
vectors whose magnitudes are equal to $s$, namely

$\displaystyle
C_{2}=\\{c\in\mathbb{C}^{M}\mid\left|c_{i}\right|=s_{i}\quad\forall
i\in\\{1,\dots,M\\}\\}.$ (3)

The set $C_{2}$ is, by definition, compact. To formulate the problem (1) as
finding the closest point between two sets, we introduce two distance
functions. The indicator function $\delta_{C}$ of a set $C$ is defined as

$\displaystyle\delta_{C}({c})=\begin{cases}0&\text{if }{c}\in C,\\\
+\infty&\text{else,}\end{cases}$

and the distance function $d_{C}$ to a compact set $C$ is defined as

$\displaystyle d_{C}({c})=\min_{{v}\in C}\left\|{c}-{v}\right\|\quad\text{ for
}c\in\mathbb{C}^{M}.$ (4)

Our aim is to solve the following optimization problem

$\displaystyle\min_{c\in\mathbb{C}^{M}}f(c):=\delta_{C_{1}}(c)+\frac{1}{2}d_{C_{2}}^{2}(c),$
(5)

which is nonconvex and has a close connection to the original problem (1), as
can be seen later.

For finding the closest point between two sets iteratively, projection
operators are a common tool. Since $C_{1}$ is a linear subspace spanned by
$T$, we can write its orthogonal projection as

$\displaystyle P_{C_{1}}({c})=TT^{\dagger}{c},$

where $T^{\dagger}$ denotes the pseudo-inverse of $T$, which is well-defined
since $T$ is assumed to have full column rank [16].

Since $C_{2}$ is a nonconvex closed set, the projection of a vector ${c}$ onto
$C_{2}$ is nonempty but not always unique. Therefore we will denote by
$\overline{P}_{C_{2}}:\mathbb{C}^{M}\rightrightarrows\mathbb{C}^{M}$ the
possibly set valued projection

$\displaystyle\overline{P}_{C_{2}}({c})=\arg\min_{{v}\in
C_{2}}\left\|{c}-{v}\right\|,$

which maps $c$ to the set of its closest points in $C_{2}$. As in [11] we will
denote by $P_{C_{2}}:\mathbb{C}^{M}\to\mathbb{C}^{M}$ a closed form for a
possible choice of the projection onto $C_{2}$, which we will use in the
algorithms

$\displaystyle(P_{C_{2}}(c))_{i}=\begin{cases}\frac{s_{i}c_{i}}{\left|c_{i}\right|}&\text{
if }c_{i}\neq 0,\\\ {s}_{i}&\text{ if }c_{i}=0.\end{cases}$ (6)

This projection is equivalent to scaling the elements of $c$ to have the
magnitudes of $s$, without changing the phase. The following proposition,
whose proof can be found in the appendix, gives another convenient way to
write $d_{C_{2}}$ and states that this choice of $P_{C_{2}}$ indeed minimizes
the distance function and is almost everywhere the unique element of
$\overline{P}_{C_{2}}$.

######  Proposition II.1.

For all $c\in\mathbb{C}^{M}$ the distance to $C_{2}$ can be written as

$\displaystyle d_{C_{2}}(c)=\left\|\left|c\right|-s\right\|$ (7)

and $d_{C_{2}}(c)=\left\|c-P_{C_{2}}(c)\right\|$ holds. If $c\notin D$, where

$D:=\\{c\in\mathbb{C}^{M}\mid\exists i\in\\{1,...,M\\}:c_{i}=0\text{ and
}s_{i}\neq 0\\}$,

then $P_{C_{2}}(c)$ is the unique closest point to $c$ in $C_{2}$, namely
$\overline{P}_{C_{2}}(c)=\\{P_{C_{2}}(c)\\}.$

The set D consists of the points, where the magnitude of a coefficient is zero
while respective measured one $s_{i}$ is not. This set has been observed to be
problematic, for example, in the work [19] it is proven that the Phase
Derivative of the STFT is numerically unstable, i.e., there is a peculiar pole
phenomenon at points in this set. It will have an important role in the
convergence proof of the iterates, as we can only guarantee differentiability
of $\frac{1}{2}d_{C_{2}}^{2}$ on $\mathbb{C}^{M}\setminus D$.

Proposition II.1 motivates the choice of the objective function $f$, since for
$c\in C_{1}$ we see that $f(c)$ coincides with the function value of (1) at
$T^{\dagger}c$. One can show that for any local/global minimizer $c^{*}$ of
(5), $x^{*}=T^{\dagger}c^{*}$ is a local/global minimizer of (1) and vice
versa.

##  III The Algorithms

In 1984, Griffin and Lim presented the algorithm known as _Griffin-Lim
algorithm_ (GLA). They showed that the iterates of the algorithm converge to a
set of critical points of a magnitude-only distance measure and that the
objective function values of the iterates are non-increasing. In the
following, $N$ denotes the amount of iterations of the algorithms, which can
be chosen as $+\infty$ as well. Here, without any risk of confusion, we use
the subscript $n$ to mean the $n^{th}$ iteration, like $c_{n},t_{n}$. On the
other hand, the subscript $i$ means $c_{i}$ is the $i^{th}$ component of the
vector $c\in\mathbb{C}^{M}$.

Algorithm 1 Griffin-Lim algorithm

Initialize $c_{0}\in\mathbb{C}^{M}$

$\textbf{Iterate for }n=1,\dots,N$

$c_{n}=P_{C_{1}}(P_{C_{2}}(c_{n-1}))$

Return  $T^{\dagger}c_{N}$

In 2013, Perraudin, Balazs and Søndergaard stated that GLA can be seen as the
method of alternating projections of the iterates onto $C_{2}$ and $C_{1}$ and
proposed the _Fast Griffin-Lim_ (FGLA) by adding an inertial/momentum step
[11]. The algorithm is based on the idea of the inertial proximal-gradient
method, in the spirit of the Heavy Ball method [20] and Fast iterative
shrinkage threshold algorithm (FISTA) [10], which also works in the nonconvex
setting [21].

This algorithm achieved better results than GLA in numerical experiments, but
a convergence guarantee was not addressed.

Algorithm 2 Fast Griffin-Lim algorithm

Initialize $c_{0}\in\mathbb{C}^{M}$, $t_{0}\in C_{1}$ and $\alpha>0$

$\textbf{Iterate for }n=1,\dots,N$

$t_{n}=P_{C_{1}}(P_{C_{2}}(c_{n-1}))$

$c_{n}=t_{n}+\alpha(t_{n}-t_{n-1}),$

Return  $T^{\dagger}c_{N}$

In this paper we present a further modification to GLA, by adding a second
inertial sequence $(d_{n})_{n\in\mathbb{N}}$, which will not be projected. Its
purpose is to stabilize the algorithm and avoid getting stuck at the points,
in which FGLA stops at, while the distance between the projection of
$(c_{n})_{n\in\mathbb{N}}$ and the nonprojected $(d_{n})_{n\in\mathbb{N}}$ is
still large. A similar idea can be found in [21, 22].

Algorithm 3 Accelerated Griffin-Lim algorithm

Initialize $c_{0}\in\mathbb{C}^{L}$, $t_{0},d_{0}\in C_{1}$ and
$\alpha,\beta,\gamma>0$

$\textbf{Iterate for }n=1,\dots,N$

$t_{n}=(1-\gamma)d_{n-1}+\gamma P_{C_{1}}(P_{C_{2}}(c_{n-1}))$

$c_{n}=t_{n}+\alpha(t_{n}-t_{n-1}),$

$d_{n}=t_{n}+\beta(t_{n}-t_{n-1})$

Return  $T^{\dagger}c_{N}$

AGLA is a generalization of FGLA since for $\gamma=1$ the generated sequences
by FGLA and AGLA coincide. In the following chapter, we will state parameter
choices of $\alpha$, $\beta$, and $\gamma$, for which we prove the convergence
of the algorithm.

##  IV Convergence of the function values

In this chapter, we prove the convergence result for AGLA. We will use the
following identity, which is a generalization of the parallelogram law,
typically used in the proof of convergence of the function values of the
iterates for algorithms with inertial sequences. It will be used several times
in the analysis. It can be shown by a simple calculation, hence we omit the
detail. Precisely, for any two vectors $a,b\in\mathbb{C}^{M}$ and any two real
numbers $\tau,\sigma\in\mathbb{R}$, it holds

$\left\lVert\tau a+\sigma
b\right\rVert^{2}=\left(\tau+\sigma\right)\tau\left\lVert
a\right\rVert^{2}+\left(\tau+\sigma\right)\sigma\left\lVert
b\right\rVert^{2}\\\ -\tau\sigma\left\lVert a-b\right\rVert^{2}.$ (8)

Using this identity we will state the proof of the function values of the
iterates generated by AGLA for certain parameter regimes.

######  Theorem IV.1.

Let $(c_{n})_{n\in\mathbb{N}}$, $(d_{n})_{n\in\mathbb{N}}$ and
$(t_{n})_{n\in\mathbb{N}}$ be the sequences generated by AGLA. Suppose that

$0<\gamma<2\textrm{ and }0\leq 2\beta\left|1-\gamma\right|<2-\gamma,$ (9)

and

$\displaystyle
0\leq\alpha<\begin{cases}\left(1-\frac{1}{\gamma}\right)\beta+\frac{1}{\gamma}-\frac{1}{2}&\text{
if }0<\gamma\leq 1,\\\ \frac{1}{2\beta(\gamma-1)+\gamma}-\frac{1}{2}&\text{ if
}1<\gamma<2.\end{cases}$ (10)

Then the following statements are true

  1. (i)

There exist constants $K_{1}>K_{2}>0$ such that the following descent property
holds for all $n\geq 1$

$\displaystyle d_{C_{2}}^{2}(c_{n})+K_{1}\Delta_{t_{n}}^{2}$
$\displaystyle\leq d_{C_{2}}^{2}(c_{n-1})+K_{2}\Delta_{t_{n-1}}^{2},$

where $\Delta_{t_{n}}:=\left\|t_{n}-t_{n-1}\right\|$. Therefore
$\Delta_{t_{n}}$ converges to zero and
$\lim_{n\to+\infty}d_{C_{2}}^{2}(c_{n})\in\mathbb{R}$ exists.

  2. (ii)

$(c_{n})_{n\in\mathbb{N}}$ is a bounded sequences and every cluster point
$c^{*}$ of $(c_{n})_{n\in\mathbb{N}}$ fulfills

$\displaystyle P_{C_{1}}(P_{C_{2}}(c^{*}))=c^{*}.$

###### Proof.

Let $n\geq 1$. By the definition of the algorithm, the sequences
$(c_{n})_{n\geq 1}$, $(t_{n})_{n\in N}$ and $(d_{n})_{n\in\mathbb{N}}$ lie in
the linear subspace $C_{1}$. This observation will be useful throughout the
proof.

$P_{C_{1}}$ is the orthogonal projection onto the linear subspace $C_{1}$ and
therefore the identity

$\displaystyle\left\|P_{C_{1}}(x)-x\right\|^{2}+\left\|y\right\|^{2}=\left\|P_{C_{1}}(x)-x+y\right\|^{2}$
(11)

holds for all $(x,y)\in\mathbb{C}^{L}\times C_{1}$. Define
$x_{n}:=P_{C_{2}}(c_{n-1})$ and $y_{n}=P_{C_{1}}(x_{n})$, then for arbitrary
$z\in C_{1}$ it holds $z-y_{n}\in C_{1}$. Hence according to (11) we have

$\left\|y_{n}-x_{n}\right\|^{2}+\left\|z-y_{n}\right\|^{2}=\left\|z-x_{n}\right\|^{2}.$
(12)

By rewriting the definition of the algorithm, we see that

$\displaystyle\frac{1}{\gamma}t_{n}+\frac{\gamma-1}{\gamma}d_{n-1}=P_{C_{1}}(P_{C_{2}}(c_{n-1})),$
(13)

and therefore we can write
$y_{n}=\frac{1}{\gamma}t_{n}+\frac{\gamma-1}{\gamma}d_{n-1}$. Since
$z-y_{n}=\frac{1}{\gamma}(z-t_{n})+\frac{\gamma-1}{\gamma}(z-d_{n-1})$ the
following expression can be expanded using the identity (8)

$\left\|z-y_{n}\right\|^{2}=\frac{1}{\gamma}\left\|z-t_{n}\right\|^{2}+\frac{\gamma-1}{\gamma}\left\|z-d_{n-1}\right\|^{2}\\\
-\frac{\gamma-1}{\gamma^{2}}\left\|t_{n}-d_{n-1}\right\|^{2}.$ (14)

Combining (12) and (14) leads to

$\left\|y_{n}-x_{n}\right\|^{2}-\frac{\gamma-1}{\gamma^{{2}}}\left\|t_{n}-d_{n-1}\right\|^{2}=\\\
\left\|z-x_{n}\right\|^{2}-\frac{1}{\gamma}\left\|z-t_{n}\right\|^{2}-\frac{\gamma-1}{\gamma}\left\|z-d_{n-1}\right\|^{2}.$
(15)

The left hand side is independent of the choice of $z$, hence we can
substitute $z$ by $c_{n}$ and $c_{n-1}$ and equate both right hand sides of
(15) to get

$\displaystyle\left\|c_{n}-x_{n}\right\|^{2}-\frac{1}{\gamma}\left\|c_{n}-t_{n}\right\|^{2}-\frac{\gamma-1}{\gamma}\left\|c_{n}-d_{n-1}\right\|^{2}=$
$\displaystyle
d_{C_{2}}^{2}(c_{n-1})-\frac{1}{\gamma}\left\|c_{n-1}-t_{n}\right\|^{2}-\frac{\gamma-1}{\gamma}\left\|c_{n-1}-d_{n-1}\right\|^{2},$

where we used the fact that $d_{C_{2}}(c_{n-1})=\left\|c_{n-1}-x_{n}\right\|.$
By the definition of the generated sequences, we can see that the following
identities hold

$\displaystyle\left\|c_{n}-t_{n}\right\|^{2}$
$\displaystyle=\alpha^{2}\Delta_{t_{n}}^{2},$ (17)
$\displaystyle\left\|c_{n}-d_{n}\right\|^{2}$
$\displaystyle=(\alpha-\beta)^{2}\Delta_{t_{n}}^{2},$ (18)
$\displaystyle\left\|t_{n}-d_{n}\right\|^{2}$
$\displaystyle=\beta^{2}\Delta_{t_{n}}^{2}.$ (19)

Furthermore, we can use the property that the distance of $c_{n}$ to $C_{2}$
is not larger than the distance of $c_{n}$ to an arbitrary point in $C_{2}$

$\displaystyle d_{C_{2}}(c_{n})=\min_{x\in
C_{2}}\left\|c_{n}-x\right\|\leq\left\|c_{n}-x_{n}\right\|.$ (20)

Applying (17), (18) and (20) into (LABEL:PR4) yields

$d_{C_{2}}^{2}(c_{n})-\frac{\alpha^{2}}{\gamma}\Delta_{t_{n}}^{2}-\frac{\gamma-1}{\gamma}\left\|c_{n}-d_{n-1}\right\|^{2}\leq\\\
d_{C_{2}}^{2}(c_{n-1})-\frac{1}{\gamma}\left\|c_{n-1}-t_{n}\right\|^{2}-\frac{\gamma-1}{\gamma}(\alpha-\beta)^{2}\Delta_{t_{n-1}}^{2}.$
(21)

At this point, we need to distinguish between the two cases $\gamma\in(0,1]$
and $\gamma>1$.
Case 1: Assume that $\gamma\in(0,1]$. By the definition of the sequences, we
see that

$\displaystyle c_{n}-d_{n-1}$
$\displaystyle=(1+\alpha)(t_{n}-t_{n-1})-\beta(t_{n-1}-t_{n-2})$
$\displaystyle t_{n}-c_{n-1}$
$\displaystyle=(t_{n}-t_{n-1})-\alpha(t_{n-1}-t_{n-2})$

and by applying the identity (8) and leaving out a positive term, we get the
following estimations

$\displaystyle\left\|c_{n}-d_{n-1}\right\|^{2}$
$\displaystyle\geq(1+\alpha-\beta)((1+\alpha)\Delta_{t_{n}}^{2}-\beta\Delta_{t_{n-1}}^{2}),$
$\displaystyle\left\|t_{n}-c_{n-1}\right\|^{2}$
$\displaystyle\geq(1-\alpha)(\Delta_{t_{n}}^{2}-\alpha\Delta_{t_{n-1}}^{2}).$

Applying these estimates into (21) leads to

$\displaystyle d_{C_{2}}^{2}(c_{n})+K_{1}\Delta_{t_{n}}^{2}\leq
d_{C_{2}}^{2}(c_{n-1})+K_{2}\Delta_{t_{n-1}}^{2},$ (22)

with
$K_{1}:=\frac{1-\gamma}{\gamma}(1+2\alpha+\alpha^{2}-\beta-\alpha\beta)+\frac{1}{\gamma}(1-\alpha-\alpha^{2})$
and
$K_{2}:=\frac{1-\gamma}{\gamma}(\beta-\alpha\beta+\alpha^{2})+\frac{1}{\gamma}(\alpha-\alpha^{2})$.
Lemma .1 ensures that (9) and (10) imply $K_{1}>K_{2}>0.$
Case 2: Assume that $\gamma>1$. Similarly, we see that

$\displaystyle c_{n}-d_{n-1}$
$\displaystyle=(1+\alpha)(t_{n}-t_{n-1})+\beta(t_{n-2}-t_{n-1})$
$\displaystyle t_{n}-c_{n-1}$
$\displaystyle=(t_{n}-t_{n-1})-\alpha(t_{n-1}-t_{n-2})$

and by applying the identity (8), we get

$\displaystyle\left\|c_{n}-d_{n-1}\right\|^{2}$
$\displaystyle\leq(1+\alpha+\beta)((1+\alpha)\Delta_{t_{n}}^{2}+\beta\Delta_{t_{n-1}}^{2}),$
$\displaystyle\left\|t_{n}-c_{n-1}\right\|^{2}$
$\displaystyle\geq(1-\alpha)(\Delta_{t_{n}}^{2}-\alpha\Delta_{t_{n-1}}^{2}).$

Applying these estimates into (21) leads to

$\displaystyle d_{C_{2}}^{2}(c_{n})+K_{1}\Delta_{t_{n}}^{2}\leq
d_{C_{2}}^{2}(c_{n-1})+K_{2}\Delta_{t_{n-1}}^{2},$ (23)

with
$K_{1}:=\frac{1-\gamma}{\gamma}(1+2\alpha+\alpha^{2}+\beta+\alpha\beta)+\frac{1}{\gamma}(1-\alpha-\alpha^{2})$
and
$K_{2}:=\frac{1-\gamma}{\gamma}(\alpha^{2}-\beta-3\alpha\beta)+\frac{1}{\gamma}(\alpha-\alpha^{2})$.
Lemma .1 asserts that (9) and (10) imply $K_{1}>K_{2}>0.$

On the one hand, we can deduce from (22) and (23) that the sequence

$\displaystyle\left(d_{C_{2}}^{2}(c_{n})+K_{2}\Delta_{t_{n}}^{2}\right)_{n\in\mathbb{N}}$
(24)

is positive and non-increasing as $n$ increases, therefore the sequence (24)
converges as $n\to+\infty$. On the other hand, we can rewrite (22) and (23) to
get

$0\leq(K_{1}-K_{2})\Delta_{t_{n}}^{2}\leq
d_{C_{2}}^{2}(c_{n-1})-d_{C_{2}}^{2}(c_{n})\\\
+K_{2}(\Delta_{t_{n-1}}^{2}-\Delta_{t_{n}}^{2}).$

If we sum up this inequality we deduce that

$(K_{1}-K_{2})\sum_{j=2}^{N}\Delta_{t_{j}}^{2}\leq
d_{C_{2}}^{2}(c_{1})-d_{C_{2}}^{2}(c_{N})\\\
+K_{2}(\Delta_{t_{1}}^{2}-\Delta_{t_{N}}^{2}).$

Since for all $n\geq 2$ it holds
$d_{C_{2}}^{2}(c_{0})+K_{2}\Delta_{t_{0}}^{2}\geq 0$, by taking the limit
$n\to+\infty$ we see that

$\displaystyle\sum_{j=2}^{+\infty}\Delta_{t_{j}}^{2}\leq
d_{C_{2}}^{2}(c_{1})+K_{2}\Delta_{t_{1}}^{2}<+\infty$

holds, and therefore $\Delta_{t_{n}}\to 0$ as $n\to+\infty.$ Moreover, we
already showed that (24) is converges and as a consequence $d_{C_{2}}(c_{n})$
also converges as $n\to+\infty$. Hence the sequence $(c_{n})_{n\in\mathbb{N}}$
must be bounded, since its distance to the bounded set $C_{2}$ converges. By
(17) and (18), we see that $(\left\|c_{n}-t_{n}\right\|)_{n\in\mathbb{N}}$ and
$(\left\|c_{n}-d_{n}\right\|)_{n\in\mathbb{N}}$ converge to zero as well.
Using this observation and (13) we conclude

$\displaystyle P_{C_{1}}(P_{C_{2}}(c_{n}))-c_{n}\to 0\text{ as }n\to+\infty.$
(25)

Furthermore, since $c_{n}$ is a bounded sequence, there exist cluster points.
For each cluster point $c^{*}$

$\displaystyle P_{C_{1}}(P_{C_{2}}(c^{*}))=c^{*}$

has to hold by (25). ∎

In numerical experiments we will see that whenever $\beta$ or $\gamma$ are not
chosen to fulfill (9), then AGLA does not converge. This suggests that it
might not be possible to extend the condition (9). On the other hand, (9) and
(10) together are sufficient conditions to guarantee convergence.

##  V Convergence of the iterates

In this section, we will associate $c\in\mathbb{C}^{M}$ with
$y\in\mathbb{R}^{M\times 2}$, where
$y_{i}=(\text{Re}(c_{i}),\text{Im}(c_{i}))$ for all $i\in\\{1,\dots,M\\}$, to
apply the subdifferential calculus and the _Kurdyka–Łojasiewicz-property_ (KL-
property), which are defined for functions from $\mathbb{R}^{M\times 2}$ to
${\overline{\mathbb{R}}:=\mathbb{R}\cup\\{\pm\infty\\}}$. The set
$C_{1}\subseteq\mathbb{R}^{M\times 2}$ remains a linear subspace and the set
$C_{2}$ can be written as

$\displaystyle C_{2}=\\{y\in\mathbb{R}^{M\times
2}:\left\|y_{i}\right\|=s_{i},\forall i=1,...,M\\}.$ (26)

The domain of an extended real-valued function $f$ is defined as
$\operatorname{dom}f=\\{{y}:f({y})<+\infty\\}.$ For our objective function (5)
it holds $\operatorname{dom}f=C_{1}$. A function is called proper if it never
attains the value $-\infty$ and its domain is a nonempty set. Since our
objective function is nonconvex and not everywhere differentiable, we
introduce the notion of the limiting subdifferential following [23, Definition
8.3].

######  Definition V.1.

For the proper function $f:\mathbb{R}^{M\times 2}\to\overline{\mathbb{R}}$ and
point $\bar{y}\in\operatorname{dom}f$, the regular subgradient
$\hat{\partial}f(\bar{y})$ is defined as the set of vectors
$\bar{v}\in\mathbb{R}^{M\times 2}$ which fulfill

$\displaystyle\liminf_{y\to\bar{y}}\frac{f(y)-f(\bar{y})-\left\langle\bar{v},y-\bar{y}\right\rangle}{\left\|y-\bar{y}\right\|}\geq
0,$

and the limiting subdifferential $\partial f(\bar{y})$ is defined as the set
of vectors $\bar{v}\in\mathbb{R}^{M\times 2}$ such that there exist sequences
$(y_{n})_{n\in\mathbb{N}}\subseteq\mathbb{R}^{M\times 2}$ and
$v_{n}\in\hat{\partial}f(y_{n})$ such that $y_{n}\to\bar{y}$, $f(y_{n})\to
f(\bar{y})$ and $v_{n}\to\bar{v}$ as $n\to+\infty$.

The subdifferential is a set-valued operator and its domain is defined as
$\operatorname{dom}\partial F:=\\{u\in\mathbb{R}^{M\times 2}:\partial
F(u)\neq\emptyset\\}$. If $f$ is continuously differentiable on a open set,
then $\partial f$ is single-valued and thus coincide with $\nabla f$ on this
set [23, Corrolary 9.19].

The following proposition states the formula for the subgradient of our
objective function, whose proof is postponed to the appendix.

######  Proposition V.2.

For the function $f:\mathbb{R}^{M\times 2}\to\overline{\mathbb{R}}$,
$y\mapsto\delta_{C_{1}}(y)+\frac{1}{2}d_{C_{2}}^{2}(y)$ the limiting
subdifferential $\partial f:\mathbb{R}^{M\times
2}\rightrightarrows\mathbb{R}^{M\times 2}$ is given by

$\displaystyle\partial f(y)=C_{1}^{\perp}+y-{P}_{C_{2}}(y),\text{ for }y\in
C_{1}\setminus D,$

where

$D=\\{y\in\mathbb{R}^{M\times 2}\mid\exists i\in\\{1,...,M\\}:y_{i}=0\text{
and }s_{i}\neq 0\\}$.

Furthermore for $y\in C_{1}\setminus D$ it holds

$\displaystyle d_{\partial
f(y)}(0)\leq\left\|y-P_{C_{1}}(P_{C_{2}}(y))\right\|.$

Here for simplicity, we keep the notation $f$ for the objective function and
write $f({y})$ when it maps from $\mathbb{R}^{M\times 2}$ to
$\overline{\mathbb{R}}$, and $f(c)$ when
$f\colon\mathbb{C}^{M}\to\overline{\mathbb{R}}$.

Before we introduce the KL-property, we have to define the class of concave
and continuous functions.

######  Definition V.3.

Let $\eta\in(0,+\infty]$. We denote by $\Phi_{\eta}$ all function
$\varphi:[0,\eta)\to[0,+\infty)$ which satisfy the following conditions

  1. (i)

$\varphi(0)=0$

  2. (ii)

$\varphi$ is $C^{1}$ on $(0,\eta)$ and continuous at $0$

  3. (iii)

for all $s\in(0,\eta):\quad\varphi^{\prime}(s)>0$

We state the definition of the KL-property, which can be used to prove
convergence iterates of first-order and second-order methods, with nonconvex
objective functions [24]. Intuitively speaking, functions that satisfy this
property are not too flat at their respective local minimizers and critical
points. For $b>a$, we will write $\llbracket a<F<b\rrbracket$ to denote the
level set $\\{u\in\mathbb{R}^{M\times 2}:a<F(u)<b\\}$ of a function
$F:\mathbb{R}^{M\times 2}\to\overline{\mathbb{R}}$.

######  Definition V.4.

Let $F:\mathbb{R}^{M\times 2}\to\overline{\mathbb{R}}$ be proper and lower
semicontinuous. $\partial F$ denotes the subdifferential of $F$. The function
$F$ is said to have the _Kurdyka–Łojasiewicz-property_ at
$\overline{u}\in\operatorname{dom}\partial F$ if there exist
$\eta\in(0,+\infty]$, a neighborhood $U$ of $\overline{u}$ and a function
$\varphi\in\Phi_{\eta}$, such that for all

$\displaystyle u\in U\cap\llbracket
F(\overline{u})<F<F(\overline{u})+\eta\rrbracket,$

the following holds

$\displaystyle\varphi^{\prime}(F(u)-F(\overline{u}))d_{\partial F(u)}(0)\geq
1.$

The function $\varphi$ is called the desingularizing function.

The following result, taken from [25, Lemma 6], provides a uniformized KL
property on a neighborhood and will be crucial in our convergence analysis.

######  Lemma V.5.

Let $\Omega$ be a compact set and $F\colon\mathbb{R}^{M\times
2}\to\overline{\mathbb{R}}$ be a proper and lower semicontinuous function.
Assume that $F$ is constant on $\Omega$ and satisfies the KL property at each
point of $\Omega$. Then there exist $\varepsilon>0,\eta>0$ and
$\varphi\in\Phi_{\eta}$ such that for every $\overline{u}\in\Omega$ and every
element $u$ in the intersection

$\left\\{u\in\mathbb{R}^{M\times 2}\colon
d_{\Omega}(u)<\varepsilon\right\\}\cap\llbracket
F\left(\overline{u}\right)<F<F\left(\overline{u}\right)+\eta\rrbracket$

the following holds:

$\varphi^{\prime}\left(F\left(u\right)-F\left(\overline{u}\right)\right)d_{\partial
F(u)}(0)\geq 1.$

The KL-property holds for a broad class of functions, especially for the
indicator functions and distance functions of semi-algebraic sets as stated in
[26]. Since $C_{1}$ as a linear subspace is algebraic and $C_{2}$ is algebraic
as we see in (26), we know that our objective function $f$ in (5) has the KL-
property.

For the proof of the convergence of the iterates, we introduce the regularized
version of $f$, namely $F_{K}:\mathbb{R}^{M\times 2}\times\mathbb{R}^{M\times
2}$ defined as

$\displaystyle
F_{K}(y,z)=\delta_{C_{1}}(y)+\frac{1}{2}d^{2}_{C_{2}}(y)+\frac{K}{2\alpha^{2}}\left\|y-z\right\|^{2},$

with $K>0$. Then by Proposition 10.5 and Corollary 10.9 of [23] the formula of
the subdifferential $\partial F_{K}:\mathbb{R}^{M\times
2}\times\mathbb{R}^{M\times 2}\rightrightarrows\mathbb{R}^{M\times
2}\times\mathbb{R}^{M\times 2}$ is given as

$\displaystyle\partial F_{K}(y,z)=\left\\{\partial
f(y)+\frac{K}{\alpha^{2}}(y-z)\right\\}\times\left\\{\frac{K}{\alpha^{2}}(z-y)\right\\}.$
(27)

Furthermore, by [27] we know that $F_{K}$ inherits the KL-property from $f$.
Simple calculations show that $F$ is non-increasing, and the distance of the
subgradient to 0 can be estimated from above.

######  Proposition V.6.

Let $(c_{n})_{n\in\mathbb{N}}$, $(d_{n})_{n\in\mathbb{N}}$ and
$(t_{n})_{n\in\mathbb{N}}$ be the sequence generated by AGLA and assume that
(9) and (10) hold. Then the following statements are true:

  1. (i)

There exist a constant $\kappa_{1}>0$ such that for all $n\in\mathbb{N}$ it
holds

$\displaystyle F_{K_{2}}(c_{n},t_{n})+\kappa_{1}\Delta_{t_{n}}^{2}$
$\displaystyle\leq F_{K_{2}}(c_{n-1},t_{n-1}),$ (28)

where $K_{2}$ is defined as in Theorem IV.1.

  2. (ii)

If $c_{n}\in D$ for at most finitely many $n\in\mathbb{N}$, where $D$ is
defined as in Proposition V.2, then there exist an integer $m\in\mathbb{N}$
and a constant $\kappa_{2}>0$ such that for all $n\geq m$ it holds

$\displaystyle d_{\partial F_{K_{2}}(c_{n},t_{n})}(0)$
$\displaystyle\leq\kappa_{2}(\Delta_{t_{n+1}}+\Delta_{t_{n}}).$ (29)

The proof of this proposition can be found in the appendix. Now we can state
the proof that the generated iterates of AGLA converge by using the KL-
property and the previous observations.

######  Theorem V.7.

Let $(c_{n})_{n\in\mathbb{N}}$, $(d_{n})_{n\in\mathbb{N}}$ and
$(t_{n})_{n\in\mathbb{N}}$ be the sequence generated by AGLA. Assume that (9)
and (10) hold and that $c_{n}\in D$ for at most finitely many
$n\in\mathbb{N}$, where $D$ is defined as in Proposition V.2. Then
$(c_{n})_{n\in\mathbb{N}}$ converges and the limit $c^{*}$ is a critical point
of $f$, if $c^{*}\notin D$.

###### Proof.

For simplicity we will denote $F_{n}=F_{K_{2}}(c_{n},t_{n})$ and
$\lim_{n\to\infty}F_{n}=F^{*}$, which exists by Theorem IV.1. For any cluster
point $c^{*}$ of the sequence $(c_{n})_{n\in\mathbb{N}}$, we see that
$F(c^{*})=F^{*}$ by Theorem IV.1. If there exists an integer
$n_{0}\in\mathbb{N}$ such that $F_{n_{0}}=F^{*}$, then the inequality (28)
implies that $\Delta_{t_{n}}=0$ for all $n\geq n_{0}$. Hence by the definition
of the algorithm and (17)-(19), the sequences $(t_{n})_{n\geq n_{0}}$,
$(d_{n})_{n\geq n_{0}}$ and $(c_{n})_{n\geq n_{0}}$ are constant and the
statement is proven.

Now assume that $F_{n}>F^{*}$ for all $n\in\mathbb{N}$. If $c_{n}\in D$ for at
most finitely many $n\in\mathbb{N}$, then we can choose $m\in\mathbb{N}$ such
that for all $n\geq m$ the vector $c_{n}\notin D$.

From Theorem IV.1, we know that the sequence
$((c_{n},t_{n}))_{n\in\mathbb{N}}$ is bounded, and therefore there exist
cluster points. Let us denote by $\Omega$ the set of all cluster points of the
sequence $((c_{n},t_{n}))_{n\in\mathbb{N}}$. We can see that $\Omega$ is
closed and also bounded. Moreover, the value of $F$ over $\Omega$ always
equals $F^{*}$. Since $F$ has the KL-property, according to Lemma V.5, there
exist $\varepsilon,\eta>0$ and a function $\varphi\in\Phi_{\eta}$ such that
all element $(y,z)$ in the intersection

$\left\\{(y,z)\in\mathbb{R}^{M\times 2}\times\mathbb{R}^{M\times 2}\colon
d_{\Omega}((y,z))<\varepsilon\right\\}\\\ \cap\llbracket
F^{*}<F_{K_{2}}<F^{*}+\eta\rrbracket$ (30)

it holds

$\varphi^{\prime}\left(F_{K_{2}}\left((y,z)\right)-F^{*}\right)d_{\partial
F_{K_{2}}\left((y,z)\right)}(0)\geq 1.$ (31)

Since $F_{n}$ converges to $F^{*}$ and $d_{\partial
F_{K_{2}}(c_{n},t_{n})}(0)\to 0$ as $n\to+\infty$ due to Proposition V.6,
there exists $n_{1}\geq m$ such that $(c_{n},t_{n})$ belongs to the
intersection (30) for all $n\geq n_{1}$. This means by (31) and (29), the
inequality

$\kappa_{2}\varphi^{\prime}(F_{n}-F^{*})(\Delta_{t_{n+1}}+\Delta_{t_{n}})\\\
\geq\varphi^{\prime}(F_{n}-F^{*})d_{\partial F_{n}}(0)\geq 1,$ (32)

holds for all $n\geq n_{1}.$ Since $\varphi$ is concave and differentiable, we
know that

$\displaystyle\varphi(z)-\varphi(y)\geq\varphi^{\prime}(z)(z-y).$

By choosing $z=F_{n}-F^{*}$ and $y=F_{n+1}-F^{*}$ then plugging (28) and (32),
we obtain after some rearranging

$\varphi(F_{n}-F^{*})-\varphi(F_{n+1}-F^{*})\geq\frac{\kappa_{1}}{\kappa_{2}}\frac{\Delta^{2}_{t_{n+1}}}{\Delta_{t_{n+1}}+\Delta_{t_{n}}}.$

holds for $n\geq n_{1}$. By applying Lemma .2 in the appendix we can see that
this implies that

$\displaystyle\frac{9\kappa_{2}}{4\kappa_{1}}\left(\varphi(F_{n}-F^{*})-\varphi(F_{n+1}-F^{*})\right)\geq
2\Delta_{t_{n+1}}-\Delta_{t_{n}}$

holds. Summing up this inequality for $j=n_{1},\dots,\bar{n}$ leads to

$\sum_{j=n_{1}}^{\bar{n}}\Delta_{t_{j}+1}\leq\frac{9\kappa_{2}}{4\kappa_{1}}\left(\varphi(F_{n_{1}}-F^{*})-\varphi(F_{\bar{n}+1}-F^{*})\right)\\\
+{\Delta_{t_{n_{1}}}}-\Delta_{t_{\bar{n}+1}}.$

Since $\varphi$ is nonnegative, by passing $\bar{n}\to\infty$, we deduce

$\displaystyle\sum_{j=n_{1}}^{+\infty}\Delta_{t_{j}}\leq\frac{9\kappa_{2}}{4\kappa_{1}}\varphi(F_{n_{1}}-F^{*})+{\Delta_{t_{n_{1}}}}<+\infty.$

This implies that $(t_{n})_{n\in\mathbb{N}}$ is a Cauchy-sequence and
therefore converges. Since $(c_{n})_{n\in\mathbb{N}}$ and
$(d_{n})_{n\in\mathbb{N}}$ are linear combinations of
$(t_{n})_{n\in\mathbb{N}}$, we conclude that these series converge as well and
the limit of $(c_{n})_{n\in\mathbb{N}}$ has to be $c^{*}$ according to Theorem
IV.1. Furthermore $0\in\partial f(c^{*})$ by Proposition V.2 if $c^{*}\notin
D.$ ∎

Since AGLA with $\gamma=1$ reduces to FGLA, we can state the following
convergence properties of FGLA to complement the result in [11]. It is a
direct consequence of Theorem IV.1 and V.7.

######  Corollary V.8.

Let $(c_{n})_{n\in\mathbb{N}}$ be the sequences generated by FGLA. If
$\alpha\in(0,0.5)$, then

  1. (i)

There exist constants $K_{1}>K_{2}>0$ such that the following descent property
holds for all $n\geq 1$

$\displaystyle d_{C_{2}}^{2}(c_{n})+K_{1}\Delta_{t_{n}}^{2}$
$\displaystyle\leq d_{C_{2}}^{2}(c_{n-1})+K_{2}\Delta_{t_{n-1}}^{2},$

where $\Delta_{t_{n}}:=\left\|t_{n}-t_{n-1}\right\|$. Therefore
$\Delta_{t_{n}}$ converges to zero and
$\lim_{n\to+\infty}d_{C_{2}}^{2}(c_{n})\in\mathbb{R}$ exists.

  2. (ii)

Furthermore $(c_{n})_{n\in\mathbb{N}}$ is a bounded sequence and every
convergent subsequence converges to a point $c^{*}$, which fulfills

$\displaystyle P_{C_{1}}(P_{C_{2}}(c^{*}))=c^{*}$

and is therefore a critical point if $c^{*}\notin D$, where $D$ is defined as
in Proposition V.2.

  3. (iii)

If $c_{n}\in D$ for at most finitely many $n\in\mathbb{N}$, then
$(c_{n})_{n\in\mathbb{N}}$ is a convergent sequence.

To summarize our results, we have established conditions and parameter regimes
for AGLA and FGLA that guarantee that the generated sequences
$(c_{n})_{n\in\mathbb{N}}$ assert a decreasing property and that every cluster
point $c^{*}\notin D$ is a local minimizer of our objective function. To
guarantee convergence, we needed the condition $c_{n}\in D$ for at most
finitely many $n\in\mathbb{N}$, since outside of $D$ the projection
$\overline{P}_{C_{2}}$ is unique and $\frac{1}{2}d_{C_{2}}^{2}$ is
continuously differentiable. It is important to mention that the inequalities
used in the statements above do not cover all possible choices of parameters
for which we have observed convergence in the simulations. A similar situation
occurs even if $\frac{1}{2}d_{C_{2}}^{2}$ is assumed to have Lipschitz-
continuous gradient, see [21, 22]. Notice that Lipschitz-continuity does not
hold in our model, according to Proposition V.2.

Most importantly, our proofs show that for AGLA and FGLA a good performance
and minimizing properties for the phase retrieval problem can be guaranteed,
when the parameters are well chosen.

Figure 1: Largest possible choice for $\alpha$ in AGLA for given $\beta$ and
$\gamma$ based on the conditions (9) and (10) that guarantee convergence

In Figure 1 we plotted for fixed $\beta\in[0,5]$ and $\gamma\in[0.1,1.5]$ the
upper bound for $\alpha$ s.t. $\alpha,\beta,\gamma$ satisfy the convergence
guarantees (9) and (10) of Theorem IV.1. The white areas symbolize the
combinations of $\beta$ and $\gamma$, for which (9) is not fulfilled, i.e.
where we expect AGLA not to converge. As noticed before, for $\gamma=1$ AGLA
coincides with FGLA and (10) reduces to $\alpha<0.5$ independently of $\beta$,
which we can see in the Figure.

Before we take a look at the numerical simulations we will state a corollary,
which motivates for which iterates we are going to plot the function values.

######  Corollary V.9.

Let $(c_{n})_{n\in\mathbb{N}}$ be the sequence generated by AGLA. Assume that
(9) and (10) hold and that $c_{n}\in D$ for at most finitely many
$n\in\mathbb{N}$, where $D$ is defined as in Proposition V.2. Then for
$y_{n}=P_{C_{1}}(P_{C_{2}}(c_{n}))$ the following properties hold:

  1. (i)

For $n\geq 0$

$\displaystyle d_{C_{2}}^{2}(y_{n})\leq
d_{C_{2}}^{2}(c_{n})-\left\|y_{n}-c_{n}\right\|^{2}.$

  2. (ii)

The sequence $(y_{n})_{n\in\mathbb{N}}$ converges as $n\to+\infty$.

###### Proof.

Let $n\geq 0$. By (11) we know that

$\displaystyle\left\|y_{n}-P_{C_{2}}(c_{n})\right\|^{2}=\left\|c_{n}-P_{C_{2}}(c_{n})\right\|^{2}-\left\|y_{n}-c_{n}\right\|^{2}.$

By the definition of the distance function we see that
$d_{C_{2}}^{2}(y_{n})\leq\left\|y_{n}-P_{C_{2}}(c_{n})\right\|^{2}$ and
$d_{C_{2}}^{2}(c_{n})=\left\|c_{n}-P_{C_{2}}(c_{n})\right\|^{2}$ hold and by
this (i) is proven. Furthermore by the results of the Theorems IV.1 and V.7 we
can deduce by (13) that $(y_{n})_{n\in\mathbb{N}}$ converges as well. ∎

##  VI Numerical Experiments

In this section we will present the results of our numerical experiments and
test the performance of the algorithm AGLA for the STFT-spectrogram inversion.
As signals we used the © EBU Audio Test sequences, which provide 70 audio
files for testing. To reduce the computational time for each signal, we
trimmed down every signal to their first two seconds. In this paper we only
present the results of some selected signals of this test set. A reproducible
research addendum is available at http://ltfat.org/notes/059/, where we
provide the code, from which one can test different configurations of windows
and parameters and the results of our parameter testing. It is important to
mention, that the presented algorithm and convergence proofs work for a broad
range of transformations. In this publication we restrict ourselves to the
application in acoustics using a STFT for $T$.

The simulations were performed with hop size of 32 and 256 FFT bins and a
Gaussian window using the LTFAT toolbox [28]. This choice of hop size and bins
ensures that it is possible to reconstruct the signals uniquely from their
measurements [17]. For more numerical experiments with a different window
function, we refer to [29]. As a quality measure we used the Spectrogram
Signal to Noise Ratio, which is defined as

$\displaystyle\text{SSNR}(x)=-10\log_{10}\left(\frac{\left\|\left|Tx\right|-s\right\|}{\left\|s\right\|}\right).$

Maximizing the SSNR for a signal $x$ is equivalent to minimizing our objective
function (5), since $d_{C_{2}}=\left\|\left|\cdot\right|-s\right\|$ for given
$s$ and the negative logarithm is monotonely decreasing.

Best 10 combinations with convergence guarantee
---
$\alpha$ | $\beta$ | $\gamma$ | Average SSNR
0.09 | 1.10 | 0.20 | 9.75505
0.60 | 0.65 | 0.75 | 9.71289
0.70 | 0.50 | 0.70 | 9.70320
0.19 | 1.10 | 0.25 | 9.68508
0.28 | 1.05 | 0.20 | 9.67243
0.22 | 1.50 | 0.65 | 9.64285
0.14 | 1.15 | 0.30 | 9.62835
0.33 | 1.05 | 0.25 | 9.60824
0.81 | 0.40 | 0.65 | 9.58805
0.39 | 1.90 | 0.90 | 9.58760
TABLE I: The best parameter combinations satisfying the convergence guarantee
with respect to average SSNR after 100 iterations over the test set,
disregarding the convergence guarantees

Having three parameters in AGLA rather than one in FGLA makes the algorithm on
the one hand more flexible and adaptable, but on the other hand makes it more
difficult to assert, which parameter combination is the best. Therefore we
first present a summary of our numerical parameter tests for the parameters of
$\alpha$, $\beta$ and $\gamma$. We took ten signals of the test sequence set
and let the algorithms run for 100 iterations, initialized with zero-phase,
namely $c_{0}=s$. The signals were chosen to cover a wide range of acoustical
signals, including single instruments, human speech and full orchestras. We
tested the performance of parameter combinations, satisfying the sufficient
conditions to guarantee convergence, and also the best possible combinations,
disregarding the convergence guarantee. It is important to note that these
results will vary for different choices of window functions and different
redundancies of the STFT. A table including the final SSNR for all tested
combinations can be found in the research addendum.

We computed for $\beta\in[0.1,2]$ and $\gamma\in[0.2,1.6]$ the largest
possible $\alpha$ up to two decimal points, which satisfies the conditions (9)
and (10) and tested the parameter combinations for ten different signals. The
results are displayed in Table I.

Best 10 combinations over all
---
$\alpha$ | $\beta$ | $\gamma$ | Average SSNR
1.05  | 1.35 | 1.25 | 12.23339
0.95 | 1.00 | 1.30 | 12.16774
0.95 | 0.99 | 1.30 | 12.08267
0.95 | 1.05 | 1.30 | 12.06661
1.00 | 1.40 | 1.25 | 11.98671
1.05 | 1.30 | 1.25 | 11.97935
0.99 | 1.00 | 1.30 | 11.89051
0.99 | 0.99 | 1.30 | 11.85429
1.00 | 1.05 | 1.30 | 11.85108
0.99 | 1.40 | 1.25 | 11.84152
TABLE II: The best parameter combinations with respect to average SSNR after
100 iterations over the test set

It is interesting to note that all parameter combinations satisfying (9) and
(10) resulted in a very similar SSNR after 100 iterations. Only for Sound 7
the second and third combinations in Table I converged to a point of
significantly larger SSNR. Overall the combinations with $\gamma\approx 0,25$
and $\beta\approx 1,1$ performed over all very well and $\alpha=0.09$,
$\beta=1.1$ and $\gamma=0.2$ was the best combination.

We did the same test considering further 832 combinations with
$\alpha\in[0.95,1.25]$, $\beta\in[0.95,1.5]$ and $\gamma\in[0.95,1.3]$. Even
though these combinations are not covered by the convergence guarantee, they
show the best possible convergence of our proposed algorithm AGLA. In these
tests, we noticed that if $\beta$ and $\gamma$ do not fulfill (9), then the
algorithm does not converge. This observation is included in the research
addendum. It seems optimal to choose $\gamma\approx 1.25$, $\alpha\approx 1$
and $\beta>\alpha$.

We compared AGLA to two other algorithms, which were observed to perform well
in the STFT phase retrieval in [30]. The first algorithm is the _Relaxed
Averaged Alternating Projections_ (RAAR) proposed by R. Luke for the phase
retrieval problem in Diffraction Imaging [31].

Algorithm 4 Relaxed Averaged Alternating Reflections

Initialize $c_{0}\in\mathbb{C}^{n}$ and $\lambda\in(0,1]$

$\textbf{Iterate for }n=1,\dots,N$

$c_{n+1}=\frac{\lambda}{2}\left(c_{n}+R_{C_{1}}(R_{C_{2}}(c_{n}))\right)+(1-\lambda)P_{C_{2}}(c_{n})$

Return  $T^{\dagger}c_{N}$

According to [32] the best performance of RAAR for speech signals can be
expected for $\lambda=0.9$.

The second algorithm is the _Difference Map_ (DM) proposed by V. Elser for
phase retrieval in [33].

Algorithm 5 Difference Map

Initialize $c_{0}\in\mathbb{C}^{n}$ and $\rho\in\mathbb{R}\setminus\\{0\\}$

$\textbf{Iterate for }n=1,\dots,N$

$t_{n}=P_{C_{2}}(c_{n})+\frac{1}{\rho}(P_{C_{2}}(c_{n})-c_{n})$

$s_{n}=P_{C_{1}}(c_{n})+\frac{1}{\rho}(P_{C_{1}}(c_{n})-c_{n})$

$c_{n+1}=c_{n}+\rho(P_{C_{1}}(t_{n})-P_{C_{2}}(s_{n}))$

Return  $T^{\dagger}c_{N}$

In general choosing $\rho$ close to 1 yields the best performance of DM and in
[30] it was observed that the choice $\rho=0.8$ performs best. To the best of
our knowledge the convergence for DM is unproven.

Based on the observation in Corollary V.9, we plotted for FGLA and AGLA the
SSNR of $y_{n}=P_{C_{1}}(P_{C_{2}}(c_{n}))$ and for RAAR and DM the SSNR of
the iterates $c_{n}$ respectively.

Figure 2: Comparison of FGLA, AGLA, RAAR, and DM with their respective best
parameter choice with zero-phase initialization

For the comparison between the algorithms, we started by comparing AGLA, FGLA,
DM, and RAAR for 1000 iterations with zero-phase initialization, namely,
taking $c_{0}=s$ without any phases. For these simulations we used signals
which were not included in the parameter search to remove any bias. For the
purpose of a better overview, we did not include the algorithm GLA, since the
observations in [11] clearly showed that FGLA outperforms GLA in nearly every
setting.

For the Figure 2 we considered five signals, varying in their nature. For DM
and RAAR we chose $\rho=0.8$ and $\lambda=0.9$ respectively, for FGLA
$\alpha=0.99$ and for AGLA the best combination from Table II.

Figure 3: Comparison of FGLA, AGLA, RAAR, and DM with their respective best
parameter choice with PGHI initialization

We can observe that DM performed over all best, but it is also important to
note that DM computes twice as many different projections per iterations
compared to the other algorithms and the projections are the computationally
most expensive segments of the algorithms. Still we see that AGLA can
outperform DM (Sound 26) or reach a very similar final SSNR (Sound 34, 41 and
61). Furthermore RAAR, an algorithm commonly used for the phase retrieval
problem in areas beyond acoustics [31], performed for Sound 19 better than
AGLA and for the other four it reached a point of similar or lower SSNR. DM
and RAAR started oscillating after 100 iterations, whereas FGLA and AGLA
stayed stable, an important trait in algorithms. AGLA achieved higher SSNR
than FGLA over all, except for Sound 26, where both of them performed similar
and better than DM and RAAR.

For the next experiment we initialized the algorithms with the reconstructed
signal from the _Phase Gradient Heap Integration_ (PGHI) presented in [34] and
compared them in Figure 3 for the same signals as in Figure 2.

PGHI is a noniterative method for the phase retrieval problem, based on the
phase-magnitude relations of an continuous STFT. It is efficient, but when
used for the discrete setting it introduced inaccuracies depending on the
parameters of the discrete STFT, and it was observed to give a good starting
point for iterative algorithms [7].

With PGHI-initialization we observe that the starting SSNR of the algorithms
was significantly higher and notice that AGLA improved the most. This could be
explained by the design of AGLA, as mentioned before, enabling the iterates to
escape local solution as long as the steps $t_{n}-t_{n-1}$ and the difference
between the direction of the projected and nonprojected sequences are large
enough. AGLA performed better or equal than DM on all five signals and RAAR
only reached a point of higher SSNR for Sound 19, similar to the zero-phase
initialization experiment. For DM and RAAR there was a slight increase in the
intensity of the oscillations. Interestingly for Sound 61, FGLA, RAAR and DM
performed slightly worse than with zero-phase initialization, and only AGLA
reached the same SSNR as before. This suggest that AGLA is an algorithm
suitable for hybrid schemes, where one initializes with either a non-iterative
scheme or the end point of another scheme, maybe faster, after a fixed number
of iterations as it has been studied in [30].

In Figure 4 we plotted GLA with FGLA and AGLA with their respective best
parameter choices covered by the convergence guarantee. We notice that AGLA
had some oscillation in the first 20 iterations and after that catches up to
GLA and FGLA, surpassing them in the end. This behaviour could be explained by
$\beta=1.1$ being relatively large and $\gamma=0.2$ being relatively small,
which means that the inertial/momentum step of the nonprojected sequence can
be quite large and the projected iterates are weighted less, therefore we
experienced not so optimal performance in the beginning, until the iterates
got closer to a local solution.

##  VII Conclusion

In this paper we presented the Accelerated Griffin-Lim algorithm and proved
convergence results for it and its predecessor, the Fast Griffin-Lim
algorithm. If the parameters are chosen to fulfill the necessary conditions to
guarantee convergence and the minimizing properties, both of them outperform
the Griffin-Lim algorithm, making it now possible for them to replace this
classical method as the standard and reliable phase retrieval algorithm for
acoustic. We showed that one can expect good convergence behaviour of inertial
based methods theoretically and practically in the phase retrieval setting.
The numerical results indicate that there are parameter combinations outside
of the convergence regimes for which the algorithm asserts fast behaviour,
further sparking interest in studying these methods. The simulations indicate
that the Accelerated Griffin-Lim algorithm has the possibility to perform
similarly error-wise to Relaxed Averaged Alternating Reflections and
Difference Map, the two other powerful retrieval methods. The proposed method
achives better convergence behaviour in the sense of having fewer to none
oscillations and performing better for good initialization.

Figure 4: Comparison of GLA, FGLA, and AGLA, with their respective parameter
choice satisfying the convergence guarantee

## References

  * [1] K. Jaganathan, Y. C. Eldar, and B. Hassibi, “Stft phase retrieval: Uniqueness guarantees and recovery algorithms,” _IEEE J Sel Top_ , vol. 10, no. 4, pp. 770–781, 2016.
  * [2] R. A. Bedoui, Z. Mnasri, and F. Benzarti, “Phase retrieval: Application to audio signal reconstruction,” in _2022 19th International Multi-Conference on Systems, Signals & Devices (SSD)_, 2022, pp. 21–30.
  * [3] O. Yurduseven, D. R. Smith, and T. Fromenteze, “Phase retrieval in frequency-diverse imaging,” in _IEEE Int. Symp. Antennas Propag. & USNC/URSI National Radio Sci. Meet._, 2018, pp. 1797–1798.
  * [4] Y. Shechtman, Y. Eldar, O. Cohen, H. Chapman, J. Miao, and M. Segev, “Phase retrieval with application to optical imaging,” _IEEE Signal Process. Mag._ , vol. 32, 02 2014.
  * [5] P. Bowlan and R. Trebino, “Phase retrieval and the measurement of the complete spatiotemporal electric field of ultrashort pulses,” in _CLEO/QELS: Laser Sci. to Photonic Appl._ , 2010, pp. 1–2.
  * [6] M. Johansson, H.-S. Lui, A. Fhager, and M. Persson, “Electromagnetic source modeling using phase retrieval methods,” in _XXXth URSI Gen. Assem. Sci. Symp._ , 2011, pp. 1–2.
  * [7] A. Marafioti, N. Holighaus, and P. Majdak, “Time-frequency phase retrieval for audio—the effect of transform parameters,” _IEEE Trans. Signal Process._ , vol. 69, pp. 3585–3596, 2021.
  * [8] D. Griffin and J. Lim, “Signal estimation from modified short-time fourier transform,” _IEEE Trans. Acoust. Speech Signal Process._ , vol. 32, pp. 236 – 243, 1984.
  * [9] R. Gerchberg and W. Saxton, “A practical algorithm for the determination of phase from image and diffraction plane pictures,” _Optik_ , vol. 35, pp. 237–250, 1971.
  * [10] A. Beck and M. Teboulle, “A fast iterative shrinkage-thresholding algorithm for linear inverse problems,” _SIAM J. Imaging Sci._ , vol. 2, no. 1, pp. 183–202, 2009.
  * [11] N. Perraudin, P. Balazs, and P. Søndergaard, “A fast griffin–lim algorithm,” _IEEE Workshop Appl. Signal Process. Audio Acoust._ , pp. 1–4, 2013.
  * [12] M. Müller, _Fundamentals of Music Processing: Audio, Analysis, Algorithms, Applications_ , 1st ed. Springer Publishing Company, Incorporated, 2015.
  * [13] K. Yatabe, “Consistent ica: Determined bss meets spectrogram consistency,” _IEEE Signal Processing Letters_ , vol. 27, pp. 870–874, 2020.
  * [14] A. Marafioti, P. Majdak, N. Holighaus, and N. Perraudin, “Gacela - a generative adversarial context encoder for long audio inpainting,” _IEEE Journal of Selected Topics in Signal Processing_ , in press.
  * [15] N. Saleem, J. Gao, M. Irfan, E. Verdu, and J. P. Fuente, “E2e-v2sresnet: Deep residual convolutional neural networks for end-to-end video driven speech synthesis,” _Image and Vision Computing_ , vol. 119, p. 104389, 2022.
  * [16] O. Christensen, _An Introduction to Frames and Riesz Bases_. Birkhäuser Cham, 2016.
  * [17] R. Balan, P. Casazza, and D. Edidin, “On signal reconstruction from absolute value of frame coefficients,” _Proceedings of SPIE_ , 2005.
  * [18] P. Grohs, S. Koppensteiner, and M. Rathmair, “Phase retrieval: Uniqueness and stability,” _SIAM Review_ , 2020.
  * [19] P. Balazs, D. Bayer, F. Jaillet, and P. Søndergaard, “The pole behaviour of the phase derivative of the short-time fourier transform,” _Applied and Computational Harmonic Analysis_ , vol. 40, 2015.
  * [20] B. Polyak, “Some methods of speeding up the convergence of iteration methods,” _USSR Computational Mathematics and Mathematical Physics_ , vol. 4, no. 5, pp. 1–17, 1964.
  * [21] R. I. Boţ, E. R. Csetnek, and S. C. Laszlo, “An inertial forward–backward algorithm for the minimization of the sum of two nonconvex functions,” _EURO J. Comput. Optim._ , vol. 4, p. 3–25, 2016.
  * [22] S. C. Laszlo, “Forward-backward algorithms with different inertial terms for structured non-convex minimization problems,” _J. Optim. Theory Appl._ , 2023\.
  * [23] R. Rockafellar and R. Wets, _Variational analysis_ , ser. Grundlehren Math. Wiss. Springer, 2011, vol. 317.
  * [24] H. Attouch and J. Bolte, “On the convergence of the proximal algorithm for nonsmooth functions involving analytic features,” _Math. Program._ , vol. 116, p. 5–16, 22009.
  * [25] J. Bolte, S. Sabach, and M. Teboulle, “Proximal alternating linearized minimization for nonconvex and nonsmooth problems,” _Math. Program._ , vol. 146, 08 2013.
  * [26] H. Attouch, J. Bolte, and B. Svaiter, “Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward-backward splitting, and regularized gauss-seidel methods,” _Math. Program._ , vol. 137, pp. 91–129, 2013.
  * [27] G. Li and T. K. Pong, “Calculus of the exponent of kurdyka-łojasiewicz inequality and its applications to linear convergence of first-order methods,” _Found. Comput. Math._ , vol. 18, no. 5, pp. 1199–1232, 2018.
  * [28] Z. Průša, P. L. Søndergaard, N. Holighaus, C. Wiesmeyr, and P. Balazs, “The large time-frequency analysis toolbox 2.0,” in _Sound, Music, and Motion_ , M. Aramaki, O. Derrien, R. Kronland-Martinet, and S. Ystad, Eds. Cham: Springer International Publishing, 2014, pp. 419–442.
  * [29] R. Nenov, D.-K. Nguyen, and P. Balazs, “Faster than fast: Accelerating the griffin-lim algorithm,” _IEEE Int. Conf. Acoust. Speech Signal Process (ICASSP)_ , pp. 1–5, 2023.
  * [30] T. Peer, S. Welker, and T. Gerkmann, “Beyond griffin-lim: Improved iterative phase retrieval for speech,” in _Int. Workshop Acoustic Signal Enhancement (IWAENC)_ , 2022, pp. 1–5.
  * [31] D. R. Luke, “Relaxed averaged alternating reflections for diffraction imaging,” _Inverse Probl._ , vol. 21, 2004.
  * [32] T. Kobayashi, T. Tanaka, K. Yatabe, and Y. Oikawa, “Acoustic application of phase reconstruction algorithms in optics,” _IEEE Int. Conf. Acoust. Speech Signal Process (ICASSP)_ , pp. 6212–6216, 2022.
  * [33] V. Elser, “Phase retrieval by iterated projections,” _J. Opt. Soc. Am. A_ , vol. 20, pp. 40–55, 2003.
  * [34] Z. Průša, P. Balazs, and P. Søndergaard, “A noniterative method for reconstruction of phase from stft magnitude,” _IEEE/ACM IEEE Trans. Audio Speech Language Process._ , vol. 25, pp. 1154–1164, 05 2017.
  * [35] G. Garrigos, “Square distance functions are polyak-Łojasiewicz and vice-versa,” _arXiv: 2301.10332_ , 2023.

###### Proof of Proposition II.1.

For given $a\in\mathbb{C}$ and $r>0$, one can deduce by rewriting in polar
coordinates that

$\displaystyle\min_{\left|b\right|=r}\left|a-b\right|^{2}$
$\displaystyle=\min_{\theta\in[0,2\pi)}\left|a-re^{i\theta}\right|^{2}$ (33)
$\displaystyle=\min_{\theta\in[0,2\pi)}\left|a\right|^{2}+r^{2}-2\left|a\right|r\cos(\angle
a-\theta).$

Since this minimum is attained at $\theta=\angle a$, we get

$\displaystyle\min_{\left|b\right|=r}\left|a-b\right|^{2}$
$\displaystyle=\left|a-re^{i\angle a}\right|^{2}$
$\displaystyle=\left|\left|a\right|-r\right|^{2}\left|e^{i\angle
a}\right|^{2}=\left|\left|a\right|-r\right|^{2}.$

If $r=0$, then $b=0$ is the unique minimizer of (33). Therefore we can see
that

$\displaystyle d_{C_{2}}^{2}(c)$ $\displaystyle=\min_{v\in
C_{2}}\left\|c-v\right\|^{2}$ (34)
$\displaystyle=\sum_{i=1}^{L}\min_{v_{i}\in\mathbb{C},\left|v_{i}\right|=s_{i}}\left|c_{i}-v_{i}\right|^{2}$
$\displaystyle=\sum_{i=1}^{L}\left|\left|c_{i}\right|-s_{i}\right|^{2}=\left\|\left|c\right|-s\right\|^{2},$

which proves the first statement. For the second statement, we use the
definition (6) of $P_{C_{2}}$

$\displaystyle\left\|c-P_{C_{2}}(c)\right\|^{2}$
$\displaystyle=\sum_{i=1}^{L}\left|c_{i}-(P_{C_{2}}(c))_{i}\right|^{2}$
$\displaystyle=\sum_{c_{i}\neq
0}\left|c_{i}-c_{i}\frac{s_{i}}{\left|c_{i}\right|}\right|^{2}+\sum_{c_{i}=0}\left|s_{i}\right|^{2}$
$\displaystyle=\sum_{c_{i}\neq
0}\left|c_{i}\right|^{2}\left|1-\frac{s_{i}}{\left|c_{i}\right|}\right|^{2}+\sum_{c_{i}=0}\left|s_{i}\right|^{2}$
$\displaystyle=\sum_{c_{i}\neq
0}\left|\left|c_{i}\right|-s_{i}\right|^{2}+\sum_{c_{i}=0}\left|s_{i}\right|^{2}$
$\displaystyle=\sum_{i=1}^{L}\left|\left|c_{i}\right|-s_{i}\right|^{2}=d^{2}_{C_{2}}(c).$

Moreover, we see from (33) that $\theta=\angle\alpha$ is the unique minimizer
when $a\neq 0$, thus $P_{C_{2}}(c)$ is the unique minimizer of (34) for
$c\notin D$ by the calculations above. ∎

###### Proof of Proposition V.2.

In [35], an explicit formula for the limiting subgradient of the power of a
distance function is derived. By this result, we know that for
$y\in\mathbb{R}^{M\times 2}$

$\displaystyle\partial\left(\frac{1}{2}d_{C_{2}}^{2}\right)(y)={y}-\overline{P}_{C_{2}}(y).$

By Proposition II.1 we can deduce that for $y\notin D$

$\displaystyle\partial\left(\frac{1}{2}d_{C_{2}}^{2}\right)(y)=\\{y-P_{C_{2}}(y)\\}$

holds, since then $\overline{P}_{C_{2}}(y)=\\{P_{C_{2}}(y)\\}$ and that
$\frac{1}{2}d_{C_{2}}^{2}(y)=\frac{1}{2}\left\|y-P_{C_{2}}(y)\right\|^{2}.$ If
we look at the definition of $P_{C_{2}}$, we notice that each component is
continuously differentiable around a neighbourhood of any $y\notin D$, since
$x\mapsto\frac{x}{\left|x\right|}$ is continously differentiable around a
neighbourhood of any $x\neq 0$. Since $\left\|\cdot\right\|^{2}$ is
continuously differentiable everywhere, we deduce that
$\frac{1}{2}d_{C_{2}}^{2}$ is continuously differentiable around a
neighbourhood of any $y\notin D$. Therefore
$\partial\frac{1}{2}d_{C_{2}}^{2}(y)=\nabla\frac{1}{2}d_{C_{2}}^{2}(y)$ for
$y\notin D$ by [23, Corrolary 9.19].

For $\delta_{C_{1}}$ the limiting subgradient is given by the orthogonal space
$\partial\delta_{C_{1}}(y)=C_{1}^{\perp}$ for $y\in C_{1}$ by [23, Exercise
8.14]. Furthermore, using the sum rule forumla [23, Exercise 8.8], we can
deduce for the objective function
$f(y)=\delta_{C_{1}}(y)+\frac{1}{2}d_{C_{2}}^{2}(y)$ that for $y\in
C_{1}\setminus D$

$\displaystyle\partial f(y)=C_{1}^{\perp}+y-P_{C_{2}}(y).$

By the definition of the distance of the sum of sets to a point, we have that
for $y\in C_{1}\setminus D$

$\displaystyle d_{\partial f(y)}(0)$ $\displaystyle\leq\min_{z\in
C_{1}^{\perp},u\in\overline{P}_{C_{2}}(y)}\left\|z+y-u\right\|$
$\displaystyle\leq\min_{z\in C_{1}^{\perp}}\left\|z+y-P_{C_{2}}(y)\right\|$
(35)

By taking $z=P_{C_{2}}(y)-P_{C_{1}}(P_{C_{2}}(y))\in C_{1}^{\perp}$, we get
the conclusion from (35). ∎

###### Proof of Proposition V.6.

Choose $m\in\mathbb{N}$ such that for all $n\geq m$ the vector $c_{n}\notin D$
and let $n\geq m$. By the decreasing property of Theorem IV.1 and by (17) we
know that

$\displaystyle
F_{K_{2}}(c_{n},t_{n})+\kappa_{1}\left\|c_{n}-t_{n}\right\|^{2}\leq
F_{K_{2}}(c_{n-1},t_{n-1}),$

where $\kappa_{1}=\frac{K_{1}-K_{2}}{2\alpha^{2}}$ and thus proving the first
statement, since $K_{1}>K_{2}$. Using the triangle inequality we can see that
by (27) and a similar argument as in Proposition V.2

$d_{\partial
F_{n}}(0)\leq\left\|c_{n}-P_{C_{1}}(P_{C_{2}}(c_{n}))+K_{2}(c_{n}-t_{n})\right\|\\\
+K_{2}\left\|c_{n}-t_{n}\right\|,$ (36)

since $c_{n}\in C_{1}\setminus D$. By (13) we know that

$\displaystyle
c_{n}-P_{C_{1}}(P_{C_{2}}(c_{n}))=\frac{1}{\gamma}(c_{n}-t_{n+1})+\frac{\gamma-1}{\gamma}(c_{n}-d_{n})$

Furthermore, by the definition of the algorithm we see that
$c_{n}-d_{n}=\frac{\alpha}{\alpha-\beta}(c_{n}-t_{n})$. Combining this
observations in (36) we see that

$\displaystyle d_{\partial
F_{n}}(0)\leq\frac{1}{\gamma}\left\|c_{n}-t_{n+1}\right\|+\mu\left\|c_{n}-t_{n}\right\|$

with
$\mu=\left|\frac{(\gamma-1)\alpha}{\gamma(\alpha-\beta)}+K_{2}\right|+K_{2}>0$.
Furthermore using the triangle inequality we see that

$\displaystyle d_{\partial
F_{n}}(0)\leq\frac{1}{\gamma}\left\|t_{n}-t_{n+1}\right\|+\left(\frac{1}{\gamma}+\mu\right)\left\|c_{n}-t_{n}\right\|.$

Since $c_{n}-t_{n}=\alpha(t_{n}-t_{n-1})$ we conclude that

$\displaystyle d_{\partial
F_{n}}(0)\leq\kappa_{2}(\Delta_{t_{n+1}}+\Delta_{t_{n}})$

with $\kappa_{2}=\max\\{\frac{1}{\gamma},{(\frac{1}{\gamma}+\mu)\alpha}\\}$. ∎

######  Lemma .1.

Suppose that $\gamma>0$ and

$0\leq 2\beta{\left\lvert 1-\gamma\right\rvert}<{2-\gamma}$ (37)

(i) For $0<\gamma\leq 1$, if

$0<\alpha<\left(1-\dfrac{1}{\gamma}\right)\beta+\dfrac{1}{\gamma}-\dfrac{1}{2}$
(38)

then

$K_{1}>K_{2}>0,$

where
$K_{1}:=\frac{1-\gamma}{\gamma}(1+2\alpha+\alpha^{2}-\beta-\alpha\beta)+\frac{1}{\gamma}(1-\alpha-\alpha^{2})$
and
$K_{2}:=\frac{1-\gamma}{\gamma}(\alpha^{2}+\beta-\alpha\beta)+\frac{1}{\gamma}(\alpha-\alpha^{2})$.

(ii) For $1<\gamma<2$, if

$0<\alpha<\frac{1}{2\beta(\gamma-1)+\gamma}-\frac{1}{2}$ (39)

then

$K_{1}>K_{2}>0,$

where
$K_{1}:=\frac{1-\gamma}{\gamma}(1+2\alpha+\alpha^{2}+\beta+\alpha\beta)+\frac{1}{\gamma}(1-\alpha-\alpha^{2})$
and
$K_{2}:=\frac{1-\gamma}{\gamma}(\alpha^{2}-\beta-3\alpha\beta)+\frac{1}{\gamma}(\alpha-\alpha^{2})$.

###### Proof.

One can check that (37) guarantees the the feasibility of $\alpha$ in both
(38) and (39). Moreover, (38) implies

$2\gamma\alpha<2-\gamma+2\left(\gamma-1\right)\beta,$

which is equivalent to $K_{1}-K_{2}>0$. After some calculations, we see that
$K_{2}>0$ is equivalent to

$\gamma\alpha^{2}-\left(1+\left(\gamma-1\right)\beta\right)\alpha+\left(\gamma-1\right)\beta<0.$
(40)

Observe that for every $0<\gamma<1$ it holds

$\displaystyle\Delta_{1}$
$\displaystyle=\left(1+\left(\gamma-1\right)\beta\right)^{2}-4\gamma\left(\gamma-1\right)\beta$
$\displaystyle>\left(1+\left(\gamma-1\right)\beta\right)^{2}>0,$

Hence the inequality (40) holds for $\alpha>0$ if and only if

$0<\alpha<\dfrac{1+\left(\gamma-1\right)\beta+\sqrt{\Delta_{1}}}{2\gamma}.$

Furthermore, if $\alpha$ fulfills (38), then for $0<\gamma<1$

$\displaystyle 2\gamma\alpha$
$\displaystyle<2-\gamma+2\left(\gamma-1\right)\beta$
$\displaystyle<2+2\left(\gamma-1\right)\beta$
$\displaystyle<1+\left(\gamma-1\right)\beta+\left\lvert
1+\left(\gamma-1\right)\beta\right\rvert$
$\displaystyle<1+\left(\gamma-1\right)\beta+\sqrt{\Delta_{1}}.$

Therefore (38) implies $K_{1}>K_{2}>0$ for this case. The result for
$1<\gamma<2$ can be deduced similarly. ∎

######  Lemma .2.

Let $A$, $B$ and $C$ be positive real numbers. Then $A\geq\frac{C^{2}}{B+C}$
implies

$\displaystyle\frac{9}{4}A\geq 2C-B.$

###### Proof.

Rewriting the given assumption leads to

$\displaystyle\sqrt{(B+C)A}\geq C.$

We can apply the weighted arithmetic-geometric mean inequality
$\frac{2}{3}\alpha+\frac{3}{2}\beta\geq 2\sqrt{\alpha\beta}$ and get

$\displaystyle\frac{2}{3}(B+C)+\frac{3}{2}A\geq 2C.$

By rewriting this inequality and multiplying by $\frac{3}{2}$ we get the
conclusion. ∎