Low-Rank Autoregressive Tensor Completion for Spatiotemporal Traffic Data Imputation

Xinyu Chen; Mengying Lei; Nicolas Saunier; Lijun Sun

Source-linked AI summary

Low-Rank Autoregressive Tensor Completion for Spatiotemporal Traffic Data Imputation

Xinyu Chen, Mengying Lei, Nicolas Saunier, Lijun Sun

arXiv:2104.14936v1Apr 30, 2021cs.LGstat.ML

TL;DR

Incomplete and corrupted traffic data require imputation that captures both global structure and local temporal consistency. LATC combines truncated-nuclear-norm tensor completion with learnable autoregressive temporal variation, and experiments report advantages over other low-rank models across diverse missing scenarios.

Problem
Spatiotemporal traffic data are often incomplete, while low-rank completion can preserve global structure but overlook local temporal consistency.
Method
LATC completes a sensor × time-of-day × day tensor using truncated nuclear norm regularization and autoregressive temporal variation with learnable coefficients.
Results
Experiments on real-world traffic datasets show LATC advantages over other low-rank models across evaluated missing scenarios.
Takeaways & Limitations
Combining tensor structure with temporal autoregressive modeling provides a framework for traffic imputation and can also support forecasting with missing values.

Abstract

from arXiv · show

Spatiotemporal traffic time series (e.g., traffic volume/speed) collected from sensing systems are often incomplete with considerable corruption and large amounts of missing values, preventing users from harnessing the full power of the data. Missing data imputation has been a long-standing research topic and critical application for real-world intelligent transportation systems. A widely applied imputation method is low-rank matrix/tensor completion; however, the low-rank assumption only preserves the global structure while ignores the strong local consistency in spatiotemporal data. In this paper, we propose a low-rank autoregressive tensor completion (LATC) framework by introducing \textit{temporal variation} as a new regularization term into the completion of a third-order (sensor $\times$ time of day $\times$ day) tensor. The third-order tensor structure allows us to better capture the global consistency of traffic data, such as the inherent seasonality and day-to-day similarity. To achieve local consistency, we design the temporal variation by imposing an AR($p$) model for each time series with coefficients as learnable parameters. Different from previous spatial and temporal regularization schemes, the minimization of temporal variation can better characterize temporal generative mechanisms beyond local smoothness, allowing us to deal with more challenging scenarios such "blackout" missing. To solve the optimization problem in LATC, we introduce an alternating minimization scheme that estimates the low-rank tensor and autoregressive coefficients iteratively. We conduct extensive numerical experiments on several real-world traffic data sets, and our results demonstrate the effectiveness of LATC in diverse missing scenarios.

I. INTRODUCTION

The paper addresses incomplete spatiotemporal traffic data by combining tensor completion with autoregressive temporal modeling. LATC is designed to capture both global traffic structure and local temporal consistency while supporting challenging missing-data scenarios.

Traffic data are large-scale, high-dimensional, and incomplete, making reliable imputation important for forecasting and traffic management.
Low-rank matrix and tensor completion captures spatial-temporal correlations, but conventional low-rank models primarily represent global structure.
LATC combines truncated nuclear norm minimization with autoregressive temporal variation to model global patterns and local trends.
The third-order sensor × time-of-day × day tensor represents day-to-day similarity, while autoregressive errors quantify temporal variation.
An alternating learning algorithm updates the tensor and coefficient matrix separately, using ADMM for the tensor and closed-form least squares for coefficients.
Experiments on four traffic datasets report that LATC outperforms recent state-of-the-art models across evaluated missing-data scenarios.

IV. METHODOLOGY

The methodology represents traffic observations as a sensor-by-time matrix, tensorizes the temporal dimension into time of day and day, and completes the resulting low-rank tensor. This representation preserves global periodic structure while retaining the original matrix form for temporal modeling.

The true traffic data matrix contains sensor rows and time-point columns, while observed entries are represented by the projection PΩ(Y).
A. Tensorization for Global Consistency: The forward tensorization operator Q(·) converts the matrix into a third-order sensor × time-of-day × day tensor.
A. Tensorization for Global Consistency: The inverse operator Q^-1(·) reconstructs the original sensor-by-time matrix from the tensor.
A. Tensorization for Global Consistency: Tensorization changes matrix completion into low-rank tensor completion, enabling representation of periodic, seasonal, cyclical, and short-term traffic patterns.

B. Temporal Variation for Local Consistency

LATC models temporal variation as autoregressive fitting error while combining it with truncated nuclear norm minimization to enforce local and global consistency. An alternating scheme updates tensor-related variables and autoregressive coefficients under observation constraints.

Temporal variation: Temporal variation quantifies the total squared autoregressive fitting error across individual time series.Minimizing it encourages the completed series to exhibit stronger temporal consistency under learnable coefficients.
LATC objective: LATC combines truncated nuclear norm minimization with temporal variation minimization to enforce global and local consistency.The weight λ controls the trade-off between these two components.
Optimization: The alternating minimization scheme fixes the autoregressive coefficients while updating X and Z, then estimates the coefficient matrix through least squares.The X-update can use ADMM while the coefficient update is formulated as a least-squares problem.
Optimization: ADMM maintains observation consistency by keeping PΩ(Z) = PΩ(Y ) fixed while solving the tensor subproblem iteratively.The ADMM subproblems update tensor variables and dual variables during the inner iterations.

1) Update Variable X:

The X-update handles the truncated nuclear norm by introducing mode-specific unfolding variables and applying generalized singular value thresholding. The resulting mode updates are gathered to produce the updated tensor variable.

1) Update Variable X:: Mode-specific variables X 1, X 2, and X 3 represent the unfoldings of X for truncated nuclear norm minimization.They allow the tensor unfolding subproblems to be solved separately despite dependencies across modes.
1) Update Variable X:: The framework models each time series with autoregressive coefficients for time lags H = {1, 2}.The figure illustrates the autoregressive structure associated with the time-series representation.
1) Update Variable X:: Generalized singular value thresholding provides the closed-form solution for each truncated nuclear norm subproblem.The operator applies positive truncation to singular values after preserving the first r components.
1) Update Variable X:: The updated tensor X is obtained by gathering the results from the three unfolding-specific variables.This aggregation follows the mode-wise thresholding steps.

2) Update Variable Z:

The Z-update minimizes autoregressive errors using a vector-form least-squares formulation, while the coefficient update estimates A from the current completed series. The algorithm alternates these updates with ADMM-based tensor processing until convergence.

2) Update Variable Z:: The Z-update uses the vector-form autoregressive error objective because the matrix-form solution can require complicated and costly operations.The vector formulation yields a closed-form solution for updating the completed time-series representation.
2) Update Variable Z:: With known coefficients and lag matrices, each time series has a least-squares solution for the Z-update.The solution can also be interpreted through a sparse linear equation involving matrices Bm.
2) Update Variable Z:: The implementation alternates tensor and coefficient updates, maintaining observation information and returning the recovered matrix after convergence.Initialization includes zero dual variables and small random autoregressive coefficients; ADMM parameters are updated during the iterations.
2) Update Variable Z:: The coefficient matrix A is estimated by solving a least-squares problem built from lagged vectors of the updated time series.The resulting optimization has a closed-form solution using the constructed design matrices.
2) Update Variable Z:: Parameter ρ controls ADMM and singular-value thresholding, while λ trades off truncated nuclear norm and temporal variation.The recovered matrix is computed at each outer iteration and the converged result is returned when convergence criteria are met.

V. EXPERIMENTS

The experiments evaluate LATC on real-world traffic data sets with different missing patterns.

V. EXPERIMENTS: The evaluation uses several real-world traffic data sets spanning different missing patterns.The passage states the experimental scope but does not report quantitative results.

A. Traffic Data Sets

The benchmark uses four real-world traffic datasets spanning urban speed, metro passenger flow, freeway speed, and highway volume, with different sensor counts, durations, and temporal resolutions.

The Guangzhou dataset contains speed from 214 road segments over 61 days at 10-minute resolution, represented as a 214 × 144 × 61 tensor.
The Hangzhou dataset contains passenger flow from 80 metro stations over 25 days at 10-minute resolution, represented as an 80 × 108 × 25 tensor.
The Seattle dataset contains speed from 323 loop detectors over four weeks at 5-minute resolution, represented as a 323 × 288 × 28 tensor.
The Portland dataset contains volume from 1156 loop detectors during January 2021 at 15-minute resolution, represented as a 1156 × 96 × 31 tensor.

B. Missing Data Generation

The experiments evaluate imputation under random, non-random, and blackout missingness, using masked observations and actual values as ground truth for MAPE and RMSE.

Random missingness masks observations at selected rates, while non-random missingness removes observations continuously during selected periods.
Blackout missingness masks observations from all spatial locations over a time window, creating complete column-wise missingness.
The experiments use a 30% missing rate for the reported evaluations.
MAPE and RMSE are computed by comparing imputed values with the actual values of masked entries.

C. Baseline Models

LATC is compared with matrix completion, tensor completion, Bayesian temporal factorization, and smooth tensor completion baselines.

LAMC is the matrix-form variant of the LATC model.
LRTC-TNN performs low-rank tensor completion using truncated nuclear norm minimization to preserve important low-rank patterns.
BTMF is a Bayesian temporal matrix factorization framework that models temporal dynamics through vector autoregression on latent factors.
SPC is a tensor-decomposition completion model with total-variation smoothness constraints.

D. Results

LATC shows dataset- and missingness-dependent sensitivity to its temporal-variation weight and truncation, and generally outperforms the compared low-rank models across the evaluated traffic datasets.

Guangzhou sensitivity: For Guangzhou data, RM and BM performance is best at c = 10 with little sensitivity to r, whereas NM performs best at relatively small r values such as 5 or 10.
Hangzhou sensitivity: For Hangzhou data, RM and BM perform best at c = 1, while NM performs best with small c and r values such as 5.
Other datasets: Seattle results show positive temporal-variation influence for BM, while Portland results show that c values such as 5 and 10 reduce sensitivity to truncation for RM and BM.
Overall comparison: Across four datasets and missing scenarios, LATC generally outperforms the baselines; tensor structure improves over LAMC, and autoregressive temporal modeling improves over LRTC-TNN.
Imputation examples: LATC accurately imputes examples with severe NM and BM missingness, but LRTC-TNN outperforms LATC on Hangzhou passenger flow where the signal lacks strong temporal dependencies.
Conclusion: The conclusion reports advantages over other low-rank models and notes that LATC can also support spatiotemporal traffic forecasting with missing values.

APPENDIX A SUPPLEMENTARY THEOREM

The appendix derives an optimal solution for an autoregressive tensor-completion subproblem by vectorizing the objective and expressing its matrices with Kronecker products. The resulting closed-form update reconstructs the vectorized tensor from the observed matrix and model operators.

Theorem 1: Theorem 1 defines matrix operators B and C from autoregressive and temporal-difference terms using Kronecker products.B = (I_M ⊗ Φ_0), while C = (I_M ⊗ Φ)[(I_M ⊙ A^T) ⊗ I_T].
Proof: Vectorization converts the subproblem into a quadratic objective involving the transformed tensor and its observed counterpart.The proof denotes the objective by f and uses vec(Z^T) and vec(X^T) as the optimization variables and data representation.
Closed-form solution: The optimal vectorized tensor is obtained by applying a regularized inverse operator to the vectorized observed matrix.The closed-form update is vec(Z^T) = α[(B − C)^T(B − C) + αI_MT]^-1 · vec(X^T).