An Integrated Approach for NonRecursive Formulation of ConnectionCoefficients of Orthogonal Functions
Electrical
Engineering Department, National Institute of Technology
Emails: monika_mittalkkr@rediffmail.com (1), l_dewan@nitkkr.ac.in (2)
^{*}Corresponding author
Abstract
In this paper, an integrated approach is proposed for nonrecursive formulation of connection coefficients of different orthogonal functions in terms of a generic orthogonal function. The application of these coefficients arises when the product of two orthogonal basis functions are to be expressed in terms of single basis functions. Two significant advantages are achieved; one, the nonrecursive formulations avoid memory and stack overflows in computer implementations; two, the integrated approach provides for digital hardware oncedesigned can be used for different functions. Computational savings achieved with the proposed nonrecursive formulation visàvis recursive formulation, reported in the literature so far, have been demonstrated using MATLAB PROFILER.
Keywords
Connection Coefficients; Haar Wavelet; Orthogonal Functions; Operational Matrices; Product Coefficients Matrices.
Introduction
Orthogonal functions, such as block pulse functions, Walsh functions, Legendre functions, Laguerre functions, Fourier functions and Haar functions, have been extensively used for providing piecewise constant solutions to different problems in Engineering and Sciences in terms of differential equations, analysis, optimization and identification of linear and nonlinear systems.
At the first place, piecewise constant solutions are computationally more efficient and secondly, they provide the only means to obtain the solution when the relevant conventional technique fails. In this approach, known and unknown continuous time functions are expanded in terms of the relevant orthogonal basis functions and various mathematical operations like integration, differentiation, multiplication etc. are replaced by matrices resulting in matrix algebraic equations which are then solved to find the required unknown functions.
The need for computing the connection coefficients of the orthogonal functions arise when product of two orthogonal basis functions are to be expressed in terms of single basis functions.
Hitherto, the recursive formulation have been reported in the literature [111,15,16] which are different for different orthogonal functions. The cited advantage of recursive formulation that the order of the involved matrices are less is not of much significance in the present era of abundant cheap computing capability available at hand. The possibility of multifaceted digitalhardware seems to be better option rather. The present formulation is a step in that direction.
Moreover, recursive formulations have the following disadvantages:
1. Matrices at higher resolutions are calculated with the help of all the matrices at lower resolutions. So it becomes computationally inefficient.
2. Recursive formulations are generally avoided in computer implementations.
3. These recursive formulations are different for different orthogonal functions [17].
Paraskevopoulos [3,4] and Razzaghi [5] derived the relevant matrices for chebyshev series and fourier series in their own right, respectively. Improved product formula for walsh functions was proposed by Watanabe and Kawata for the LQG control design [6]. Afterwards, Hsiao et al. derived the matrix of integration for Haar wavelet [7] and proposed recursive formulations for different matrices for Haar wavelet [8]. In a number of studies, Karimi et al. [911] applied these recursive formulations for analysis, optimal control and robust vibration control of linear timeinvariant and timevarying systems.
Lin Wu et al. [12] made
the sole effort in presenting the integrated approach for computing the
integration matrix for different orthogonal functions in terms of the generic
orthogonal function and applied it for numerical inversion of the
In [17,18] and the present paper, the work of Lin Wu et al. is further extended and an integrated approach is proposed for computing connection coefficients of orthogonal functions. The proposed nonrecursive formulation is developed in terms of generic orthogonal function which is replaced by corresponding basis function for computing coefficients of a particular orthogonal function.
The paper is organized as follows: In the second section, the principle, on which the proposed method is based, is discussed. The integrated nonrecursive formulation for computing connection coefficients of orthogonal functions is developed in terms of a generic orthogonal function and is presented in third section. In fourth section, connection coefficients of different orthogonal functions are computed using the generic formulation. Computational savings achieved and an application of connection coefficients is demonstrated in next section, followed by conclusions in the end.
Principle of the Proposed Method
The proposed unified method is based on the following fundamental properties of orthogonal functions in general and block pulse functions in particular:
1. The generic orthogonal function _{} can be represented in symbolic form as
_{} (1)
where elements _{} are the basic functions. In numeric form, the corresponding sampled values of _{} are arranged as rows to form the generic orthogonal function matrix _{}.
2. The symbolic form of a generic orthogonal function _{} can be represented as the product of numeric form of the function _{} and symbolic form of the block pulse functions _{} i.e.:
_{} (2)
where:
_{} and
_{} are the block functions (3)
The _{} block function is unity over the interval _{} and zero elsewhere and in numeric form _{} where _{} is Identity matrix of dimension _{}.
For a particular orthogonal function the generic function _{} is replaced by corresponding basis function.
Analytical nonrecursive formulation for computing connection coefficients is presented in the next section.
Proposed NonRecursive Formulation for Computing Connection Coefficients
The multiplication of two generic orthogonal functions i.e. _{} can be spanned by corresponding basis functions. Related expansion coefficients are known as connection coefficients, expressed as:
_{} (4)
where _{} is the generic orthogonal function connection coefficients’ matrix of dimension _{} and _{} are corresponding expansion coefficients.
Using the fundamental property of orthogonal functions from (2), (4) can be expressed as:
(5)
where the disjoint property of block pulse functions _{} is used.
Eqn. (5) can be further simplified, using (2), by expressing expansion coefficients _{} in terms of block function expansion coefficients _{} as:
(6)
Simplifying (6) after post multiplying by _{} on both sides, results in:
(7)
Substituting (7) in (5), we get:
(8)
Simplifying (8), using the orthogonal property of the generic orthogonal function and numeric form of the block pulse function, _{} is obtained as
(9)
Equation (9) is the desired nonrecursive formulation for computing connection coefficients of generic orthogonal function.
The nonrecursive formulation in (9) is shown to result in the connection coefficients of different orthogonal functions like Walsh, Fourier and Haar functions by using the appropriate basis functions in the next section.
Computation of Connection Coefficients for Different Orthogonal Functions using the Proposed Method
The proposed integrated approach is applied for computing connection coefficients of different orthogonal functions such as Walsh, Haar and Fourier functions in this section. For demonstration purpose, the results at resolution _{} are given for the example discrete sequence consisting of four samples accordingly and hence _{} due to identity nature of block basis functions.
Walsh Function
The kernel of discrete Walsh transform, for _{}, is defined as:
(10)
Where _{} is the _{} bit in the binary representation of _{}.
For computing connection coefficients of walsh functions, denoted as _{} at resolution _{}, the corresponding basis function from (10) are substituted in (9) in place of generic orthogonal basis functions, resulting in:
(11)
It is indeed the result derived by Chen and Hsiao in their original paper [1].
Haar Function
The orthogonal set of Haar functions _{} is a group of square waves with magnitude of ±1 in certain intervals and zeros elsewhere [14], defined as:
(12)
(13)
All the other functions are dilations and translations of (13), according to the relation:
(14)
where _{} indicate dilations and translations respectively. The resolution m is given by:
_{}
For computing connection coefficients of Haar functions, denoted as _{} at resolution _{}, the corresponding basis function from (12) & (13) are substituted in (9) in place of generic orthogonal basis functions, resulting in:
(15)
The result is exactly the same as reported in [8].
Fourier Function
The basis of Fourier Series are complex exponentials, _{}, where _{} represents the _{} harmonic of fundamental frequency _{}. Discretized version of these continuous time complex exponentials gives the bases of Discrete Fourier Transform which are represented by _{}, where _{}, _{} and _{} is the total number of points at which the transform is calculated [4,5].
In terms of the orthogonal set of functions _{}, where _{} is the resolution. The discretized complex exponentials are then expressed as _{} where _{}. The _{} represent the piecewiseconstant approximation of discrete orthogonal set of functions as:
(16)
For computing connection coefficients of Fourier functions, denoted as _{} at resolution _{}, the corresponding basis function from (16) are substituted in (9) in place of generic orthogonal basis functions, resulting in
(17)
Note that since the basis of Fourier function are complex, its connection coefficients are also complex. The result in (17) is exactly same as reported in [5].
Similarly connection coefficients of other orthogonal functions, possessing sinusoidal and nonsinusoidal basis functions such as Discrete cosine functions (DCT) and Hartley functions (DHT), can also be computed by the proposed integrated approach.
Computational savings achieved via the proposed integrated nonrecursive formulation for computing the connection coefficients of orthogonal functions, visàvis the recursive formulation, is demonstrated in the next section for the case of Haar functions due to its nice properties of multiresolution and compact support. State response of a linear timevariant system is also presented as an application.
Computational Savings and Application
Computational Savings
The analytical nonrecursive formulation for computing the connection coefficients for the case of Haar functions is obtained, as in (15), for any resolution _{} as _{}.
The corresponding recursive formulation reported in the literature [8] is:
_{}
where _{}, _{}.
Computational savings achieved in computing connection coefficients using the proposed nonrecursive formulation visàvis recursive formulation is shown using MATLAB PROFILER in Table 1. The PROFILER is obtained on a PENTIUM(R) M 1.73 GHz machine for the same number of files called.
Resolution 
Proposed Integrated Nonrecursive Approach 
Existing Recursive Approach 
_{} 


_{} 


It is evident from
Application
Consider a firstorder linear timevariant system given as:
(18)
where _{} is the state, _{} is the input and _{} is the initial state of the system.
Comparing (18) with the generalized linear timevariant system statespace model of the following form:
(19)
we get _{} and _{}.
The product of _{} and _{} are simplified to be spanned by Haar basis with the help of proposed nonrecursive formulation for computing connection coefficients to obtain state response of the system in (18).
In Haar transform domain, the final simulation time _{} is normalized to be unity by substituting _{} in (18) where _{}.
After normalization of time scale, (18) becomes:
(20)
Next each term in (18) is expanded into the Haar transform as
(21)
(22)
where _{} and _{} are the expansion coefficients of _{} and _{} respectively. The _{} is the Haar basis.
Relation between _{} and _{} are obtained by integrating (21) on both sides:
(23)
Using forward operational matrix of integration _{} derived by Lin Wu et. al [12] and substituting the expansions from (21) and (22), (23) becomes:
(24)
where initial state _{} is expanded in Haar domain as _{}, _{}. The effect of the term _{}, arising out of normalization of time scale, is incorporated in _{}.
Solving (24) for _{} yields:
(25)
On the similar lines, the expansions of _{},_{} and _{} are expressed as:
(26)
(27)
(28)
where _{},_{} and _{} are the expansion coefficients of _{},_{} and _{} respectively.
The problem involves obtaining the state response of the system, hence Haar expansions of various functions, from (21) – (28), are substituted in (18) to obtain:
(29)
Rearranging (29) yields:
(30)
Each of the term _{} in (30) is expressed to be spanned by Haar basis using the proposed integrated nonrecursive formulation for computing connection coefficients, which are evaluated nonrecursively in (15), as:
(31)
where _{} denotes the connection coefficients for the corresponding variables.
Right multiplying each term in (31) by _{}, we get:
(32)
Substituting the value of _{} from (25) and collecting the terms results in:
(33)
_{} is obtained from (33) as:
(34)
It is trivial to calculate the inverse of the term _{} due to sparse nature of the matrix  a key characteristics of Haar function [14]. The computed values of _{} from (34) are used to evaluate the desired values of state _{} using (22) for the input _{}, resolution _{} are shown in Fig. 1 along with the analytical solution.
Figure 1. State response of linear timevarying system
It is evident from Fig. 1 that the state response, of the linear timevariant system, evaluated using the proposed integrated nonrecursive approach, is conforming well to the analytical solution which is shown as continuous curve.
Conclusions
An integrated nonrecursive formulation for computing the connection coefficients of orthogonal functions has been successfully developed and presented in terms of a generic orthogonal function. This generic formulation is then shown leading to particular cases of different orthogonal functions such as Walsh, Haar, and Fourier. The integrated scope of the proposed formulation is established by obtaining these particular instances merely by replacing the generic basis with the corresponding basis. Computational savings obtained, in using the proposed nonrecursive formulation, are demonstrated with the help of MATLAB PROFILER visàvis recursive formulation, reported and used in the literature so far. State response of a linear timevarying statespace system is obtained to demonstrate an application of the connection coefficients. Further computational savings can be explored by devising computationally efficient algorithms for finding the inverses of matrices involved.
References
1. Chen C.F., Hsiao C.H., A statespace approach to Walsh series solution of linear systems, Int. J. System Sci., 1965, 6(9), p. 833858.
2. Hsu N.S., Cheng B., Analysis and optimal control of timevarying linear systems via block pulse functions, Int. J. Control, June 1981, 33(6), p. 11071123.
3. Paraskevopoulos P.N., Chebyshev series approach to system identification, analysis and optimal control, J. Franklin Inst., 1983, 316, p. 135157.
4. Paraskevopoulos P.N., Sparis P.D., Mouroutsos S.G., The Fourier series operational matrix of integration, Int. J. System Sci., 1985, 16(2), p.171176.
5. Razzaghi M., Optimal control of linear timevarying systems via Fourier Series, Journal of Optimization Theory and Applications, 1990, 65(2), p. 375384.
6. Jin L., Watanabe A., Kawata S., The LinearQuadraticGaussian Control design using an improved product formula of Walsh functions, SICE '95, July 2628, 1995, Sapporo, p. 13751378.
7. Chen C.F., Hsiao C.H., Haar wavelet method for solving lumped and distributedparameter systems, IEE Proc. Control Theory Appl., 1997, 144(1), p. 8794.
8. Hsiao C.H., Wang W.J., Optimal control of linear timevarying systems via Haar wavelets, J. Optimization Theory Appl., 1999, 103, p. 641655.
9. Karimi H.R., Lohmann B., Jabehdar Maralani P. and Moshiri B., A Computational Method for solving optimal control and parameter estimation of linear systems using Haar Wavelets, Int. J. of Computer Mathematics, 2004, 81(9), p. 11211132.
10. Karimi H.R., Lohmann B., Jabehdar Maralani P. and Moshiri B., Haar waveletbased optimal control of timevarying statedelayed system: A computationa method, IEEE Proc. Conf. Computer Aided Control System Design, 2006, p. 15281533.
11. Karimi H.R., Lohmann B., A computational method to robust vibration control of vehicle enginebody system using haar wavelet, IEEE Proc. Int. Conf. Control Applications, 2006, p. 169174.
12. Wu J.L., Chen C.H., Chen C.F., A unified derivation of operational matrices of integration for integration in system analysis, IEEE Proc. Int. Conf. on Information Technology: Coding and Computing, 2000, p. 436442.
13. Wu J.L., Chen C.H., Chen C.F., Numerical inversion of Laplace transform using Haar wavelet operational matrices, IEEE Trans. on Circuits and SystemsPart I: Fundamental Theory and Applications, 2001, 48(1), p.120122.
14.
15. Ordokhani Y., Numerical solution of nonlinear volterrahammerstein integral equations using the hybrid block pulse and rationalized Haar functions, Applied Mathematical Sciences, 2008, 2(51), p. 25312541.
16. Oishi M., Moro S., Matsumoto T., A modified method for circuit analysis using Haar wavelet transform with adaptive resolution  For circuits with waveform with sharp convex ranges, European Conf. on Circuit Theory and Design, ECCTD 2009, 2009, p. 299302.
17. Garg M., Dewan L., A novel method of computing Haar connection coefficients for analysis of HCI systems, Proc. of Second 2^{nd} International Conference on Intelligent Human Computer Interaction (IHCI 2010), Lecture Notes in Control and Information Sciences (LNCS), SpringerVerlag, ISBN 9788184895407, 2010, p. 360365.
18. Garg M. and Dewan L., A numerical method for linear ODEs using nonrecursive Haar connection coefficients, International Journal of Computational Science and Mathematics (IJCSM) (Accepted).