# Representing and Inferring Massive Network Traffic Condition: A Case Study in Nashville, Tennessee
## 2 Materials and Methods
### CIR Decomposition
To tackle this challenge, two major randomized algorithms have been introduced [21; 24] to compute the importance score of each column and then sample columns based on the score:  
* L2 norm-based: this method calculates the square of L2 norm for each column and divides it by the sum of squares of all entries of the matrix, expressed as the following equation: \[\mathrm{P_{j}^{L2}}=\frac{\sum_{i=1}^{t}\mathrm{A(i,\,j)}^{2}}{\sum_{i=1}^{t} \sum_{j=1}^{n}\mathrm{A(i,\,j)}^{2}},\] (4) where j = 1, 2, 3, \(\ldots\), n. The concept behind this method is to select detector links with high speed. L2 norm-based sampling offers benefits like rapid computation and a better understanding of the column magnitudes. The drawback lies in the neglect of detectors that record a significant portion of low-speed intervals, leading to substantial estimation errors during congestion periods. * Leverage-based: this method utilizes statistical leverage [9], which measures the contribution of each column to the overall variance of the data, as the importance score for each column. The importance score can be conceptually understood as quantifying the \"statistical leverage\" or \"impact\" of a specific column on achieving the most accurate low-rank approximation of the data matrix. By prioritizing the selection of columns that has a disproportionately significant influence over the low-rank approximation, as opposed to L2 norm method that samples columns with higher Euclidean distances, we can ensure that CUR performs nearly as effectively as the best rank-k approximation \(\mathbf{A_{k}}\) in capturing the predominant portion of the spectrum of A [9]. Columns with high leverage scores are often considered important. The underlying concept is to consider detector links with large variations in speed, thus covering various traffic conditions and providing a better capture of the detectors with different traffic states. However, the limitations associated with this approach include the substantial computational cost. The detailed steps are described as follows. Firstly, singular value decomposition (SVD) is performed on the original data matrix \(\mathbf{A}\)[11] to represent \(\mathbf{A}\) as:  
\[\mathbf{A}=\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{\mathbf{T}}, \tag{5}\]  
where \(\mathbf{U}\in\mathbb{R}^{t\times t}\) and \(\mathbf{V}\in\mathbb{R}^{n\times n}\) are unitary matrices, and the columns of \(\mathbf{U}\) and \(\mathbf{V}\) are left and right singular vectors of \(\mathbf{A}\), respectively. Matrix \(\boldsymbol{\Sigma}\in\mathbb{R}^{t\times n}\) is a rectangular diagonal matrix with non-negative diagonal entries, known as the singular values of matrix \(\mathbf{A}\). Then, the best rank-k approximation can be obtained by keeping top k columns of \(\mathbf{U}\), \(\boldsymbol{\Sigma}\), and \(\mathbf{V}\) so that the explained variance is at least 80%:  
\[\mathbf{A_{t\times n}}=\mathbf{U_{t\times k}}\boldsymbol{\Sigma_{t\times k}} \mathbf{V}_{k\times n}^{\mathbf{T}}. \tag{6}\]  
Then, the leverage score of column j can be calculated as:  
\[\mathrm{P_{j}^{SVD}}=\frac{1}{\xi}\sum_{\xi=1}^{k}\left(\mathbf{v}_{j}^{\xi} \right)^{2}, \tag{7}\]  
where \(\mathbf{v}_{j}^{\xi}\) is the jth coordinate of \(\xi\)th right singular vector. It is obvious that the sum of \(\mathrm{P_{j}}\) is equal to one because matrix \(\mathbf{V}\) is unitary. Based on the two previous options, we propose a weighted method considering both L2 norm and statistical leverage, expressed as Equation (8):  
\[\mathrm{P_{j}^{W}}=\mathrm{w}\cdot\mathrm{P_{j}^{L2}}+(1-\mathrm{w})\cdot \mathrm{P_{j}^{SVD}}, \tag{8}\]  
where w is a weight parameter, and w is set to be 0.5 in this study to assign equal weights to column magnitude and column variation. In addition to the three options, a random sampling method to select c columns with equal probability for each column is also implemented. This process was repeated five times, and average performance was recorded.