Proc. of the 13th Int. Conference on Digital Audio Effects (DAFx-10), Graz, Austria , September 6-10, 2010

FAST SIGNAL RECONSTRUCTION FROM MAGNITUDE STFT SPECTROGRAM
BASED ON SPECTROGRAM CONSISTENCY
Jonathan Le Roux1 , Hirokazu Kameoka1 , Nobutaka Ono2 and Shigeki Sagayama2
1

NTT Communication Science Laboratories, NTT Corporation,
3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan
2
Graduate School of Information Science and Technology, The University of Tokyo,
7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan{leroux,kameoka}@cs.brl.ntt.co.jp, {onono,sagayama}@hil.t.u-tokyo.ac.jp

ABSTRACTThe modification of magnitude spectrograms is at the core ofmany audio signal processing methods, from source separation tosound modification or noise canceling, and reconstructing a natural sounding signal in such situations is thus a very important issue.
This article presents recent theoretical and experimental developments on the application to signal reconstruction from a modified
magnitude spectrogram of the constraints that an array of complex
numbers must verify to be a consistent short-time Fourier transform (STFT) spectrogram, i.e., to be the STFT spectrogram of an
actual real-valued signal. We give here further theoretical insights,
present several potential variations on our previously introduced
algorithm, investigate various techniques to speed up the signal
reconstruction process, and present a thorough experimental comparison of the performance of all the considered algorithms.

complex numbers. We shall call consistent spectrograms the arrays for which such a signal exists.
This article is a follow-up to our previous paper on phase estimation from a magnitude spectrogram [3], which formulated the
problem of phase estimation as that of minimizing a numericalconsistency criterion and derived a fast optimization algorithm.
We give here further theoretical insights, present several potential variations on our previously introduced algorithm, make clear
the relation between our framework and Griffin and Lim’s iterative STFT algorithm [1], and perform a thorough experimental
evaluation of the performance of all the considered algorithms incomparison with the iterative STFT algorithm.
After briefly reviewing the concept of spectrogram consistency and the derivation of the numerical consistency criterion, we
present the proposed algorithms for fast phase estimation. Finally,
we investigate the performance of the proposed methods.

1. INTRODUCTION

2. CONSISTENT STFT SPECTROGRAMS

Short-time Fourier transform (STFT) is one of the most fundamental and ubiquitous tools in audio signal processing, and an extremely large amount of techniques developed for a wide range
of applications such as noise canceling, source separation, dereverberation or audio modification, are based on or involve the processing of the STFT spectrogram of a waveform. The main reasonsfor its success are that its computation is both fast and simple toimplement, and that it efficiently unveils the time-frequency structure of a signal under the assumption that it is short-term stationary, which is often a good approximation for natural sounds, suchas speech or music. Moreover, the STFT is both linear and invertible: an additive mixture of time-domain signals transforms to thecorresponding additive mixture of STFT spectrograms, and there
is a perfect equivalence between a time-domain signal and its complex STFT spectrogram, as the signal can be exactly reconstructed
through a weighted overlap-add procedure [1, 2].
A very important issue is however often overlooked: the STFT
spectrogram is a redundant representation, computed by concatenating Fourier transforms of overlapping short-time frames of thesignal, and any processing performed in the STFT domain should
thus take into account this redundancy. Concretely, starting froma “spectrogram-like” array of complex numbers in the complex
time-frequency domain, it is not guaranteed whether there exists
a signal in the time domain whose STFT is equal to that array of

2.1. Constraints in the time-frequency domain
We consider in this paper arrays of complex numbers (Hm,n ) ∈CM N , where m ∈ [[0, M − 1]] will correspond to the frame index and n ∈ [[0, N − 1]] to the frequency band index. We assume
that these arrays of complex numbers correspond to the (possibly modified) time-frequency representation of some time-domain
signals, obtained through the short-time Fourier transform (STFT)
with analysis window function w of length N and window shift R,
such that Q = N/R ∈ N. We assume that the inverse STFT, denoted by iSTFT, is performed through the overlap-add procedureusing a synthesis window s equal to∑w, followed by normalization
by an R-periodic function u(t) = q w2 (t + qR) (t denoting thetime index), and we note s̃ = s/u the normalized synthesis window. In this setting, a signal can be perfectly reconstructed fromits STFT spectrogram through the inverse STFT, and the inverse
STFT of a modified STFT spectrogram H leads to a reconstructedsignal whose spectrogram is closest to H in a least-squares sense,as shown by Griffin and Lim [1].
In the following, we will call “consistent spectrograms” the elements of CM N which can be obtained as the STFT spectrogramof a time-domain signal. As the STFT is a redundant representation, not all elements of CM N are consistent. We characterizehere consistency directly in the time-frequency domain. For an ar-

DAFX-1

Proc. of the 13th Int. Conference on Digital Audio Effects (DAFx-10), Graz, Austria , September 6-10, 2010

1.2

a

1
50% overlap
75% overlap

0.8
0.6
0.4 a
0

Figure 1: Illustration of the concept of spectrogram consistency.
ray H ∈ CM N to be a consistent spectrogram, it needs to be the
STFT spectrogram of a signal which by perfect reconstruction is
iSTFT(H). The set of consistent spectrograms can thus be described as the kernel (or null space) of the R-linear operator from
CM N to itself defined by
F(H) = G(H) − H,(1)

where G(H) = STFT(iSTFT(H)). This result is illustrated inFig. 1. We can obtain an explicit expression for F by writing down
the computations in the STFT and inverse STFT as
N −1
2

F(H)m,n =

∑

∑

Q−1

e

q
j2π Q
n

αq,p Hm−q,n−p ,(2)

q=−(Q−1)p=− N
2where frequency bin indices are considered modulo N and
αq,p =

k+qR
1 ∑w(k)s̃(k + qR)e−j2πp N − δp δq ,
N

(3)

5
10
Approximation order

15

Figure 2: Example of evolution of the approximated numericalconsistency criterion Il (H) w.r.t. the truncation order l.
constituted by the magnitude part only is, as the phase information
is discarded, not consistent. We show in Fig. 2, for both 50 % and
75 % overlap cases, the evolution of the approximated numericalconsistency
criterion Il w.r.t. the truncation order l, as the square√root Il (H)/I(H) of the ratio of Il (H) to the exact criterion
I(H). We used the sine window for the analysis and synthesis
windows. In both cases, the numerical criterion I(H) is roughly
equal to the total energy ||H||2 . Most of the contribution is alreadytaken into account for truncation orders larger than or equal to 2, inboth 50 % and 75 % overlap cases. For l = 2, the approximation
error is roughly equal to 0.12 % for both overlap cases, and it falls
below 0.1 % for larger l.
These results show more generally that the values ofF (H)m,n or G(H)m,n can be computed with very good accuracy
j2π q nas a sum over only a few terms of the form e Q αq,p Hm−q,n−pinstead of convolutions over all the bins involving FFTs. This is
the key point which will enable us to develop fast phase estimation
algorithms in the following.

k

3. APPLICATION TO PHASE ESTIMATION

where δi is the Kronecker delta.
2.2. Numerical consistency criterion
Instead of enforcing consistency through the “hard” constraints (1), as they may be too restrictive or hard to solve exactly,
we relax them by taking the L2 norm of F (H), defining a numerical criterion I(H) = ||F (H)||2 as follows:
I(H) =

∑
m,n

N −1
2

∑

∑

Q−1

q
j2π Q
n

e

2

αq,p Hm−q,n−p .

(4)

q=−(Q−1)
p=− N
2

Looking at the actual values of the coefficients αq,p involvedin the definition of F (H), we notice that most of the weight isactually concentrated near (0, 0). One can thus approximate theconsistency criterion by using only (2l+1)×(2Q−1) coefficients
instead of the total N × (2Q − 1), where l ≪ N/2:
Il (H) =

∑

Q−1

∑

m,n

q=−(Q−1)

e

q
n
j2π Q

∑

2

αq,p Hm−q,n−p .

(5)

|p|≤l

We investigate how good this approximation is on the example of the magnitude spectrogram of 20 s of speech by a malespeaker. Denoting by S the complex spectrogram of the utterance,
the array of complex (actually here all real) numbers H = |S|In the problem of phase estimation from a magnitude STFT spectrogram, we are given an array of real non-negative numbers Am,nwhich are supposedly the magnitude part of an STFT spectrogram, for example obtained through modifications of the magnitude spectrogram of a sound. The goal is to find the “most relevant” phase for A. We formulate here this problem as that ofestimating a phase ϕm,n to adjoin to A such that Am,n ejϕm,n is“as consistent as possible”. Based on the above derivation, theproblem amounts to minimizing the consistency criterion I w.r.t.
the phase ϕ, with the∑ magnitude A given, defining a new2objectivefunction Ĩ(ϕ) = m,n G(Aejϕ )m,n − Am,n ejϕm,n to minimize.
3.1. Griffin and Lim’s iterative STFT
In [1], Griffin and Lim formulated the problem as that of estimating a real-valued time-domain signal x such that the magnitudeof its STFT is closest to the magnitude spectrogram A in a leastsquares sense. To solve it, they proposed the iterative STFT algo(k)rithm, which consists in iteratively updating the phase ϕm,n at stepk by replacing it with the phase of the STFT of its inverse STFT,(k)∠G(Aejϕ ), while keeping A fixed.
We can actually interpret the iterative STFT as the application of the auxiliary function method [4] to the minimization of

DAFX-2

Proc. of the 13th Int. Conference on Digital Audio Effects (DAFx-10), Graz, Austria , September 6-10, 2010Ĩ. Indeed, G(H) can be shown [1] to be the closest consistent
spectrogram to H in a least-squares sense, i.e., ∀H,∑∑
2
2
G(H)m,n − Hm,n = minH̄m,n − Hm,n . (6)H̄∈Ker(F )m,n(p,q)̸=(0,0)
p∈[[− N
, N −1]]2 2m,nFrom the above relation, we can see that the functionĨ (ϕ, H̄) =+∑from the neighboring bins. More precisely, as we can easily seethat α0,0 = 1/Q − 1 < 0, the update for bin (m, n) is()∑
j2π q nϕm,n ← ∠e Q αq,p Hm−q,n−p .
(10)H̄m,n − Am,n e

jϕm,n

2

,

(7)

m,n

is an auxiliary function for Ĩ with auxiliary variable H̄ ∈ Ker(F ).
Alternate minimizations of Ĩ + w.r.t. ϕ and H̄ lead to an iterative
optimization scheme for Ĩ(ϕ) which is none other than Griffin andLim’s update,ϕ ← ∠G(Aejϕ ).
(8)
We can also show through this method that Ĩ(ϕ) still decreases
when updating a few bins only before recomputing G(Aejϕ ).
3.2. Fast minimization of Ĩ
The iterative STFT algorithm is based on the computation of
STFTs and inverse STFTs, and is thus quite costly. This way ofcomputing G(Aejϕ ) is the bottleneck of the algorithm, and wewould like to replace it by a light computation for each bin directlyin the time-frequency domain. Using explicit summations of theform of Eq. (2) to replace the FFT-based updates would only raise
the computational cost, but we saw in 2.2 that very good approximations involving only a few terms could be derived. We shallnow explain in more details the approximations we consider andthe many advantages that can be drawn from them.
3.2.1. Approximate optimizations
As mentioned in 2.2, thanks to the concentration of the coefficients αq,p near (0, 0), we can approximate the computation of
F (Aejϕ )m,n by using only (2l + 1) × (2Q − 1) central coefficients. This approximation enables us to compute directly the
update of each bin through the summation of a few terms. Let
H = Aejϕ . As G(H) = H + F (H), the update (8) becomes()∑ j2π q nϕm,n ← ∠ Hm,n +e Q αq,p Hm−q,n−p , (9)
p,q
|p|≤l

which we will refer to as the “Truncated Update”, as it relies on
the truncation of the sum involved in the original iterative STFT
update. For l = 2 and a 50 % overlap, for example, we only
consider 5 × 3 coefficients.
We also investigate another kind of approximation. Noticingthat α0,0 dominates over the other coefficients, we can attempt toneglect the influence of ϕm,n in all the terms F (H)m′ ,n′ otherthan F(H)m,n , which is the one where it is multiplied by α0,0 .
We could thus consider, for the update of a bin Hm,n , looking at
the minimization of |F (H)m,n | only instead of the whole |I(H)|.
From Eq. (2), |F(H)m,n | is minimized w.r.t. Hm,n with the otherterms fixed when α0,0 Hm,n is equal to the opposite of the sumof the terms coming from the neighboring bins. As we want here
to keep Am,n fixed, the phase ϕm,n should be updated such that
α0,0 Am,n ejϕm,n is in opposite direction with the terms coming

Further combining this with the truncation introduced above, we
obtain the following update:( ∑)j2π q nϕm,n ← ∠e Q αq,p Hm−q,n−p .
(11)(p,q)̸=(0,0)|p|≤l

We will refer to these updates as the “Modified Update” and the“Truncated Modified Update”, respectively. Although the way inwhich these modified updates have been obtained may look rather
exotic, they can actually be linked to the original iterative STFT
update (8). Indeed, in concise form, the update (10) can also be
written, using the operator G,
)
(
1
(12)
ϕm,n ← ∠ G(H)m,n − Hm,n ,Q
1
Hm,n . Unwhich is very close to (8), up to the extra term − Q

fortunately, Ĩ is not in general non-increasing under the modified
update. However, we noticed experimentally that the truncatedmodified update leads to a very efficient minimization procedure
for Ĩ when the newly updated values for each bin are used in thesubsequent updates of the other bins.
3.2.2. Taking advantage of sparsenessThe auxiliary function interpretation of the iterative STFT showsthat we can update only a few bins, even only one, before recomputing G(Aejϕ ). Thanks to the low-cost updates derived above,
we can efficiently exploit this property by selecting which bins to
update. The idea here is to exploit the sparseness of the acoustic
signal in the time-frequency domain to limit the updates to bins
with a significant magnitude, as those with relatively small magnitude arguably contribute less to the objective function and are lesslikely to give disturbing perceptual artifacts. We progressively decrease the magnitude threshold above which the bins are updated,starting with the most significant bins and refining afterwards. Obviously, the speed at which this threshold is decreased at each iteration is likely to have a strong impact on performance: at a given
iteration, if a very large threshold is used, only a few bins will be
updated, leading to a very short computation time for this iteration
on one hand, but also limiting the improvement which can be expected from that iteration; if on the contrary a very low threshold isused, most bins will be updated, leading to a significant improvement in the objective function but at the cost of a longer computation time. We experimentally evaluate in 4.3 several types ofdecreasing contours for the threshold as a function of the iteration
number.
We note that further improvement could be obtained by sorting
the bins by decreasing magnitude order beforehand and updatingthem from the largest to the smallest, stopping when the threshold is reached: we could then avoid comparison tests for each bin
by precomputing where to stop for each step’s threshold by going
through the ordered magnitude list once only. We shall however
leave such refinements for future developments.

DAFX-3

Proc. of the 13th Int. Conference on Digital Audio Effects (DAFx-10), Graz, Austria , September 6-10, 2010c

3.2.3. Reducing computational cost using symmetries
We easily notice that αq,−p = αq,p and α−q,p = αq,p . Basedon these symmetries and on the fact that, for complex numbers
a, b and c, the computation of the quantity ab + ac can be performed using only four real-number multiplications instead of theeight real-number multiplications required in general for the sumof two products of two complex numbers, we can reduce the number of multiplications involved in the computation of the truncatedupdates (9) and (11) by a factor 4.
3.2.4. Update schemesAs, in the truncated updates, the bins are updated one by one
through independent low-cost computations, we can use at once
the newly updated values for the computation of the subsequent
updates of the other bins. We shall call this update scheme “onthe-fly” update, and the usual scheme where updates are computed
using only values of the previous step as “stepwise” update. We
expect the on-the-fly updates to lead to faster convergence, as the
new values are re-used straight away, and incoherences between
neighboring bins are thus likely to be smoothed more efficiently.
Another benefit of the on-the-fly scheme is that updates are performed “in place”, reducing the computation cost and the required
memory space.
4. EXPERIMENTAL EVALUATION
We investigate the performances of the various proposed methods and compare them with that of Griffin and Lim’s algorithm
in terms of the decrease of a normalized inconsistency measureI(H)defined as C(H) = 10 log10 ∥H∥
2 (i.e., the objective function
I(H) represented in decibels with the total energy of the original spectrogram as a reference) w.r.t. the number of iterations aswell as w.r.t. the computation time. The task we consider is thatof the estimation of the most consistent phase for a given magnitude spectrogram for the purpose of time-scale modification. All
methods were implemented in C on a PC with 3.16 GHz CPU running Linux. We used 100 speech utterances (both male and female
speakers, taken from Bagshaw’s database [5], totaling 5 min and32 s) and 8 excerpts of music pieces (piano and guitar solos fromthe RWC music database [6], totaling 3 min and 04 s) as the data.
The sampling rate was 16 kHz. The sine window was used as analysis and synthesis window. The time-scaled spectrograms are built
through a sliding-block analysis technique described in [3].
4.1. General performance comparison
In a first experiment, we compare the behaviors of the various
methods under several time-scale modification and analysis conditions. The time-scale modification factors f used were 0.7 (slowdown by 30 %), 1 (no time-scale modification), and 1.3 (pace up
by 30 %). We used a frame length of 1024 samples for all theexperiments, and two different settings for the frame shift, namely
512 (50 % overlap) and 256 (75 % overlap). We use the magnitudeof the time-scaled spectrograms as the initial point for all the methods, i.e., we set the initial phase to zero. All methods are stopped
after 200 iterations. Only the time required by the phase estimation part of the algorithm is reported as other parts are identical.

The sparseness threshold at iteration k is set to ae−bk E, where E
denotes the mean magnitude of the given magnitude spectrogramand is introduced for the purpose of normalization. The parameters
were set to a = 100, b = 0.1 and c = 1 based on a preliminary
experiment on one music piece.
Figure 3 shows the evolution of the normalized inconsistency
measure C w.r.t. the number of iteration (left) and the computation time (right) on the speech data. We can see first in generalthat the On-the-fly Truncated Modified update (11) (solid blackline) constantly outperforms all other methods, and in particular
the iterative STFT (8) (solid gray line), in terms of decrease of inconsistency w.r.t. the computation time, and w.r.t. the number of iterations as well in the no sparseness threshold case. However, theModified update (10) (dotted gray line) and Stepwise Truncated
Modified update (dash-dot black line) do not lead to a significant
decrease in the 50 % overlap case: it seems that the influence of1
H is harmful when not used in on-the-fly upthe extra term − Q
1dates. In the 75 % overlap case, the Q
factor decreases and these
two methods lead to very good results as well. The On-the-fly andStepwise Truncated versions (9) of the iterative STFT algorithm(dotted black line and dashed gray line) perform similarly to theiterative STFT, but seem to lead to better performance in termsof computational time when a sparseness threshold is introduced,
as can be seen in Figs. 3 (d) and (e). Results on the music data
showed similar trends.
Several other remarks can be made on these results. We cansee by comparing Figs. 3 (a) and (b) that the typical values of C differ between 50 % and 75 % overlap, the decrease reached for 75 %overlap being smaller than for 50 % overlap, and they should not
be directly compared numerically. It turns out that, from our experience based on informal listening experiments, a −17 dB measurewith 75 % overlap for example actually tends to sound better than
−22 dB with 50 % overlap. From Figs. 3 (b) and (c), obtained withdifferent f , we can see the influence of the modification factor on
the values reached: lower C values are usually obtained for themagnitude spectrogram without time-scale modification (f = 1)
than for those with modification (f = 0.7 and f = 1.3). Thiscan be connected to the fact that for f = 1 there actually exists
a solution to the phase estimation problem, for which C is equalto −∞, while there may be no exact solution in general for modified magnitude spectrograms. This tendency is especially true for
75 % overlap, where the constraints are stronger. The influenceof the introduction of a sparseness threshold can be seen by comparing Figs. 3 (a) and (d), in which the parameters differ only by
the value of a. As only a small part of the time-frequency bins
are updated in the first few iterations, the decrease of C w.r.t. thenumber of iterations is much slower when a sparseness thresholdis used. However, each iteration being much faster, overall the performance is much better w.r.t. the computation time than when allbins are updated at each iteration. Looking now at Fig. 3 (e), we
see that raising the truncation order to l = 5 seems to lead to aslightly better final value, generally for a similar computation timeor only slightly longer than for l = 2. Each iteration is slightly
slower, but larger improvements compensate for this extra computational time per iteration. This is especially true when combinedwith the use of a sparseness threshold for bin selection.
We show in Table 1 and Table 2 the computation time requiredby the iterative STFT and the proposed On-the-fly Truncated Mod-DAFX-4

Proc. of the 13th Int. Conference on Digital Audio Effects (DAFx-10), Graz, Austria , September 6-10, 20100On−the−fly Trunc. Modif.
Stepwise Trunc. Modif.
On−the−fly Trunc.
Stepwise Trunc.
Original (iterative STFT)
Modified

−10
−15
−20

Inconsistency (dB)

Inconsistency (dB)

0
−5

−25
−30

On−the−fly Trunc. Modif.
Stepwise Trunc. Modif.
On−the−fly Trunc.
Stepwise Trunc.
Original (iterative STFT)
Modified

−5
−10
−15
−20
−25
−30

0

50

100

150

200

0

5

Nb. of iterations

10

15

Time (s)(a) 50 % overlap, f = 0.7, l = 2, a = 0.
0Inconsistency (dB)

Inconsistency (dB)0On−the−fly Trunc. Modif.

−5

Stepwise Trunc. Modif.

−10On−the−fly Trunc.
Stepwise Trunc.
Original (iterative STFT)
Modified

−15
−20
−25
−30

On−the−fly Trunc. Modif.

−5

Stepwise Trunc. Modif.
On−the−fly Trunc.
Stepwise Trunc.
Original (iterative STFT)

−10
−15
−20

Modified

−25
−30

0

50

100

150

200

0

5

10

Nb. of iterations

15

20

25

30

Time (s)(b) 75 % overlap, f = 0.7, l = 2, a = 0.
0On−the−fly Trunc. Modif.
Stepwise Trunc. Modif.
On−the−fly Trunc.
Stepwise Trunc.
Original (iterative STFT)
Modified

−5
−10
−15
−20

Inconsistency (dB)

Inconsistency (dB)

0

−25
−30

On−the−fly Trunc. Modif.
Stepwise Trunc. Modif.
On−the−fly Trunc.
Stepwise Trunc.
Original (iterative STFT)
Modified

−5
−10
−15
−20
−25
−30

0

50

100

150

200

0

5

10

Nb. of iterations

15

20

Time (s)(c) 75 % overlap, f = 1, l = 2, a = 0.
0On−the−fly Trunc. Modif.
Stepwise Trunc. Modif.
On−the−fly Trunc.
Stepwise Trunc.
Original (iterative STFT)
Modified

−5
−10
−15
−20

Inconsistency (dB)

Inconsistency (dB)

0

−25
−30

On−the−fly Trunc. Modif.
Stepwise Trunc. Modif.
On−the−fly Trunc.
Stepwise Trunc.
Original (iterative STFT)
Modified

−5
−10
−15
−20
−25
−30

0

50

100

150

200

0

5

Nb. of iterations

10

15

Time (s)(d) 50 % overlap, f = 0.7, l = 2, a = 100.
0On−the−fly Trunc. Modif.
Stepwise Trunc. Modif.
On−the−fly Trunc.
Stepwise Trunc.
Original (iterative STFT)
Modified

−5
−10
−15
−20

Inconsistency (dB)

Inconsistency (dB)

0

−25
−30

On−the−fly Trunc. Modif.
Stepwise Trunc. Modif.
On−the−fly Trunc.
Stepwise Trunc.
Original (iterative STFT)
Modified

−5
−10
−15
−20
−25
−30

0

50

100

150

200

0

Nb. of iterations

5

10

15

Time (s)(e) 50 % overlap, f = 0.7, l = 5, a = 100.

Figure 3: Evolution of the inconsistency measure C w.r.t. the number of iterations (left) and the computation time (right) on the speech data.
ified update (11) to reach a given level of decrease in C, for 50 %overlap and 75 % overlap respectively. The results are averaged
on the speech and music data, for f = 0.7, and the average output
signal length is 41 s. We notice again the very important reduction
in computation time brought first by using truncated computations

for G(H) and second by the bin selection scheme: for example,
compared with the iterative STFT, the average computation timerequired to reach −21 dB for 50 % overlap is divided by a factor 3
in the proposed method with a = 0 and l = 5, and by a factor 60
with a = 100.

DAFX-5

Proc. of the 13th Int. Conference on Digital Audio Effects (DAFx-10), Graz, Austria , September 6-10, 2010

Table 2: Computation time (s) required to reach a given decrease
of C (75 % overlap, f = 0.7).
Time to reach-16 dB -17 dB -17.5 dB
Iterative STFT
7.75 s
14.41 s20.84 sProp., a = 0, l = 2
1.22 s3.42 s
6.63 sProp., a = 0, l = 5
1.56 s4.05 s7.16 sProp., a = 100, l = 2
0.49 s1.76 s9.84 s0.52 s1.10 s
4.84 sProp., a = 100, l = 5

4.2. Divergence from equilibrium
Consistent spectrograms are invariant by G, and are thus stability
points for the iterative STFT algorithm. We investigate here the influence of the truncations on this stability property. The methods
we proposed are expected not to be stable anymore and to diverge
from the initial consistent spectrogram, but hopefully they should
not diverge too much. We performed experiments with both truncated methods (modified or not). We tested both stepwise and onthe-fly updates for the unmodified method, while we dropped the
stepwise update for the modified method as we saw in the previous experiment that it did not lead to an effective algorithm. Notethat the consistent spectrograms are invariant through the iterative
STFT (8) and the modified update (10), which are thus not relevant for the current experiment. We used the unmodified complex
STFT spectrogram of each piece of data as initial point, the frame
overlap being set to 50 %. The evolution of the measure of inconsistency C averaged on the music data for the three methods
considered is shown in Fig. 4. Similar results were obtained on the
speech data. We can see that all the methods slightly diverge fromthe initial point, although the measure C stays lower than −30 dB.
This is typically lower than the results we obtained in the previous section starting from a magnitude spectrogram with any of themethods, truncated or not, and the divergence can be considered
moderate. This result also gives an estimate of the maximum decrease which can be expected from the truncated methods.
4.3. Sparseness threshold experiments
We investigate here the influence of the way the sparsenessthreshold decreases on the performance of the on-the-fly truncated modified update (11). As a general setting, we consider a time-scale modification factor of 0.7 and 50 % overlap, and the truncation order is set to l = 2. We investigate several settings for the decrease of the sparseness threshold introduced in 4.1. At iteration k, only bins whose magc
nitude is larger than ae−bk E are updated. Depending on thevalues of a, b and c, at each step a certain subset of the timefrequency bins only is updated, and this subset grows at each it-−30
Inconsistency (dB)

Table 1: Computation time (s) required to reach a given decrease
of C (50 % overlap, f = 0.7).
Time to reach-15 dB -18 dB -21 dB
Iterative STFT
0.81 s2.36 s10.01 sProp., a = 0, l = 2
0.09 s0.43 s3.52 sProp., a = 0, l = 5
0.11 s0.37 s3.32 sProp., a = 100, l = 2
0.06 s
0.09 s0.18 sProp., a = 100, l = 50.06 s0.08 s0.16 s−32
On−the−fly Trunc. Modif.
On−the−fly Trunc.
Stepwise Trunc.

−34
−36
−38
1

50

100
Nb. of iterations

150

200

Figure 4: Divergence of the truncated methods starting from a consistent spectrogram.
eration. The values we investigated were a ∈ {1, 10, 50, 100},b ∈ {0.0001, 0.0005, 0.001, 0.005, 0.01, 0.05, 0.1, 0.5} and c ∈{1, 2}, corresponding to linear and quadratic decreases with various slopes and starting points in the decibel domain.
We show in Fig. 5 a few examples of results for various sparseness threshold decrease settings on the speech data (results on music data showed similar behaviors), as the evolution of C w.r.t. thenumber of iterations (left) and the computation time (right). We
also show for comparison on each plot the results obtained by the
proposed truncated modified update without sparseness threshold(a = 0) as a dark continuous line, and by the iterative STFT (G.L.) as a gray continuous line. The top and middle plots both correspond to c = 1, and differ by the initial value aE used, witha = 1 for the top plots and a = 50 for the middle ones. The
results for a = 10 and a = 100 are omitted as they are similar to those for a = 50. In the bottom plots, the decrease in
the log-domain is quadratic (c = 2), and the initial value is set
to aE = 10E (10 times the average magnitude). Results fora ∈ {1, 50, 100} are omitted as they show only limited variation to those for a = 10. Note that the meaning of the plot
styles varies with the plots: we omitted for clarity the results forb ∈ {0.0001, 0.0005, 0.001} in the plots for c = 1 as the threshold decreases too slowly to lead to a significant decrease in 200
iterations, and the results for b ∈ {0.01, 0.1} as they showed intermediate behaviors to the plots displayed. Similarly, we omitted
the results for b ∈ {0.05, 0.1, 0.5} in the plots for c = 2 as thethreshold decreases so fast that the results are very close to the nothreshold (a = 0) curve, and the results for b ∈ {0.0005, 0.005}
as they showed intermediate behaviors to the plots displayed.
The experiments performed here show that a very good tradeoff between updating enough bins so as to make the inconsistency
measure decrease and skipping enough bins to make the computation faster can be obtained, leading to very important reductionsin the computation time required to reach a given decrease of theinconsistency measure C. Even if the number of iterations necessary to reach a given decrease of the inconsistency measure may
be larger with sparseness thresholds than for the iterative STFT
or the proposed method without sparseness threshold, as can for
example be seen in the left part of Fig. 5 (b) for b = 0.005 or
Fig. 5 (c) for b = 0.0001, the shorter time taken by each iteration
when only updating a fraction of the time-frequency bins leads toa faster decrease in terms of computation time, as can be seen in
the right part of Figs. 5 (b) and (c). Furthermore, we can see thatseveral settings of a, b and c lead to similar computation times.
The performance of the algorithm is thus expected to be robust to
the choice of threshold parameters within a wide range of values.

DAFX-6

Proc. of the 13th Int. Conference on Digital Audio Effects (DAFx-10), Graz, Austria , September 6-10, 20100
b=0.005b=0.05
b=0.5
a=0
G.−L.

−10
−15

Inconsistency (dB)

Inconsistency (dB)

0
−5

−20
−25
−30

0

50

100

150

b=0.005b=0.05
b=0.5
a=0
G.−L.

−5
−10
−15
−20
−25
−30

200

0

5

10

15

Time (s)Nb. of iterations(a) a = 1, c = 10
b=0.005b=0.05
b=0.5
a=0
G.−L.

−5
−10
−15

Inconsistency (dB)

Inconsistency (dB)

0

−20
−25
−30

0

50

100

150

b=0.005b=0.05
b=0.5
a=0
G.−L.

−5
−10
−15
−20
−25
−30

200

0

5

10

15

Time (s)Nb. of iterations(b) a = 50, c = 10
b=0.0001b=0.001b=0.01
a=0
G.−L.

−5
−10
−15

Inconsistency (dB)

Inconsistency (dB)

0

−20
−25
−30

0

50

100

150

b=0.0001b=0.001b=0.01
a=0
G.−L.

−5
−10
−15
−20
−25
−30

200

0

5

10

15

Time (s)Nb. of iterations(c) a = 10, c = 2

Figure 5: Evolution of the inconsistency measure C w.r.t. the number of iterations (left) and the computation time (right) on the speech datafor various sparseness threshold decrease settings.

5. CONCLUSION

constraints for STFT spectrograms and their application tophase reconstruction,” in Proc. SAPA, Sep. 2008.

We introduced a general framework to assess for the consistency ofcomplex STFT spectrograms, studied the relationship between ourframework and Griffin and Lim’s iterative STFT algorithm, anddeveloped a fast phase estimation algorithm which can take advantage of the sparseness of the input signal in the time-frequency
domain. We performed a thorough experimental evaluation showing that, to reach the same level of quality in the estimation of thephase from a given magnitude spectrogram, our method required
much less computation time. Future work will investigate the introduction of consistency concepts in various signal processing algorithms and the use of techniques similar to those introduced here
to reduce computational cost.

[4] D. D. Lee and H. S. Seung, “Algorithms for non-negative matrix factorization,” in Proc. NIPS*2000, 2001, pp. 556–562.
[5] P. C. Bagshaw, S. M. Hiller, and M. A. Jack, “Enhanced
pitch tracking and the processing of F0 contours for computerand intonation teaching,” in Proc. Eurospeech, Sep. 1993, pp.
1003–1006.
[6] M. Goto, “Development of the RWC Music Database,” inProc. ICA 2004, vol. I, 2004, pp. 553–556.

6. REFERENCES[1] D. W. Griffin and J. S. Lim, “Signal estimation from modified short-time Fourier transform,” IEEE Trans. ASSP, vol. 32,
no. 2, pp. 236–243, Apr. 1984.
[2] B. Yang, “A study of inverse short-time Fourier transform,” inProc. ICASSP, Apr. 2008, pp. 3541–3544.
[3] J. Le Roux, N. Ono, and S. Sagayama, “Explicit consistency

DAFX-7