{'fraction_non_alphanumeric': 0.036199799755256425, 'fraction_numerical': 0.012615418845255312, 'mean_word_length': 4.463230825331227, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Designing Gabor windows using convex optimization

Redundant Gabor frames admit an infinite number of dual frames, yet only the canonical dual Gabor system, constructed from the minimal l2-norm dual window, is widely used. This window function however, might lack desirable properties, e.g. good time-frequency concentration, small support or smoothness. We employ convex optimization methods to design dual windows satisfying the Wexler-Raz equations and optimizing various constraints. Numerical experiments suggest that alternate dual windows with considerably improved features can be found.


Introduction
The construction of good synthesis filterbanks is an important topic for signal processing. For perfect reconstruction filterbanks several methods have been proposed in the signal processing literature, relying on several approaches, like polyphase representation [39] or algebraic methods [32], also on frame theory [7], similar to our approach. Modulated cosine filterbanks, which are closely related to Gabor systems (sampled short-time Fourier transforms) [20,19], are ubiquitous in signal processing. Gabor transforms represent a signal as superposition of translates and modulations of a single window function. A window function is particularly suitable for representation and processing if it is well-concentrated in time and frequency.
A signal can be reconstructed from its Gabor transform using a dual system with the same modulation and translation structure. Moreover, infinitely many such systems exist if the Gabor transform is redundant, which allows a choice of the synthesis system given other constraints [5]. Yet, traditional methods utilize the so-called canonical dual window, which is computed by applying the inverse frame operator to the analysis window. It is the only dual window that can be found by the application of a linear operator to the original window. Since, in this contribution, we are interested in finding a dual system with desirable properties given a prescribed analysis window, an alternative method is required.
As an example, a compactly supported window leads to perfect reconstruction with a finite number of computations. The canonical dual window is only guaranteed to be compactly supported in the special case where the number of frequency channels is greater or equal to the support the window (known as the painless case), though. The technique presented in this paper allows to get rid of this limit. A method for computing dual windows satisfying specific support constraints was proposed by Strohmer [37], based on the Moore-Penrose pseudoinverse of a linear equation system describing duality and the support conditions. The method therein allows the use of other regularization constraints, if these can be expressed through a Hermitian positive definite matrix, e.g. weighted 2 -norms. Already Wexler and Raz [41] impose linear constraints to find alternative dual windows, while Daubechies [16] presents a formula for finding dual windows that are optimal in a modified L 2 sense.
We will introduce a more general method that allows for simple fine-tuning of multiple optimization criteria at once. In general, the construction of dual pairs of compactly supported Gabor windows has received much interest, see e.g. [10,11] and references therein.
Since all dual windows perform perfect reconstruction from unmodified Gabor coefficients, the purpose of constructing alternative dual windows might not immediately be obvious beside the simple minimization of the support. However, if the coefficients are modified, e.g. through signal processing procedures such as frame multipliers [18,3,36], the shape of the dual window plays an important role in the quality and localization of the performed modifications, see e.g. Figure 1. Therefore, we desire to improve certain criteria over the canonical dual window.
We propose a convex optimization scheme that selects a dual window such that several regularization parameters of the user's choice are optimized. As the solution of a convex optimization problem, the proposed window will be optimal with regards to the selected criteria, cf. Section 2.2, provided that the set of admissible dual windows is nonempty.
Recently, convex optimization in the context of audio signal processing has grown into a active field of research and in particular proximal splitting methods [13,12,14] have been used to great effect, e.g. in audio inpainting [2,1] and sparse representation [25]. In those cases, optimization techniques are applied directly to the signal or its time-frequency representation. In this contribution, we apply optimization techniques to shape the building blocks of the time-frequency representation instead.
More similar to our approach, the authors in [26] solve a different convex optimization problem to find sparse dual systems. Using a weighted 1norm. They also provide a method to obtain compactly supported dual windows. This problem is optimized for the research of sparse windows and not suitable for other constraint such as smoothness. With the method proposed in this paper, similar results can be obtained, but sparse dual windows only form a particular example for its possible applications.
We also introduce a new way to design tight windows, based on the proposed convex optimization technique. However, this case is beyond the assumption of our methods, i.e. it is not a convex problem. Even though Figure 1. Reconstruction from modified coefficients: (a) Synthetic test signal and its spectrogram (b) Analysis window used to compute the spectrogram and modified spectrogram. (c,d) 2 different dual windows recomputed spectrograms after synthesis with the corresponding dual window to the left. Note that the smearing effect depends on the concentration of the synthesis window and is considerably worse in the 2nd case.
we lack any theoretical guarantee, we observe experimentally that favorable results can be obtained.
The rest of this article is structured as follows. In the next section, we repeat the necessary background from Gabor and frame theory, as well as convex optimization. The convex optimization problem that forms the backbone of our method is described in detail in Section 3, where we also recall, respectively introduce, some of the regularization functions we have found most useful in our experiments and an algorithm designed to solve the problem. Finally, Section 4 presents a wealth of examples showing the effect of different regularizers and possible applications of our method.
Some content of this contribution has been presented as [29].

Preliminaries
In this contribution, we consider sampled functions, i.e. sequences f in 2 pZq or C L . Here, the latter is interpreted as the space of L-periodic sequences with indices considered modulo L. For such f , we refer to the smallest closed interval containing all nonzero values of f as its support, denoted by supppf q.
Furthermore, we denote translation and modulation operators T n f rls " f rl´ns and M ω f rls " f rlse 2πiωl , for f P 2 pZq, l, n P Z and ω P r0, 1q. Their counterparts on C L are defined in the usual way with indexing modulo L.

2.1.
Gabor systems and frames. We define the Gabor system (1) Gpg, a, M q :"`g m,n " M m{M T na g˘n PZ, m"0,...,M´1 , for a given window g P 2 pZq, the hop size a P Z and the number of frequency bins M P Z. For any f P 2 pZq, the Gabor coefficients (or Gabor analysis) with respect to Gpg, a, M q is given by (2) pGf qrm`nM s " xf, g m,n y " with the analysis operator G given as the infinite matrix Grm`nM, ls :" G g,a,M rm`nM, ls :" g m,n rls. The coefficients pGf qrm`nM s can be interpreted as a sequence of Fourier transforms of the signal f , localized by multiplication with a translate of the window g.
Furthermore, we can perform Gabor synthesis of a coefficient sequence c P 2 pZq with respect to Gpg, a, M q: (3) f syn rls " pG˚cqrls " where G˚denotes the transpose conjugate, of G. A maximally redundant Gabor transform, setting a " 1, M " L, is also known as (unsampled) short-time Fourier transform (STFT). Only this highly overcomplete setup allows for straightforward inversion using the synthesis operator, i.e. f " G˚Gf , however. Otherwise, we require that Gpg, a, M q forms a stable, (over-)complete system, i.e. a frame.
A Gabor system constitutes a Gabor frame [9] if constants 0 ă A ď B ă 8 exist, such that In that case, the closed linear span of its elements equals 2 pZq and every sequence f P 2 pZq can be written as (5) f " Gg ,a,M c for some coefficient sequence c P 2 pZq. Moreover, the signal can be reconstructed from the Gabor coefficients by means of a dual Gabor frame Gph, a, M q, i.e. f " Gh ,a,M pG g,a,M f q. Since frames are mutually dual, also f " Gg ,a,M pG h,a,M f q holds for all f P 2 pZq, showing that the sequence c in (5) can be chosen to be the Gabor coefficients with respect to Gph, a, M q. If Gpg, a, M q is redundant, then the dual window h P 2 pZq is not unique.
Instead, the space of dual windows forms an affine subspace of 2 pZq. It equals the solution set of the Wexler-Raz (WR) equations [41,34], that provide a necessary and sufficient condition for a function h P 2 pZq to be a dual Gabor window for Gpg, a, M q. They are given by for m " 0, ..., a´1, n P Z. Here, δ denotes the Kronecker delta. With the analysis matrix G˝" G g,M,a , i.e. switching the role of a and M , they can be stated as While any of these dual windows facilitates perfect reconstruction from unmodified coefficients, their features influence synthesis results from processed coefficients as illustrated by Figure 1.
A particular dual window is the so-called canonical dual window, obtained by applying the inverse frame operator to the frame elements. The frame operator is given by the concatenation S g,a,M :" Gg ,a,M G g,a,M of the analysis and synthesis operators.
The frame operator is invertible if and only if Gpg, a, M q forms a frame, in which case the canonical dual frame is given by Gpγ, a, M q, where γ " S´1 g,a,M g is the canonical dual window. The synthesis operator of γ coincides with the pseudoinverse of the original analysis operator, i.e. Gγ ,a,M " G : . Consequently, the inversion formula reads (8) f rls " ÿ m,n xf, g m,n yγ m,n rls " G : Gf rls.
Several approaches exist for finding the canonical dual efficiently, cf. [6,22]. Unless the length of the window g is less than or equal to the number of channels M (sometimes referred to as the painless case), the canonical dual is most often infinitely long. This has made the construction where the length of the window equals the number of channels omnipresent in signal processing, to the point where these two numbers are not distinguished. We note that the canonical dual window γ minimizes both the 2 -norm as well as the 2 distance to g among all duals, see e.g [20,Prop. 7.6.2]. However, alternate duals might possess properties preferable to those of the canonical dual, e.g. shorter support, better localization or smoothness.
In the following sections, we will select dual windows optimizing certain desired properties and/or satisfying a support constraint from the solution set of the WR equations (6) by means of convex optimization.

Proximal splitting.
The convex optimization problems we consider are of the form where the f i are convex functions. Note that if at least one function f i is not differentiable, it is not possible to apply smooth optimization techniques [21]. A simple example for a nondifferentiable choice of f i , is given by 1 regularization. Proximal splitting methods [13], on the other hand may still apply, so long as the f i are at least lower-semi-continuous. More precisely, we require f i P Γ 0 pR L q for all i, where Γ 0 pR L q " f : R L Þ Ñ R : f lower semi-continuous, convex and proper ( .
The proximity operator of a function f P Γ 0 pR L q is defined by Since f is convex, the minimization problem in (10) has a unique solution for every y P R L and consequently prox f : R L Ñ R L is well-defined.
More information on the properties of proximity operators can be found in [31,27,13].
In many cases, we would like to restrict that set of admissible functions to a subset C of R L , i.e. find the optimal solution to (9) considering only functions in C. This is achieved by the indicator function. For any nonempty, closed and convex set C Ă R L , the indicator function [13] of C is defined as (11) i The corresponding proximity operator is given by the projection onto the set C: Such restrictions are called constraints and can be given, e.g. by a set of linear equations that the solution is required to satisfy. We rewrite an optimization problem on C into a problem of the form (9): We also call C " tx P R L : x satisfies the constraints u the set of admissible points. If C is nonempty and convex, Equation (12) has a solution for any given choice of regularization parameters λ i , uniquely determined if at least one f i is strictly convex.

Design of optimal dual windows
Suppose that for a a given Gabor frame Gpg, a, M q, we are looking for a dual window which is concentrated in time and in frequency. In this section, we transform those requirements into a convex optimization problem, subsequently solved by algorithms proven to converge to an optimal solution. That solution is the desired dual window. The set of eligible functions is described by a set of constraints, i.e. compulsory requirements on the solution. In this case these are duality and possibly support constraints. Both are given by a linear equation system, the WR equations (6) in the case of duality. Note that the solution set of a linear equation system is always convex.
Furthermore, objective functions f i are chosen in order to select a dual windows in the set C dual (or C dual X C supp ) that is optimal with regards to certain criteria, see Section 3.1. Those properties can be balanced by regularizations parameter λ i in order to fine-tune the window. A list of common objective functions with their effect is given in Table 1.
When computing dual Gabor windows for a frame Gpg, a, M q, with finite L g " |I g | and I g " supppgq the support of g, the most general problem we consider is (13) arg min Here, C dual is the set of functions x P 2 pZq that satisfy the WR equations.
In general, a solution of the above problem will have infinite support and thus cannot be computed in finite time. Therefore, we add an additional support constraint. This support constraint serves two distinct purposes. Firstly, restricting the support of the solution to a length L, with a, M | L and L ě L g allows computing a solution in finite time since both the number of relevant, i.e. not trivially solved, WR equations as well as the number of computations in each optimization step is finite. Secondly, we can restrict the support further, to a length of L h ă L to design dual windows with small support.
Let I h be the interval of length L h on which we wish to constrain the support of the solution, then the final convex problem is of the form (14) arg min where C supp is the set of functions supported on I h . Since C supp " tx P 2 pZq : V x " 0u, where the square matrix V is given by the set C supp is also convex. Consequently, C dual X C supp is also a convex set. From here on, we assume C dual X C supp ‰ H for the rest of this section.
Remark 1. It is known [37] that the WR equations are linearly independent. The same can easily be seen for the equations describing the support set C supp . Therefore, controlling the number of equations is sufficient for ensuring solvability. However, when jointly considering both equation systems, we have observed linear dependencies for nonrandom analysis windows. Thus, this restriction is not optimal. An investigation of this issue is planned for a later contribution.
Compactly supported dual windows: We will now discuss in detail, how to construct compactly supported dual windows. As before, we assume L g and L h " |I h | to be finite, where I h is the desired support of the dual solution window. To this end, we determine which WR equations are trivially satisfied. Furthermore, we will show that duality of compactly supported Gabor windows on 2 pZq is equivalent to duality on C L 0 and sufficient for duality on C L 1 , where L 0 ą L g`Lh and L 1 ě maxpL g , L h q are multiples of a, M . Lemma 1. Let I g , I h be intervals of length L g and L h , without loss of generality centered around 0. For any Gabor system Gpg, a, M q with supppgq Ď I g and any h P 2 pZq with suppphq Ď I h , all but ap2r Lg`L h 2M s´1q of the WR equations are trivally satisfied. Moreover, if and only if g, h are Gabor dual windows on 2 pZq for a, M , so are g f in rls " ř kPZ grl´kLs for l " 0, . . . , L´1 and h f in , defined analogous, on C L , for any L ą L g`Lh with a, M | L.
Proof. To prove the first part, note that I g XpI h`n M q " H for |n| ě Therefore xh, M ma´1 T nM gy " 0 for all such n and only ap2r Lg`L h 2M s´1q equations remain. However, since L ą L g`Lh and M | L, showing that g f in , h f in are dual on C L . Note that translation on the left side of the equation is circular. The equation above covers all WR equations of C L and, since L{M´1 ě 2r Lg`L h 2M s, all WR equations on 2 not trivially satisfied, proving equivalence.
The solutions of the nontrivial equations from the WR equation system (6) form a convex set denoted by C dual .
It is easily checked that, in addition to the equvalence proven above, duality of the windows g, h P 2 pZq above is sufficient for duality of g f in , h f in on C L , if at least L ě L g , L h and a, M | L. In that case, we have Compactly supported duals by truncation: In [37], Strohmer proposed a simple algorithm for the computation of compactly supported dual windows, which we will call the truncation method. Note that adding a support constraint to the equation system given by the WR matrix (7) is equivalent to deleting the corresponding columns and only computing the values that are possibly nonzero. The method proposed by Strohmer is based on this truncated WR matrix, considering only the nontrivial equations, see the previous section. The resulting equation system is then solved by computing the pseudoinverse, obtaining the least-squares solution. While the resulting windows satisfy the duality conditions, they are not very smooth and indeed show some discontinuity-like behavior, see also Figure 9(e,f). One of the goals of this contribution is the improvement of these undesirable effects.
It should be noted that Strohmer's method is not restricted to support constraints, but can be used to compute directly dual windows h P C dual that minimize }Rh} 2 , for some Hermitian positive definite matrix R. Naturally, solving this problem in finite time requires a support constraint, as in the previous section. pyq i C pxq force x P C P C pyq 3.1. Functionals and proximal operators. In order to tune the solution of a convex optimization problem (12) towards the properties we desire, e.g. time-frequency localization in the case of dual Gabor windows, we have to select objective functions f i , also called regularizers, that promote these properties. The purpose of this section is to review some relevant regularizers and their effect on the solution window. If more than one objective function is selected, their effects can be weighed against each other by tuning the regularization parameters λ i appropriately. Intuitively, each regularization parameter should be chosen proportional to the importance of the properties it promotes. However, by definition, different regularizers will scale differently, which has to be taken into account when setting λ i . Table 1 lists the regularizers we consider for this work, their effects and proximity operators. Most of the listed regularizers are widely used because they provide important properties. Moreover, their proximity operators are easily computed, therefore allowing their efficient application in proximal splitting algorithms.
Most of the regularizers we use are variations on the widely used 1and 2 -norm objective functions. In particular, 1 -norm minimization is considered, whenever sparsity is desired. It forms the convex relaxation of the 0 minimization problem and its solution is therefore the optimal convex approximation of a truly sparse solution. Under some specific conditions [26,8], it can be shown to be equivalent or at least close to sparsity optimization.
Therefore, the solution of 1 minimization can be expected to yield a solution that is at least approximately sparse, i.e. has few large values. This norm jointly used with a linear operator can also provide sparsity in the image of the operator. In time-frequency literature, modulation space norms, i.e. p norms on the short-time Fourier coefficients are frequently used to measure joint time-frequency localization, see e.g. [20,17]. In particular }x} S0 " }G g,1,L x} 1 , where g is a Gaussian function, is considered a quality measure for window functions. The reader interested in 1 minimization by means of proximal splitting is referred to [15,13,8,38] for more information.
Minimization of the 2 norm on the other hand has the tendency to spread values evenly over the whole signal range. The associated objective function is not only convex, but also smooth, admitting gradient descent approaches for minimization. It is traditionally used as a data fidelity term, i.e. the solution is expected to be close, in the 2 -norm sense, to a given estimate.
Similar to the 1 -norm, the 2 -norm can be used jointly with linear operator. In particular, we propose to use the gradient operator to ensure smoothness in the time domain. In our experiments, we observed that gradient 2 minimization smoothens out large jumps in the solution. Consequently, we obtain a solution well-concentrated in the frequency domain. Similarly, optimizing the gradient 2 -norm of the Fourier transform provides localization in time.
Yet another measure for localization is variance, either in magnitude or energy. We use the following definition of the (magnitude) variance of a signal x P R L : To compute the energy variance of x instead, consider varpf 2 q. It can easily be seen that these variances are nothing but weighted 1 -or 2 -norms. Therefore, minimization using proximal splitting is very efficient. Furthermore, we usually desire symmetric analysis and synthesis windows, such that fixingx " 0 is no restriction and magnitude variance is equal to 1 -norm with the weight vector

3.2.
Solving the problem. After the selection of suitable constraints, e.g. duality and support, and objective functions, we have formulated a welldefined convex optimization problem. Depending on the constraints and regularizers chosen, various methods exist for computing the solution. For the purpose of demonstration and providing a complete working framework, we decided to use and present the parallel proximal algorithm (PPXA, Algorithm 1). However, our aim is not to provide the most efficient solution to Equation (9), but to present a novel application of convex optimization methods. Alternative algorithms, e.g. generalized forward backward [30] or simultaneousdirection method of multipliers (SDMM) [33] [13], might prove more efficient. Existing optimization toolboxes like CVX (for MATLAB) can also be used.
If at least one of the regularizers has a well defined gradient, the generalized forward backward algorithm can be used, providing considerable speedup in many cases.
The parallel proximal algorithm minimizes the functions f i in (12) iteratively, employing the corresponding proximal operator.

Algorithm 1 Parallel proximal algorithm (PPXA)
Initialize Ps0, 1r,γ ą 0, pω i q 1ďiďK Ps0, 1s K with ř K i"1 ω i " 1, y 1,0 P R L , ..., y K,0 P R L Fix λ P r , 2´ r x 0 Ð ř K i"1 ω i y i,0 for n " 1, 2, ... do for i " 1, ..., K do p i,n Ð proxγ f i {ω i py i,n q end for p n Ð ř K i"1 ω i p i,n for i " 1, ..., K do y i,n`1 Ð y i,n`λ p2p n´xn´pi,n q end for x n`1 Ð x n`λ pp n´xn q end for 3.3. Tight windows. Instead of computing the dual window to a previously selected analysis window, we now aim to compute a tight Gabor frame with good properties, given the parameters a, M . A system Gph, a, M q is a tight frame, if it is a dual frame to itself. This is no longer a convex problem, since the set of tight windows for a, M is not a convex set. Indeed, it is the solution set associated to the nonlinear equation system M a A h, hr¨´nM se 2πim¨{a E " δrnsδrms, obtained by setting g " h in the WR equations (6). In this situation, the framework proposed before is no longer guaranteed to converge to an optimal solution or, in fact, to converge at all. We have observed experimentally, see also Experiment 5 in Section 4, that good solutions are obtained nonetheless, with the algorithm seemingly converging to a local minimum. Therefore, we propose our method as a heuristic scheme to find optimized, yet possibly not optimal, tight Gabor frames. Before that can be done, 2 issues remain to be solved.
Firstly, since the problem is not convex, the starting value is very important. Good results have been obtained choosing a window function that is already close to what we aim for, i.e. provides good frame bounds for the Gabor parameters a, M and shows the properties we wish to promote in the tight window.
Secondly, and more importantly, we need to define the projection operator to the set of tight windows C tight : Luckily, this projection can be computed via the formula y,a,M y, where S y,a,M is the frame operator with respect to Gpy, a, M q, cf. [23]. The result of S´1 {2 y,a,M y is called the canonical tight window and efficient algorithms for its computation are freely available, e.g. in the LTFAT toolbox [35], see also [24].

Numerical experiments
Simulations were performed using the LTFAT [35] and the UNLocBoX Matlab toolbox. A reproducible research addendum is available in http: //unlocbox.sourceforge.net/rr/gdwuco. We refer to this address as the webpage.

Experiment 1 -Effect of the objective function:
We wish to demonstrate that different optimization criteria lead to widely different solution windows, with each criterion promoting a certain shape or behavior in the optimized dual. To emphasize this effect, we apply the regularizer functions introduced in the previous section to the same tight starting system. More precisely, our setup considers Gpg, 15, 120q, i.e. a system with redundancy 8, where g is a Itersine window [40] of length L g " 120 samples, see Figure  2(a,b). The (continuous) Itersine window is defined as gptq " # sin`0.5π cospπtq 2˘i f t P r´1{2, 1{2s, 0 else.
This window yields a tight frame for half-overlap and shows a better frequency decay and concentration, the latter in terms of main lobe width, than the more widely used cosine window.
In this experiment, we fixed L to 240, therefore forcing L h ď 240, but not adding further support constraints. This setup, in particular its high redundancy, allows us to shape the dual windows rather freely for different objective functions, therefore producing characteristic examples. Since the Itersine window forms a tight frame for the chosen parameters we do not show the canonical dual. Moreover, the 2 -norm minimizing dual window coincides with the canonical dual and consequently with the original window up to normalization, cf. Section 2.1. All presented dual windows are assumed to perform perfect reconstruction. More precisely, using [22,Eq. (60)], the maximum relative reconstruction error can be shown to be of the order of precision of the machine, i.e. around 10´1 5 . Due to numerical issues of proximal splitting methods, the timestepγ (See Algorithm 1), has influence on the solution. In particular, there is a tradeoff between precision and convergence speed. Our contribution is intended as conceptual, rather than algorithmic work therefore we do not discuss those issues in detail.
Concentration in time and in frequency is a very important property for Gabor synthesis. Indeed when modifying the coefficients in the Gabor domain, the time-frequency spread of this operation will strongly depend on the time-frequency concentration of the synthesis window. To improve concentration in one domain, we will smooth the function in the other. For instance, the smoothest function in time is also the most concentrated in frequency. It can be computed by minimizing the function }∇x} 2 2 . In a same manner, the smoothest function in frequency (and most concentrated in time) is the solution of the minimizing the function }∇Fx} 2 2 . Result are presented in Figure 2 (c,d) and (e,f).
Simultaneous time-frequency concentration can be obtained using the S 0 norm as regularizer. However, minimizing the norm is computationally less efficient than optimizing smoothness in time and frequency as described above. The result is presented in Figure 2 (g,h).
As convex relaxation of the 0 problem, we also consider the 1 -norm minimal dual window. It should be noted however, that minimizing the 1norm does not guarantee a solution with small support. Even if the solution has few nonzero values, there is no theoretical guarantee that those zeros are concentrated, i.e. contained in a small interval. The example shown in Figure 2 (i,j) is produced by considering pure 1 minimization. In order to analyze the result, we begin by setting to zero all coefficients smaller than the tolerance of our algorithm (-100 dB). The resulting number of nonzero coefficients is 32 which is very close to the number of WR equations L M a " 30. However the length of the support is 82 which is far greater than minimum possible compact support (L min " L M a " 30). This problem stems from the fact that the 1 minimization provides no localization.
However, this localization can be obtained with other functionals. In particular optimizing the variance can be of great interest. In Figure 2 (m,n) and (o,p), the variance in time and in frequency is optimized. For more information about the variance and its optimization, see Experiment 2. Instead of optimizing a function that promotes certain abstract features, free design can be performed using the objective function }x´g sh } 2 2 , where g sh is used as a model for the dual window. The algorithm then returns the dual window closest to g sh in the 2 -norm sense. For x to have similar shape as g sh , correct normalization of g sh is important. We have observed that choosing g sh such that }g sh } 2 " }γ} 2 , where γ is the canonical dual, yields good results. Therefore, we chose that approach for the examples presented in Figure 3(a,b) and (c,d).
Experiment 2 -Optimizing time-frequency concentration I: In this experiment, we aim to model time-frequency concentration through the combination of 2 objective functions. Since concentration in time is closely related to smoothness in frequency and vice-versa, we select the two smoothing functionals: }∇x} 2 2 and }∇Fx} 2 2 and balance them to form the optimization problem: We apply this optimization scheme in the setup proposed in Experiment 1, to obtain a dual window with good concentration and smoothness in both time and frequency. The solution we obtain is shown in Figure 4(a,b). In comparison to the canonical dual, Figure 2(a,b), the solution window is more concentrated in time, with slightly broader spread in frequency but considerably improved decay. In fact, it closely resembles a Gaussian function. To illustrate the improved time-frequency concentration and its use in Gabor synthesis, Figure 5 shows the differences of synthesizing a group of nonzero coefficients with the 2 alternative windows. Note that these coefficients are not the result of an analysis, but are freely chosen in the time-frequency plane. Optimally, to be able to perform precise time-frequency processing using a Gabor analysis/synthesis scheme, the spectrogram of the synthesized coefficients in this example should have as little spread as possible. Note though, that the actual spread shown combines the leaking caused by the synthesis window with the smearing effect caused by the analysis. To minimize the latter, we have decided to used a well-concentrated window for analysis. Therefore, all spectrograms show a full STFT, computed using a Nuttall [28] window of length 60. The continuous Nuttall window is defined as where c 0 " 0.355768, c 1 " 0.487396, c 2 " 0.144232 and c 3 " 0.012604. See also Figure 9(a,b) for a sampled Nuttall window. We observe that, indeed, the window computed with our optimization scheme shows improved concentration, in particular in time.

Experiment 3 -Optimizing time-frequency concentration II:
We present the construction of time-frequency concentrated dual Gabor windows for a system of fixed length L " 500. Our setup considers  Gpg, 25, 125q, i.e. a system with redundancy 5, where g is a rectangular window of length L g " 125 samples. This construction allows the comparison of alternative time-frequency localization measures and their effect on the solution window. The system forms a tight frame, hence the canonical dual window is given by the same, badly localized window, up to normalization. Consequently, this setup is an ideal sandbox for experimenting with various localization measures.
We apply 3 different methods for measuring joint time-frequency localization: ‚ As in Experiment 2, we combine the 2 -norms of the gradient of x and of Fx, to optimize the smoothness in the time and the frequency domain. ‚ Variance is associated with the Heisenberg uncertainty principle, a classical measure for time-frequency localization. While we cannot directly optimize the Heisenberg uncertainty (the product varpxq varpFxq), the sum of variances provides a very similar measure. We consider both the magnitude variance, as in Heisenberg's uncertainty, as well as energy variance. ‚ The S 0 -norm of x, or equivalently 1 -norm of its STFT, is widely used in Gabor analysis to measure the spread of x in the time-frequency plane. Since truly sparse short-time Fourier transforms do not exist, it promotes functions that are concentrated around few points in the time-frequency plane. Since concentrated windows have small spread, they also have a small S 0 -norm. However, small spread is not a guarantee for concentration. To further improve the concentration, we also consider to weight the S 0 -norm as with the following: To show the effect of the gradient and variance measures when applied in a single domain, Figure 6 shows the results obtained for optimizing the concentration in time only. Since the analysis system forms a tight frame, the canonical dual is a rectangular windows of length 125. In this example, magnitude variance minimization provides the strongest concentration in terms of support, albeit at the cost of the clear, slim peak obtained from the very similar energy variance and gradient optimization. The results for a similar experiment, optimizing frequency concentration can be found on the webpage.
In fact, we are more interested in simultaneous time-frequency concentration. Therefore, we performed another experiment comparing the timefrequency localization measures proposed above. Figures 7 and 8 present the results of the experiment. The advantage of the gradient and variance approaches is the simplicity of tuning the tradeoff between time and frequency concentration, which involves only the appropriate choice of regularization parameter. On the other hand, only S 0 -norm based optimization schemes truly measure concentration on the whole time frequency plane, instead of its one dimensional projection on the time, respectively frequency domain.  The results show that pure S 0 -norm optimization is insufficient to obtain good concentration. Weighted S 0 -norm and magnitude variance optimization on the other hand, provide very good results. The magnitude variance shows slightly better concentration in time, while the weighted S 0norm solution is superior to all other measures in terms of time-frequency decay. As observed for the previous experiment, energy variance and gradient approaches produce very similar results, providing slightly worse timefrequency concentration compared to magnitude variance and weighted S 0norm. While the experiment suggests weighted S 0 -norm and magnitude variance as the most promising approaches, this experiment should not be considered an exhaustive study of the various time-frequency localization measures. More experiments are required to study the different approaches in detail. Note the good decay of the weighted S 0 -norm Experiment 4 -Smooth compactly supported duals: Now, we want to construct a dual Gabor window with short support in a nonpainless setup, i.e. for a system with few frequency channels. This has previously been attempted in [37]. However, the solutions obtained by the truncation method proposed therein, cf. Section 3, are often badly localized in frequency due to the tendency of the truncation method to yield nonsmooth solutions, i.e. solutions with "jumps" or discontinuity-like behavior in time.
Here, we present the construction of a dual window that combines short support with reasonable smoothness and therefore frequency concentration. We start from a Gabor system Gpg, 30, 60q with redundancy 2. The analysis window g is chosen as a Nuttall window of length L g " 120 samples.
We desire a dual window h with the same support as g, i.e. L h " L g " 120. Therefore, the set of admissible windows is given by C dual X C supp , where C supp " tx P R L : supppxq Ď r´60, 59su. Furthermore, we aim to achieve localization and smoothness by selecting the regularization functions f 1 " }¨} 1 ,f 2 " }Fp¨q} 1 , f 3 " }∇p¨q} 2 2 and f 4 " }∇Fp¨q} 2 2 . The results in Figure 9(c,d) show the optimal dual window with regards to the regularization parameters λ 1 " λ 2 " 0.001 and λ 3 " λ 4 " 1. Those values were chosen experimentally, balancing the effect of the regularization functions described in Table 1. As reference, we included the least-squares solution provided by the truncation method, see Figure 9(e,f).
Minimizing the selected regularization functions improves upon the desired features, in particular smoothness and localization by means of minimizing f 3 and f 4 . The addition of f 1 and f 2 is supposed to suppress the tendency of the solution to have M-like shape, i.e. multiple peaks. This is unwanted as it leads to windows with ambiguous temporal or frequency position. Heuristically, minimizing the l 1 -norm pushes all big coefficients to similar values, therefore achieving the suppression of multiple significant peaks.
The solution provided is assumed to perform perfect reconstruction on any signal with admissible length greater or equal to L. As in the previous experiments, the maximum relative reconstruction error (4.5e´1 4 ) is of the order of the machine precision.
To guarantee the canonical dual window to be supported on L h " L g , we would be required to increase the number of frequency channels to M ě 120, putting us in the painless case. Therefore the redundancy is increased twofold, which is an unwanted side effect. Alternatively, in this setting, we could decide to keep the parameters a " 30, M " 60 fixed, but decrease the window size to L g ď 60. However, this construction provides a system with a more than 8 times larger frame bound ratio. Consequently, the resulting canonical dual window h, shown in Figure 10, shows bad frequency behavior and an undesirable, M-like shape in time. In contrast, the method proposed in this manuscript allows the use of nicely shaped, compactly supported dual Gabor windows at low redundancies, without the strong restrictions of the painless case.
Experiment 5 -Improvement of classical tight frame constructions: Especially for frames with small redundancy, it has been observed that a tradeoff between localization and smoothness in time-frequency exists between the analysis and dual windows. From the perspective of tight frames, this has the consequence that the available tight prototypes show, in comparison, suboptimal time-frequency concentration. In this final experiment, we will propose 2 approaches for the improvement of a popular tight frame construction. In particular, the Itersine window, already introduced in Experiment 1, forms a tight frame in a half-overlap situation when sufficient frequency channels are used. The Itersine window has been proposed as an improvement of the rectangular and cosine windows, both widely used for tight frames with redundancy 2, providing better smoothness and time-frequency concentration than either.  Consequently, the starting point of our experiment is a Gabor system of the form Gpg, 30, 60q, i.e. a system with redundancy 2, with an Itersine window g of length L g " 60. Our aim is to construct both an alternative tight frame, as well as a pair of dual windows, such that all 3 obtained prototypes show improved time-frequency concentration over the Itersine window g.
First, we construct an improved tight window. To that end, we use the heuristic method for tight window design proposed in Section 3. Additionally, to gain some design freedom, we allow the tight window g t to have support length L gt ď 360. We then attempt to solve the optimization problem arg min xPC tight XCsupp λ 1 }∇Fx} 2 2`λ 2 }∇x} 2 2 The gradient functionals have been selected to promote a window that is smooth and well-localized in both domains. We initialized the algorithm with the Itersine window g. Despite the proposed optimization problem not being convex, we obtain a tight window with roughly the same concentration in time, but improved decay and sidelobe attenuation in frequency, see the comparison in Figure 11. The tight window shown was obtained for the regularization parameters λ 1 " 1, λ 2 " 5. Figure 11. Gpg, 30, 60q, L g " 60, compactly supported tight windows: L g " 360.
In the second part of the experiment, we construct a pair of compactly supported dual windows g 0 , h such that Gpg 0 , 30, 60q and Gph, 30, 60q form dual frames. Again, we allow some freedom for the support, choosing for g 0 a Nuttall window of length L g 0 " 120. This window is slightly broader than the Itersine window g in time, but very good decay and localization in frequency, see Figure 12. For the dual window, we consider L h ď 360 as in the tight case and the convex optimization problem arg min xPC dual XCsupp µ 1 }∇Fx} 2 2`µ 2 }∇x} 2 2 .
The dual window we obtain (using the regularization parameters µ 1 " 0.1, µ 2 " 1), shows roughly the same time localization as the Nuttall window or the tight window obtained before and is quite similar to the latter in frequency. The result is shown in Figure 12. Figure 12. Construction of a pair of dual FIR windows both beating the 'Itersine' (Gpg, 30, 60q, Itersine L g " 60, Nuttall L g 0 " 120, Dual window L h " 120): windows in time and frequency In terms of joint time-frequency localization, we strongly feel that all 3 prototypes constructed in this experiment show a considerable improvement upon the Itersine window and therefore also over the cosine window.

Conclusion
In this contribution, we have proposed an algorithm for the design of Gabor dual windows relying on standard techniques from convex optimization. The proposed method extends previous approaches and provides a framework for tuning various properties of the synthesis system. It can also be used for the construction of tight windows, albeit only in a heuristic fashion without mathematical convergence guarantees.
Our method can be applied in various situations to construct dual frames with properties more important for application than minimal 2 -norm. Therefore, we introduced several useful regularizer functionals and discussed their effect on the shape and behavior of the dual window. In an extensive experiment section, we demonstrated these effects and their application to design pairs of dual windows with good properties. In particular, we use smoothness regularizers in time and frequency to construct a dual window with improved time-frequency concentration compared to the canonical dual. We compare this measure of time-frequency concentration to alternate approaches based on variance or S 0 -norm, both of which perform similar or even better than the smoothness prior in our experiments.
Through a combination of smoothness an 1 priors, we show that our method can improve previous results by Strohmer [37] on the construction of dual windows with short support.
Finally, a classical setup for tight Gabor frames is examined and improvements are proposed based on our framework for dual and tight windows, respectively. Future work will further be concerned with applying the findings herein to frames with a different structure, e.g. nonstationary Gabor frames [4].