# Bit Rate Adaptation Using Linear Quadratic Optimization for Mobile Video Streaming
## 4 Approach  
### Linear Quadratic Optimization  
The optimal control theory seeks to operate a system with the minimum cost. If the system dynamics are described by a set of linear differential equations and the cost a quadratic function, the linear quadratic optimization provides the solution for the control problem. In this section, we propose an ABR selection scheme (LQ) based on the control theory using a discrete-time linear quadratic regulator, which uses the playback buffer level as a feedback signal. Based on the control outputs from the linear quadratic regulator, LQ targets the buffer level to maintain the reference buffer level. Figure 1 presents the control loop diagram to design the basic LQ ABR scheme and Table 1 presents its terms. Let \(\hat{R}_{k}\) be the estimated bit rate for \(k\)th chunk by the controller output \(u_{k}\). Suppose that the set of available \(m\) bit rates is \(V=\{v_{1},v_{2},\ldots,v_{m}\}\) where \(v_{1}<v_{2}<\ldots<v_{m}\). The basic LQ ABR scheme works as follows:  
\[e_{i} = B_{i}-q_{0}\qquad i=1\ldots k\] \[S_{k} = \sum_{i=1}^{k-1}e_{i}\] \[u_{k} = -K_{i}pe_{k}-K_{i}S_{k}\] \[\hat{R}_{k} = F\bigg{(}\min(\frac{1}{1(u_{k}>0)u_{k}},v_{m})\bigg{)}\]  
where \(q_{0}\) is the reference buffer level, \(B_{i}\) is the buffer level measured in second when \(i\)th chunk download starts, \(e_{i}\) is the error between the buffer level, \(S_{k}\) is the sum of previous errors, \(F(x)=argmax_{v_{i}\in V}(v_{i}\leq x)\), which is a function to quantize a controller output to an available chunk bit rate, and \(1(\textit{condition})\) is a function to set one if the condition is satisfied and zero otherwise. In this controller system, we seek to keep \(e_{k}\) and \(S_{k}\) close to 0 while maximizing \(\hat{R}_{k}\). We define a two dimensional state vector \(\mathbf{x}_{k}=\left[ \begin{array}{c}e_{k}\\ S_{k}\end{array} \right]\) that evolves as follows:  
\[\mathbf{x}_{k+1} = \mathbf{A}\mathbf{x}_{k}+\mathbf{B}u_{k}\]  
where \(\mathbf{A}=\left[ \begin{array}{cc}1&0\\ 1&1\end{array} \right]\), \(\mathbf{B}=\left[ \begin{array}{c}L\times C_{0}\\ 0\end{array} \right]\), and \(L\) is the chunk length measured in seconds. Then, we formulate a quadratic cost optimization problem for an infinite-horizon where the goal is to minimize the cost function \(J\), i.e., to keep \(\mathbf{x}_{k}\) close to 0 using small \(u_{k}\) (large \(\hat{R}_{k}\)) as:  
\[\underset{u_{k}}{\text{min}} J=\sum_{k=1}^{N}(\mathbf{x}_{k}^{T}\mathbf{Q}\mathbf{x}_{k}+ \rho u_{k}^{2})+\mathbf{x}_{N}^{T}\mathbf{Q}\mathbf{x}_{N}\]  
where \(N\) is the number of chunks in an entire video, \(\mathbf{Q}\) is a \(2\times 2\) dimensional symmetric positive definite _state_ transition matrix, and \(\rho\) is a _control_ weight. Assuming \(N\rightarrow\infty\), the gain matrix for optimal control, \(\mathbf{K}=\left[ \begin{array}{cc}K_{P}&K_{I}\end{array} \right]\), is given by [15]:  
\[\mathbf{K} = (\rho+\mathbf{B}^{T}\mathbf{P}\mathbf{B})^{-1}\mathbf{B}^{T} \mathbf{P}\mathbf{A}\]  
where \(\mathbf{P}\) is the solution of the discrete time algebraic Riccati equation  
\[\mathbf{P} = \mathbf{A}^{T}\mathbf{P}\mathbf{A}-\mathbf{A}^{T}\mathbf{P} \mathbf{B}(\rho+\mathbf{B}^{T}\mathbf{P}\mathbf{B})^{-1}\mathbf{B}^{T} \mathbf{P}\mathbf{A}+\mathbf{Q}.\] \begin{table}
\begin{tabular}{c c} \hline \hline
**Term** & **Descriptions** \\ \hline  & when \(k\)th chunk download starts \\ \hline \(q_{0}\) & Reference buffer level in seconds \\ \(B_{k}\) & Buffer level in seconds \\ \(e_{k}\) & Error between the buffer level and \(q_{0}\) \\ \(S_{k}\) & Sum of previous errors \\ \(u_{k}\) & Controller output \\ \(C_{0}\) & Expected mean throughput \\ \(\hat{R}_{k}\) & Controller estimated bit rate for \(k\)th chunk \\ \(K_{P}\) & Proportional gain \\ \(K_{I}\) & Integral gain \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Notations. Figure 1: Control Loop.