Analysis of Signals via Non-Maximally Decimated Non-Uniform Filter Banks
Sandeep Patel Ravindra Dhuli Brejesh Lall
eess.SP












































































1


This is the accepted version of the paper


Link to IEEE version: https://ieeexplore.ieee.org/abstract/document/8716585https://ieeexplore.ieee.org/abstract/document/8716585 



Digital Object Identifier 10.1109/TCSI.2019.2914302



Citation: S. Patel, R. Dhuli and B. Lall, “Analysis of Signals via Non-Maximally Decimated Non-Uniform Filter Banks," in IEEE Transactions on Circuits and Systems I: Regular Papers.



©2019 IEEE.  Personal use of this material is permitted.  Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
 





Analysis of Signals via Non-Maximally Decimated Non-Uniform Filter Banks
    Sandeep Patel, Ravindra Dhuli, and Brejesh Lall
Sandeep Patel and Brejesh Lall are with the Bharti School of Telecom Technology and Management, Indian Institute of Technology Delhi, New Delhi, India - 110 016
(e-mail: sanpatel90@gmail.com; brejesh@ee.iitd.ac.in).
Ravindra Dhuli is with the Department of Electronics and Communications Engineering, Vellore Institute of Technology, Andhra Pradesh, India - 522 237 (email: ravindra.d@vitap.ac.in).
©2019 IEEE.  Personal use of this material is permitted.  Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Digital Object Identifier 10.1109/TCSI.2019.2914302
    December 30, 2023
=======================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================






This paper addresses the important problem of reconstructing a signal from multiple multirate observations. The observations are modeled as the output of an analysis bank, and time-domain analysis is carried out to design an optimal FIR synthesis bank. We pose this as a minimizing the mean-square problem and prove that at least one optimal solution is always possible. A parametric form for all optimal solutions is obtained for a non-maximally decimated filter bank. The necessary and sufficient conditions for an optimal solution, that results in perfect reconstruction (PR), are derived as time-domain pseudocirculant conditions. This represents a novel theoretical contribution in multirate filter bank theory. We explore PR in a more general setting. This results in the ability to design a synthesis bank with a particular delay in the reconstruction. Using this delay, one can achieve PR in cases where it might not have been possible otherwise. Further, we extend the design and analysis to non-uniform filter banks and carry out simulations to verify the derived results.







Matrix Wiener filter, Multirate filter bank, Perfect reconstruction, Time-domain pseudocirculant conditions.


















§ INTRODUCTION





































Multirate filter banks have been used extensively for applications in the fields of image and video processing <cit.>, communications <cit.>, subband adaptive filtering <cit.>, radar systems <cit.>, etc. 
The filter bank theory evolved from the need to decompose a signal spectrum into multiple frequency subbands in order to efficiently perform a number of operations like compression, coding, noise cancellation, etc. Initially, two channel quadrature mirror filter bank (QMF) was proposed in the literature <cit.>, and later, it was extended to arbitrary M-channel case <cit.>. To better exploit the signal characteristics in a number of applications like audio coding, spectral analysis, subband adaptive filtering, etc., non-uniform filter banks (NUFBs) having different channel bandwidth were introduced <cit.>. In <cit.>, filter banks with different multirate factors were used, to realize the filter transfer functions for reducing the multiplicative complexity. NUFBs with rational sampling factors were considered in <cit.>. However, they were found to be equivalent 
to integer decimated NUFBs <cit.>. A number of design methods
like direct method <cit.>, recombination method <cit.>, modulation based method <cit.>, etc. exist in the literature. Application specific design methods have also been proposed in the literature. For example, in <cit.>, an NUFB was designed for acoustic echo-cancellation by maximizing the signal-to-alias ratio. All these methods design both the analysis and synthesis banks of an NUFB. The analysis and synthesis filters in a filter bank can be IIR or FIR. FIR filters have advantage over IIR in respect of stability and linear-phase property. In the literature, various design methods using transform like Lapped Orthogonal Transform <cit.>, Generalized Lapped Orthogonal Transform <cit.>, Extended Lapped Transform <cit.>, etc. have been proposed to design a perfect reconstruction (PR) FIR maximally decimated uniform filter bank (UFB). A comprehensive analysis of FIR perfect reconstruction filter banks can be found in <cit.>. It has been shown that oversampled filter banks (OFBs) offer additional design freedom as compared to critically sampled filter banks <cit.>. The inbuilt redundancy present in them has been exploited for a variety of applications <cit.>. A frame theoretic analysis of OFBs can be found in <cit.>. Given an oversampled analysis bank, a parameterization for all synthesis banks resulting in PR was developed in <cit.>. Undersampled filter banks which provide underdetermined representation of signals have found application in compression of signals <cit.>. Despite the filter banks have been around for more than two decades, they continue to be applied to new and emerging areas. Graph signal processing is one such interesting area where filter banks techniques find applications in solving diverse problems <cit.>. 

The necessity in any scenario to estimate a signal or its properties from its subband components can be addressed well using the filter bank based processing. Expectedly, many research problems appear posing such requirement. Synthesis from subband components has been utilized in applications like subband coding <cit.>, analog/digital conversion <cit.>, transmultiplexer <cit.>, ultrawideband receiver <cit.>, TV white space transceiver <cit.>, channel coding <cit.>, etc. To get better results, processing on subband components, rather than on full-band signal, have been carried out in problems like speech enhancement <cit.>, ECG processing <cit.>, subband adaptive filtering <cit.>, seismic signals processing <cit.>, etc. The processed subband signals are then combined using a synthesis bank to get the final output. In multirate sensors networks, sensor outputs are modeled as an analysis bank output, and these outputs are fused to get a unified measurement <cit.>. In <cit.>, construction of a high-resolution signal from multiple low-resolution signals has been carried out. The problem of linear prediction from multirate observations has been examined in <cit.>. In many applications, rather than a signal, a property of interest is to be estimated from multirate observations. Time delay estimation from low rate samples is an example of that, and it finds application in speech localization, processing using microphone arrays, radar, underwater acoustics, wireless communications and other areas <cit.>. Direction of arrival estimation is another example which finds application in wireless communications, medical imaging, seismology, etc. <cit.>. In [31], estimation of the spectrum of a signal from its low resolution signals was carried out. This is required when a signal can be observed only indirectly using low-rate sensors. 

To address the problem of estimating a signal from its subbands, various solutions using Wiener filtering, Kalman filtering, ℋ^∞ filtering, compressive sensing, adaptive filtering, etc. have been proposed in the literature. Wiener filtering based methods require joint stationarity of the subband input and desired signals along with the knowledge of second order statistics of them. Kuchler and Therrien <cit.> used Wiener filtering to estimate a signal from multiple multirate observations. Scrofani and Therrien <cit.> extended the analysis to two-dimensional signals. Vaidyanathan and Chen <cit.> designed a statistically optimal synthesis bank for a subband coder by using the biorthogonal solution followed by a matrix Wiener filter in the synthesis stage. In case of Kalman filtering, the statistics of the input and noise signals are required to be known even if that vary with time. Multirate Kalman filter based methods can be found in <cit.>. ℋ^∞ optimization based methods, on the other hand, do not require any statistical assumption and perform worst-case design <cit.>. As ℋ^∞ solution is generally not unique, mixed ℋ^2/ℋ^∞ optimization methods <cit.> have also been proposed in the literature. The complexity of ℋ^2 and ℋ^2/ℋ^∞ solutions are very high since they are solved as linear matrix inequalities (LMIs) <cit.>. A least square based solution for the problem was presented in <cit.>. However, the solution presented  was for two channels only. In <cit.>, Li Chai et al. formulated the problem using structural similarity criterion and obtained closed-form solution under certain assumptions like the filter length is equal to the decimation factor, the mean of the source is zero, etc. Compresive sensing based method was used in <cit.> to estimate a signal from multirate observations. However, the signal has to be sparse. In <cit.>, adaptive filters were used to estimate a signal from two observation sequences. An adaptive least square lattice filter was used in <cit.>. However, the filter obtained was periodically time-varying. Statistical analysis of the estimation from the subbands has been performed by a number of authors. For example, in <cit.>, power spectral density of a signal was estimated from multiple observations. In <cit.>, a measure for information contained in a multirate observations was defined.



 §.§ Contribution

In this paper, the problem of synthesizing a signal from its multirate observations is addressed by performing time-domain analysis. This approach has led to some additional novel contributions to the field which are now briefly presented. Under time-domain analysis, the matrix representation for various operations like filtering, downsampling, upsampling, etc. are developed and used to parameterize synthesis bank solutions. This parameterization is consistent and at least one optimum synthesis filter bank is guaranteed. We design the synthesis bank for a more general set up in comparison to existing methods <cit.>. The synthesis filter length can be arbitrary but given. Further, we have used delay in the reconstruction as a parameter to have flexibility in the synthesis filter design, and using that, we obtain better reconstruction error than possible with a zero delay design. Another advantage of our analysis is that we obtain a linear time-invariant (LTI) optimal matrix filter unlike the linear periodically time-varying (LPTV) optimal filters obtained in earlier works <cit.>. Our method always results in a solution in comparison to LMI based methods <cit.> where a solution for an LMI may not be feasible <cit.>. The necessary and sufficient condition on a synthesis bank solution to result in PR is derived. Under this condition, the polyphase matrices for the analysis and synthesis banks satisfy the general pseudocirculant property <cit.>, unlike the limited identity matrix condition in the earlier works <cit.>. The necessary and sufficient conditions on the analysis bank and the delay for a PR synthesis bank solution to exist are derived. This analysis forms an alternative to the frame theory based approach in previous works <cit.>. Time-domain pseudocirculant result derived in this paper form an important theoretical contribution to the multirate theory. The derivation of a range of delay values for which PR is possible is another contribution. We have also extended the design methodology for any arbitrary NUFB. Under experimental results, a number of experiments are presented to highlight contributions and to show application of our work. 



 §.§ Organization

This paper is organized as follows: Section <ref> discusses the various matrix representations for time-domain signals and operations. In Section <ref>, we introduce the framework used to design the synthesis filter for a given analysis bank. In Section <ref>, we derive the pseudocirculant condition in time-domain and present the necessary and sufficient conditions on an analysis bank and on the delay to result in PR. We provide the experimental results in Section <ref> and finally, concluding remarks are given in Section <ref>. 



 §.§ Notation

The (i,j)-th entry of a matrix 𝐁 is given by B_i,j or B(i,j). The transpose and conjugate-transpose of a matrix or vector quantity are denoted by the superscripts (.)^T and (.)^H, respectively. An identity matrix of size P is represented by 𝐈 when the size is implicit and by 𝐈_P otherwise. The pseudoinverse of a matrix 𝐀 is denoted by 𝐀^†. The superscript (.)^* stands for conjugation of a quantity. Convolution of two sequences is denoted by ∗. The ceiling function is represented by ⌈.⌉.


































































































§ MATRIX REPRESENTATIONS


In this section, we develop the matrix representations for various multirate operations, which are required for an effective time-domain analysis of multirate filter banks.



 §.§ Time-domain Sequence Representation

A vector signal is developed from the given signal v(n) by stacking the past P samples as:

    𝐯(n) = [ v(n-P+1) v(n-P+2)        …     v(n) ]^T.

It is termed as an observation vector for the signal v(n) <cit.>. Its flipped version or reversal can be obtained as

    𝐯(n) = 𝐉_P 𝐯(n),

where 𝐉_P is a counter-identity or reverse-identity matrix. For a matrix 𝐁, reversal operation results in reversing of order along both rows and columns. Mathematically, the same can be expressed as

    𝐁 = 𝐉_M 𝐁𝐉_N

if the size of the matrix is M × N. For two matrices 𝐀 and 𝐁 whose product is defined, we have the following relation:

    𝐀𝐁 = 𝐀𝐁.
 



 §.§ Decimation

Consider a system, as shown in Fig. <ref>, with a M-fold decimator preceded by a time-advance by l. The input and output of it are related as

    y(n) = x(Mn+l).


Such a system can be used to obtain polyphase components of a signal when l is in the range [0, M-1]. Two matrix representations are possible for a system. If an observation vector 

    𝐲 = [   y(0)   y(1)      … y(P-1) ]^T

for the output is to be evaluated, then the same can be done as follows:

    =2pt
    =0mu
    [   y(0);   y(1);      ⋮; y(P-1) ]   = [ 1 0 … 0 … 0; 0 0 … 1 … 0; ⋮ ⋮ ⋱ ⋮ ⋱ ⋮; 0 0 … 0 … 1 ][          x(l);        x(l+1);             ⋮;        x(M+l);             ⋮; x(M(P-1) + l) ], 
    𝐲   = 𝐃_P , M(P-1)+1^0 𝐱 ,

where 𝐃_P , M(P-1)+1^0 is known as a decimation matrix. On the other hand, if an input sample vector 

    𝐱 = [   x(0)   x(1)      … x(P-1) ]^T

is given, then the corresponding output samples can be obtained as

    𝐲 = 𝐃_⌈P/M⌉ , P^l 𝐱,
 
where the elements of the decimation matrix 𝐃_⌈ P/M  ⌉ , P^l are given by

    D_⌈P/M⌉ , P^l(i,j)    = 
    1,        if  j = Mi+l  
    
    0,        otherwise.

Here l is in the range 0 ≤ l ≤ M-1. For l ≥ M, the same matrix representations can be extended.



 §.§ Expansion

If an input observation vector

    𝐱 = [   x(0)   x(1)      … x(P-1) ]^T

is available, then the output of a M-fold expander can be obtained as

    𝐲   = 𝐔_M(P-1)+1 , P𝐱,

where 𝐔_M(P-1)+1 , P is an expansion matrix. This matrix is related to a decimation matrix as

    𝐔_M(P-1)+1 , P = (𝐃_P , M(P-1)+1^0 )^T.

It can be easily verified that

    𝐃_P , M(P-1)+1^0  𝐔_M(P-1)+1 , P   = 𝐈_P, 
    𝐔_M(P-1)+1 , P𝐃_P , M(P-1)+1^0    ≠𝐈_M(P-1)+1.




 §.§ Convolution

Consider a causal linear time-invariant (LTI) filter with impulse response {h(0), h(1),…,  h(Q-1)}. Its input and output are related as

    y(n) = ∑_k=0^Q-1 h(k) x(n-k).

We present the matrix representations for the above relation for two use cases. Under first case, consider an observation vector 

    𝐲(n) = [ y(n-P+1) y(n-P+2)        …     y(n) ]^T

for the output which needs to be evaluated. The same can be achieved using

    𝐲(n) = 𝐇𝐱(n),

where

    = 2pt
    =0mu
    𝐱(n) = [ x(n-P+2-Q) x(n-P+3-Q)          …       x(n) ]^T,

and 𝐇 is a convolution matrix given by

    =0mu
    =2pt
    𝐇 = [ h(Q-1) h(Q-2)      …   h(0)      …      0;      0 h(Q-1)      …   h(1)      …      0;      ⋮      ⋮      ⋱      ⋮      ⋱      ⋮;      0      0      …      0      …   h(0) ].

The second representation is obtained for a scenario where an input observation vector is given, and the corresponding output samples need to be evaluated. Consider an input observation vector 

    𝐱 = [   x(0)   x(1)      … x(P-1) ]^T,

then the complete output due to it can be expressed as

    = 2mu
     = 1pt
    =0mu
    1![     y(0);     y(1);        ⋮;   y(Q-1);        ⋮; y(P+Q-2) ] = [   h(0)      0      …      0;   h(1)   h(0)      …      0;      ⋮      ⋮      ⋱      ⋮; h(Q-1) h(Q-2)      …      0;      ⋮      ⋮      ⋱      ⋮;      0      0      … h(Q-1);        ][   x(0);   x(1);      ⋮; x(P-1) ]

or 

    𝐲 = 𝐇̃𝐱.

It is implicit in the above representation that x(n) = 0 for n ∉ [0, P-1]. The utility of the representation is in evaluation  of convolution of two filters. The two convolution matrices, so far obtained, are related with each other as:

    𝐇̃ = 𝐇^T,

where 𝐇 denotes the reversal of the matrix.

In the following section, we address the design of a synthesis filter bank using the time-domain representations discussed so far.




§ DESIGN FRAMEWORK


We have multirate observations, derived from various sub bands, and we aim to reconstruct or estimate the original high resolution signal. Initially, we consider observations to be at the same low rate and model them as output of a uniform analysis bank. The case when the observations are at different rates is addressed later in this paper. The subbands are applied to a matrix synthesis filter, as shown in Fig. <ref>, where reconstruction happens at a low rate to reduce computational cost. The output of the synthesis filter is then unblocked <cit.> to get the final high resolution signal. We model our problem of designing the matrix synthesis filter bank in the framework of Wiener filtering. The Wiener filter is an optimum filter to minimize the mean-square error (MSE). For a multi-input multi-output system, the solution is known as a matrix Wiener filter. The details of the design setup are explained next.

Consider the filter bank shown in Fig. <ref>. A wide-sense stationary (WSS) input signal u(n) passes through a given analysis bank consisting of the filters {h_i(n)}_i=0^L-1. The analysis filters are assumed to be FIR and causal. The output signals {x_i(n)}_i=0^L-1 of the analysis bank are uniformly decimated by the factor M to obtain the subband signals {v_i(n)}_i=0^L-1 which are then applied to a matrix synthesis filter 𝐀(n). We choose the synthesis filter to be FIR and causal, and formulate a Wiener filtering problem for a given length of the synthesis filter. The desired signal for the problem is derived from the input signal u(n) by adding a given delay d and then performing blocking operation <cit.>. The delay is added to compensate the time lag that appears in the input signal when it passes through the filter bank. The blocking operation ensures that the desired signal 𝐝(n) is jointly stationary with the subband signal 𝐯(n) <cit.>—a necessary condition required for application of Wiener filtering <cit.>.  




 §.§ FIR Matrix Synthesis Filter Expression

In Appendix <ref>, we obtain the following expression for an FIR matrix Wiener filter with length P:

    𝐫_d_i v = 𝐚_i^T 𝐑_vv,      0 ≤ i ≤ M-1,

where 𝐑_vv is the auto-correlation matrix of the input signal 𝐯(n) to the filter, 𝐫_d_i v is the cross-correlation vector between the desired signal component d_i(n) and the signal 𝐯(n), and 𝐚_i is the i-th row of the filter. This expression can be simplified in the context of the UFB given in Fig. <ref>. In order to do that, a vector 𝐯_s(n) is created by stacking the observation vectors of the subband signals as

    𝐯_s(n) = [   𝐯_0^T(n)   𝐯_1^T(n)          … 𝐯_L-1^T(n) ]^T,

where 𝐯_j(n) is an observation vector representing the j-th input to the Wiener filter at time n and is given by

    = 2pt
    =0mu
    𝐯_j(n) =    [ v_j(n-P+1) v_j(n-P+2)          …     v_j(n) ]^T.

The quantities 𝐑_vv and 𝐫_d_i v can be expressed in terms of 𝐯_s(n) as

    𝐑_vv   = 𝐄[𝐯_s(n) 𝐯_s^H(n)], 
    𝐫_d_i v   = 𝐄[ d_i(n) 𝐯_s^H(n)].

To make use of the Wiener filter in (<ref>), we derive an expression of the vector 𝐯_s(n) in terms of the input to the filter bank. We can note from Fig. <ref> that v_j(n)=x_j(Mn) and this relationship can also be expressed in matrix form as

    𝐯_j(n)    = 𝐃^0_P , M(P-1)+1𝐱_j(Mn),

where

    = 2pt
    =0mu 
    1!𝐱_j(Mn) = [   x_j(M(n-P+1)) x_j(M(n-P+1)+1)               …         x_j(Mn) ]^T.

Further, the vector 𝐱_j(Mn) can be expressed in terms of the input u(n). We start with an assumption that all the analysis filters are causal and have equal length Q. It can be assured by appropriate zero padding. Now we can obtain 𝐱_j(Mn) as

    𝐱_j(Mn) = 𝐇_j 𝐮(Mn),

where 𝐇_j is a convolution matrix. The entire input to the Wiener filter can be expressed as follows:

    = 2mu
    =0mu
    𝐯_s(n) = [   𝐯_0(n);   𝐯_1(n);        ⋮; 𝐯_L-1(n) ]   = [   𝐃^0_P , M(P-1)+1𝐇_0;   𝐃^0_P , M(P-1)+1𝐇_1;                     ⋮; 𝐃^0_P , M(P-1)+1𝐇_L-1 ]𝐮(Mn), 
       = 𝐊𝐮(Mn),

where 𝐊 is a matrix of size LP × [M(P-1)+Q]. Using this result, the auto-correlation matrix 𝐑_vv can be written as

    𝐑_vv   = 𝐊𝐄[𝐮(Mn) 𝐮^H(Mn)] 𝐊^H, 
       = 𝐊𝐑_uu𝐊^H .

Similarly the cross-correlation vector 𝐫_d_i v becomes

    𝐫_d_i v   = 𝐄[u(Mn-i-d) 𝐮^H(Mn)] 𝐊^H, 
       = 𝐫_uu^i+d𝐊^H,

where 𝐫_uu^i+d is a row vector given by

    =2pt
    =0mu
    𝐫_uu^i+d = [                     r_uu(-i-d);                 r_uu(-i-d + 1);                              ⋮; r_uu(-i - d +M(P - 1) + Q - 1) ]^T.

By substituting these results in (<ref>), we obtain

    𝐫_uu^i+d𝐊^H = 𝐚_i^T 𝐊𝐑_uu𝐊^H,      0 ≤ i ≤ M-1.

The resulting equation is of form

    𝐀𝐚_i = 𝐛_i,

where

    𝐀   = ( 𝐊𝐑_uu𝐊^H ) ^T, 
    𝐛_i    = ( 𝐫_uu^i+d𝐊^H ) ^T.

If 𝐀 is invertible, then we have a unique solution. Otherwise, the existence of a solution depends on the nature of the system of equations. If the same is consistent, then all solutions can be expressed as

    𝐚_i = 𝐀^†𝐛_i + (𝐈 -  𝐀^†𝐀) 𝐰,

where 𝐰 is an arbitrary vector. In the next theorem, we prove that the equation always results in a solution. 


For an FIR uniform analysis bank, there will be at least one optimal synthesis bank solution that minimizes the mean-square error. 


We have to prove that the solution given by (<ref>) is always an exact solution of the equation. Substituting the solution in the equation, we obtain

    𝐀𝐚_i    = 𝐀𝐀^†𝐛_i + 𝐀(𝐈 -  𝐀^†𝐀) 𝐰, 
       = 𝐀𝐀^†𝐛_i.

The matrix 𝐀 can be expressed as

    𝐀   = ( 𝐊𝐔Λ𝐔^H 𝐊^H ) ^T, 
       = (𝐊𝐔Λ^1/2)^* (𝐊𝐔Λ^1/2)^T, 
       = 𝐂𝐂^H ,

by performing eigendecomposition of the auto-correlation matrix 𝐑_uu. With this,

    𝐀𝐚_i    =  𝐂𝐂^H (𝐂𝐂^H)^†𝐛_i, 
       = 𝐂𝐂^H (𝐂^H)^†𝐂^†𝐛_i.

Using the pseudoinverse identities <cit.>, the equation reduces to 

    𝐀𝐚_i    = 𝐂𝐂^†𝐛_i, 
       = (𝐊𝐔Λ^1/2 )^* ( (𝐊𝐔Λ^1/2 )^*)^†𝐊^* (𝐫_uu^i+d )^T.

The auto-correlation matrix 𝐑_uu is in general positive definite but always positive semi-definite. We consider the solution of equation under these two cases:


  * Case I: Positive Definite Correlation Matrix

In this case, the auto-correlation matrix is invertible, so is the diagonal matrix Λ. Hence we can process the equation as follows:

    =0mu
    𝐀𝐚_i    = (𝐊𝐔Λ^1/2 )^* ( (𝐊𝐔Λ^1/2 )^*)^†   (𝐊𝐔Λ^1/2 )^*  
           ·(( 𝐔Λ^1/2 )^*)^-1 (𝐫_uu^i+d )^T, 
       = (𝐊𝐔Λ^1/2 )^*  (( 𝐔Λ^1/2 )^*)^-1 (𝐫_uu^i+d )^T, 
       = 𝐛_i.


  * Case II: Positive Semi-Definite Correlation Matrix

The diagonal matrix Λ is not invertible under this case. However we exploit the relation between the vector 𝐫_uu^i+d and the matrix 𝐑_uu. For (i+d) < (M(P-1)+Q), the vector 𝐫^i+d_uu is one of  the row of the correlation matrix. If (i+d) ≥ (M(P-1)+Q), then the vector 𝐫^i+d_uu can still be expressed as a linear combination of the rows of the auto-correlation matrix <cit.>. Thus, we can always express the vector 𝐫^i+d_uu as 

    𝐫^i+d_uu = ∑_j c_j 𝐑_uu(j,:) = ∑_j c_j 𝐔(j,:) Λ𝐔^H,

where 𝐑_uu(j,:) is the j-th row of the correlation matrix. With this, 

    = 2mu
    𝐀𝐚_i    = (𝐊𝐔Λ^1/2 )^* ( (𝐊𝐔Λ^1/2 )^*)^†    (𝐊𝐔Λ^1/2 )^*  
           ·Λ^1/2(∑_j c_j 𝐔(j,:)  )^T ,
       = (𝐊𝐔Λ^1/2 )^* Λ^1/2(∑_j c_j 𝐔(j,:) )^T ,
       = 𝐛_i.

 
We can observe that we have 

    𝐀𝐚_i = 𝐀𝐀^†𝐛_i = 𝐛_i

under both the cases and hence the solution given by (<ref>) is exact. 


From the above theorem, we can conclude that if the matrix 𝐀 is non-invertible, we have infinite number of optimum solutions possible. This gives an opportunity to optimize the synthesis bank for a desired property. 



  §.§.§ Computational Complexity

The computational complexity can be evaluated from various algebraic manipulations required for the solution in (<ref>). To start with, the matrix 𝐀 evaluation needs O(LP(M(P-1)+Q)^2) + O((LP)^2) calculations and its pseudoinverse requires O((LP)^3) calculations. The term (𝐈 - 𝐀^†𝐀) can then be evaluated with O((LP)^3) cost. As the vector 𝐛_i needs to be evaluated for each i ∈ [0, M-1], the total cost of obtaining 𝐛_i's is O(MLP(M(P-1)+Q)). All the products 𝐀^†𝐛_i and (𝐈 - 𝐀^†𝐀)𝐰 can then be obtained with complexity O(M(LP)^2). Therefore, the complexity is quadratic with respect to M and Q, and cubic with respect to L and P. 

Our synthesis filter is multiple-input multiple-output (MIMO) FIR system, thus enabling the operations at the lowest sampling rate. The MIMO implementation brings down the complexity drastically, thereby for each reconstructed output sample, the number of multiplication and additions required are only LP and (LP-1), respectively.





 §.§ Extension to NUFB

The results developed so far for a UFB can be extended for an NUFB case. Before applying Wiener filtering on an NUFB, we convert it into an equivalent UFB with the help of blocking operation. This conversion is needed as Wiener filtering requires joint stationarity of the input and the desired signals <cit.>. Each subband of the NUFB with a decimation factor M_i is blocked with a factor

    k_i = M/M_i,     0 ≤ i < L

where L is the number of subbands and M is the LCM of all decimation factors. The process is shown in Fig. <ref>. An equivalent representation of the process, as shown in Fig. <ref>, can be derived using the noble identities <cit.>. Thus with blocking, the NUFB behaves like a UFB with decimation factor equal to M and with analysis filters given by

    h'_i,l(n) = h_i(n-lM_i),      0 ≤ i < L;      0 ≤ l < k_i.

Now the Wiener synthesis filter for the NUFB can be obtained using (<ref>).



 §.§ Minimum Mean-square Error


We now determine the MSE for a given length of the Wiener filter. The result can be used to choose the length of the synthesis filter based on the desired level of the error. The MSE is defined as

    J    = 𝐄[𝐞^H(n) 𝐞(n)] = ∑_i=0^M-1𝐄[e_i^*(n) e_i(n)] .

Its minimum value is achieved using the Wiener filter and is denoted by J_min. Further, J_min is the sum of channel-wise MSEs which are given by 

    J_min^i    = 𝐄[e_i^*(n) e_i(n)], 
       = 𝐄[e_i^*(n) d_i(n)] - 𝐄[e_i^*(n) y_i(n)] .

Using the principle of orthogonality <cit.>, the above equation reduces to 

    J_min^i    = 𝐄[e_i^*(n) d_i(n)], 
       = 𝐄[d_i^*(n) d_i(n)] - 𝐄[y_i^*(n) d_i(n)], 
       = r_uu(0) - 𝐄[𝐯_s^H(n)𝐚_i^* d_i(n)], 
       = r_uu(0) - 𝐫_d_i v𝐚_i^* .

Substituting the expressions for 𝐫_d_i v and 𝐚_i from (<ref>) and (<ref>), respectively, we obtain

    =0mu
    
    J_min^i    = r_uu(0) - 𝐛_i^T 𝐀^†*𝐛_i^* - ( 𝐛_i - 𝐀^H (𝐀^† )^H 𝐛_i  )^T 𝐰^*, 
       = r_uu(0) - 𝐛_i^T 𝐀^†*𝐛_i^* - ( 𝐛_i - 𝐀𝐀^†𝐛_i  )^T 𝐰^*.
  
The term with the arbitrary vector is zero due to (<ref>) and the equation reduces to 

    J_min^i    = r_uu(0) - 𝐛_i^T 𝐀^†*𝐛_i^*.

This proves that all the solutions for the synthesis bank results in the same MSE, which is intuitive. 



  §.§.§ Optimal Delay

The channel MSE J_min^i depends on the delay d. The same is also observed in our simulation results. The exact form of the relation can be obtained from (<ref>) as

    J_min^i    = r_uu(0) - 𝐫_uu^i+d𝐊^H  ( 𝐊𝐑_uu𝐊^H ) ^†𝐊(𝐫_uu^i+d)^H 
       = r_uu(0) - 𝐫_uu^i+d𝐁(𝐫_uu^i+d)^H

J_min^i can be observed as a quadratic form with the matrix 𝐁 being a Hermitian matrix. If we are interested to obtain an optimal delay value, we can use the existing results <cit.> on the quadratic forms.      

In the following section, we derive the necessary and sufficient conditions on a filter bank for the MSE to be zero. 



§ FIR PERFECT RECONSTRUCTION FILTER BANK


In the following analysis, we prove that the designed synthesis bank can achieve PR provided that the analysis bank satisfies certain condition. To justify PR property for any arbitrary input signal on a strong analytical background, we verify the pseudocirculant property <cit.> for the solution. 



 §.§ Pseudocirculant Property

We evaluate the product 𝐏(z) = 𝐀(z)𝐄(z) in time-domain where 𝐀(z) and 𝐄(z) are the polyphase component matrices for the synthesis bank and the analysis bank, respectively <cit.>. The matrix P(z) is designed as an identity matrix in previous works <cit.>. Our design approach is more general where P(z) satisfies the pseudocirculant property. In time-domain, we obtain the matrix P(z) from convolution of the two matrix filters as

    p_i,j(n) = ∑_r=0^L-1 a_i,r(n) ∗ e_r,j(n),      0 ≤ i,j ≤ M-1 .

In the above equation, the filter e_r,j(n) can be obtained from the analysis filters as <cit.>

    e_r,j(n) = h_r(Mn+j).

As Q is the length of the analysis filters, the length of the filter e_r,j(n) will be at max

    T = ⌈Q/M⌉.

By zero padding, we ensure that all the constituent filters of the polyphase filter 𝐄(n) have the same length T. With that, the convolution given in (<ref>) can be expressed in matrix form using (<ref>) as

    𝐩_i,j = ∑_r=0^L-1𝐄̃_r,j𝐚_i,r ,

where 𝐄̃_r,j is a convolution matrix of size (P+T-1) × P. We like to express this convolution matrix in terms of the analysis filter h_r(n). For that, we use a polyphase identity, as shown in Fig. <ref>, obtained from the existing result <cit.> by finding the 0-th polyphase component of a time-advanced filter h_r(n+j).

Using this identity, we obtain the following relation

    𝐄̃_r,j   = 𝐃_P+T-1 , M(P-1)+Q^j 𝐇̃_r (𝐃_P , M(P-1)+1^0)^T, 
       = 𝐃_P+T-1 , M(P-1)+Q^j 𝐇_r^T (𝐃_P , M(P-1)+1^0)^T, 
       = 𝐃_P+T-1 , M(P-1)+Q^j ( 𝐃_P , M(P-1)+1^0 𝐇_r )^T .

It can be seen that Fig. <ref> contains a combination of upsampling, filtering, time-advance and downsampling. Even then the matrix representations developed in this paper for various multirate operations have been successfully applied to deal with it. Continuing forward, we use the above relation in (<ref>) and obtain

    𝐩_i,j   = 𝐃_P+T-1 , M(P-1)+Q^j ∑_r=0^L-1( 𝐃_P , M(P-1)+1^0 𝐇_r )^T 𝐚_i,r, 
       = 𝐃_P+T-1 , M(P-1)+Q^j 𝐊^T 𝐚_i .

Next we derive a necessary and sufficient condition, in the form of a theorem, for the analysis and synthesis banks of a filter bank to result in PR.


An FIR uniform filter bank is PR if and only if

    𝐊^T 𝐚_i = c 𝐞_i+d,

where c is a non-zero constant and the column vector  𝐞_i+d is defined as follows:

    e_i+d (l) = 
    1,        if  l = i+d 
    
    0,        otherwise.



The proof follows the Vaidyanathan's well-known pseudocirculant property. A PR filter bank must satisfies the generalized pseudocirculant condition given by <cit.>

    𝐏(z) = c z^-n_0[       0   𝐈_M-r; z^-1𝐈_r       0 ].

We have evaluated 𝐏(z) in time-domain and next we find conditions for it to be pseudocirculant. Let 𝐊^T 𝐚_i = 𝐬_i, then (<ref>) becomes

    =0mu
    =2pt
    𝐩_i,j = [          s_i(j)        s_i(j+M)               … s_i(j+M(P+T-2)) ]^T.

If the matrix filter 𝐏(z) is pseudocirculant, then the following properties are true in time-domain:


  * Property 1: In a row, only one 𝐩_i,j is non-zero i.e. only one out of 𝐩_i,0, 𝐩_i,1, …, 𝐩_i,M-1 is non-zero.

  * Property 2: In a column, only one 𝐩_i,j is non-zero i.e. only one out of 𝐩_0,j, 𝐩_1,j, …, 𝐩_M-1,j is non-zero.

  * Property 3: For a vector 𝐩_i,j, at most one entry is non-zero.

  * Property 4: All the entries on upper-left to lower-right diagonals are the same i.e.

    𝐩_i+1,j+1 = 𝐩_i,j,      0 ≤ i,j ≤ M-2.


  * Property 5: The first column will have 

    =0mu
    
    p_i+1,0(l)    = 
    0,        if  l = 0 
    
    p_i,M-1(l-1),        otherwise, 
            0 ≤ i ≤ M-2.


The above properties will result in the following constraints on the vector 𝐬_i:
 

  * Property 1 implies that only one vector 

    = 2mu
    =0mu
    =1pt
    𝐩_i,j   = 
    [          s_i(j)        s_i(j+M)               … s_i(j+M(P+T-2)) ]^T, 
            0 ≤ j < M

is non-zero in a row. Further, Property 3 means that only one element of the non-zero vector is non-zero. Together these two conditions imply that only one element of the vector 𝐬_i is non-zero. Assume that 𝐩_i,j≠ 0 for j = j_i and
p_i,j_i(l_i) = s_i(j_i + Ml_i) ≠ 0, then we can express

    𝐬_i = c_i 𝐞_j_i + Ml_i.


  * Property 4 results in

    = 2mu
    =0mu
    
    s_i+1(Ml+j+1)    = s_i(Ml+j),      0 ≤ j ≤ M-2; 
            0 ≤ l ≤ P+T-2.

From the above equation, all the elements of the vector 𝐬_i+1, except at indices that are multiples of M, 
can be obtained from the vector 𝐬_i.

  * Property 5 implies 

    p_i+1,0(0) = s_i+1(0)  = 0,      0 ≤ i ≤ M-2.

Another implication is that 

    s_i+1(Ml) = s_i(Ml-1).

Combining the two results (<ref>) and (<ref>), we get

    s_i+1(l) = 
    0,         l = 0, 
    
    s_i(l-1),        otherwise.

Thus the vector 𝐬_i+1 is just a shifted version of the vector 𝐬_i. 

The last constraint implies that all the vectors 𝐬_i can be obtained from a single vector  𝐬_0. If the vector 𝐬_0 has form  

    𝐬_0 = c 𝐞_Ml_0 + j_0 = c 𝐞_d_0,
 
then all the vectors 𝐬_i can be expressed as

    𝐬_i = c 𝐞_i+d_0,      0 ≤ i ≤ M-1.

Due to the above equation, we have

    𝐩_i,j = c 𝐃_P+T-1 , M(P-1)+Q^j 𝐞_i+d_0 .

In z-domain, this means that

    𝐏(z) = c z^-l_0[         0   𝐈_M-j_0; z^-1𝐈_j_0         0 ]

and the reconstructed output is û(n) = cu(n-d_0-M+1). One can easily see that the variable d_0 is the same as the delay d in the desired signal path.

It is to be noted that the above theorem puts restriction on both the analysis and synthesis banks. It may happen that a solution may not exist for the synthesis bank to result in PR. We will first obtain a parameterization of all PR solutions for the synthesis bank and later derive necessary & sufficient conditions for the same to exist. 



 §.§ Parametric Form for PR Solutions

In the previous subsection, we obtained the following condition on the analysis and synthesis banks to have PR:

    𝐊^T 𝐚_i = c 𝐞_i+d,      0 ≤ i < M.

The above equation is of form 

    𝐀𝐚_i = 𝐛_i

and thus represents a system of equations. If the same is consistent, then all the PR solutions for the synthesis bank are given by

    𝐚_i    = 𝐀^†𝐛_i + (𝐈 - 𝐀^†𝐀)𝐰, 
       = c(𝐊^†)^T 𝐞_i+d + (𝐈 - 𝐊𝐊^†)^T 𝐰,

where 𝐰 is an arbitrary vector. We can observe that the solutions have turned out to be independent of the input signal. 



 §.§ Necessary and Sufficient Conditions on Analysis Bank and Delay

In order for a PR solution to exist, the analysis bank has to satisfy certain condition. We present the same in the form of a theorem about the matrix 𝐊 which represents the analysis bank.
 
For an FIR uniform analysis bank, at least one PR synthesis bank solution is possible if the matrix 𝐊 satisfies the relation

    =0mu
     = 0mu
    =1pt
    0.88!𝐊^†𝐊 = 𝐈 + [             𝐁_p × p             0_p × r       𝐂_p × (q-p-r);             0_r × p             0_r × r       0_r × (q-p-r);     𝐂^H_p × (q-p-r)       0_(q-p-r) × r 𝐃_(q-p-r) × (q-p-r) ],

where 0_r × r is the largest zero sub-block possible with r ≥ M, and 𝐁_p × p, 𝐃_(q-p-r) × (q-p-r) and 𝐂_p × (q-p-r) are arbitrary matrices with the first two being Hermitian.

   
We require the system of linear equations given by 

    𝐊^T 𝐚_i = c 𝐞_i+d

to be consistent to have an exact solution. In order to obtain the condition for that, we substitute a PR solution in the above equation and obtain 

    c ( 𝐊^†𝐊)^T 𝐞_i+d + ( 𝐊 - 𝐊𝐊^†𝐊)^T 𝐰   = c 𝐞_i+d.

Using the fact that 𝐊𝐊^†𝐊 = 𝐊, the equation simplifies to

    ( ( 𝐊^†𝐊)^T - 𝐈) 𝐞_i+d   = 0,      0 ≤ i ≤ M-1 .

If the matrix 𝐊^†𝐊 is of dimension q × q, then in order for the above equation to be satisfied, we require

    (𝐊^†𝐊)^H = 𝐈 + [       𝐗_q × p       0_q × r 𝐘_q × (q-p-r) ],

where p ≤ d, r ≥ M, and 𝐗_q × p and 𝐘_q × (q-p-r) are arbitrary matrices of dimensions q × p and q × (q-p-r), respectively. As 𝐊^†𝐊 is a Hermitian matrix, we have

    [       𝐗_q × p       0_q × r 𝐘_q × (q-p-r) ] = [       𝐗^H_q × p;         0_r × q; 𝐘^H_q × (q-p-r) ].

Thus the two matrices 𝐗_q × p and 𝐘_q × (q-p-r) have following form:

    𝐗_q × p = [         𝐁_p × p;         0_r × p; 𝐂^H_p × (q-p-r) ]

and 

    𝐘_q × (q-p-r) = [       𝐂_p × (q-p-r);       0_r × (q-p-r); 𝐃_(q-p-r) × (q-p-r) ],

where matrices 𝐁_p × p and 𝐃_(q-p-r) × (q-p-r) are Hermitian matrices. Hence the condition on the matrix 𝐊 becomes

    =1pt
     = 0mu
    =0mu
    0.88!𝐊^†𝐊 = 𝐈 + [             𝐁_p × p             0_p × r       𝐂_p × (q-p-r);             0_r × p             0_r × r       0_r × (q-p-r);     𝐂^H_p × (q-p-r)       0_(q-p-r) × r 𝐃_(q-p-r) × (q-p-r) ].


The PR requirement imposes the following condition on the desired signal delay d. 

With an analysis bank matrix 𝐊 satisfying the above condition, PR is possible only when the delay d is in the range: 

    p ≤ d ≤ p+r-M.



The proof easily follows from the equations (<ref>) and (<ref>). 

The above lemma together with Theorem <ref> constitute the necessary and sufficient conditions for a PR synthesis solution to exist. The lemma points that with suitable delay, PR is achievable for an analysis bank which is otherwise not possible. This way we have attempted to expand the space of PR FIR filter banks. Further, we can have PR for a number of delay values which gives an opportunity to use delay as an optimization parameter, based on various design criterion like Hermitian symmetry, time or frequency localization <cit.>, coding gain <cit.>, etc. For this, the number of channels required is L > M and the channels should satisfy the PR condition given by Theorem <ref>. For a fixed delay, it is an unconstrained problem with respect to the arbitrary vector 𝐰 <cit.>. The required optimized solution can  be selected among the solutions for various delays by imposing an additional constraint. Design specific constraints and their solutions can be considered for future work. 

It can be seen that the matrix 𝐊 easily satisfy the PR condition if it has full column rank. The PR condition induces certain restriction on its null space which is given by the following lemma. 

For a PR UFB, the analysis bank matrix 𝐊 has a null space spanned by the following set of vectors:

    𝐳 = [      𝐟_ 1 × p       0_1 × r 𝐠_1 × (q-p-r);               ]^T,

where 𝐟_ 1 × p and 𝐠_1 × (q-p-r) are arbitrary vectors. 

 
The matrix 𝐊 represents the analysis bank of a filter bank. Hence, when an input signal u(n) is applied to the analysis bank, the resulting subband vector can be obtained as

    𝐯_s(n) = 𝐊𝐮̅(Mn).

Consider a case where  the vector 𝐮̅(Mn) lies in the null space of the matrix 𝐊. As a result, the vector 𝐯_s(n) as well as the output of the synthesis bank, both are zero. The reconstructed signal is then 

    û(Mn+i) = y_M-1-i(n) = 0,      0 ≤ i < M.

For PR, we require

    û(n) = u(n-d-M+1).

Combining the two, we get

    = 2mu
     = 0mu  
    û(Mn+i) = u(Mn+i-d-M+1) = 0 ,      0 ≤ i ≤ M-1.

Thus the vector 𝐮̅(Mn) should be of form

    = 0mu
     = 0mu  
     = 1pt
    𝐮̅(Mn) = [         [u(Mn)        u(Mn-1)              …      u(Mn-d+1)        0_1 × M;                     u(Mn-d-M)              … u(Mn-q+1) ]^T. ]
 
A basis vector for the null space of the matrix 𝐊 should satisfy the above condition for all possible values of d and hence should have the form

    𝐳 = [      𝐟_ 1 × p       0_1 × r 𝐠_1 × (q-p-r);               ]^T,

where 𝐟_ 1 × p and 𝐠_1 × (q-p-r) are arbitrary vectors. 

In this section, we presented various necessary and sufficient conditions for a PR synthesis bank solution to exist. In the next section, we present some experiments which validates our results. 




§ EXPERIMENTAL RESULTS


In this section, we verify the derived results with a number of experiments. These experiments are chosen to demonstrate the wide scope of application of our design. In Experiment 1, we obtain the MSE for various delay values in the desired signal and compare the results. We present the improvement in reconstruction, in terms of the MSE, with addition of a new subband in Experiment 2. We also examine the impact of delay on PR. In Experiment 3, a PR non-uniform filter bank obtained through our design is verified with a non-stationary input signal. 


 §.§ Experiment 1

We consider a 2-channel maximally decimated uniform analysis bank designed using fir1 routine of Matlab with the following parameters: the analysis filter h_0(n) is low-pass filter with cut-off 0.6 and length 9, and h_1(n) is high-pass filter with cut-off 0.4 and length 10. The input to the filter bank is a zero mean, unit variance second-order autoregressive(AR(2)) process with coefficients 0.7 and 0.1. We choose the length of the constituent filters of the matrix synthesis filter to be 11 and design the filter for various delay values using (<ref>). We obtain ensembled-averages of the channel-wise squared errors, shown in Figs. <ref> and  <ref>, for these synthesis filters by performing 200 independent runs. The corresponding theoretical values, obtained using (<ref>), are provided in Table <ref>. It is to be mentioned here that the analysis bank does not satisfy Theorem <ref>. We can see that the observed error values  are closer to the theoretical values for both channels. Further, we can notice that the best result among the selected delay values, in terms of the total MSE, is with delay 10. This shows that a better reconstruction can be obtained if some delay in the reconstructed output is acceptable. 





 §.§ Experiment 2

In this experiment, we examine the effect of number of subbands on the MSE along with the role of delay in achieving PR. We consider an Extended Lapped Transform (ELT) filter bank with decimation factor M=4 and overlapping factor K'=2. The prototype filter for ELT is designed using the optimized butterflies angles mentioned in <cit.>. The input signal to the filter bank is a realization of an AR(1) process with coefficient 0.95, zero mean and unit variance. The length of the synthesis filter is 4 and the delay is 10. We vary the number of subbands (L) available to the synthesis filter and obtain the MSE for each channel. On analyzing the obtained results, as given in Table <ref>, we can conclude that for number of subbands L < 4, there is a variation in the MSE with subbands chosen. However independent of the choice of subbands, if we add additional subband to the system, then we always see an improvement in the total MSE as well as in the channel-wise MSEs. This is possible since we have exploited the correlation between the input signal components while designing the matrix synthesis filter. With the number of subbands L = 4, the analysis bank satisfies the PR condition given by Theorem <ref>. We vary the delay and find out that PR is possible only with d=12. This is consistent with the range of delay values provided by (<ref>).





 §.§ Experiment 3

In this experiment, we design a PR synthesis bank for a non-uniform analysis bank and test it with a non-stationary input signal. We have the following setup:



    M_0    = 2,     h_0(n)    = {-0.1295, -0.12,0.3695,0.5018, 
              0.3695,-0.12,-0.1295} ,
    
    M_1    = 3,     h_1(n)    = {0.1308, 0.1728,-0.3775,0.2117, 
              0.2117,-0.3775,0.1728, 0.1308}, 
    
    M_2    = 6,     h_2(n)    = {0.0717, 0.0749,-0.1148,0.1659, 
              -0.2069,0.2224,-0.2069, 0.1659,-0.1148, 
              0.0749,0.0717}, 
    
    M_3    = 6,     h_3(n)    = {0.0881, 0.1617,-0.1686,-0.1538, 
              0.1752,0.1752,-0.1538, -0.1686, 
              0.1617,0.0881}.

The analysis filters are designed using Parks-McClellan algorithm. We convert the NUFB into an equivalent UFB with the help of blocking operation. The resulting UFB has decimation factor equal to 6 and the following analysis filters:



    g_0(n)    = h_0(n),     g_1(n)    = h_0(n-2),     g_2(n)    = h_0(n-4), 
    
    g_3(n)    = h_1(n),     g_4(n)    = h_1(n-3),     g_5(n)    = h_2(n), 
    
    g_6(n)    = h_3(n).

We choose the length of the synthesis filter to be 7 and delay d = 0. The resulting matrix 𝐊 satisfies the PR condition (<ref>) and using (<ref>), we obtain a PR solution with 𝐰 = 0. We apply a non-stationary signal generated using (n) sin(0.1n^2) to the filter bank and evaluate the reconstruction error as (refer Fig. <ref>):

    e(n) = |û(n) - d(n-M+1)|.

Fig. <ref> shows the resulting error versus time curve. The small error which we obtain is due to finite precision in MATLAB. 




§ CONCLUSION


We have addressed an important problem of designing an optimal FIR synthesis bank for a given non-maximally decimated analysis bank. To design such a synthesis bank, a framework was developed to apply matrix Wiener filtering to the problem and solution is obtained for a given length of synthesis filter and delay in the reconstructed output. We experimentally showed that better MSE can be obtained in some cases by adding appropriate delay in the reconstructed output. We found that the reconstruction error keeps decreasing as more and more multirate observations are added for a signal. The matrix representation developed in this paper can be utilized to carry out time-domain analysis of any multirate circuit. The infinite number of PR or non-PR synthesis bank solutions possible with our design can be optimized for a desired property in a future work. 


























[FIR Matrix Wiener Filter Derivation]

Consider an optimum matrix filtering problem as shown in Fig. <ref> where the vector signal 𝐯(n) is the input and the signal 𝐝(n) is an estimate of the desired signal. In order to obtain the Wiener solution, the input and desired signals are assumed to be jointly stationary <cit.>. The Wiener solution can be derived for either FIR or IIR case. Here we derive the FIR Wiener solution for a matrix filter whose constituent filters are causal and of length P. 

We begin by applying the principle of orthogonality <cit.> to the setup and obtain

    = 0mu
    𝐄[e_i(n) v_j^*(n-k)]    = 0,      0 ≤ i < M; 
          0 ≤ j < L;        0 ≤ k < P.

The above equation can be written as

    = 3mu
    =0mu
    𝐄[d_i(n) v_j^*(n-k)]    = 𝐄[y_i(n) v_j^*(n-k)] 
       = ∑_r=0^L-1∑_l=0^P-1 a_i,r(l) 𝐄[v_r(n-l)v_j^*(n-k)].

As the input and desired signals are jointly stationary, we can write

    r_d_i v_j(k) = ∑_r=0^L-1∑_l=0^P-1 a_i,r(l) r_v_r v_j(k-l) .

The above equation can be expressed in matrix form as

    = 2mu
    𝐫_d_i v_j = ∑_r=0^L-1𝐚_i,r^T 𝐑_v_r v_j,      0 ≤ i < M;      0 ≤ j < L,

where




    𝐫_d_i v_j   = [   r_d_i v_j(0)   r_d_i v_j(1)              … r_d_i v_j(P-1) ], 
    𝐚_i,r   = [   a_i,r(0)   a_i,r(1)          … a_i,r(P-1) ]^T, 
    𝐑_v_r v_j   = [    r_v_r v_j(0)    r_v_r v_j(1)               …  r_v_r v_j(P-1);   r_v_r v_j(-1)    r_v_r v_j(0)               …  r_v_r v_j(P-2);               ⋮               ⋮               ⋱               ⋮; r_v_r v_j(-P+1) r_v_r v_j(-P+2)               …    r_v_r v_j(0) ].

A further compact form is

    𝐫_d_i v = 𝐚_i^T 𝐑_v v,      0 ≤ i ≤ M-1,

where

    𝐫_d_i v   = [   𝐫_d_i v_0   𝐫_d_i v_1           … 𝐫_d_i v_L-1 ], 
    𝐚_i   = [   𝐚_i,0^T   𝐚_i,1^T         … 𝐚_i,L-1^T ]^T, 
    𝐑_v v   = [     𝐑_v_0 v_0     𝐑_v_0 v_1             …   𝐑_v_0 v_L-1;     𝐑_v_1 v_0     𝐑_v_1 v_1             …   𝐑_v_1 v_L-1;             ⋮             ⋮             ⋱             ⋮;   𝐑_v_L-1 v_0   𝐑_v_L-1 v_1             … 𝐑_v_L-1 v_L-1 ] .

The obtained result is a system of equations containing LP equations in terms of LP unknowns. These are the Wiener-Hopf equations for the matrix Wiener filter. Using them, we can determine the i-th row of the matrix Wiener filter.




























IEEEtran




10

url@samestyle








jn:strelafb
V. Strela, P. Heller, G. Strang, P. Topiwala, and C. Heil, “The application of
  multiwavelet filterbanks to image processing,” IEEE Trans. Image
  Process., vol. 8, no. 4, pp. 548–563, Apr. 1999.

jn:ChengDFB
K.-O. Cheng, N.-F. Law, and W.-C. Siu, “Multiscale directional filter bank
  with applications to structured and random texture retrieval,” Pattern
  Recognition, vol. 40, no. 4, pp. 1182–1194, 2007.

jn:HsiangVideoFB
S.-T. Hsiang and J. W. Woods, “Embedded video coding using invertible motion
  compensated 3-D subband/wavelet filter bank,” Signal Process.: Image
  Commun., vol. 16, no. 8, pp. 705–724, 2001.

jn:cognitivefb
B. Farhang-Boroujeny, “Filter bank spectrum sensing for cognitive radios,”
  IEEE Trans. Signal Process., vol. 56, no. 5, pp. 1801–1811, May 2008.

jn:CruzRoldn
F. Cruz-Roldán and M. Blanco-Velasco, “Joint use of DFT filter banks
  and modulated transmultiplexers for multicarrier communications,”
  Signal Process., vol. 91, no. 7, pp. 1622–1635, 2011.

jn:shynk
J. Shynk, “Frequency-domain and multirate adaptive filtering,” IEEE
  Signal Processing Mag., vol. 9, no. 1, pp. 14–37, Jan. 1992.

jn:radar_xu
J. Xu, J. Yu, Y.-N. Peng, and X.-G. Xia, “Radon-fourier transform for radar
  target detection, I: Generalized doppler filter bank,” IEEE Trans.
  Aerosp. Electron. Syst., vol. 47, no. 2, pp. 1186–1202, Apr. 2011.

conf:qmf_first_paper
D. E. A. Crosier and C. Galand, “Perfect channel splitting by use of
  interpolation/ decimation techniques,” in Int. Conf. Inform. Sci.
  Syst., vol. 2, Patras, Greece, 1976.

jn:vaid_mqmf
P. Vaidyanathan, “Theory and design of M-channel maximally decimated
  quadrature mirror filters with arbitrary M, having the
  perfect-reconstruction property,” IEEE Trans. Acoust., Speech, Signal
  Process., vol. 35, no. 4, pp. 476–492, Apr. 1987.

jn:vaid_assp_mag
——, “Quadrature mirror filter banks, M-band extensions and
  perfect-reconstruction techniques,” IEEE ASSP Mag., vol. 4, no. 3,
  pp. 4–20, July 1987.

jn:xie_nufb_adv
X. Xie, S. Chan, and T. Yuk, “Design of perfect-reconstruction nonuniform
  recombination filter banks with flexible rational sampling factors,”
  IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 52, no. 9, pp.
  1965–1981, Sept. 2005.

conf:hoang
P.-Q. Hoang and P. P. Vaidyanathan, “Non-uniform multirate filter banks:
  theory and design,” in IEEE Int. Symp. Circuits Syst., vol. 1, May
  1989, pp. 371–374.

conf:nayebi_nufb_timed
K. Nayebi, T. P. Barnwell, and M. Smith, “The design of perfect
  reconstruction nonuniform band filter banks,” in Proc. ICASSP, 91,
  Apr. 1991, pp. 1781–1784 vol.3.

jn:gadre
V. M. Gadre and R. K. Patney, “Some novel multirate architectures for
  filter realization with reduced multiplicative complexity,” IEEE
  Trans. Signal Process., vol. 42, no. 9, pp. 2492–2495, Sept. 1994.

jn:vetterli_nufb
J. Kovacevic and M. Vetterli, “Perfect reconstruction filter banks with
  rational sampling factors,” IEEE Trans. Signal Process., vol. 41,
  no. 6, pp. 2047–2066, June 1993.

conf:Akkarakaran
S. Akkarakaran and P. P. Vaidyanathan, “New results and open problems on
  nonuniform filter-banks,” in Proc. ICASSP99, vol. 3, Mar. 1999, pp.
  1501–1504.

jn:modulated_nufb
B. W. Ling, C. Y. Ho, K. Teo, W. Siu, J. Cao, and Q. Dai, “Optimal
  design of cosine modulated nonuniform linear phase FIR filter bank via both
  stretching and shifting frequency response of single prototype filter,”
  IEEE Trans. Signal Process., vol. 62, no. 10, pp. 2517–2530, May
  2014.

jn:acoustic
R. C. Nongpiur and D. J. Shpak, “Maximizing the signal-to-alias ratio in
  non-uniform filter banks for acoustic echo cancellation,” IEEE Trans.
  Circuits Syst. I, Reg. Papers, vol. 59, no. 10, pp. 2315–2325, Oct. 2012.

jn:LoT_malvar
H. Malvar, “Lapped transforms for efficient transform/subband coding,”
  IEEE Trans. Acoust., Speech, Signal Process., vol. 38, no. 6, pp.
  969–978, June 1990.

jn:genlot
R. de Queiroz, T. Nguyen, and K. Rao, “The GenLOT: generalized linear-phase
  lapped orthogonal transform,” IEEE Trans. Signal Process., vol. 44,
  no. 3, pp. 497–507, Mar. 1996.

jn:malvar_fast_elt
H. Malvar, “Extended lapped transforms: properties, applications, and fast
  algorithms,” IEEE Trans. Signal Process., vol. 40, no. 11, pp.
  2703–2714, Nov. 1992.

jn:vetterli_fir_pr
M. Vetterli and D. Le Gall, “Perfect reconstruction FIR filter banks: some
  properties and factorizations,” IEEE Trans. Acoust., Speech, Signal
  Process., vol. 37, no. 7, pp. 1057–1071, July 1989.

jn:duval
J. Gauthier, L. Duval, and J. Pesquet, “Optimization of synthesis oversampled
  complex filter banks,” IEEE Trans. Signal Process., vol. 57,
  no. 10, pp. 3827–3843, Oct. 2009.

jn:bolc_OFB_cosinepf
H. Bölcskei and F. Hlawatsch, “Oversampled cosine modulated filter banks
  with perfect reconstruction,” IEEE Trans. Circuits Syst. II, Analog
  Digit. Signal Process., vol. 45, no. 8, pp. 1057–1071, Aug. 1998.

jn:duhamel
F. Labeau, J.-C. Chiang, M. Kieffer, P. Duhamel, L. Vandendorpe, and B. Macq,
  “Oversampled filter banks as error correcting codes: theory and impulse
  noise correction,” IEEE Trans. Signal Process., vol. 53, no. 12,
  pp. 4619–4630, Dec. 2005.

jn:johansson2007flexible
H. Johansson and P. Löwenborg, “Flexible frequency-band reallocation
  networks using variable oversampled complex-modulated filter banks,”
  EURASIP J. Appl. Signal Process., vol. 2007, no. 1, pp. 143–143,
  2007.

jn:OFBAppLiu
Q. Liu, B. Champagne, and D. K. C. Ho, “Simple design of oversampled uniform
  DFT filter banks with applications to subband acoustic echo cancellation,”
  Signal Process., vol. 80, no. 5, pp. 831–847, 2000.

jn:OFBRahimi
S. Rahimi and B. Champagne, “Oversampled perfect reconstruction DFT
  modulated filter banks for multi-carrier transceiver systems,” Signal
  Process., vol. 93, no. 11, pp. 2942–2955, 2013.

jn:Cvetkovic
Z. Cvetković and M. Vetterli, “Oversampled filter banks,” IEEE
  Trans. Signal Process., vol. 46, no. 5, pp. 1245–1255, May 1998.

jn:bolcskeiframe
H. Bölcskei, F. Hlawatsch, and H. G. Feichtinger, “Frame-theoretic
  analysis of oversampled filter banks,” IEEE Trans. Signal Process.,
  vol. 46, no. 12, pp. 3256–3268, Dec. 1998.

conf:undersampled_compressive
L. Gan, “Block compressed sensing of natural images,” in 15th Int.
  Conf. Digital Signal Process., Jul. 2007, pp. 403–406.

jn:dsp_graph
A. Sandryhaila and J. M. F. Moura, “Discrete signal processing on graphs,”
  IEEE Trans. Signal Process., vol. 61, no. 7, pp. 1644–1656, Apr.
  2013.

jn:vetterli_mfb
M. Vetterli, “A theory of multirate filter banks,” IEEE Trans. Acoust.,
  Speech, Signal Process., vol. 35, no. 3, pp. 356–372, Mar. 1987.

conf:rothweiler
J. Rothweiler, “Polyphase quadrature filters–a new subband coding
  technique,” in ICASSP '83, vol. 8, Apr. 1983, pp. 1280–1283.

jn:analog-digital-conversion
S. R. Velazquez, T. Q. Nguyen, and S. R. Broadstone, “Design of hybrid filter
  banks for analog/digital conversion,” IEEE Trans. Signal Process.,
  vol. 46, no. 4, pp. 956–967, Apr. 1998.

1198100
W. Namgoong, “A channelized digital ultrawideband receiver,” IEEE
  Trans. Wireless Commun., vol. 2, no. 3, pp. 502–510, May 2003.

6334306
R. A. Elliot, M. A. Enderwitz, F. Darbari, L. H. Crockett, S. Weiss, and R. W.
  Stewart, “Efficient TV white space filter bank transceiver,” in
  Proc. 20th European Signal Process. Conf. (EUSIPCO), Aug. 2012, pp.
  1079–1083.

Weiss2006
S. Weiss, S. Redif, T. Cooper, C. Liu, P. D. Baxter, and J. G. McWhirter,
  “Paraunitary oversampled filter bank design for channel coding,”
  EURASIP J. Appl. Signal Process., vol. 2006, pp. 99–99, Jan. 2006.

jn:speech_enhancement_wu
W.-R. Wu and P.-C. Chen, “Subband kalman filtering for speech enhancement,”
  IEEE Trans. Circuits Syst. II, Analog Digit. Signal Process., vol. 45,
  no. 8, pp. 1072–1083, Aug. 1998.

conf:afonso_ecg
V. X. Afonso, W. J. Tompkins, T. Q. Nguyen, and S. Luo, “Multirate processing
  of the ECG using filter banks,” in Computers in Cardiology 1996,
  Sept. 1996, pp. 245–248.

jn:lee_nlms
K. A. Lee and W. S. Gan, “Improving convergence of the NLMS algorithm using
  constrained subband updates,” IEEE Signal Process. Lett., vol. 11,
  no. 9, pp. 736–739, Sept. 2004.

conf:duval_seismic
L. Duval and T. Tanaka, “Denoising of seismic signals with oversampled filter
  banks,” in Proc. ICASSP '03, vol. 6, Apr. 2003, pp. VI–189–92.

jn:jahromisensor
O. S. Jahromi and P. Aarabi, “Theory and design of multirate sensor arrays,”
  IEEE Trans. Signal Process., vol. 53, no. 5, pp. 1739–1753, May
  2005.

conf:scrofani_icassp
J. Scrofani and C. Therrien, “A stochastic multirate signal processing
  approach to high-resolution signal reconstruction,” in Proc. IEEE
  ICASSP '05, vol. 4, Mar. 2005, pp. 561–564.

conf:therrien_prediction
C. W. Therrien, “Multirate linear prediction,” in 13th European Signal
  Process. Conf., Sept. 2005, pp. 1–4.

jn:tdoa_gedalyahu
K. Gedalyahu and Y. C. Eldar, “Time-delay estimation from low-rate samples: A
  union of subspaces approach,” IEEE Trans. Signal Process., vol. 58,
  no. 6, pp. 3017–3031, June 2010.

conf:jahromi_tdoa
O. Jahromi and P. Aarabi, “Time delay estimation and signal reconstruction
  using multi-rate measurements,” in Proc. ICME '03, vol. 2, July 2003,
  pp. II–597.

5278497
Y. Wang, G. Leus, and A. Pandharipande, “Direction estimation using
  compressive sampling array processing,” in 2009 IEEE/SP 15th Workshop
  on Statistical Signal Processing, Aug. 2009, pp. 626–629.

conf:kuchler
R. J. Kuchler and C. W. Therrien, “Optimal filtering with multirate
  observations,” in Conf. Rec. 37th Asilomar Conf. Signals, Syst.
  Comput., vol. 1, Nov. 2003, pp. 1208–1212.

conf:chen
P. P. Vaidyanathan and T. Chen, “Statistically optimal synthesis banks for
  subband coders,” in Conf. Rec. 28th Asilomar Conf. Signals, Syst.
  Comput., vol. 2, Nov. 1994, pp. 986– 990.

jn:chen_multirate_kalman
B.-S. Chen, C.-W. Lin, and Y.-L. Chen, “Optimal signal reconstruction in noisy
  filter bank systems: multirate kalman synthesis filtering approach,”
  IEEE Trans. Signal Process., vol. 43, no. 11, pp. 2496–2504, Nov.
  1995.

jn:chen_kalman_nufb
Y.-M. Cheng and B.-S. Chen, “Nonuniform filter bank design with noises,”
  IEEE Trans. Signal Process., vol. 46, no. 9, pp. 2326–2344, Sept.
  1998.

conf:kalman_2D
J. Ni, K. Ho, K. Tse, J. Ni, and M. Shen, “Multirate kalman filtering approach
  for optimal two-dimensional signal reconstruction from noisy subband
  systems,” in Proc. ICIP, 1997, vol. 1, Oct. 1997, pp. 157–160.

conf:vikalo_hinf
H. Vikalo, B. Hassibi, and T. Kailath, “On H^∞ optimal signal
  reconstruction in noisy filter banks,” in Proc. IEEE ICASSP, 1999,
  vol. 3, Mar. 1999, pp. 1493–1496.

conf:vikalo_mixedh2hinf
——, “Mixed H^2/H^∞ optimal signal reconstruction in noisy
  filter banks,” in Proc. IEEE ICASSP, 2000, vol. 1, 2000, pp.
  500–503.

conf:bora_hinf
S. Bora, R. Dhuli, and B. Lall, “Mixed H^2/H^∞ design of
  non-uniform filter banks using an efficient realisation of synthesis stage,”
  in Annual IEEE India Conference (INDICON), Dec. 2010, pp. 1–4.

conf:hawes_leastsqu
C. Therrien and A. Hawes, “Least squares optimal filtering with multirate
  observations,” in Conf. Rec. 36th Asilomar Conf. Signals, Syst.
  Comput., vol. 2, Nov. 2002, pp. 1782–1786.

conf:chai_ssim
L. Chai, Y. Sheng, and J. Zhang, “Design of synthesis filter banks for the
  structural similarity index,” in 20th ICIP, Sept. 2013, pp. 849–853.

5605572
E. M. Ekşioğlu, A. K. Tanc, and A. H. Kayran, “A compressive sensing
  framework for multirate signal estimation,” in 10th ISSPA 2010, May
  2010, pp. 716–719.

conf:hawes_adaptive
A. Hawes and C. Therrien, “LMS adaptive filtering with multirate
  observations,” in Conf. Rec. 37th Asilomar Conf. Signals, Syst.
  Comput., vol. 1, Nov. 2003, pp. 567–570.

jn:delopoulos
A. Delopoulos and S. Kollias, “Optimal filter banks for signal reconstruction
  from noisy subband components,” IEEE Trans. Signal Process., vol. 44,
  no. 2, pp. 212–224, Feb. 1996.

conf:tanc_adaptive
A. Tanc, E. Eksioglu, and A. Hamdi Kayran, “Adaptive multirate signal
  estimation with lattice orthogonalization,” in 16th ICECS 2009, Dec.
  2009, pp. 117–119.

jn:jahromiesti3e
O. S. Jahromi, B. A. Francis, and R. H. Kwong, “Spectrum estimation using
  multirate observations,” IEEE Trans. Signal Process., vol. 52,
  no. 7, pp. 1878–1890, July 2004.

jn:Tanc201093
A. Tanc and A. Kayran, “Iterative maximum entropy power spectrum estimation
  for multirate systems,” AEU-Int. J. Electron. Commun., vol. 64,
  no. 2, pp. 93–98, 2010.

conf:amini_homotopy
A. Amini, M. Takyar, and T. Georgiou, “A homotopy approach for multirate
  spectrum estimation,” in Proc. IEEE ICASSP, 2006, vol. 3, May 2006,
  pp. 532–535.

conf:JahromiInformation
O. S. Jahromi, R. H. Kwong, and B. A. Francis, “Information theory of
  multirate systems,” in Proc. IEEE ISIT, 2001, Washington, DC, June
  2001.

VANANTWERP2000363
J. G. VanAntwerp and R. D. Braatz, “A tutorial on linear and bilinear matrix
  inequalities,” J. Process Control, vol. 10, no. 4, pp. 363–385,
  2000.

bk:vaidyn
P. P. Vaidyanathan, Multirate Systems and Filter Banks.1em plus
  0.5em minus 0.4emEnglewood Cliffs, NJ: Prentice-Hall, 1993.

jn:vaidypoly
P. Vaidyanathan and S. Mitra, “Polyphase networks, block digital filtering,
  LPTV systems, and alias-free QMF banks: a unified approach based on
  pseudocirculants,” IEEE Trans. Acoust., Speech, Signal Process.,
  vol. 36, no. 3, pp. 381–391, Mar. 1988.

master:koup
D. A. Koupatsiaris, “Analysis of multirate random signals,” Thesis for the
  M.S. and E.E. degree, Naval Postgraduate School, Monterey, CA, Dec. 2000.

conf:rdhulicyclo
R. Dhuli and B. Lall, “Cyclostationary signals in multirate linear systems,”
  in Nat. Conf. Commun.(NCC), Jan. 2010, pp. 1–5.

jn:sanelsevier
S. Patel, R. Dhuli, and B. Lall, “Design and analysis of matrix wiener
  synthesis filter for multirate filter bank,” Signal Process., vol.
  102, no. 0, pp. 256–264, 2014.

bk:hayes
M. H. Hayes, Statistical Digital Signal Processing and Modeling.1em plus 0.5em minus 0.4emJohn Wiley & Sons, Inc., 2002.

jn:ps-tutorial-review
J. Barata and M. Hussein, “The moore-penrose pseudoinverse: A tutorial review
  of the theory,” Brazilian Journal of Physics, vol. 42, no. 1-2, pp.
  146–165, 2012.

bk:koch
K.-R. Koch, Parameter estimation and hypothesis testing in linear
  models.1em plus 0.5em minus 0.4emSpringer-Verlag, 1999.

bk:haykin
S. Haykin, Adaptive Filter Theory, 3rd ed.1em plus 0.5em minus
  0.4emEnglewood Cliffs, NJ: Prentice-Hall, 1996.

bk:moon2000mathematical
T. Moon and W. Stirling, Mathematical Methods and Algorithms for Signal
  Processing.1em plus 0.5em minus 0.4emPrentice Hall, 2000.

jn:quad_opt
C. A Floudas and V. Visweswaran, “Quadratic optimization,” Handbook of
  Global Optimization, 1995.

jn:labeau
F. Labeau, “Synthesis filters design for coding gain in oversampled filter
  banks,” IEEE Signal Process. Lett., vol. 12, no. 10, pp. 697–700,
  Oct. 2005.





























-1.5plus -1fil
[
    < g r a p h i c s >
]Sandeep Patel received the B.Tech degree in Electronics and Communications Engineering from the Indian Institute of Technology, Roorkee, in 2007. After completing graduation, he joined Nvidia Graphics and worked on video technologies till June, 2008. From June, 2008 to July, 2010, he was with Adobe Systems working in the flash media server team. He received the MS(R) degree from the Indian Insitute of Technology, Delhi in 2013. He is currently pursuing his Ph.D. degree from the Bharti School of Telecom Technology and Management, Indian Institute of Technology, Delhi.

-1.5plus -1fil
[
    < g r a p h i c s >
]Ravindra Dhuli received the Ph.D. degree in signal processing from the Department of Electrical Engineering, Indian Institute of Technology Delhi, in 2010. He is currently an Associate Professor with the Department of Electronics and Communications Engineering, Vellore Institute of Technology, Andhra Pradesh, India. His research interests include multirate signal processing, statistical signal processing, image processing, and mathematical modeling.

-1.5plus -1fil
[
    < g r a p h i c s >
]Brejesh Lall (M'05) received the B.E. and M.E. degrees in electronics and communications engineering from Delhi College of Engineering, Delhi University, in 1991 and 1992, respectively, and the Ph.D. degree in the area of multirate signal processing from the Indian Institute of Technology, Delhi, in 1999. His research interests are in signal processing with application to image processing and communication systems. He has over 150 papers in international journals and refereed conferences. From September 1997 to June 2005, he worked at Hughes Software Systems, in the digital signal processing group. Since July 2005, he has been with the faculty of the Department of Electrical Engineering, Indian Institute of Technology, Delhi, where he is currently a Professor and head of the Bharti School of Telecom Technology and Management. He is also the coordinator of Ericsson 5G Center of Excellence at IIT Delhi. 






























