Numerical stability of spline-based Gabor-like systems

Numerical stability of spline-based Gabor-like systems Darian M. Onchis West University of Timisoara, Timisoara, Romania, University of Vienna, Vienna, Austria, Email: [email protected] Simone Zappalà University of Vienna Vienna, Austria Email: [email protected] Pedro Real University of Seville Seville, Spain Email: [email protected] Codruta Istin Politehnica University of Timisoara Timisoara, Romania Email: [email protected] Abstract—The paper provides a theorem for the characterization of numerical stability of spline-type systems. These systems are generated through shifted copies of a given atom over a time lattice. Also, we reformulate the well known Gabor systems via modulated spline-type systems and we apply the corresponding numerical stability to these systems. The numerical stability is tested for consistency against deformations. Index terms: spline-type spaces, numerical stability, Gabor systems. I. INTRODUCTION Time-frequency analysis and in particular the Gabor transform as a special case of localized Fourier transform played a major role in the modern development of signal processing [2], [9], [22]. Gabor systems provide an efficient tool to represent locally by a finite number of data the information of a signal which is given a priori through uncountably many function values. These systems had a wide impact in applications ranging from wireless communications to image processing [21], [23]. By reformulating Gabor systems as modulated spline-type systems a speed boost to the computation of such systems is achieved. But how stable is this reformulation ? And subsequently, are these systems consistent against deformations that could appear in applications ? In this paper, we give answers to the questions of numerical stability of such systems. The paper is structured in five chapters, including the introduction and the conclusions. In the second chapter, we introduce the notations and the mathematical preliminaries, the third chapter gives the main stability result and in the forth chapter the numerical experiments are performed using as case study Gabor systems. Finally, conclusions are drawn. II. NOTATION AND MATHEMATICAL PRELIMINARIES Locally compact (LC) groups are topological groups such that every point has a compact neighborhood. If the group is Abelian we will shortly say that it is a LCA group. The left translation operator is defined as the operator acting on a function or distribution fdefined over the LC group Gas Lyf(x) := f(y−1x), y, x ∈G. The morphisms from Ginto the torus Tare called characters of the group. The set of characters of a LC group Gform together with function composition a LC group b Gcalled the dual group. If Gis Abelian, the topological dual of b Gis isomorphic to G; a characters bx∈b Gcan be represented as x7→ hx, ˆxifor x∈Gand the element of x∈Gas ˆx7→ hx, ˆxi,ˆx∈b G. The Fourier transform of a function in L1(G)is defined as ˆ f(ˆx) := ZG f(x)hx,ˆxidx ˆx∈b G while the convolution can be defined for the space K(G)of compactly supported functions f∗g:= ZG f(x)Lxg(y)dx and extended to the whole L1(G)as in the case of standard real analysis. We will denote for a subgroup Hthe convolution f∗Hg:= RHf(x)Lxg(y)dHx. We introduce spline-type (ST) spaces as subspaces of translation invariant Banach spaces. Definition 1. Given Ga LC group, Ha subgroup of G, and Φ = {φi:G→C}R i=1 a finite set of functions or distributions in a translation invariant Banach space (B,k · kB), the collection of left shifts (Φ, H) := {Laφi:a∈H, i = 1, . . . , R} is called spline-type system of generating set Φand subgroup H, while its closed span in Bis called and spline-type space generated by Φand H, which will be indicated as S(Φ, H). On vector valued functions f= (fi)r i=1 defined on Hwe can apply the so called synthesis operator of the ST system (Φ, H): UΦ,H f= r X i=1 fi∗Hφi In the representation of signals through a discrete set of functions, central role have biorthogonal systems. Definition 2. Given a Banach space Band it’s dual B∗, a biorthogonal system in B × B∗is a family (φi, φ∗ i)i∈Isuch that φi1, φ∗ i2=δi1,i2. A biorthogonal system is a projection basis in B0⊂ B if it is 2018 26th European Signal Processing Conference (EUSIPCO) ISBN 978-90-827970-1-5 © EURASIP 2018 1337 Authorized licensed use limited to: Universidad de Sevilla. Downloaded on July 23,2021 at 11:27:55 UTC from IEEE Xplore. Restrictions apply. a basis for B0and P(f) :=X i∈I hf, φ∗ iiφi∀f∈X(1) A family is a Riesz projection basis if 1) There is a solid Banach space of coefficients s.t. the synthesis map is a well defined continuous bijection. 2) The synthesis operator has a bounded left inverse. For ST spaces, we have characterized the boundedness from below and the injectivity of the synthesis operator as linear independence of the Fourier transforms of the atoms on the orthogonal subgroup, see [17, Theorem 7] H⊥:= nˆx∈ˆ G:∀x∈H, hx,ˆxi= 1o During the proof of the [17, Theorem 7] a biorthogonal system to the ST system (Φ, H)is built. To find the dual system means to invert the Gramian of the given atoms, locally, on H⊥. III. NUMERICAL STABILITY In this section, we analyze the problem of numerical stability of the biorthogonal construction with the use of the invertibility of the Gramian. Its entries are: (G)i,j =Dˆ φi,ˆ φjE To analyze such a matrix, we need to define our concept of numerical stability. This concept relies on both deformation of the subgroup and the atoms. We are interested in shifts of atoms in the Fourier domain, such that a continuous procedure of optimization of the generating set to the given signal can be established. Shifts in frequency are multiplication by a character: \ h·,ˆyif=Lbyˆ fˆy∈ˆ G Because we want to establish the continuity of the inversion of the Gramian G, for every ˆ y= (ˆy1,...,ˆyr)∈ˆ Gr, we define the deformed Gramian as (Lˆ yG)i,j := DLˆyiˆ φi, Lˆyjˆ φjE We aim to control the Frobenius norm of the difference matrix D:= Lˆ yG − G (2) hence we need to find the proper neighbourhood Uof ˆ 0∈ˆ Gr where to choose ˆ y. We can formulate the following theorem. Theorem 1. Given a LCA group Gand a generating set Φ = {φ1, . . . , φr}of compactly supported distributions defined over G, then for every ǫ > 0there exists a vector of shifts in the frequency domain such that the Frobenius norm of the matrix Ddefined in (2) can be bounded as ||D||F<2ǫr max j=1,...,r kφjk1(3) Proof. Because our atoms are compactly supported distribution, their Fourier transform are uniformly continuous: ∀ǫ > 0∃Uis.t. ∀yi∈ UiLyiˆ φi−ˆ φi< ǫ Choosing ˆ y∈Ni=1,...,r Ui, we can control the entries of the matrix D (D)i,j=Lˆyiˆ φi·Lˆyjˆ φj−ˆ φi·ˆ φj =Lˆyiˆ φi·Lˆyjˆ φj−Lˆyiˆ φi·ˆ φj+Lˆyiˆ φi·ˆ φj−ˆ φi·ˆ φj ≤Lˆyiˆ φiLˆyjˆ φj−Lˆyiˆ φi·ˆ φj+Lˆyiˆ φi·ˆ φj−ˆ φi·ˆ φj =Lˆyiˆ φi·Lˆyjˆ φj−ˆ φj+Lˆyiˆ φi−ˆ φi·ˆ φj < ǫ kˆ φik∞+kˆ φjk∞ ≤ǫ(kφik1+kφjk1) Since the matrix Dis symmetric its 1and ∞norms coincide: ||D||∞=||D||1=maxj=1,...,r r X i=1 Lˆyiˆ φi·Lˆyjˆ φj−ˆ φi·ˆ φj < maxj=1,...,r r X i=1 ǫ(kφik1+kφjk1) =ǫ r maxj=1,...,r kφjk1+ r X i=1 kφik1! ≤2ǫr maxj=1,...,r kφjk1 Hence ||D||F≤q||D||1||D||∞=||D||∞ <2ǫr maxj=1,...,r kφjk1 IV. CASE STUDY: GABOR SYSTEMS ON T Time-frequency analysis is a branch of harmonic analysis that aims to extract features of a signal (information theory) or an operator (quantum physics) starting from the concept of time-frequency shift. A common tool to analyze the local frequency behavior of a function is the continuous short time Fourier transform defined over G×b Gas Vφf(y, by) := hf, MbyLyφi=y, by−1hf, LyMbyφi . where Mbyis the character multiplication operator, interpreted as modulation operator, and the joint shift operator MbyLyis noted as π(y, by). Traditional tools in time-frequency analysis are Gabor systems, which are usually introduced under the following notation [14]. 2018 26th European Signal Processing Conference (EUSIPCO) ISBN 978-90-827970-1-5 © EURASIP 2018 1338 Authorized licensed use limited to: Universidad de Sevilla. Downloaded on July 23,2021 at 11:27:55 UTC from IEEE Xplore. Restrictions apply. Definition 3. Given a function φin some function space on Gand a lattice ∆∈G׈ G, we define the Gabor system (or Weyl-Heisenberg system) as the collection N(φ, ∆) = {π(λ)φ|λ∈∆} If the lattice is separable, i.e. ∆ = ∆t×∆fbeing ∆t and ∆flattices respectively in Gand b G, we can consider a Gabor system as a spline-type system generated by an infinite generating set: S({Mωg:ω∈∆f},∆t) = span N(g,∆) The analysis and synthesis operators of a Gabor system build the so called frame operator Sf := X λ∈∆ hf, π(λ)giπ(λ)g If the frame operator is invertible, due to the commutation between frame operator and shifts, we obtain the key reproduction formula for Gabor frames: for any f∈span N(g,∆) f=X λ∈∆f, π(λ)#S−1φπ(λ)φ(4) The function S−1gis called the canonical dual of the window g. In applications, sampled signals of finite length (L) are analysed and therefore the standard process of sampling and periodization is employed [20]. In this way, also the number of shifts in time and frequency becomes finite. The redundancy of a discrete system, not necessarily a ST or Gabor system, is defined as the fraction of the number of used discrete function over the length of the domain, #shifts L. The built systems are placed in three categories: •undersampled: #shifts L<1 •critical case #shifts L=1 •oversampled #shift L>1 It is well known that undersampled Gabor systems are not stable, while critical and oversampled case are usually analysed for every choice of the window and lattice [6]. A. Numerical Experiments The Gabor-like systems based on spline-type constructions have been tested for the following 3 cases: oversampled frames, undersampled systems and deformation of the generating set of a frame. To test stability we have used two different types of atoms: bump function and Gaussian function. Numerical tests show that a spline-type reformulation of Gabor system works efficiently for both cases. This was easily foreseeable, since convergence theorems for integrals hold over LC groups. This will give the numerical scheme a really important feature: the capability to select atoms better localized in the Fourier domain than compactly supported distributions. We will not discuss extensively in here about the approximation error produced for oversampled Gabor frames, but it is important to stress about this particular case because it displays the only weakness of the multi-window spline-type (MST) numerical scheme: the computation of the Gramian and its inversion rely heavily on the fast Fourier transform, this produces a loss linear in the length of the signal as shown in Table I. Table I: Approximation error: L = length of the signal, a = uniform time-step, #c number of frequency-equispaced windows MST Gabor L=675, a=27, #c=45 1.5733e-13 3.6865e-16 L=1080, a=36, #c=45 2.3081e-13 3.8005e-16 L=2160, a=45, #c=45 7.7652e-13 8.0959e-16 L=3780, a=32, #c=45 1.3103e-12 4.1540e-16 More important is to show that our result is a characterization of stability: considering the unstable oversampled systems built for signal of length L=9072, over the lattice having constants gap_t=24, by 48 equispaced modulations of a bump function having support of radius 7gap_t and we run the short Matlab code: fourier = fft(GG); fourier_s = fourier(1:L/gap_t:end,:); det(fourier_s’*fourier_s) for the matrix GG containing the modulations, we obtain ans = 0. As a consequence, the run of the spline-type reformulation gives NaN results. We have also performed tests on undersampled Gabor systems for bandlimited signals. In the undersampled case standard Gabor algorithm is highly numerically unstable, giving often a NaN result. We show the result coming from a Gabor system generated by a normalised Gaussian over the separable lattice having parameters gap_t=27, gap_f=315 and applied to signal of length L=3780.For signal having bandwidth of radius 70, exactly the sampling rate, Gabor’s error display the unstable nature of undersampled Gabor system, while MTS’s error is always bounded (Figure 1). From our perspective, problems arise from holes in the frequency domain[16]. Due to the Wiener’s inversion theorem, the dual windows belong to the same ideal of the original atoms (characterized by their spectrum), hence they display the same localization in frequency, as shown in Figure 2; the same does not occur for different modulations of Gabor’s dual, which display the unstable nature on the global inversion of the frame operator as in (4). Finally, we want to numerically explore the stability of our method by testing the usefulness of the Theorem 1. The traditional inversion of Gabor frame is not continuous under the shift parameters [14]. That is the reason why we want to explore the possibility to deform a separable lattice, once a non-uniform reformulation is available. After having deformed a given generating set substituting to each element a modulated version φi→φi,m := h·,byiφ, being byuniformly randomly chosen in a neighbourhood of 2018 26th European Signal Processing Conference (EUSIPCO) ISBN 978-90-827970-1-5 © EURASIP 2018 1339 Authorized licensed use limited to: Universidad de Sevilla. Downloaded on July 23,2021 at 11:27:55 UTC from IEEE Xplore. Restrictions apply. the unity, we have considered the related biorthogonal system Ψm.The result is shown in Figure 4. It display the linear dependence stated in Theorem 1 between the deformation and ǫ. To test the linear dependence between the deformation on the number of atoms we have used a system of parameters L=3780, gapt=21 and number of channel #chan=27, 28, 30, 35, 36, 42, 45 and magnitude of deformation ω= 5. The thesis is validated as it appears in (3), since the norm increase in a linear way, while the surprising fact is that the error in the coefficients decrease with the number of atoms. This outcomes is not yet explained, since Theorem 1 focus on the Gramian rather than the coefficients. We think it is connected to the approximation power of the ST space since more windows, hence better localized information, are added. This aspect will be explored in future works. V. CONCLUSIONS We proposed and we characterized in this paper stability in relation with spline-types spaces and their approximation properties. The stability analysis shows that spline-type systems can be deformed through frequency shifts while they still display continuity for the inversion procedure. The method was numerically tested on different Gabor-like constructions obtained via a reformulation in multi-window spline-type spaces with the outline of advantages. 10 20 30 40 50 60 70 80 90 100 10−6 10−5 10−4 10−3 10−2 10−1 100 101 102 103 104 Bandwidth of the signal MST Gabor Figure 1: Approximation error of bandlimited signals: L=3780, gap_t=27, gap_f=315 VI. ACKNOWLEDGMENTS The authors gratefully acknowledge the support of the Austrian Science Fund (FWF): project number P27516. REFERENCES [1] Aldroubi, A., Gröchenig, K., Nonuniform sampling and reconstruction in shift-invariant spaces SIAM Rev., 43 (4), pp. 585-620 (2001) 0 500 1000 1500 2000 2500 3000 3500 4000 −5 0 5 10 15 Frequency domain 0 500 1000 1500 2000 2500 3000 3500 4000 −20 0 20 40 FFT(DUALS) FFT(ATOMS) Figure 2: Top: Gaussian atoms and their duals in dual domain for MSTS with L=3780, gap_t=27, gap_f=315: Numerical proof of Wiener’s Theorems. Down: Shifts in dual domain of same Gaussian and related (rescaled) Gaborian dual and its modulations. The dual was rescaled with a magnitude 109for plot reason: a not full spectrum coverage produce instability. 0 1 2 3 4 5 6 7 8 9 10 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 ||y||∞ Maximum of ||Ly ⋅ −⋅||F Gramian Inverse Figure 3: Deformation from approximated biorthogonality: increasing step size [2] Benedetto, J.J., Li, S., The theory of multiresolution analysis frames and applications to filter banks Appl. Comput. Harmon. Anal., 5 (4), pp. 389-427 (1998) [3] Bownik, M., The structure of shift-invariant subspaces of L2(Rn) J. Funct. Anal., 177 (2), pp. 282-309 (2000) [4] Bownik, M., The structure of shift-modulation invariant spaces: the rational case J. Funct. Anal., 244 (1), pp. 172-219 (2007) [5] Casazza, P. G., Christensen, O., and Janssen, A. J. E. M.. WeylHeisenberg frames, translation invariant systems and the Walnut representation. Journal of Functional Analysis, 180(1), 85-147. (2001) [6] Christensen, O., An introduction to frames and Riesz bases. Springer Science & Business Media. (2013) [7] de Boor, C., DeVore, R.A., Ron, A., The structure of finitely generated 2018 26th European Signal Processing Conference (EUSIPCO) ISBN 978-90-827970-1-5 © EURASIP 2018 1340 Authorized licensed use limited to: Universidad de Sevilla. Downloaded on July 23,2021 at 11:27:55 UTC from IEEE Xplore. Restrictions apply. 26 28 30 32 34 36 38 40 42 44 46 0.5 0.6 0.7 0.8 0.9 Number of atoms Maximum of ||Ly G −G||F 26 28 30 32 34 36 38 40 42 44 46 0.1 0.12 0.14 0.16 0.18 0.2 Number of atoms Maximum of || CoeffLy −Coeff||F Figure 4: Deformation from approximated biorthogonality: increasing number of atoms 0 5 10 0 0.5 1 0 0.5 1 1.5 2 Magnitude Probability ||LyG − G||F 0 5 10 0 0.5 1 0 0.5 1 1.5 2 Magnitude Probability ||IFFT((LyG)−1) − IFFT(G−1)||F Figure 5: Deformation in Frobenius norm of the Gramian and the coefficients shift-invariant spaces in L2(Rd) J. Funct. Anal., 119 (1), pp. 37-78 (1994) [8] Eldar, Y. C., Matusiak, E., and Werther, T.. A constructive inversion framework for twisted convolution. Monatshefte fuer Mathematik, 150(4), 297-308. (2007) [9] Feichtinger, H.G., Spline-type spaces in Gabor analysis ,in: D.X. Zhou (Ed.), Wavelet Analysis: Twenty Years Developments. Proceedings of the international conference of computational harmonic analysis, Hong Kong, China, June 4-8, 2001, Ser. Anal., vol. 1, , World Sci.Pub, River Edge, NJ, pp. 100-122 (2002) [10] Feichtinger, H.G., Kaiblinger, N., Quasi-interpolation in the Fourier algebra J. Approx. Theory, 144 (1), pp. 103-118 (2007) [11] Feichtinger, H. G., and Onchis, D. M. (2010). Constructive realization of dual systems for generators of multi-window spline-type spaces. Journal of computational and applied mathematics, 234(12), 3467-3479. [12] Feichtinger, H. G., Grybos, A., and Onchis, D. M.. Approximate dual Gabor atoms via the adjoint lattice method. Advances in Computational Mathematics, 40(3), 651-665. (2014) [13] Golub, G. H., and Van Loan, C. F.. Matrix computations (Vol. 3). JHU Press. (2012) [14] Gröchenig, K., Foundations of Time-Frequency Analysis Appl. Numer. Harmon. Anal.Birkhäuser Boston, Boston, MA (2001) [15] Jia, R. Q., and Micchelli, C. A.. On linear independence for integer translates of a finite number of functions. Proceedings of the Edinburgh Mathematical Society (Series 2), 36(01), 69-85. (1993) [16] D. M. Onchis and S. Zappalà, “Approximate duals of Gabor-like frames based on realizable multi-window spline-type constructions,” in Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), 2016 18th International Symposium on. IEEE, 2016, pp. 99–104. [17] D. M. Onchis and S. Zappalà, “Stability of Spline-Type Systems in the Abelian Case.,” in Symmetry. 2018, 10, 7. [18] Reiter, H., Stegeman, J.D., Classical Harmonic Analysis and Locally Compact Groups (2nd ed.)Clarendon Press, Oxford (2000) [19] Ron, A.. A necessary and sufficient condition for the linear independence of the integer translates of a compactly supported distribution. Constructive Approximation, 5(1), 297-308. (1989) [20] Søndergaard, P., Gabor frames by sampling and periodization. Advances in Computational Mathematics, 2007, 27.4: 355-373. [21] Y. Wang and C.-S. Chua. Face recognition from 2D and 3D images using 3D Gabor filters. Image and Vision Computing, Volume 23, Issue 11, (2005), 1018–1028. [22] Werther, T., Eldar, Y. C., and Subbanna, N. K.. Dual Gabor frames: theory and computational aspects. Signal Processing, IEEE Transactions on, 53(11), 4147-4158. (2005) [23] Various, LTFAT:The Large Time-Frequency Analysis Toolbox, ltfat.sourceforge.net, Accessed: 2017-09-01 2018 26th European Signal Processing Conference (EUSIPCO) ISBN 978-90-827970-1-5 © EURASIP 2018 1341 Authorized licensed use limited to: Universidad de Sevilla. Downloaded on July 23,2021 at 11:27:55 UTC from IEEE Xplore. Restrictions apply.