On Homotopy Continuation for Speech Restoration

On Homotopy Continuation for Speech Restoration Darian M. Onchis1(B)and Pedro Real2 1Faculty of Mathematics, University of Vienna, Vienna, Austria [email protected] 2Department of Applied Mathematics I, University of Seville, Seville, Spain [email protected] Abstract. In this paper, a homotopy-based method is employed for the recovery of speech recordings from missing or corrupted samples taken in a noisy environment. The model for the acquisition device is a compressed sensing scenario using Gabor frames. To recover an approximation of the speech file, we used the basis pursuit denoising method with the homotopy continuation algorithm. We tested the proposed method with various speech recordings. Keywords: Homotopy continuation ·Speech restoration ·Basis pursuit ·1regularization ·Gabor frames ·Numerical algorithm 1 Introduction The reconstruction of an audio signal with missing sampled or clipped, is a classical problem in signal processing and it was largely discussed in the specialized scientific literature, see [1–3]. In this paper, we report the experiments performed with a method inspired from computational topology, namely the homotopy continuation method in order to enhance the typical recovery of audio speech recordings based on 1− minimization, [4–6]. To precisely formulate the problem, we consider the following non parametric model with observations: y=Θs +e∈RP where s∈RNis the speech signal to recover, e∈RPis a noise vector, and Θ∈RP×Nmodels the acquisition device. This device is nowadays equipped with the additional assumption of sparsity, which refers to the circumstance that many natural signals can be expanded (using a suited dictionary Θ) with only few non zero coefficients. We assume a compressed sensing scenario where the operator Θcould be the realization of a random Gaussian, Bernoulli, or partial Fourier matrix satisfying the restricted isometry property (RIP) [7]. But given the special characteristics of nature signals as the speech recordings, which usually consist of sets of distinct components as transients and harmonics with orientation in time and frequency, we have used for the proposed method a Gabor frame generated by the Alltop sequences as proposed in [8,9]. c Springer International Publishing Switzerland 2016 A. Bac and J.-L. Mari (Eds.): CTIC 2016, LNCS 9667, pp. 152–156, 2016. DOI: 10.1007/978-3-319-39441-1 14 On Homotopy Continuation for Speech Restoration 153 2 Gabor Frames and the 1 −minimization Frames (gi)i∈Igeneralize the idea of a basis in a Hilbert space Hand consist of the indexed families such that the so-called frame operator S Sf = i∈I f,gigi(1) is invertible. The main tool for time-frequency analysis is the Short-Time Fourier Transform, defined for functions f,g ∈L2(Rd)atλ=(α, β)∈R2dby Vgf(λ)=Vgf(α, β)=f,MβTαg=f,π(λ)g(2) where Tαf(t)=f(t−α) is the translation (time shift) and Mβf(t)=e2πiβ·tf(t) is the modulation (frequency shift). The operators π(λ):=MβTαare called timefrequency shifts and the set Λ={λ;λ=(α, β)∈Rd× Rd}is a lattice, [11]. The Gabor system G(g,Λ)={π(λ)g;λ∈Λ}over the lattice Λconsisting of the translated and modulated versions of one atom g, is a frame for the space L2(Rd), if and only if there exist 0 <A≤B<∞(frame bounds) with A||f||2≤ λ∈Λ |f,π(λ)g|2≤B||f||2for everyf∈L2(Rd),(3) We will use in the construction of Gabor frames the Alltop sequences as proposed in [8]. To recover an approximation of the signal s, a standard method is the basis pursuit denoising or 1-minimization [10]. This method is based on using the 1 norm as a sparsity enforcing penalty. That turns into an optimization problem and allows us to recover the signal minimizing the expression: sρ∈argmins∈RN 1 2y−Θs2+ρs1(4) where the 1norm is defined as s1=i|si|. The parameter ρshould be set in accordance to the noise level e. In the case where there is no noise, e=0,weletλ→0+and solve the basis pursuit constrained optimization s0+∈argminΘs=ys1. In order to avoid technical difficulties, we could further assume that Θis such that sρis uniquely defined. In the following, for some index set I⊂{1,...,N}, we denote by ΘI=(θi)i∈I∈RP×|I| the sub-matrix obtained by extracting the columns θi∈RPof Θindexed by I. The support of a vector is supp(x)={i∈{1,...,N}:xi=0}. Using results from the convex analysis, we obtain that sρis a solution of (4) if and only if (C1) Θ∗ I(y−ΘIsρ,I )=ρsign(sρ,I ), (C2) Θ∗ J(y−ΘIsρ,I )∞≤ρ where I=supp(sρ)andJ=Icis the complementary. 154 D.M. Onchis and P. Real 3 The Homotopy-Continuation Algorithm and Experiments Topology helps to understand the different degrees of connectivity a geometric object has. To deal with topological isomorphisms or homeomorphisms between continuous geometric objects is a hard task and discretization strategies, such as triangulations, are employed for reducing the computational complexity of the topological interrogation. While homology considers the notion of hole in linear algebra terms, the homotopy is dealing with the same issues in a purely combinatorial terms. Therefore, homotopy computation is much more harder in general than homology computation, but in combination with numerical methods it can be proven to be a useful tool for signal recovery but also in image recognition. The proposed homotopy-based method for speech recovery is gradually deforming a trivial initialization of the speech vector into the original speech vector through the process of path-tracking. The numerical homotopy procedure is based on the fact that the objective function undergoes a homotopy from the 2to the 1optimization as the algorithm progresses. The homotopy algorithm proceeds by computing iteratively the value sρ. We sum below the complete algorithm: Homotopy-speech restoration algorithm Input: y-noisy speech file , Θ-Gabor frame compressed sensing operator , Initialization: Corr =Θ∗y,ρ=max(Corr),sρ=0, Isparsity =supp(sρ) Output: sρ-restored speech file, ρ, Isparsity Begin iteration Compute the correlations Corr =Θ∗(y−Θ∗sρ); Update direction dir =Θ∗Θsign(Corr); Compute Jthe complementary support of Isparsity Compute minimum αfor condition (C1) and (C2) Update solution sρ=sρ+α∗dir;ρ=ρ−α;Isparsity =supp(sρ). End Iteration (1 −minimization with homotopy deformation) For the numerical experiments, we have used 5 speech data sof2to5s, recorded by a microphone and sampled at 16 kHz. All signals were normalized, and after that the following noise level σ=0.05 ∗norm(Θ∗s)/sqrt(P)was applied. We used P=round(N/4) where N=size(s). The distorted measurements where defined by the expression y=Θ∗s+σ∗randn(P,1) as in [5]. These measurements were the input for our algorithm. In Fig. 1, we displayed 6 iterations of the algorithm to visualize the homotopic progression towards the correct restoration. For clarity reasons, only the first 2000 samples of the speech signal are shown. On Homotopy Continuation for Speech Restoration 155 Fig. 1. First 6 iterations of the homotopy algorithm (orginal in red, recovered in blue) (Color figure online) Even though the application of the algorithm provides a complete recovery of the original speech recording, a drawback is the large number of iterations. In our experiments, we managed to recover the 5 speech data, with a number of iterations proportional with almost half the size of the signal, depending on the distortion applied. In comparison with other 1−minimization methods like the iterative shrinkage-thresholding, proximal gradient or augmented Lagrange multiplier, the homotopy achieves the best accuracy, even though, as mentioned before, in terms of speed, the homotopy takes longer time to converge when the distortion is high. But since speech recognition is usually a sensitive issue, the accuracy degree of the reconstruction made us confident in the utility of the proposed algorithm. 4 Conclusions In this report, we presented the results of speech restoration using the basis pursuit algorithm in a sparse Gabor frames scenario, enhanced with a topologyinspired procedure entitled the homotopy-continuation method. The method allows a complete recovery of a speech recording with missing samples or clipped but with a high computational cost given by a large number of iteration necessary. Further parallelization of the algorithm are considered by the authors. Acknowledgments. The first author gratefully acknowledge the support of the Austrian Science Fund (FWF): project number P27516. 156 D.M. Onchis and P. Real References 1. Abel, J.S., Smith III., J.O.: Restoring a clipped signal. In: Proceedings of the International Conference on Acoustics, Speech, and Signal Processing. IEEE, pp. 1745–1748 (1991) 2. Godsill, S.J., Rayner, P.J.: A Bayesian approach to the restoration of degraded audio signals. IEEE Trans. Speech Audio Process. 3(4), 267–278 (1995) 3. Adler, A., Emiya, V., Jafari, M., Elad, M., Gribonval, R., Plumbley, M.D.: Audio inpainting. IEEE Trans. Audio Speech Lang. Process. 20(3), 922–932 (2012) 4. Emmanuel Candes. http://statweb.stanford.edu/∼candes/l1magic/ 5. Numerical Tours of Signal Processing. http://www.numerical-tours.com/matlab/ optim8homotopy/ 6. Malioutov, D.M., Cetin, M., Willsky, A.S.: Homotopy continuation for sparse signal representation. In: IEEE International Conference on Acoustics, Speech and Signal Processing, Philadelphia, PA, vol. 5, pp. 733–736, March 2005 7. Candes, E.J., Tao, T.: Decoding by linear programming. IEEE Trans. Inf. Theor. 51(12), 4203–4215 (2005) 8. Herman, M.A., Strohmer, T.: High-resolution radar via compressed sensing. IEEE Trans. Signal Process. 57(6), 2275–2284 (2009) 9. Strohmer, T., Heath, R.: Grassmanian frames with applications to coding and communication. Appl. Comput. Harmon. Anal. 14(3), 257–275 (2003) 10. Gill, P.R., Wang, A., Molnar, A.: The in-crowd algorithm for fast basis pursuit denoising. IEEE Trans. Signal Process. 59(10), 4595–4605 (2011) 11. Ricaud, B., Stempfel, G., Torresani, B., Wiesmeyr, C., Lachambre, H., Onchis, D.: An optimally concentrated Gabor transform for localized time-frequency components. Adv. Comput. Math. 40(3), 683–702 (2014)