A Parameter-free Nonconvex Low-rank Tensor Completion Model for Spatiotemporal Traffic Data Recovery

Yang He, Yuheng Jia, Liyang Hu, Chengchuan An, Zhenbo Lu, Jingxin XiaarXiv 2022 · DOI · arXiv

Abstract

Reliable traffic data is fundamental to Intelligent Transportation Systems (ITS). However, real-world data often suffers from missing values and outliers due to sensor failures or communication issues. While Low-Rank Tensor Completion (LRTC) is a popular recovery technique, existing models typically require manual hyperparameter tuning. This paper introduces a Parameter-free Nonconvex (PFNC) model that utilizes a log-based regularizer to recover spatiotemporal traffic data accurately without manual calibration. We propose two variants: TC-PFNC for missing data recovery and RTC-PFNC for robust recovery in the presence of outliers. Evaluations on four real-world datasets show that our approach outperforms state-of-the-art methods in both accuracy and robustness.

1. Introduction

Intelligent Transportation Systems rely on high-quality spatiotemporal data for traffic forecasting and management. Unfortunately, traffic data is frequently "dirty," characterized by random missing values, non-random blocks of missing data, and anomalous outliers. Traditional recovery methods based on convex nuclear norm minimization often lead to biased results by over-shrinking significant singular values. Conversely, nonconvex methods, while more accurate, often require sensitive hyperparameters like the truncation rank, which vary across different datasets and cities.

2. Problem Formulation and Data Representation

Traffic data is inherently low-rank due to daily periodicities and spatial correlations between adjacent sensors. To exploit this structure, we organize traffic data into a 3D tensor $\mathcal{Y}$ with dimensions representing Space, Time-of-Day, and Day.

Overview of traffic data challenges and the proposed tensor completion framework.

As shown in Figure 1, the raw time series data contains various artifacts. By transforming this data into a tensor, we can leverage multi-dimensional correlations to fill gaps (Random and Nonrandom Missing) and identify potential outliers. This tensor representation allows the model to capture the "pulse" of the city across different temporal scales simultaneously.

3. Methodology

The core innovation of this work is a log-based nonconvex regularizer: $$f(\mathbf{X}) = \sum_{i=1}^{n} \log(\sigma_i(\mathbf{X}) + \epsilon)$$ This function serves as a smooth approximation of the rank function, penalizing smaller singular values (noise) more heavily than larger ones (signal). Unlike standard nuclear norm methods, this approach avoids the "over-shrinking" of primary traffic patterns.

3.1 TC-PFNC and RTC-PFNC

We develop two models based on this regularizer:

  • TC-PFNC: A tensor completion model optimized for scenarios with missing data.
  • RTC-PFNC: A robust version that decomposes the observed tensor $\mathcal{Y}$ into a low-rank component $\mathcal{L}$ and a sparse anomaly component $\mathcal{E}$ (i.e., $\mathcal{Y} = \mathcal{L} + \mathcal{E}$).

Both models are solved using the Alternating Direction Method of Multipliers (ADMM), an iterative framework that ensures efficient convergence without the need for manual parameter tuning, making the solution highly "plug-and-play" for traffic engineers.

4. Experimental Evaluation

We evaluated the models on four diverse real-world datasets:

  • PeMS (P): Traffic volume from 228 loop detectors in California.
  • Seattle (S): Traffic speed from 323 loop detectors.
  • Guangzhou (G): Urban traffic speed from 214 road segments.
  • Birmingham (B): Parking occupancy from 30 car parks.

The models were tested against two missing patterns: Random Missing (RM) and Non-random Missing (NM), where entire days or sensor "fibers" are absent.

5. Key Results

The TC-PFNC model consistently achieved superior accuracy compared to state-of-the-art baselines like HaLRTC and LRTC-TNN.

Recovery performance of TC-PFNC across four real-world traffic datasets.

As illustrated in Figure 5, TC-PFNC (red line) closely tracks the ground truth (blue line) across all four datasets, even in regions with significant missing data (indicated by green shaded areas). In the PeMS dataset with 60% missing data, TC-PFNC achieved a Mean Absolute Percentage Error (MAPE) of 3.35%, significantly lower than the 4.77% achieved by the best baseline. Furthermore, RTC-PFNC demonstrated exceptional stability in corrupted environments, maintaining low error rates even when 70% of observations were outliers.

6. Conclusion

The proposed PFNC framework offers a robust, parameter-free solution for traffic data recovery. By utilizing a log-based nonconvex regularizer, the model avoids the bias of convex methods and the parameter sensitivity of existing nonconvex approaches. Future work will focus on incorporating spatial network topology and scaling the ADMM solver for real-time, city-wide applications.

Summary updated

Abstract

Traffic data chronically suffer from missing and corruption, leading to accuracy and utility reduction in subsequent Intelligent Transportation System (ITS) applications. Noticing the inherent low-rank property of traffic data, numerous studies formulated missing traffic data recovery as a low-rank tensor completion (LRTC) problem. Due to the non-convexity and discreteness of the rank minimization in LRTC, existing methods either replaced rank with convex surrogates that are quite far away from the rank function or approximated rank with nonconvex surrogates involving many parameters. In this study, we proposed a Parameter-Free Non-Convex Tensor Completion model (TC-PFNC) for traffic data recovery, in which a log-based relaxation term was designed to approximate tensor algebraic rank. Moreover, previous studies usually assumed the observations are reliable without any outliers. Therefore, we extended the TC-PFNC to a robust version (RTC-PFNC) by modeling potential traffic data outliers, which can recover the missing value from partial and corrupted observations and remove the anomalies in observations. The numerical solutions of TC-PFNC and RTC-PFNC were elaborated based on the alternating direction multiplier method (ADMM). The extensive experimental results conducted on four real-world traffic data sets demonstrated that the proposed methods outperform other state-of-the-art methods in both missing and corrupted data recovery. The code used in this paper is available at: https://github.com/YoungHe49/T-ITSPFNC.
BibTeX
@misc{he2022parameter,
  author = {Yang He and Yuheng Jia and Liyang Hu and Chengchuan An and Zhenbo Lu and Jingxin Xia},
  title = {{A Parameter-free Nonconvex Low-rank Tensor Completion Model for Spatiotemporal Traffic Data Recovery}},
  year = {2022},
  eprint = {2209.13786},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2209.13786},
}
Figure