55 Al-Khwarizmi Engineering Journal Al-Khwarizmi Engineering Journal, Vol. 5, No. 4, PP 51-57 (2009) Improve Akaike’s Information Criterion Estimation Based on Denoising of Quadrature Mirror Filter Bank Mohammed H. Miry Department of Electrical and Electronic Engineering/ University of Technology (Received 1 Febreuary 2008; accepted 17 September 2008) Abstract Akaike’s Information Criterion (AIC) is a popular method for estimation the number of sources impinging on an array of sensors, which is a problem of great interest in several applications. The performance of AIC degrades under low Signal-to-Noise Ratio (SNR). This paper is concerned with the development and application of quadrature mirror filters (QMF) for improving the performance of AIC. A new system is proposed to estimate the number of sources by applying AIC to the outputs of filter bank consisting quadrature mirror filters (QMF). The proposed system can estimate the number of sources under low signal-to-noise ratio (SNR). Keywords: Akaike’s information criterion (AIC), quadrature mirror filters (QMF). 1. Introduction The Quadrature Mirror Filters (QMF) has diffused into most signal processing applications. It plays a very important role in the denoising of signals since it gives an effective, informative and compact description of the analyzed signals. In 1988, Mallat produced a fast wavelet transform. The Mallat algorithm for discrete wavelet transform (DWT) is known as quadrature mirror filters (QMF) [1-3].This property also endows wavelets with a remarkable aptitude for denoising by means of a simple nonlinear thresholding filter. Mallat and Hwang first showed that effective noise suppression may be achieved by transforming the noisy signal into the wavelet domain by QMF, and preserving only the local maxima of the transform. A wavelet reconstruction that uses only large-magnitude coefficients has also been shown to approximate well the uncorrupted signal; in other words, noise suppression is achieved by thresholding the wavelet transform of the contaminated signal. The problem of estimating the number of sources impinging on a passive array of sensors has received a considerable amount of attention during the last two decades. The first to address this problem were Wax and Kailath. In their seminal work it is assumed that the additive noise process is a spatially and temporally white Gaussian random process. Given this assumption, the number of sources can be deduced from the multiplicity of the received signal correlation matrix’s smallest eigenvalue [4]. In order to avoid the use of subjective thresholds required by multiple hypothesis testing detectors, Wax and Kailath suggested the use of the Akaike’s Information Criterion (AIC)[5] for estimating the number of sources. The AIC estimator can be interpreted as a test for determining the multiplicity of the smallest eigenvalue [5], but its response degrades under low Signal to Noise Ratio (SNR) condition due to errors in estimation the data covariance matrix from finite data. In this paper, a new system is proposed to determine the number of sources using AIC and QMF bank. The method can estimate the number of sources under low SNR environment. 2. Quadrature Mirror Filter Quadrature mirror filters (QMF) is the Mallat algorithm for discrete wavelet transform (DWT), it analyses a finite-length time-domain signal at Mohammed H. Miry Al-Khwarizmi Engineering Journal, Vol.5, No. 4, PP 51-57 (2009) 52 different frequency bands with different resolutions by successive decomposition into coarse approximation and detail information as shown in Fig (1). Approximations represent the slowly changing features of the signal and conversely details represent the rapidly changing features of the signal. The impulse response of the decomposition and reconstruction QMF pairs are related by[6] )1()1()( 1'   nhnl n )1()1()( 1'   nlnh n …(1) Where h(n) and l(n) are the low-pass and the high- pass FIR filters of decomposition QMF and h ' (n) and l ' (n) are the low-pass and the high-pass FIR filters of reconstruction QMF. The decomposition level of QMF bank is denoted by M (select a suitable number of levels based on the nature of the signals, or on a suitable criteria such as entropy). The wavelet de-noising approach is based on the assumption that random errors in a signal are present over all the coefficients while deterministic changes get captured in a small number of relatively large coefficients. As a result, a nonlinear thresholding (shrinking) function in the wavelet domain will tend to keep a few larger coefficients representing the underlying signal, while the noise coefficients will tend to reduce to zero. Practically, the wavelet denoising method consists of applying the QMF bank to the original noisy data, thresholding the wavelet coefficients, and then inverse transforming the thresholded coefficients to obtain the time-domain de-noised data [7]. It should be noted that the performance of the wavelet de-noising depends to the choice of the thresholding rule, the type of wavelet, the maximum depth of wavelet decomposition and the initial SNR. In this paper, we use soft thresholding method to eliminate noise from noisy data. According to soft thresholding method, the wavelet coefficient between -δ and δ is set zero [8], while the other are shrunk in absolute value. The threshold δ proposed by Donoho is )log(2 N  …(2) where N is the total number of samples and σ is the standard deviation of noise. In order to apply this method in practice, one usually needs to estimate σ. Donoho & Johnstone suggest using as an estimator the median of the coefficients on the finest level divided by 0.6745 which usually works well as long as the signal is contained mainly in the low frequency coefficients [8]. 2 2 2 A 1 Fig.1. Structure of the QMF Bank. S = Signal, L = Low-Pass Decomposition Filter; H = High-Pass Decomposition, L' = Low-Pass Reconstruction Filter; H' = High-Pass Reconstruction Filter Filter; = Down-Sampling Operation, = Up-Sampling Operation. A 1 , A 2 are the Approximated Coefficient of the Original Signal at Levels 1, 2 etc. D 1 , D 2 are the Detailed Coefficient at Levels 1,2. A 1 ', A 2 ' are the Processed or Non-Processed Approximated Coefficient of the Original Signal at Levels 1, 2 etc. D 1 ', D 2 ' are the Processed or Non-Processed Detailed Coefficient at Levels 1,2. 2 2 Analysis Decomposition Synthesis Reconstruction Original Signal Level 1 Level 1 Level 2 Level 2 Reconstructed Signal 2 2 2 2 2 A 2 D 2 D 1 D 1' D 2' A 2' A 1' Mohammed H. Miry Al-Khwarizmi Engineering Journal, Vol.5, No. 4, PP 51-57 (2009) 55 3. AIC Principle The array model assumes the presence of q sources impinging on an p-channel array according to [9] ZASY  …(3) where NP Y   denotes the multichannel observations in the sampled time interval nTt  , where n is an integer, qP A   denotes the mixing (steering) matrix, Nq S   denotes the source signal matrix, and NP Z   denotes an additive Gaussian noise component with nontrivial temporal and spatial covariance matrices. It will be assumed that within the N snapshots consisting the analysis window, no more than pq  sources is present. The matrix S is full rank when all the q sources are independent. When S is rank-deficient, this usually means that either the source signals have correlated waveforms, or subsets of the signals are perfectly coherent, i.e., at least one of the signals is just a scaled and delayed version of another signal. This type of situation arises when the multipath phenomenon occurs, i.e., a direct signal path and one or more indirect paths are received by the array in which case the signals are not independent. On the other hand, the columns of the matrix A represent the array response due to each of the q signals impinging on the array. Each column depends only on the geometrical construction of the array and the directional response of the sensors. Generally speaking, if the array is properly designed and the sources are independent and treated as point sources, A will be full rank. A can also be rank deficient when the propagating medium has nonstationary characteristics, or in some sense anisotropic. This situation can very likely arise in a neurophysiological experiment. First, consider the noise free observations given by the product matrix X = AS. If A or S has rank less than q, X will also have rank less than q. If there are q ≤ p ≤ N independent rows in X, then this matrix is said to have a P-dimensional range or row space, which is a subspace of the M-dimensional Euclidean space ℜ M . The rank of this matrix is the dimension of this subspace. The spatial covariance of X when spectrally factored yields   T XXX T X UDUXXER .. …(4) where pp X D   is a diagonal matrix containing the rank ordered eigenvalues 0.................. 121   pqq  o f RX. If there are q signal sources, the largest q eigenvalues correspond to the q sources and the first q columns of the unitary matrix UX span the signal subspace. The remaining p-q eigenvalues are equal to zero with probability one. In practice, the finite sample size and the presence of noise amount to estimating the sample eigenvalues 0................. 21  pq  from the sample covariance matrix [10-11]     1 0 ][][ 1 N n T Y nyny N R …(5) The remaining p-q eigenvalues are no longer equal to zero and the corresponding p-q eigenvectors span the noise subspace. When the noise is cross correlated with the signal of interest, RY can be expressed as T ZSSZZ T SY ARARRAARR  …(6) where sR is the autocorrelation of signal, zR is the autocorrelation of noise, szR is the crosscorrelation between the signal and noise and zsR is the crosscorrelation between the noise and signal. The presence of the cross covariance terms shrinks the separation distance that should be observed to determine the subset of eigenvalues belonging to the signal subspace because of the mutual correlation of the sample eigenvalues, making it practically impossible to determine q. In good SNR conditions, the separation between the signal and noise subspaces is easily obtained. In low SNR conditions, this separation does not yield easily and the source detection problem amounts to the so-called sphericity test to determine the multiplicity of the smallest p-q eigenvalues using the Akaike’s Information Criterion (AIC) [5]    KPK l KP l KAIC P Ki i P ki kP i                     22 1 log2 1 1 )/(1 …(7) where i l denote the eigenvalues of ^ R . The number of signals is taken to be the value of  1,......,1,0  pK for which AIC is minimized. Mohammed H. Miry Al-Khwarizmi Engineering Journal, Vol.5, No. 4, PP 51-57 (2009) 54 4. Proposed Model Figure 2 shows the block diagram of the proposed system to estimate the number of sources. The main procedure of the system is described as follows. First, the signals are received by antennas. Next, these signals are processed by the QMF bank. Then, in every bank, the channel that exceeds threshold level (δ) as compared with other channels will be chosen at the selection unit. The selected channel’s output data is applied to IDWT (inverse of discrete wavelet transform). The output of IDWT is used to compute its covariance matrix. Finally AIC is calculated to estimate the numbers of sources. WP,M QMF QMF QMF Y1(t) Y2(t) YP(t) ……. ……. ……. ……. ……. W1,1 W1,M WP,1 Antenna 1 m.m, Antenna 2 m.m, Antenna P m.m, W2,1 W2,M W1,2 W2,2 WP,2 Covariance Matrix Computation Inverse of Discrete Wavelet Transform Selection Unit W1,m W2,m WP,m AIC Estimation the Number of the Sources Fig.2. Block Diagram of the Proposed System. ……. ……. Where m = 1, 2, 3, …..., M Fig.3. Structure of the Selection Unit. Wl ,m W2, m WP,m Threshold Level Threshold Level Threshold Level . : gate switches Where m = 1,2,…., M Mohammed H. Miry Al-Khwarizmi Engineering Journal, Vol.5, No. 4, PP 51-57 (2009) 55 4.1. Selection Unit Figure 3 shows the structure of selection unit. The role of the unit is to select the channel that exceeds threshold level (δ) as compared with other channels. In every bank, the soft threshold is applied to the output of QMF bank. The gate switches are simultaneously closed when the output of QMF banks exceeds threshold level (δ) Table 1, The Response of the AIC Method With Two Sources K 0 1 2 3 4 5 6 7 Classical System AIC(K) 1505.5 25.7 * 31.6 114.6 225.9 389.8 703.5 1615.9 Modified System AIC(K) 1875.4 87.7 41.1 * 49.1 171.3 353.5 703.5 1724.8 * refers to the minimum value Table 2, The Response of the AIC Method With Three Sources K 0 1 2 3 4 5 6 7 8 9 10 Classical System AIC(K) 1371.1 96.4 29 * 98.2 190.6 280.4 368.1 455.8 541.2 625.6 710.2 Modified System AIC(K) 19451.5 263.7 157.3 38.6 * 124.4 411.2 1204.1 1637.3 1872.1 1017.5 791.9 Table 2, Continue K 11 12 13 14 15 16 17 18 19 20 21 Classical System AIC(K) 811.2 903.5 1004.8 1120.1 1255.6 1431.3 1673.9 2077.0 2816.4 4978.5 5816.3 Modified System AIC(K) 682.0 619.7 581.3 558.1 544.5 537.7 536.5 539.9 547.2 557.7 554.3 * refers to the minimum value 5. Simulation and Results In order to compare the performance of the above proposed system with classical system (without applying proposed model for AIC method), we consider two cases with different values for SNR, the number of sources and direction of arrival for the sources. The first case, A uniform linear array (ULA) of 8 sensors is consider with a half-wave length inter-element spacing, used to separate two uncorrelated emitters based on a batch of N=100 data samples with SNR=13 dB. The first source is at 50 o while the second source is at 55 o . It is noticed the response of classical system shown in table(1), the minimum value of AIC is obtained incorrectly for K = 1. The parameter are used in proposed system include Daubechies wavelet (db18) and one level decomposition, the response of proposed system shown in table (1), the minimum value of AIC is obtained correctly for K = 2. The second case, A uniform linear array (ULA) of 22 sensors is consider with a half-wave length inter-element spacing, used to separate three uncorrelated emitters based on a batch of N=100 data samples with SNR= 2 dB. The first source is at 50 o , the second source is at 52 o , while the third source is at 54 o . It is noticed the response of classical system Mohammed H. Miry Al-Khwarizmi Engineering Journal, Vol.5, No. 4, PP 51-57 (2009) 56 shown in table (2), the minimum value of AIC is obtained incorrectly for K = 2. The response of proposed system shown in table (2), the minimum value of AIC is obtained correctly for K = 3. Through comparison between the responses of classical system with the responses of proposed system, it is seen that the first does not yield the correct number of the sources but the proposed model gives the correct number of the sources as seen in table (1) and table (2). 6. Conclusion In this paper, we have introduced a new system to determine the number of sources by applying AIC to the outputs of filter banks consisting QMF. In the paper, the classical system and proposed system are compared through simulation. The proposed method can give good estimation for the number of the sources even if low SNR environment while the classical system is fail under low SNR. The QMF in proposed model helps to reduce the error of the array data covariance estimated from finite data and thus reduce the error of the AIC estimation. 7. References [1] A. Kumar, G. K. Singh, and R. S. Anand, "Near Perfect Reconstruction Quadrature Mirror Filter", Proceedings of World Academy of Science, Engineering and |Technology Volume 27 February 2008 ISSN 1307-6884. [2] D. Estaban and C. Galand, “Application of quadrature mirror filters to split band voice coding scheme,” in Proc. IEEE ICASSP, 1997, pp. 191–195. [3] C. Tsai, "Analysis of Complex Quadrature Mirror Filter Banks", Proceeding of World Academy of Science, Engineering and |Technology Volume 13 February 2006 ISSN 1307-6884. [4] M. Kaveh, H. Wang, and H. Hung, “On the theoretical performance of a class of estimators of the number of narrow-band sources,” IEEE Trans. on Acustic Speech and Signal Processing, vol. ASSP-35, no. 11, pp. 1350–1352, 1987. [5] F. Ridder, R. Pintelon, J. Schouken and D. Gillikin, "Modified AIC and MDL Model Selection Criteria for short Data Records" IEEE Trans. On Instrumentation and Measurement, vol. 54 , no. 1, February 2005. [6] A. Bal, "Wavelet Denoising for Geophysics Images", International Conference on Earth Sciences and Electronics-2002 (ICESE-2002) pp. 165-170 [7] U. E. Emir, C. B. Akgül and A. Akın, "Wavelet Denoising vs ICA Denoising for Functional Optical Imaging", Proceedings of the 1st International IEEE EMBS, Conference on Neural Engineering, Capri Island, Italy, March 20-22, 2003. [8] D. L. Donoho, “De-noising by soft- thresholding,” IEEE Trans. Inform. Theory, vol. 41, pp. 613-27, 1995. [9] E. Fisher, M. Grossman, and H. Messer, “Estimation the Number of Sources Using Information Theoretic Criteria General Performance Analysis”, IEEE Trans. on Signal Processing vol. 50, pp. 1026-1035, may 2002 [10] M. Cedervall and L. Moses "Efficient Maximum Likelihood DOA Estimation for Signals with Known Waveforms in the Presence of Multipath", IEEE Tran. on Signal Processing, vol. 45. no. 3, March 1997. [11] T. Ayoub and A. Haimovich, "Modified GLRT Signal Detection Algorithm" IEEE Tran. on Aerospace and Electronic Systems vol.36 no. 3, July 2000. 57- 51 ، صفحة 4 ، العذد 5محمذ حسٍن مري مجلة الخوارزمً الهنذسٍة المجلذ (2009) 57 لحسمة أزالة التشوٌه باألعتماد علىAkaikeمعٍار معلومات تطوٌر تخمٍن مرشح مربع المرأة محمذ حسٍن مري الجبهعت التكٌىلىجٍت/ قسن الهٌذست الكهزببئٍت و األلكتزوًٍت الخالصة والتً تعتبز ههوت فً العذٌذ هي , هً طزٌقت هعزوفت لتخوٍي عذد الوصبدر الوزتطوت بٌظبم الوتذسسبث Akaike (AIC)هعٍبر هعلىهبث هذا البذث هختص بتطىٌز و تطبٍق هزشخ هزبع . واطئت(SNR) تصبخ سٍئت عٌذهب تكىى ًسبت األشبرة الى التشىٌه (AIC)اى أستجببت طزٌقت .التطبٍقبث على ًتبئج دزهت هزشخ ٌذتىي على (AIC)ًذي أقتزدٌب ًظبم جذٌذ لتخوٍي عذد الوصبدر بىاسطت تسلٍط . (AIC) لتذسٍي استجببت(QMF)الوزأة . واطئت(SNR)الٌظبم الوقتزح ٌستطٍع تخوٍي عذد الوصبدر عٌذهب تكىى ًسبت األشبرة الى التشىٌه . (QMF)هزشخ هزبع الوزأة