Low-Rank Matrix and Tensor Factorization for Speed Field Reconstruction

Introduce a sequence of matrix/tensor factorization methods and their applications to traffic flow modeling

Matrix factorization is a classical method for reconstructing missing values in matrix data. In such method, we can decompose a matrix into two factor matrices if it is possible to formulate a certain kind of optimization problem for the factorization. Tensor factorization is a higher-order extension of matrix factorization, showing a more complicated formula. In this story, we will first introduce a benchmark problem as speed field reconstruction in road traffic flow modeling. Then, on the well-defined problem, we are trying to find and provide a sequence of matrix and tensor factorization methods for imputing missing values in the given data matrix. Finally, we will provide some reconstruction results to make comparison among these matrix and tensor factorization methods.

Content:

• Motivation
• Matrix factorization

a) Optimization problem; b) Gradient descent; c) Steepest gradient descent; d) Alternating least squares; e) Comparison among GD, SGD, and ALS.

• Smoothing matrix factorization
• Tensor factorization

a) What is tensor? b) Tensor decomposition: A brief history; c) Hankel matrix & Hankel tensor; d) Hankel tensor factorization.

• Which model is better?
• Conclusion

Let’s get started!

Motivation

In real-world transportation systems, it is possible to gather traffic state information from highway and urban road networks. These traffic state variables include traffic volume and traffic speed. As an example, Figure 1 shows a publicly available dataset for traffic states of highways. In the right panel of Figure 1, we have a speed field in the form of matrix, showing rows as spatial locations and columns as time steps. Without loss of generality, the speed field can be represented as a matrix such as Y of size N-by-T (i.e., N rows and T columns). As can be seen, this speed field also demonstrates very strong spatial dependencies and temporal dependencies.

Figure 1. Portland traffic speed dataset (see https://portal.its.pdx.edu/home). (Left panel) Portland highway network and sensing system. (Right panel) Traffic speed data over consecutive locations and a certain time period.