extfieldsofstudy:
Computer Science
Mathematics

text:
Reduced Basis Decomposition: a Certified and Fast Lossy Data Compression Algorithm

Dimension reduction is often needed in the area of data mining. The goal of these methods is to map the given high-dimensional data into a low-dimensional space preserving certain properties of the initial data. There are two kinds of techniques for this purpose. The first, projective methods, builds an explicit linear projection from the high-dimensional space to the low-dimensional one. On the other hand, the nonlinear methods utilizes nonlinear and implicit mapping between the two spaces. In both cases, the methods considered in literature have usually relied on computationally very intensive matrix factorizations, frequently the Singular Value Decomposition (SVD). The computational burden of SVD quickly renders these dimension reduction methods infeasible thanks to the ever-increasing sizes of the practical datasets. In this paper, we present a new decomposition strategy, Reduced Basis Decomposition (RBD), which is inspired by the Reduced Basis Method (RBM). Given $X$ the high-dimensional data, the method approximates it by $Y \, T (\approx X)$ with $Y$ being the low-dimensional surrogate and $T$ the transformation matrix. $Y$ is obtained through a greedy algorithm thus extremely efficient. In fact, it is significantly faster than SVD with comparable accuracy. $T$ can be computed on the fly. Moreover, unlike many compression algorithms, it easily finds the mapping for an arbitrary ``out-of-sample'' vector and it comes with an ``error indicator'' certifying the accuracy of the compression. Numerical results are shown validating these claims.

Introduction
Dimension reduction is ubiquitous in many areas ranging from pattern recognition, clustering, classification, to fast numerical simulation of complicated physical phenomena. The fundamental question to address is how to approximate a n-dimensional space by a d-dimensional one with d n. Specifically, we are given a set of high-dimensional data and the goal is to find its low-dimensional approximation Y = [y 1 , y 2 , . . . , y d ] ∈ R m×d (2) with reasonable accuracy. There are two types of dimension reduction methods. The first category consists of "projective" ones. These are the linear methods that are global in nature, and that explicitly transform the data matrix X into a low-dimensional one by Y = T X. The leading examples are the Principal Component Analysis (PCA) and its variants. The methods in the second category act locally and are inherently nonlinear. For each sample in the high-dimensional space (e.g. each column of X), they directly find their lowdimensional approximations by preserving certain locality or affinity between nearby points.
In this paper, inspired by the reduced basis method (RBM), we propose a linear method called "Reduced Basis Decomposition (RBD)". It is much faster than PCA/SVD-based techniques. Moreover, its low-dimensional vectors are equipped with error estimator indicating how close they are approximating the high-dimensional data. RBM is a relative recent approach to speed up the numerical simulation of parametric Partial Differential Equations (PDEs) [16,19,20,6,5]. It utilizes an Offline-Online computational decomposition strategy to produce surrogate solution (of dimension N ) in a time that is of orders of magnitude shorter than what is needed by the underlying numerical solver of dimension N N (called truth solver hereafter). The RBM relies on a projection onto a low dimensional space spanned by truth approximations at an optimally sampled set of parameter values [1,8,17,18,13]. This low-dimensional manifold is generated by a greedy algorithm making use of a rigorous a posteriori error bounds for the field variable and associated functional outputs of interest which also guarantees the fidelity of the surrogate solution in approximating the truth approximation.
The RBD method acts in a similar fashion. Given the data matrix X as in (1), it iteratively builds up Y (2) whose column space approximates that of X. It starts with a randomly selected column of X (or a user input if existent). At each step where we have k vectors {y 1 , . . . , y k }, the next vector y k+1 is found by scanning the columns of X and locating the one whose error of projection into the current space span{y 1 , . . . , y k } is the largest. This process is continued until the maximum projection/compression error is small enough or until the limit on the size of the reduced space is reached. An important feature is an offline-online decomposition that allows the computation of the compression error, and thus the cost of locating y k+1 , to be independent of (the potentially large) m.
This paper is organized as follows. In Section 2, we review the background material, mainly the RBM. Section 3 describes the reduced basis decomposition algorithm and discuss its properties. Numerical validations are presented in Section 4, and finally some concluding remarks are offered in Section 5.

Background
The reduced basis method was developed for use with finite element methods to numerically solve PDEs. We assume, for simplicity, that the problems (usually parametric partial differential equations (PDE)) to simulate are written in the weak form: find u(µ) in an Hilbert space X such that a(u(µ), v; µ) = f (v; µ), ∀v ∈ X where µ is an input parameter. These simulations need to be performed for many values of µ chosen in a given parameter set D. In this problem a and f are bilinear and linear forms, respectively, associated to the PDE (with a N and f N denoting their numerical counterparts). We assume that there is a numerical method to solve this problem and the solution u N , called the "truth approximation" or "snapshot", is accurate enough for all µ ∈ D.
The fundamental observation utilized by RBM is that the parameter dependent solution u N (µ) is not simply an arbitrary member of the infinitedimensional space associated with the PDE. Instead, the solution manifold M = {u N (µ), µ ∈ D} can typically be well approximated by a lowdimensional vector space. The idea is then to propose an approximation of M by W N = span{u N (µ 1 ), . . . , u N (µ N )} where, u N (µ 1 ), . . . , u N (µ N ) are N ( N ) pre-computed truth approximations corresponding to the parameters {µ 1 , . . . , µ N } judiciously selected according to a sampling strategy [13]. For a given µ, we now solve in W N for the reduced solution u (N ) (µ). The online computation is N -independent, thanks to the assumption that the (bi)linear forms are affine 2 and the fact that they can be approximated by affine (bi)linear forms when they are nonaffine [2,10]. Hence, the online part is very efficient. In order to be able to "optimally" find the N parameters and to assure the fidelity of the reduced basis solution u (N ) (µ) to approximate the truth solution u N (µ), we need an a posteriori error estima- and stability information of the bilinear form [12,14,19,20,21]. With this estimator, we can describe briefly the classical greedy algorithm used to find the N parameters µ 1 , . . . , µ N and the space W N . We first randomly select one parameter value and compute the associated truth approximation. Next, we scan the entire (discrete) parameter space and for each parameter in this space compute its RB approximation u (N =1) and the error estimator ∆ 1 (µ). The next parameter value we select, µ 2 , is the one corresponding to the largest error estimator. We then compute the truth approximation and thus have a new basis set consisting of two elements. This process is repeated until the maximum of the error estimators is sufficiently small.
The reduced basis method typically has exponential convergence with respect to the number of pre-computed solutions [15,4,3]. This means that the number of pre-computed solutions can be small, thus the computational cost reduced significantly, for the reduced basis solution to approximate the finite element solution reasonably well. The author and his collaborators showed [7] that it works well even for a complicated geometric electromagnetic scattering problem that efficiently reveals a very sensitive angle dependence (the object being stealthy with a particular configuration).

Reduced basis decomposition
In this section, we detail our proposed methodology by stating the algorithm, studying the error evaluation, and pinpointing the computational cost.

The algorithm
At the heart of the method stated in Algorithm 1 is a greedy algorithm similar to that used by RBM. It builds the reduced space dimension-bydimension. At each step, the greedy decision for the best next dimension to pursue in the space corresponding to the data is made by examining an error indicator quantifying the discrepancy between the uncompressed data and the one compressed into the current (reduced) space.
In the context of the RBM, we view each column (or row if we are compressing the row space) of the matrix as the fine solution of certain (virtual) parametric PDE with the (imaginary) parameter taking a particular value. Since this solution is explicitly given already by the data, the fact that the PDE and the parameter are absent does not matter. Once this common mechanism satisfied by each column (or row) is identified, the greedy algorithm still relies on an accurate and efficient estimate quantifying the error between the original data and the compressed one. This will be the topic of the next subsection.
To state the algorithm, we assume that we are given a data matrix X ∈ R m×n , the largest dimension d max < n that the practitioner wants to retain, and a tolerance R capping the discrepancy between the original and the compressed data. The output is the set of bases for the compressed data (a low-dimensional approximation of the original data) Y ∈ R m×d and the transformation matrix T ∈ R d×n . Here, d ≤ d max is the actual dimension of the compressed data.
With this output, we can Compress. We represent any data entry X(:, j), the j th column of X ∈ R m , by the j th column of T , T (:, j) ∈ R d , with usually d m.
Uncompress. An approximation of the data is reconstructed by , E cur = +∞, and i a random integer between 1 and n.

2.2.
Apply the modified Gram-Schmidt orthonormalization to obtain the d th basis of the compressed space Evaluate the compression of out-of-sample data. Given any v ∈ R m×1 that is not equal to any column of X, its compressed representation in

Efficient quantification of the error
A critical part to facilitate the greedy algorithm and make the algorithm realistic is an efficient mechanism measuring (or estimating) the error v − v C under certain norm, v − v C , in Step 2.3 of the algorithm. In this work, we are using the A−norm defined as follows. For a given symmetric and positive definite matrix A ∈ R m×m , the A−norm of a vector v ∈ R m×1 is defined by For v being any column of the data matrix X and v C its low-dimensional This makes the quality of compression uniform. In this case, the evaluation of (3) is greatly simplified and the algorithm is the fastest as shown below by the numerical results.
2. General diagonal matrix: This setting can be used if part of each data entry needs to be preserved better and other parts can afford less fidelity.
3. General SPD matrix: This most general case can be helpful if the goal is to preserve data across different entries anisotropiclly.
The goal is then to evaluate the error through (3) as efficiently as possible for any given c. This is achieved by employing an offline-online decomposition strategy where the c-independent parts are evaluated beforehand (offline) enabling a quick turnaround time for any given c encountered online. The specifics are given in the next subsection.

Computational cost and implementation aspects
The Offline-Online decomposition of the computations and their complexities are as follows. Here, we use nnz(A) to denote the number of nonzero entries of a sparse matrix A.
Offline The total cost is of order Offline MGS Every basis needs to orthogonalized against the current set of bases. The total cost is of order m d 2 max . Offline Calculation of Errors The next basis is located by comparing each column with its compressed version into the current space. To enable that, we encounter the following computational cost: Pre-computation of diag(X AX) (for v Av in (3)) and AX (for Av in (3)). The cost is of order nnz(A) n. Expansion of Y AX and Y AY . The former takes time of order nnz(A) d max m, and the latter of order nnz(A) d 2 max . Offline Searching After these calculations, the comparison between the original and compressed data is then only dependent on the size of c (which is also the number of columns for Y ). The complexity is of order d 2 max . It will be repeated for up to n times in the searching process of step 2.3 of the algorithm for each of the up to d max basis elements. The total cost is at the level of n d 3 max .
Online Given any (possibly out-of-sample) data v ∈ R m×1 , its coefficients in the compressed space is obtained by evaluating c = Y v. The cost is of order m d max . The decoding (Y c) can be done with the same cost.
The online computation has complexity of order m d max .
We remark that, if the actual practice does not requires forming v C (e.g. clustering and classification etc) and so we only work with the coordinates c of v in the compressed space, then the online cost will be independent of m and thus much smaller.

Numerical Results
In this section, we test the reduced basis decomposition on image compression, and data compression. Lastly, we devise a simple face recognition algorithm based on RBD and test it on a database of 575 images while comparing RBD with 6 other face recognition algorithms. The computation is done, and thus the speedup numbers reported herein should be understood as, in Matlab 2014a on a 2011 IMac with a 3.4 GHz Intel Core i7 processor.

Image Compression and comparison with SVD
We first test it on compressing two standard images Lena and Mandrill in Figure 1. They both have an original resolution of 512 × 512. We take A = I and test the algorithm. For each component of every image, we run the algorithm with d max ∈ {170, 51, 25} which implies a compression ratio of 33%, 10%, and 5% respectively. The resulting images (formed by multiplying the corresponding Y and T together) are shown on the 1 st and 3 rd row of Figures 2. As a comparison, we run SVD and obtain the reconstructed matrices with the first d max singular values accordingly. The resulting images are on the second and last row. Clearly, SVD provides the best quality pictures among all possible algorithms (and thus better than what RBD provides). However, we see that the RBD pictures are only slightly blurrier. Moreover, it takes much less time. In fact, we show the comparison in time between SVD and RBD in Table 1. We see that, when d = 51, RBD is three times faster than SVD and seven times faster when d = 25. Here the SVD time is the shorter between those taken by svd and svds commands in Matlab.

Data Compression
Here, we test the algorithm on a few artificially-generated data sets. Given a function f (x, y), the data denoted by f (D) is constructed by evaluating f on a uniform tensorial grid D := (x i , y j ) n i,j=1 .

Exact reconstruction
For tensorial functions such as those listed in Table 2 with their corresponding d values, the RBD method detects the optimal dimension, stops the greedy algorithm after d steps and decompose the matrix f (D) accordingly, that is, as an exact product of n × d and d × n matrices.

Face Recognition
Here, we demonstrate the superior efficiency and accuracy of the RBD method on a classical classification task -face recognition. The goal of face recognition is to recognize subjects based on facial images. It has important applications in areas ranging from surveillance, authentication, to humancomputer interaction etc. We use the UMIST database [9] that is publicly available on Roweis' web page 4 . Table 3 summarizes its characteristics: It contains 20 people under different poses. The number of different views per subject varies from 19 to 48. We use the cropped version whose snapshot is shown in Figure 4.
As in [11], we randomly choose 10 views from each class to form a training set. The rest of the samples (375 of them) are used as testing images. We show the average classification error rates in Figure 5 Left. These averages are computed over 100 random formations of the training and test sets. Shown in the middle are the results of six traditional dimension reduction techniques taken from [11]. Clearly, our method has similar performance as the PCA 9. Beyond spectral methods and trace optimization. While this paper focused on dimension reduction based on spectral techniques and trace optimization, other existing powerful methods rely on convex optimization with constraints. This section briefly describes two examples in this class for illustration purposes. For a recent survey of these techniques see [7] for example.
Possibly the best known technique along these lines in supervised learning is the method of Support Vector Machines (SVM); see [8,12,48].
It is in spirit similar to LDA (cf. Section 5.2) in that it finds a one dimensional projection to separate the data in some optimal way. Formally, the SVM approach consists of finding a hyperplane which best separates two training sets belonging to two classes. If the hyperplane is w T x + b = 0, then the classification function would be f (x) = sign(w T x + b). This will assign the value y = +1 to one class and y = −1 to the other, and it is capable of perfectly separating the two classes in ideal situations when the classes are linearly separable.
One of the key ingredients used by SVM is the notion of margin, which is the distance between two parallel support planes for the two classes. First, observe that the parameters w, b can be normalized by looking for hyperplanes of the form w T x + b ≥ 1 to include one set and w T x + b ≤ −1 to include the other. With y i = +1 for one class and y i = −1 for method, and outperforms three of the other five methods. However, RBD is much faster than PCA and other methods since they all involves solving eigenproblems [11]. A speedup factor as a function of the number of bases is plotted in Figure 5 Right which demonstrates a speedup factor of larger than two for this particular test when we reach the asymptotic region (around when the number of basis vectors is 25).

Concluding remarks
This paper presents and tests an extremely efficient dimension reduction algorithm for data processing. It is multiple times faster than the SVD/PCAbased algorithms. What makes this possible is a greedy algorithm that iteratively builds up the reduced space of basis vectors. Each time, the next dimension is located by exploring the errors of compression into the current space for all data entries. Thanks to an offline-online decomposition mechanism, this searching is independent of the size of each entry. Numerical results including one concerning a real world face recognition problem confirm these findings.


Modeling the Error Term by Moving Average and Generalized Autoregressive Conditional Heteroscedasticity Processes

Corresponding Author: Ayodele Abraham Agboluaje School of Quantitative Sciences, College of Arts and Sciences, Universiti Utara Malaysia Department of Mathematics and Computer Science, Faculty of Natural Sciences, Ibrahim Badamasi Babangida University, Lapai, Nigeria Email: ayo_dele1960@yahoo.com Abstract: This study has been able to reveal that the Combine White Noise model outperforms the existing Generalized Autoregressive Conditional Heteroscedasticity (GARCH) and Moving Average (MA) models in modeling the errors, that exhibits conditional heteroscedasticity and leverage effect. MA process cannot model the data that reveals conditional heteroscedasticity and GARCH cannot model the leverage effect also. The standardized residuals of GARCH errors are decomposed into series of white noise, modeled to be Combine White Noise model (CWN). CWN model estimation yields best results with minimum information criteria and high log likelihood values. While the EGARCH model estimation yields better results of minimum information criteria and high log likelihood values when compare with MA model. CWN has the minimum forecast errors which are indications of best results when compare with the GARCH and MA models dynamic evaluation forecast errors. Every result of CWN outperforms the results of both GARCH and MA.

Introduction
The study is to model the error term that produces better and accurate results when compared with the existing models. The most important requirement in model building procedure in time series is that, the series must be stationary. The probability properties of the model assumed do not vary with time but changing with a fixed constant level mean and with constant variance. When there is an increase or decrease in the mean as time varies or as the variance is not constant with time, the series needs transformation to make it stationary for further computation to have reliable results. The results of model estimation can be spurious if the series is not stationary. The finite moving average procedure is constantly stationary (Said and Dickey, 1984;Harvey, 1993;Miettinen et al., 2014;Jentsch and Rao, 2015).
Moving average is the white noise error from previous periods. Moving average process is invertible if the coefficient of the white noise error is less than one. The residuals of moving average or mixed autoregressive moving average procedure will have equivalent residuals of properly selected autoregressive procedure. Therefore, the results from autoregressive procedure can be used in computing the variance or covariance matrix for autoregressive integrated moving average procedure by taking into consideration the equivalent variance or covariance matrix for the unpolluted autoregressive procedure. Tests of fit and diagnose checks by employing residuals autocorrelation of autoregressive model is applicable to moving average model (Box and Pierce, 1970;Miettinen et al., 2014).
The proposition approach of theory of testing autocorrelation when the lagged dependent variables of the regressors of a regression equation are integrated (Godfrey, 1978). This test is asymptotically corresponding to the suitable Likelihood Ratio (LR) test. This testing for the null hypothesis of serially uncorrelated against the alternative that a steady first order Autoregressive {AR (1)} process produces the errors of the regression model. This test is commonly employed in empirical studies. It is evident that the moving average error model of order n {MA (n)} is a better hypothesis when compare with the AR(1) scheme, because the null hypothesis is that the moving average error are independently and normally distributed with zero mean and constant variance (Godfrey, 1978). Yet, there is no discovery of fourth order autocorrelation with this test (Godfrey, 1978).
The behaviour of the error term in the stochastic time series depends on the data size and high data frequencies.
The error term can be white noise or heteroscedasticity, this dependent on the type of data. When the data exhibit heteroscedastic errors the moving average, autoregressive, mixed autoregressive moving average processes cannot model the heteroscedastic errors because of the non constant variances in the error term (Harvey, 1993). Engle (1982) proposes autoregressive conditional heteroscedasticity (ARCH) model because of time varying volatility, to capture the effect of non constant variances in the error term. The equations are not normally distributed as there are changes in stock market distribution and fat tail measuring effect and this effect is named ARCH. ARCH models are able to grip group errors and can withstand any changes made by economic forecaster. But ARCH cannot handle the abnormalities like crashes, mergers, news effect or threshold effects in the financial and economic sector. ARCH can only model limited lag length. Bollerslev (1986) comes up with generalized ARCH to capture the volatility persistent that is flexible to uplift the weaknesses of ARCH model. Vivian and Wohar (2012;Ewing and Malik, 2013) investigate that there are excess kurtosis and volatility persistence in GARCH which determines the asymmetric/leverage effects that GARCH cannot handled properly.
Threshold GARCH and exponential GARCH capture the asymmetric effects of positive and negative shocks of the same dimension on conditional volatility in various ways (Nelson, 1991;Hentschel, 1995;McAleer, 2014;McAleer and Hafner, 2014;Kamaruzzaman and Isa, 2015;Al-Hagyan et al., 2015;Farnoosh et al., 2015). GARCH modeling the leverage effect is not possible because any restriction imposed will be positivity restriction which has no leverage effect, since the negative correlation between returns shocks and subsequent shocks to volatility is the leverage effect (McAleer, 2014;McAleer and Hafner, 2014).
With these models weaknesses, CWN model is more appropriate to tackle these weaknesses.
CWN is computed by decomposing EGARCH error standardized results of unequal variances into equal variances series. Several statistics approaches and tests on CWN developments are detailed in the methodology and empirical data analysis of how the new model CWN is carried out to deal with conditional heteroscedastic errors and leverage effect.

Materials and Methodology
The data is retrieved from the DataStream of Universiti Utara Malaysia library. The U.S. Real Gross Domestic Product (GDP) quarterly data from 1960 to 2014 is used to investigate the efficiency of CWN model estimation when compared with the existing models.
Consider the model: Permit the stochastic approach of a real-valued time to be ε t and the complete information through t time is I.
The GARCH model is: The EGARCH specification is: The unequal variances (heteroscedastic errors) behaviors in the process of estimation being exhibited by GARCH models can be simplified into Combine White Noise models. The standardized residuals of GARCH errors which are unequal variances are decomposed into equal variances (white noise) in series to deal with the heteroscedasticity and leverage effect. The regression model is employed to transform each equal variances series to model.
Moving average process is employed for the estimation of these white noise series which is called Combine White Noise: It can be written as: where, A(L) + B(L) + … = Q which are the matrix polynomial, U t is the error term of combine white noise model and 2 c σ is the combination of equal variances. The combine variance of the combine white noise is: Considering the two variances in the best two models of the first best models produced by the Bayesian model averaging output. The combine variance follows: The variance of errors, 2 c σ in the combine white noise can be written: where, the balanced weight specified for the model is W. where, ρ is the correlation; intra-class correlation coefficient is used for a reliable measurement.

Results
The time plot of the data shows an upward trend which is a behavior of non-stationary.
The data is transformed in returns series to observe the volatility clustering, long tail skewness and excess kurtosis which are the characteristics of heteroscedasticity. The graph exhibits irregular variances that indicate volatility.
The Table 1 reports that, there are left long tail skewness, excess kurtosis and Jarque-Bera test is significant that is an indication of non-normality. Also standard deviation is less than one. Table 1 shows the ARCH LM tests for the effect of heteroscedasticity in the data series; F-Statistic and Obs*R-squared are not significant that is an indication of ARCH presence in the data.
The Table 2 shows that the AIC, BIC and HQ minimum information criteria with log-likelihood that are used to select the appropriate model between ARCH and GARCH models. EGARCH model is choosing because it has minimum values of AIC, BIC and HQ with high log-likelihood values.
Combine White Noise (CWN) has the minimum information criteria with high log likelihood. The CWN model gives the best results with minimum information criteria and high log likelihood when compare with GARCH and MA models estimation. The estimation of GARCH model and Combine White Noise model with their forecasting values are in Table 4.
In GARCH modeling, the leverage is not possible because any restriction imposed will be positivity restriction which has no leverage effect (McAleer, 2014;McAleer and Hafner, 2014). No proposition has removed heteroscedasticity completely (White, 1980;Antoine and Laveragne, 2014;Uchôa et al., 2014).
To avoid the above challenges, the standardized residuals graph of the GARCH model (GARCH errors) with unequal variances and zero mean are decomposed into equal variances series (white noise series). There are some graphs of equal variances (white noise series) with mean zero being obtained from graph of GARCH errors. These white noise series are fit into regression model to make each a model.
The implementation of Bayesian model averaging produces two best models from the first best models (Asatryan and Feld, 2014). For confirmations, fitting linear regression with autoregressive errors; 220 is the number of observation, with zero mean and variance one (Higgins and Bera, 1992). Therefore, the best two models are the white noise models. Table 3 indicates an independent samples test is conducted to test whether data set of the two white noise models have equal variances or not. The test revealed that the variability in the distribution of the two data sets is no significantly different value which is greater than the p-value 0.05. Hence, the two models have equal variances (Lim and Loh, 1996;Boos and Brownie, 2004;Bast et al., 2015). Table 4 reveals that Combine White Noise (CWN) appears to be the most appropriate model for estimation and forecasting, when comparing the three models.    Chuffart (2015) argues that Logistic Smooth Transition GARCH and Markov-Switching GARCH models are employed to confirm that Bayesian Information Criteria (BIC) can lead to wrong specification. CWN model employs Akaike Information Criteria (AIC), Bayesian Information Criteria (BIC) and log likelihood for specification of the model. Chang et al. (2015) develop ample conditions for strict stationary and ergodicity of three nonlinear models of Self-Exciting Threshold Autoregressive (SETAR)-GARCH process, the multiple-regime logistic Transition Auto Regressive (STAR) model with GARCH errors and Exponential STAR-GARCH model. They consider the STAR-GARCH models estimation results to be vital in financial econometrics. The development of CWN model is from GARCH family errors. CWN is tested using different countries data set with outstanding performance when compare with family GARCH model (EGARCH) which (Mutunga et al., 2015) considered to be suitable.

Discussion
McAleer (2014) describes the asymmetry and leverage to be indistinguishable, and that leverage is asymmetry. The challenge is that there are no statistical properties for the estimation of this leverage effect. The estimation is only possible through positivity restriction of the parameters which is not an estimate for that can model the leverage effect. CWN model estimates with available statistical properties of maximum likelihood estimation to obtain efficient estimation and proves better than the estimation of the existing models.
McAleer and Hafner (2014) introduce one line derivation of EGARCH to model the asymmetric leverage effect, but in this process, stationarity and invertibility conditions are not determined. This makes it impossible to model the leverage effect. CWN model stationarity and invertibility are met.
Therefore, from these discussions, CWN model is suitable for efficient estimation.

Conclusion
It has been observed that the GARCH models have not been able to model the leverage effect, because when the positivity restriction is imposed, it has no leverage effect. The coefficient of variance equation must be negative for the existence of leverage (McAleer, 2014;McAleer and Hafner, 2014).
The standardized residual GARCH errors are decomposed into Combine White Noise (CWN). CWN has proved to be more efficient and it takes care of GARCH weaknesses. The estimation of Combine White Noise model passes stability condition, stationary, serial correlation, the ARCH effect tests and it also passes the Levene's test of equal variances.
The results in Table 2 and 4 show that CWN model estimation yield best results with minimum information criteria and high log likelihood values. While the EGARCH model estimation yield better results of minimum information criteria and high log likelihood values when compare with MA model. CWN has the minimum forecast errors which are indications of best results when compare with the GARCH and MA models dynamic evaluation forecast errors (Ismail and Muda, 2006;Fildes et al., 2011;Lazim, 2013). The determinant of the residual of covariance matrix value indicates that CWN is efficient.
Based on the every result in the empirical analysis, CWN is the most appropriate model. For this reason, CWN is recommended for the modeling of data that exhibits conditional heteroscedasticity and leverage effect.
The contribution of this study to the scientific community is that the CWN gives good results that improve the weaknesses of the existing models. CWN forecast output is more reasonable for effective policy making.


Optimizing Quality of Experience of Dynamic Video Streaming over Fading Wireless Networks

We address the problem of video streaming packets from an Access Point (AP) to multiple clients over a shared wireless channel with fading. In such systems, each client maintains a buffer of packets from which to play the video, and an outage occurs in the streaming whenever the buffer is empty. Clients can switch to a lower-quality of video packet, or request packet transmission at a higher energy level in order to minimize the number of outages plus the number of outage periods and the number of low quality video packets streamed, while there is an average power constraint on the AP. We pose the problem of choosing the video quality and transmission power as a Constrained Markov Decision Process (CMDP). We show that the problem involving $N$ clients decomposes into $N$ MDPs, each involving only a single client, and furthermore that the optimal policy has a threshold structure, in which the decision to choose the video-quality and power-level of transmission depends solely on the buffer-level.

I. INTRODUCTION
Scheduling packets for video streaming over a shared wireless downlink is of increasing attention [18]. Predominantly, this problem has been addressed with the goal of minimizing the average number of outages, i.e., time-slots during which a client has no packet to play [1], [2], [3], [4], [5], [6], [7], [8], [9]. However the models considered in these works do not incorporate the communication constraints imposed by the network over which the streaming occurs. Typically clients streaming video files will share a common wireless channel, which again typically has a constraint on the average power. The access point (AP) has to choose the power level at which to transmit individual packets to each client so as to maximize the total Quality of Experience (QoE) experienced by the clients. The system also has an additional degree of freedom in that the AP can transmit lower quality packets on occasion, leading to a softer loss of video quality than an abrupt outage. Another important aspect is that the quality of video streaming experienced by a client depends not only on the number of outages, but also on the number of "outage periods", i.e., number of interruption periods as well. Thus an outage lasting 10 time-slots is not the same as 10 outages each lasting 1 time-slot. The QoE experienced by a client thus has to take into account several metrics: the average number This material is based upon work partially supported by AFOSR Contract FA9550-13-1-0008, and NSF under Contract Nos. CNS-1302182 and Science & Technology Center Grant CCF-0939370. 1  of outages, the average number of outage-periods, and the quality of video-packets streamed. In this paper we address this overall problem. While we focus here on the single last-hop case for ease of exposition and brevity, our results can be generalized to multi-hop networks as well. In order to provide non-interruptive video streaming experience to the clients, the AP has to guarantee some sort of service regularity to the clients, i.e., it has to ensure that the packet deliveries to the clients are not in a bursty fashion. References [19], [20], [21], [22], [23] develop a framework to design policies which provide services to clients in a regular fashion, though not in a video streaming context.

II. SYSTEM DESCRIPTION
Consider a system where a wireless channel is shared by N clients for the purpose of streaming video packets. It is assumed that the system evolves over discrete timeslots, and one time-slot is taken by the access point (AP) for attempting one packet transmission.
Client n maintains a buffer of size B n packets and plays a packet for a duration of T n time-slots. Once it has finished playing a video packet, it looks for the next packet in the buffer. In case the buffer is empty, there is an "outage", meaning that the video streaming is interrupted, and the client has to wait for a packet to be delivered to its buffer before it can resume the video streaming.
The wireless channels connecting the clients to the AP are assumed to be random. For ease of exposition, we will derive the results for the case when the channel conditions are fixed. These results carry over to the case of fading channels in a straight-forward manner. Later, in Section VIII, we will outline the results for the case of fading channels.
There are Q n different video qualities {1, 2, . . . , Q n } of packets that can be transmitted for client n, with class 1 video quality providing the best viewing experience. Similarly there are {Ê 1 ,Ê 2 , . . . ,Ê n } different power levels at which the packets for client n can be transmitted. We letÊ 1 = 0, i.e., a user may choose to not request a packet in a time-slot. The probability that the packet for client n is successfully delivered upon a transmission attempt, P n (q, E), depends on the amount of power E used in the packet transmission and the quality of video packet q that was attempted. We also incorporate an average power constraint on the AP.
The basic problem considered is that of scheduling the AP's packet transmissions to clients so as to maximize the combined Quality of Experience (QoE) of the clients. The QoE of a single client depends on multiple factors 1) The average number of outages. 2) How "often" the video gets interrupted, i.e., the number of outage-periods, or the number of timeslots in which the transition from "non-outage" to outage occurs.
3) The number of packets of different quality types that are streamed.

III. PROBLEM FORMULATION
We denote by O n (s) the random variable that assumes the value 1 if the n-th client faces an outage at time s, and 0 otherwise, and by E n (s) the transmission power utilized by the n-th client at time-slot s. Also, let I n (q, s) be the random variable that takes the value 1 if a packet of quality q is delivered to client n in time-slot s.
The Constrained Markov Decision Process (CMDP) of interest is then to choose the quality of video packets and transmission power for each client, in order to Minimize lim sup lim sup Note that the term |O n (s) (O n (s − 1) − 1) | assumes the value 1 if time-slot s is the beginning of an outageperiod for client n, and is 0 otherwise. It thereby measures the number of outage periods incurred. The parameters {λ q,n } Qn q=1 , λ O,n n = 1, 2, . . . , N are employed for tuning the QoS to account for the relative importance placed on each of the objectives. We note that for i > j, λ i,n > λ j,n for all n, since we assumed that the video quality of a packet is less if the packet belongs to a higher valued class.
Thus the above problem is a CMDP in which the system state at time t is described by the N dimensional vector L(t) := (l 1 (t), l 2 (t), . . . , l N (t)), where l n (t) is the amount of play time remaining in the buffer of client n at time t.
The central difficulty which arises is that the cardinality of the state-space of the system increases exponentially with the number of clients N , and thus the problem is computationally infeasible as formulated above.
We show that the problem of serving N clients can be decomposed into N separate problems each involving only a single client. Thus the computational complexity of the problem grows linearly in the number of clients. Moreover, we show that the optimal policy is easily implementable since it has a simple threshold structure.

IV. THE DUAL MDP
The Lagrangian associated with a policy π for the system (1) is given by, where λ E is the Lagrangian multiplier associated with the average power constraint. The associated Lagrange dual is, Next we present a useful bound on the dual, the proof of which follows from the super-additivity of lim sup and sub-additivity of lim inf operations. Lemma 1:

V. SINGLE CLIENT PROBLEM
We consider minimizing the bound obtained in Lemma 1. Observing the bound, we find that we have decomposed the original problem (1) into N singleclient problems, i.e., the expression in the r.h.s. of (4) is the sum of the costs of N clients, in which the cost of a single client depends only on the action chosen for it in each time-slot.
The problem for the single client is described as follows. We omit the sub-script n in the following discussion. The channel connecting the client to the AP is random. The client maintains a buffer of capacity B time-slots of play-time video (this assumption is equivalent to the assumption of maintaining a buffer of B packets since a packet is played for T time-slots), and in each time-slot, the AP has to choose two quantities, which together comprise the control action chosen for the client: • The video quality q ∈ {1, 2, . . . , Q}.
The state of the client is thus described by l(t), the playtime duration of the packets present in the buffer at time t. If the client is scheduled a packet transmission of quality q at an power E at time t, and the remaining playtime at time t, l(t), is less than or equal to B −T +1, However if the value of remaining playtime l(t) is strictly greater than B − T + 1, then the system state at time t + 1 is l(t) − 1 with a probability 1.
We let be the transitions associated with the remaining playtimes associated for a successful and failed packet transmission respectively. The control action at time t will be denoted u(t) := (q(t), E(t)), where q(t), E(t) are the video quality and transmission power level chosen at time t.
The transmissions at power level E incur a cost of λ E × E. There is a penalty of 1 unit upon an outage at time t. A penalty of λ q units is imposed if a packet of quality q is delivered to it, while a penalty of λ O units is imposed at time t in case there was no outage at timeslot t − 1, and an outage occurs in time-slot t, i.e. if a new outage-period begins at time t.
Since the probability distribution of the system state at time t + 1 is completely determined by the system state at time t, and the action (q, E) chosen at time t, i.e., requested video quality and power level at which transmission occurs, the single client problem is a Markov Decision Process (MDP) involving only a finite number of actions and states, and is thus solved by a stationary Markov policy [12].
Denote by π n a policy for the client n. The single client problem is to solve, Denote by π n (λ E ), the optimal policy which solves the single client problem. We also let be the optimal cost, and V n (λ E , π) be the cost associated with a policy π.
VI. THRESHOLD STRUCTURE OF THE OPTIMAL POLICY FOR THE SINGLE CLIENT PROBLEM We will suppress the subscript n in the following discussion, and begin with a discussion of the β ∈ (0, 1) discounted infinite horizon cost problem for the single client. Let be the minimum β-discounted infinite horizon cost for the system starting in state x at time 0, where x can assume values in the set {0, 1, . . . , B}. The function V s β (x) is similarly defined to be the minimum β-discounted cost incurred in s time-slots for the system starting in state x, i.e., where π s is a policy for the s horizon β-discounted problem. The quantities V β (x), V s β (x) should not be confused with the quantities V n (λ E ) defined in the previous section. We have, where is the one-step cost associated with the action u = (q, E), and for s = 1, 2, . . ., We assume that a lower video quality packet, or a higher power packet transmission, leads to an increase in the success of packet transmission P (q, E), i.e., an increase in cost is associated with a higher transmission success probability. Definition 1: We say a policy is of threshold-type if it satisfies the following for each stage s: . . , B} are such that x > y, let u x , u y be the actions chosen by a threshold policy π in states x and y. Then it is easily verified that P (u x ) < P (u y ).
Next we present a useful lemma that is easily proved. In the following, (u, π) is the policy that follows the action u in the first slot, and then follows policy π, while V s,π β (x) is the cost achieved under the policy π in s timeslots for the system starting in state x.
Lemma 2: Let u 1 , u 2 be two actions where P (u 2 ) > P (u 1 ), or equivalently, P (u 2 ) > P (u 1 ). Then,  Proof: Within this proof, let π s be the optimal policy for the β-discounted s time-slots problem, and let (u, π s−1 ) be the policy for s time-slots which takes the action u at the first time-slot, and then follows the policy π s−1 . In order to prove the claim, we will use induction on s, the number of time-slots.
Let us assume that the statement is true for the functions D β z (x), for all z ≤ s. In particular the function, is decreasing for x ∈ {1, 2, . . . , B − T + 1}.
Fix an x ∈ {1, 2, . . . , B − T } and denote by u 1 , u 2 , u 3 , u 4 , the optimal actions at stage s for the states S(x), F(x), S(x + 1), F(x + 1) respectively. Note that the threshold nature of π s implies that, P (u 1 ) < P (u 2 ), P (u 3 ) < P (u 4 ) and , This is true because as the value of state decreases in the interval {1, 2, . . . , B}, a threshold policy switches to an action that has a higher transmission success probability. So it follows from Lemma 2 that where the first inequality follows since a sub-optimal action in the state F(x + 1) increases the cost-to-go for s time-slots, the second inequality is a consequence of the assumption that the functions V s−1 β (F(x)) − V s−1 β (S(x)) are decreasing in x, while the last inequality follows from the fact that a sub-optimal action in the state S(x) will increase the cost-to-go for s time-slots. Thus we have proved the decreasing property of D β s+1 (·) for x ∈ {2, 3, . . . , B − T + 1}, and it remains to show that D β s+1 (1) > D β s+1 (2). Once again, let u 1 , u 2 , u 3 , u 4 be the optimal actions at stage s for the states T, 0, T + 1, 1 respectively. Using the same argument as above (i.e., assuming that the actions taken in stage s at states T, T + 1 are the same, and the actions taken in the states 0, 1 are the same), it follows that However, then V s β (T ) − V s β (T + 1) ≤ 1 + λ O − βλ O (for s stages, apply the same actions for the system starting in state T , as that for a system starting in state T + 1, and note that the two systems couple at a stage t − 1, when the latter system hits the state 1 at any stage t; the hitting stage is of course random). This gives us, and thus we conclude that the function D s+1 (x) is decreasing for x ∈ {1, 2, . . . , B}. In order to complete the proof, we notice that for s = 1, we have, and thus the assertion of Lemma is true for s = 1. Theorem 1: Consider the single client problem discussed in Section V. There is a threshold policy that is Blackwell optimal [17], i.e., it is optimal for all values of β ∈ (β, 1) for someβ ∈ (0, 1), and is also optimal for the Average cost problem. Thus π n (λ E ) is of threshold-type and can be obtained in time O(B E×Q ) via comparing the costs of all threshold-type policies.
Proof: Fix a q and let E i , E j , i > j be two power levels. Without loss of generality, let u 1 = (q, E i ), u 2 = (q, E j ). Clearly C(u 1 ) > C(u 2 ) (11). In the Bellman equation (10), consider the term depending on u, i.e. the term C(u) − P (u)D β s (x). For x, y ∈ {1, 2, . . . , B − T + 1}, x > y, we have, where the last inequality follows from Lemma 3. Thus it follows that if action u 1 is preferred over action u 2 for any state x, then u 1 will also be preferred over action u 2 for any state y < x, y ∈ {1, 2, . . . , B −T +1}. Finally note that it follows from the Bellman equation (10) and (5), that the optimal action for states x > B − T + 1 is to let E = 0 (since any packet that is received will be lost due to buffer over flow). The proof for variations in power levels is similar. Thus it follows from the definition of a threshold policy that the optimal policy is of threshold type.
Finally note that the statement regarding Blackwell optimality follows from the result in the above paragraph, and because the state-space is finite.

VII. SOLUTION OF PRIMAL MDP
We now present the solution of the Primal Problem.
Proof: Let π (λ E ) := ⊗π n (λ E ) be the policy obtained by following the policy π n (λ E ) for each client n. Then from the definition of dual function, Lagrangian (2), cost associated with a policy π (8) and Lemma 1, we have However since the policy π (λ E ) is stationary, (all the lim inf and lim sup become lim in the definition of its Lagrangian, and associated rewards in the single-client problem change to lim), we have that which, along with (14) gives us D(λ E ) = n V n (λ E ) − λ EĒ .
Theorem 2: Consider the Primal MDP (1) and its associated dual problem defined in (3). There exists a price λ E such that (π (λ E ), λ E ) is an optimal primal-dual pair and thus the policy π (λ E ) solves the Primal MDP.
Proof: We observe that there is a one-to-one correspondence between any stationary randomized policy, and the measure it induces on the state-action space, and thus the Primal MDP can be posed as a linear program [13], [14]. Thus it follows from Slater's condition [15] that for the Primal MDP, strong duality holds if there exists a policy π that satisfies the constraints lim sup t→∞ 1 t E n s E n (s) <Ē. However the policy which never schedules any packets incurs a net power expenditure of 0, and thus Slater's condition is true for the Primal MDP ifĒ > 0. The claim of the Theorem then follows from Lemma 3. We note that the policy π (λ E ) is a decentralized policy. That is, the decision to choose the video-quality and power-level at each time t for client n, i.e., (q n (t), E n (t)) can be taken by client n itself, and doesn't require the AP to co-ordinate the clients. Thus a client n need not know the state values of other clients, l m (t) for m = n, nor does the AP need to know the values of l n (t). Thus the policy is easy to implement.

A. Obtaining λ E iteratively in a decentralized fashion
We note that in order to implement the optimal policy π (λ E ) as in Theorem 2, we need to find the optimal value of the price λ E . We iterate on the price λ E using the sub-gradient method [16], and since the problem is concave, the prices converge to the optimal value λ E . Moreover the iterations involving price-updates are decentralized, i.e., the clients need only the knowledge of the current price λ E for the iteration.
where E π (λ E ) n τ (n, π (λ E )) is the expected cost incurred on the power over all the users. This is the total "congestion" at the AP. The iteration for λ E is, where d k is the sub-gradient evaluated in (15).

VIII. FADING CHANNELS
The results in the previous sections can be extended in a straight forward manner to the case of fading channels. Let the channel conditions for client n be described by a Markov process evolving on finitely many states {1, 2, . . . , C n } having a transition matrix Π n . The state of client n is described by the vector x n (t) := (l n (t), c n (t)), where l n (t) is the play-time duration of the packets present in the buffer at time t, and c n (t) is the channel condition at time t. If the client n is scheduled a packet transmission of quality q at an power E at time t, then the system state at time t + 1 is (S(l(t)),c) with a probability P n,cn(t) (q, E)Π(c n (t),c), while it is (F(l(t)),c) with a probability P n,cn(t) (q, E)Π(c n (t),c).
However now the cost associated to an action u also depends on the channel condition, i.e., and a threshold policy will have a threshold structure for each value of channel condition (as defined in Section V).

IX. CONCLUDING REMARKS
We have formulated the problem of dynamically choosing the qualities and power levels for packet transmissions across unreliable wireless so as to maximize the Quality of Experience of video streaming channels as an MDP. Using Lagrangian techniques, we have shown that the problem exhibits a decentralized solution, wherein the clients can dynamically decide these quantities on their own using their local information, i.e., the channel state and the amount of playtime remaining in their buffers. Thus the optimal policy can be obtained in time linear in the number of users.
Furthermore we have shown that the optimal policy has a threshold structure, thus further reducing the complexity of searching for the optimal policy. Moreover due to the threshold nature of the policy, it is easy to implement.