# Representing and Inferring Massive Network Traffic Condition: A Case Study in Nashville, Tennessee
## 2 Materials and Methods
### CIR Decomposition  
This section will briefly describe the details of different CUR decomposition methods and present the proposed column-based CUR decomposition algorithm integrated with clustering method. As shown in Figure 3, let \(\mathbf{A}\in\mathbb{R}^{t\times n}\) denote the original data matrix with t time instances in row and n detector links in column. Firstly, we define a compression rate as the ratio of number of selected columns to the total number of columns in matrix \(\mathbf{A}\) (CR = c/n). The objective of column-based CUR is to find a submatrix \(\mathbf{C}\in\mathbb{R}^{t\times c}\) consisting of c columns of \(\mathbf{A}\) to create a low-rank approximation \(\hat{\mathbf{A}}\) as shown in Equation (1):  
\[\mathbf{A}\approx\hat{\mathbf{A}}=\mathbf{C}\mathbf{X}=\mathbf{C}\mathbf{C}^{ +}\mathbf{A}, \tag{1}\]  
where  
* \(\mathbf{C}^{+}\) is Moore-Penrose pseudo-inverse of matrix \(\mathbf{C}\)[20]. Figure 1: (**a**) Location of Nashville, TN, on US map; (**b**) RDS detector locations in Nashville, TN. Figure 2: Input data matrix with training period in red rectangle and testing period in the green rectangle; columns in blue rectangles represent the selected group of detectors and blue shaded areas are data entries for testing period at selected detector locations. * \(\mathbf{X}=\mathbf{C}^{+}\mathbf{A}\) (\(\mathbf{X}\in\mathbb{R}^{\mathbf{c}\times\mathbf{n}}\)) is the relationship matrix which projects the selected columns back onto all the columns in original data space [21]. For the given matrices \(\mathbf{A}\) and \(\mathbf{C}\), the relationship matrix is computed as the matrix product of \(\mathbf{C}^{+}\) and \(\mathbf{A}\). The crucial problem with CUR method is how to select the most representative columns so that the relative error between approximation matrix and original matrix is as small as possible. The goal is to capture the essential information in the data while reducing dimensionality. To evaluate the approximation result, we calculated the percent-root-mean-square distortion (PRD), which is commonly used to assess reconstruction performance [22], provided by the following formula:  
\[\text{PRD}\;(\%)=\frac{\left\|\mathbf{A}-\mathbf{C}\mathbf{X}\right\|_{ \text{F}}}{\left\|\mathbf{A}\right\|_{\text{F}}}, \tag{2}\]  
where  
\[\left\|\mathbf{A}\right\|_{\text{F}}=\left(\sum_{\text{i}}\sum_{\text{j}} \mathbf{a}_{\text{ij}}^{2}\right)^{\frac{1}{2}} \tag{3}\]  
And it represents the Frobenius norm of matrix \(\mathbf{A}\). A lesser PRD represents a better compression result. More specifically, we can break down the column-based CUR method into the following steps:  
1. Determine the importance score of each column in the network matrix. Each column in the matrix \(\mathbf{A}\) is assigned a probability score indicating its likelihood of being selected;
2. Create matrix \(\mathbf{C}\) by selecting top c columns from matrix \(\mathbf{A}\) in the descending order of probability scores calculated in the first step;
3. Calculate the relationship matrix \(\mathbf{X}=\mathbf{C}^{+}\mathbf{A}\) (\(\mathbf{X}\in\mathbb{R}^{\mathbf{c}\times\mathbf{n}}\));
4. Assume traffic is stationary, infer the future traffic speed for the entire network using only speed measurements at the selected link, and calculate PRD for the testing data as the performance measurement. Step 1 is clearly the most essential step in the CUR process. To identify the optimal set of columns for a specified number of columns, one would normally need to evaluate all possible \( \begin{pmatrix}n\\ c\end{pmatrix} \) combinations. Nevertheless, employing a brute-force approach entails a computational complexity of \(\text{O}(n^{c})\)[23]. Given this computational burden, it is usually  
Figure 3: CUR decomposition. impractical to assess every potential selection of c columns.