A Truncated SVD-Based ARIMA Model for Multiple QoS Prediction in Mobile Edge Computing

We aim to predict all the QoS values at time slots $T+1$ simultaneously. Here, we formulate the problem as a TSF problem. $\chi$ can be considered as a sequence of matrices ${\chi }_1,{\chi }_2,\mathrm{\dots },{\chi }_T$ , where ${\chi }_t$ represents the historical QoS matrix at time slot $t$ . Letting ${\mathrm{\Delta }}^d\chi$ denote the $d$ -order differencing of $\chi$ , then

(7) $${\mathrm{\Delta }}^d\chi =\{{\mathrm{\Delta }}^d{\chi }_d,{\mathrm{\Delta }}^d{\chi }_{d+1},\mathrm{\dots },{\mathrm{\Delta }}^d{\chi }_T\}$$

As a user only invokes a tiny proportion of services, the QoS data of a user are very sparse. To reduce the computational and storage cost, we compress the columns of ${\mathrm{\Delta }}^d{\chi }_t$ through the truncated SVD method, which can be represented as

(8) $${\mathrm{\Delta }}^d{\kappa }_t={\mathrm{\Delta }}^d{\chi }_{t}V,$$ $$\mathrm{s}.\mathrm{t}.\mathit{\hspace{1em}}{\mathrm{VV}}^{\mathrm{T}}=I$$

where $V\in {\text{𝐑}}^{N\times R}$ is an orthogonal factor matrix, and $R\ll N$ . ${\mathrm{\Delta }}^d{\kappa }_t\in {\text{𝐑}}^{M\times R}$ is the compressed matrix of ${\mathrm{\Delta }}^d{\chi }_t$ , which represents the most important feature of ${\mathrm{\Delta }}^d{\chi }_t$ , but has many fewer elements than ${\mathrm{\Delta }}^d{\chi }_t$ . ${\mathrm{\Delta }}^d{\chi }_t$ can be recovered by ${\mathrm{\Delta }}^d{\kappa }_t$ and $V$ ,

(9) $$\widehat{{\mathrm{\Delta }}^d{\chi }_t}={\mathrm{\Delta }}^d{\kappa }_t{V}^{\mathrm{T}}$$

The first goal of our optimization is to minimize the difference between ${\mathrm{\Delta }}^d{\chi }_t$ and $\widehat{{\mathrm{\Delta }}^d{\chi }_t}$ .

To reduce the computational cost, we incorporate the compressed matrix instead of the original QoS matrix into the ARIMA model. Therefore, the generalized ARIMA model is defined as follows:

(10) $${\mathrm{\Delta }}^d{\kappa }_t={\displaystyle \underset{i=1}{\overset{p}{\sum }}}{\gamma }_i{\mathrm{\Delta }}^d{\kappa }_{t-i}-{\displaystyle \underset{j=1}{\overset{q}{\sum }}}{\theta }_j{ϵ}_{t-j}+{ϵ}_t$$

where ${\gamma }_i$ and ${\theta }_j$ are the parameters of AR and MA respectively, and ${ϵ}_{t-j}$ is the random error terms of the past $q$ observations, which are assumed to be independent, identically distributed variables with zero mean. ${ϵ}_t$ is the prediction error at the current time slot. Therefore, our second goal is to minimize ${ϵ}_t$ to zero. On the basis of the two goals of our optimization, the objective function can be defined as follows:

(11) $$\underset{\{{\mathrm{\Delta }}^d{\kappa }_t,V,{ϵ}_{t-j},{\gamma }_i,{\theta }_j\}}{\min }{\displaystyle \underset{t=s+1}{\overset{T}{\sum }}}({\displaystyle \frac{1}{2}}\Vert {\mathrm{\Delta }}^d{\kappa }_t-{\mathrm{\Delta }}^d{\chi }_{t}V{\Vert }_F^2+$$ $${\displaystyle \frac{1}{2}}\Vert {\mathrm{\Delta }}^d{\kappa }_t-{\displaystyle \underset{i=1}{\overset{p}{\sum }}}{\gamma }_i{\mathrm{\Delta }}^d{\kappa }_{t-i}+{\displaystyle \underset{j=1}{\overset{q}{\sum }}}{\theta }_j{ϵ}_{t-j}{\Vert }_F^2)$$

where $s=p+d+q$ , which is the minimum number of time slots.

We adopt the augmented Lagrangian method, which is widely used in mathematical optimization problems, to minimize the above objective function. We first fix $V,{ϵ}_{t-j},{\gamma }_i,$ and ${\theta }_j$ , compute the partial derivation of the objective function ( 11 ) with respect to ${\mathrm{\Delta }}^d{\kappa }_t$ , and equate it to zero. Then, we can obtain the updated formulation of ${\mathrm{\Delta }}^d{\kappa }_t$ as follows:

(12) $${\mathrm{\Delta }}^d{\kappa }_t={\displaystyle \frac{1}{2}}({\mathrm{\Delta }}^d{\chi }_{t}V+{\displaystyle \underset{i=1}{\overset{p}{\sum }}}{\gamma }_i{\mathrm{\Delta }}^d{\kappa }_{t-i}-{\displaystyle \underset{j=1}{\overset{q}{\sum }}}{\theta }_j{ϵ}_{t-j})$$

Formula ( 11 ) with respect to $V$ is

(13) $$\underset{\{V\}}{\min }{\displaystyle \underset{t=s+1}{\overset{T}{\sum }}}\left({\displaystyle \frac{1}{2}}{\Vert {\mathrm{\Delta }}^d{\kappa }_t-{\mathrm{\Delta }}^d{\chi }_{t}V\Vert }_F^2\right),$$ $$\mathrm{s}.\mathrm{t}.\mathit{\hspace{1em}}{\mathrm{VV}}^{\mathrm{T}}=I$$

which is equivalent to the orthogonal Procrustes problem^{[ 22 ]}. Then the global optimal solution of Formula ( 13 ) is ${\mathrm{BA}}^{\mathrm{T}}$ . $A$ and $B$ are the left and right singular vectors of the singular value decomposition of ${\displaystyle \underset{t=s+1}{\overset{T}{\sum }}}({\mathrm{\Delta }}^d{\kappa }_t^{\mathrm{T}}{\mathrm{\Delta }}^d{\chi }_t)$ , respectively, which is calculated as

(14) $${\displaystyle \underset{t=s+1}{\overset{T}{\sum }}}({\mathrm{\Delta }}^d{\kappa }_t^{\mathrm{T}}{\mathrm{\Delta }}^d{\chi }_t)=A\mathrm{\Sigma }{B}^{\mathrm{T}}$$

The parameters of AR and MA are typically minimized using Yule-Walker method in classical ARIMA. Calculate the partial derivation of Formula ( 11 ) with respect to ${ϵ}_{t-j}$ , and equate it to zero. Then, ${ϵ}_{t-j}$ can be updated by

(15) $${ϵ}_{t-j}=$$ $${\displaystyle \frac{{\displaystyle \underset{t=s+1}{\overset{T}{\sum }}}\left({\mathrm{\Delta }}^d{\kappa }_t-{\displaystyle \underset{i=1}{\overset{p}{\sum }}}{\gamma }_i{\mathrm{\Delta }}^d{\kappa }_{t-i}+{\displaystyle \underset{k\ne j}{\overset{q}{\sum }}}{\theta }_k{ϵ}_{t-k}\right)}{(s+1-T){\theta }_j}}$$

Formally, we summarize the pseudo-code of the model learning process in Algorithm 1.

We calculate the new ${\mathrm{\Delta }}^d{\kappa }_{T+1}$ by

(16) $${\mathrm{\Delta }}^d{\kappa }_{T+1}={\displaystyle \underset{i=1}{\overset{p}{\sum }}}{\gamma }_i{\mathrm{\Delta }}^d{\kappa }_{T+1-i}-{\displaystyle \underset{j=1}{\overset{q}{\sum }}}{\theta }_j{ϵ}_{T+1-j}$$

Then, we reconstruct the new ${\mathrm{\Delta }}^d{\chi }_{T+1}$ according to Eq. ( 9 ). Finally, we perform inverse d-order differencing for ${\mathrm{\Delta }}^d{\chi }_{T+1}$ and obtain ${\chi }_{T+1}$ . The pseudo-code of the prediction process can be described in Algorithm 2.