An Integrated Approach for Non-Recursive Formulation of Connection-Coefficients of Orthogonal Functions
Engineering Department, National Institute of Technology
In this paper, an integrated approach is proposed for non-recursive 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 non-recursive formulations avoid memory and stack overflows in computer implementations; two, the integrated approach provides for digital hardware once-designed can be used for different functions. Computational savings achieved with the proposed non-recursive formulation vis-à-vis recursive formulation, reported in the literature so far, have been demonstrated using MATLAB PROFILER.
Connection Coefficients; Haar Wavelet; Orthogonal Functions; Operational Matrices; Product Coefficients Matrices.
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 non-linear 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 [1-11,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 digital-hardware 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 [1-7].
Paraskevopoulos [3,4] and Razzaghi  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 . Afterwards, Hsiao et al. derived the matrix of integration for Haar wavelet  and proposed recursive formulations for different matrices for Haar wavelet . In a number of studies, Karimi et al. [9-11] applied these recursive formulations for analysis, optimal control and robust vibration control of linear time-invariant and time-varying systems.
Lin Wu et al.  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 non-recursive 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 non-recursive 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
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.:
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 non-recursive formulation for computing connection coefficients is presented in the next section.
Proposed Non-Recursive 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:
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:
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:
Simplifying (6) after post multiplying by on both sides, results in:
Substituting (7) in (5), we get:
Simplifying (8), using the orthogonal property of the generic orthogonal function and numeric form of the block pulse function, is obtained as
Equation (9) is the desired non-recursive formulation for computing connection coefficients of generic orthogonal function.
The non-recursive 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.
The kernel of discrete Walsh transform, for , is defined as:
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:
It is indeed the result derived by Chen and Hsiao in their original paper .
The orthogonal set of Haar functions is a group of square waves with magnitude of ±1 in certain intervals and zeros elsewhere , defined as:
All the other functions are dilations and translations of (13), according to the relation:
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:
The result is exactly the same as reported in .
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 piecewise-constant approximation of discrete orthogonal set of functions as:
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
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 .
Similarly connection coefficients of other orthogonal functions, possessing sinusoidal and non-sinusoidal 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 non-recursive 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 multi-resolution and compact support. State response of a linear time-variant system is also presented as an application.
Computational Savings and Application
The analytical non-recursive 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  is:
where , .
Computational savings achieved in computing connection coefficients using the proposed non-recursive 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.
Proposed Integrated Non-recursive Approach
Existing Recursive Approach
It is evident from
Consider a first-order linear time-variant system given as:
where is the state, is the input and is the initial state of the system.
Comparing (18) with the generalized linear time-variant system state-space model of the following form:
we get and .
The product of and are simplified to be spanned by Haar basis with the help of proposed non-recursive 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:
Next each term in (18) is expanded into the Haar transform as
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:
Using forward operational matrix of integration derived by Lin Wu et. al  and substituting the expansions from (21) and (22), (23) becomes:
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:
On the similar lines, the expansions of , and are expressed as:
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:
Rearranging (29) yields:
Each of the term in (30) is expressed to be spanned by Haar basis using the proposed integrated non-recursive formulation for computing connection coefficients, which are evaluated non-recursively in (15), as:
where denotes the connection coefficients for the corresponding variables.
Right multiplying each term in (31) by , we get:
Substituting the value of from (25) and collecting the terms results in:
is obtained from (33) as:
It is trivial to calculate the inverse of the term due to sparse nature of the matrix - a key characteristics of Haar function . 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 time-varying system
It is evident from Fig. 1 that the state response, of the linear time-variant system, evaluated using the proposed integrated non-recursive approach, is conforming well to the analytical solution which is shown as continuous curve.
An integrated non-recursive 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 non-recursive 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 time-varying state-space 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.
1. Chen C.F., Hsiao C.H., A state-space approach to Walsh series solution of linear systems, Int. J. System Sci., 1965, 6(9), p. 833-858.
2. Hsu N.S., Cheng B., Analysis and optimal control of time-varying linear systems via block pulse functions, Int. J. Control, June 1981, 33(6), p. 1107-1123.
3. Paraskevopoulos P.N., Chebyshev series approach to system identification, analysis and optimal control, J. Franklin Inst., 1983, 316, p. 135-157.
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.171-176.
5. Razzaghi M., Optimal control of linear time-varying systems via Fourier Series, Journal of Optimization Theory and Applications, 1990, 65(2), p. 375-384.
6. Jin L., Watanabe A., Kawata S., The Linear-Quadratic-Gaussian Control design using an improved product formula of Walsh functions, SICE '95, July 26-28, 1995, Sapporo, p. 1375-1378.
7. Chen C.F., Hsiao C.H., Haar wavelet method for solving lumped and distributed-parameter systems, IEE Proc. Control Theory Appl., 1997, 144(1), p. 87-94.
8. Hsiao C.H., Wang W.J., Optimal control of linear time-varying systems via Haar wavelets, J. Optimization Theory Appl., 1999, 103, p. 641-655.
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. 1121-1132.
10. Karimi H.R., Lohmann B., Jabehdar Maralani P. and Moshiri B., Haar wavelet-based optimal control of time-varying state-delayed system: A computationa method, IEEE Proc. Conf. Computer Aided Control System Design, 2006, p. 1528-1533.
11. Karimi H.R., Lohmann B., A computational method to robust vibration control of vehicle engine-body system using haar wavelet, IEEE Proc. Int. Conf. Control Applications, 2006, p. 169-174.
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. 436-442.
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 Systems-Part I: Fundamental Theory and Applications, 2001, 48(1), p.120-122.
15. Ordokhani Y., Numerical solution of non-linear volterra-hammerstein integral equations using the hybrid block pulse and rationalized Haar functions, Applied Mathematical Sciences, 2008, 2(51), p. 2531-2541.
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. 299-302.
17. Garg M., Dewan L., A novel method of computing Haar connection coefficients for analysis of HCI systems, Proc. of Second 2nd International Conference on Intelligent Human Computer Interaction (IHCI 2010), Lecture Notes in Control and Information Sciences (LNCS), Springer-Verlag, ISBN 978-81-8489-540-7, 2010, p. 360-365.
18. Garg M. and Dewan L., A numerical method for linear ODEs using non-recursive Haar connection coefficients, International Journal of Computational Science and Mathematics (IJCSM) (Accepted).