Traffic data imputation via tensor completion based on soft thresholding of Tucker core

José Henrique de Morais Goulart, Alain Y. Kibangou, Gérard FavierTransportation 2017 · DOI

TL;DR

This paper introduces a novel tensor completion method, IFHST, for imputing missing traffic data. By leveraging the compressibility of Tucker core representations and incorporating a soft-thresholding approach with feedback correction, IFHST significantly improves accuracy and computational efficiency compared to existing methods, even in the presence of systematic, long-term data loss.

What Problem Does This Paper Address?

Intelligent transportation systems (ITS) rely heavily on continuous and reliable traffic data for tasks like monitoring, prediction, and management. However, data acquisition is prone to failures, leading to significant data loss (up to 90% in some studies). This missing data can severely impact ITS performance. While various imputation techniques exist, they often struggle with the multidimensional and spatio-temporal nature of traffic data, especially when data loss is systematic (e.g., sensor failures over extended periods). This paper aims to address this challenge by developing a robust and efficient tensor completion method specifically tailored for traffic data imputation.

Methods

The core of the proposed method, IFHST (Imputation scheme with feedback and HOSVD core soft thresholding), is an iterative single imputation scheme. It builds upon the idea of representing traffic data as a tensor and employing a Tucker decomposition. The novelty lies in:

  • Compressible Tucker Model: Instead of assuming a strictly low-rank Tucker model, IFHST assumes a "compressible" Tucker core. This means the core tensor can be well-approximated by a sparse tensor, reflecting the inherent structure and correlations in traffic data. This is motivated by the observation that modal singular values of traffic data often decay rapidly.
  • Soft Thresholding of HOSVD Core: The algorithm iteratively estimates the Tucker model. In each iteration, it computes the Higher-Order Singular Value Decomposition (HOSVD) of the current imputed tensor. The core of this HOSVD is then "soft-thresholded" using an l1-norm regularization term. This process encourages sparsity in the core, effectively promoting a parsimonious representation.
  • Exponentially Decaying Threshold: To balance convergence speed and accuracy, the soft-thresholding parameter ($\tau$) is exponentially decreased over iterations. This allows for faster initial convergence with a strong sparsity prior, followed by refinement.
  • Feedback Correction: A first-order feedback control rule is introduced to update the observed data entries in each iteration. This mechanism uses the previously imputed values and the observed data as setpoints, leading to a significant reduction in steady-state error.

Datasets

The paper uses the Grenoble Traffic Lab (GTL) dataset for evaluation. This dataset comprises time-mean vehicle speeds and vehicle counts collected from 136 magneto-resistive sensors along a highway. The data spans a 91-day period and is sampled every 15 seconds. For their experiments, the authors preprocessed the data by:

  • Discarding data from ramp sensors with high missing data ratios and from Sundays.
  • Thresholding speeds at 90 km/h.
  • Downsampling to per-minute average speeds.
  • Filtering out data outside the 6:00-20:00 window.

The resulting tensor dimensions for speed data are $840 \times 56 \times 78$. The paper also mentions simulating missing data by randomly distributing windows of a specified length ($L$) and sampling ratio ($p$).

Key Insights and Ideas

  • Compressibility over Strict Sparsity: The key insight is that real-world traffic data might not have a strictly low-rank tensor representation, but its Tucker core is often "compressible." This means it can be well-approximated by a sparse tensor, which is a more flexible and realistic assumption.
  • Soft Thresholding as a Parsimony Inducer: Applying soft thresholding to the HOSVD core is an effective way to enforce this compressibility and find a parsimonious Tucker model without pre-specifying a fixed low mrank.
  • Synergy of Techniques: The combination of exponentially decaying thresholds and feedback correction significantly boosts both the convergence speed and the final accuracy of the imputation process.
  • Robustness to Systematic Loss: The IFHST method demonstrates remarkable robustness to systematic data loss, a critical requirement for real-world traffic data imputation where sensor failures are common.

Key Results

The IFHST algorithm consistently outperformed four other tensor completion algorithms and one matrix completion technique across various scenarios.

  • Accuracy: IFHST achieved the smallest errors (RMSEspeed, MAPEspeed, RMSEtt, MAPEtt) in most tested scenarios, particularly in cases of significant data loss (e.g., $L=180$ minutes). For instance, in estimating travel times, IFHST and BCD showed absolute percentage errors of around 3.20% and 3.63% respectively, significantly better than other methods.
  • Computational Efficiency: IFHST was the fastest algorithm among those compared, with computing times consistently under 1.5 minutes for the GTL dataset. This is a significant advantage over other competitive methods like BCD, which took over six times longer.
  • Robustness: The method showed robust performance even with long periods of missing data, a crucial advantage for practical applications.

Limitations and Future Work

  • Exploiting Early Sparsity: The authors note that the typical sparsity of the thresholded core in the early iterations of the algorithm was not fully exploited for computational efficiency. Future work could incorporate this to further reduce computing time.
  • Parameter Tuning: While the paper suggests parameter values that yield satisfactory results, a systematic way of choosing parameters like $\psi$ and $\gamma$ is still an open area.
  • Noise Reduction: The paper briefly mentions that parsimonious models can inherently perform noise reduction. Further investigation into this aspect could be beneficial.

Summary updated

BibTeX
@inproceedings{goulart2017traffic,
  author = {José Henrique de Morais Goulart and Alain Y. Kibangou and Gérard Favier},
  title = {{Traffic data imputation via tensor completion based on soft thresholding of Tucker core}},
  booktitle = {Transportation},
  year = {2017},
  doi = {10.1016/j.trc.2017.09.011},
}
Figure