Signal Reconstruction from Spectrogram

1. Signal Reconstruction from its Spectrogram Radu Balan IMAHA 2010, Northern Illinois University, April 24, 2010

2. 2/23 Overview 1. Problem formulation 2. Reconstruction from absolute value of frame coefficients 3. Our approach Embedding into the Hilbert-Schmidt space Discrete Gabor multipliers Quadratic reconstruction 4. Numerical example

3. 3/23 1. Problem formulation Typical signal processing pipeline: Analysis Processing Synthesis In Out Features: Relative low complexity O(Nlog(N)) On-line version if possible

4. 4/23 < ,g i > x Analysis Synthesis c y The Analysis/Synthesis Components: Example: Short-Time Fourier Transform

5. 5/23 * = fft fft = * Data frame index (k) f c k,0 c k,F-1 c k+1,F-1 c k+1,0 g(t) x(t+kb:t+kb+M-1) x(t+kb+M:t+kb+2M-1) x(t+kb)g(t) x(t+(k+1)b)g(t)

6. 6/23 * = ifft ifft = * (t) c k,0 c k,F-1 c k+1,F-1 c k+1,0 +

7. 7/23 Problem : Given the Short-Time Fourier Amplitudes (STFA): we want an efficient reconstruction algorithm: Reduced computational complexity On-line (on-the-fly) processing |.| Reconstruction c k,f d k,f x

8. 8/23 Where is this problem important: Speech enhancement Speech separation Old recording processing

9. 9/23 Setup: H=E n , where E= R or E= C F={f 1 ,f 2 ,...,f m } a spanning set of m>n vectors Consider the map: Problem 1 : When is N injective? Problem 2 : Assume N is injective, Given c=N(x) construct a vector y equivalent to x (that is, invert N up to a constant phase factor) 2. Reconstruction from absolute value of frame coefficients

10. 10/23 Theorem [R.B.,Casazza, Edidin, ACHA(2006)] For E = R : if m 2n-1 , and a generic frame set F, then N is injective; if m 2n-2 then for any set F, N cannot be injective; N is injective iff for any subset J F either J or F\J spans R n . if any n-element subset of F is linearly independent, then N is injective; for m=2n-1 this is a necessary and sufficient condition.

11. 11/23 Theorem [R.B.,Casazza, Edidin, ACHA(2006)] For E = C : if m 4n-2 , and a generic frame set F, then N is injective. if m 2n and a generic frame set F, then the set of points in C n where N fails to be injective is thin (its complement has dense interior).

12. 12/23 3. Our approach First observation : Hilbert-Schmidt Signal space: l 2 ( Z ) x K x K nonlinear embedding K g k,f E=span{K g k,f } Hilbert-Schmidt: HS(l 2 ( Z )) Recall:

13. 13/23 Assume {K g k,f } form a frame for its span, E. Then the projection P E can be written as : where {Q k,f } is the canonical dual of {K g k,f } . Frame operator

14. 14/23 Second observation : since: it follows:

15. 15/23 However: Explicitely:

16. 16/23 Short digression: Gabor Multipliers Goes back to Weyl, Klauder, Daubechies More recently: Feichtinger (2000), Benedetto- Pfander (2006), D rfler-Toressani (2008) Theorem [F00] Assume {g , Lattice} is a frame for L 2 ( R ) . Then the following are equivalent: 1. {<.,g >g , Lattice} is a frame for its span, in HS(L 2 ( R )) ; 2. {<.,g >g , Lattice} is a Riesz basis for its span, in HS(L2( R )) ; 3. The function H does not vanish,

17. 17/23 Return to our setting. Let Theorem Assume {g k,f } (k,f) ZxZ F is a frame for l 2 ( Z ) . Then 1. is a frame for its span in HS(l 2 ( Z )) iff for each m Z F , H( ,m) either vanishes identically in , or it is never zero; 2. is a Riesz basis for its span in HS(l 2 ( Z )) iff for each m Z F and , H( ,m) is never zero.

18. 18/23 Third observation . Under the following settings: For translation step b=1; For window support supp(g)={0,1,2,...,L-1} For F 2L The span of is the set of 2L-1 diagonal band matrices.

19. 19/23 The reproducing condition (i.e. of the projection onto E) implies that Q must satisfy: By working out this condition we obtain :

20. 20/23 The fourth observation : We are able now to reconstruct up to L-1 diagonals of K x . This means we can estimate Assuming we already estimated x s for s

21. 21/23 Reconstruction Scheme Putting all blocks together we get: I F F T |c k,0 | 2 |c k,F-1 | 2 W 0 W L-1 Least Square Solver Stage 1 Stage 2

22. 22/23 3. Numerical Example

23. 23/23 Conclusions All is well but ... For nice analysis windows (Hamming, Hanning, gaussian) the set {K g k,f } DOES NOT form a frame for its span! The lower frame bound is 0. This is the (main) reason for the observed numerical instability! Solution: Regularization.