Source-linked AI summary
A Nonconvex Low-Rank Tensor Completion Model for Spatiotemporal Traffic Data Imputation
Xinyu Chen, Jinming Yang, Lijun Sun
TL;DR
Missing data limit the utility of spatiotemporal traffic data, motivating accurate imputation that captures their higher-order structure. The paper develops LRTC-TNN with flexible tensor truncation and ADMM optimization, and reports consistent superiority across four data sets, missing patterns, and rates, including extreme missing scenarios.
Problem
Missing data in spatiotemporal traffic observations threaten their utility for intelligent transportation applications, while convex nuclear norm relaxation may insufficiently approximate rank.
Method
The paper formulates imputation as low-rank tensor completion with a tensor truncated nuclear norm, a universal truncation-rate parameter, and an ADMM-based optimization procedure.
Results
LRTC-TNN consistently outperforms state-of-the-art imputation models on four real-world traffic data sets across random and non-random missing patterns, including extreme missing scenarios.
Takeaways & Limitations
The results support tensor representations with an additional day dimension for capturing low-rank structure in traffic time series at different temporal scales.
Takeaways & Limitations
The tensor nuclear norm uses the same αk for all three unfoldings despite heterogeneous sensor, time-of-day, and day dimensions.
Abstract
from arXiv · showhide
Sparsity and missing data problems are very common in spatiotemporal traffic data collected from various sensing systems. Making accurate imputation is critical to many applications in intelligent transportation systems. In this paper, we formulate the missing data imputation problem in spatiotemporal traffic data in a low-rank tensor completion (LRTC) framework and define a novel truncated nuclear norm (TNN) on traffic tensors of location$\times$day$\times$time of day. In particular, we introduce an universal rate parameter to control the degree of truncation on all tensor modes in the proposed LRTC-TNN model, and this allows us to better characterize the hidden patterns in spatiotemporal traffic data. Based on the framework of the Alternating Direction Method of Multipliers (ADMM), we present an efficient algorithm to obtain the optimal solution for each variable. We conduct numerical experiments on four spatiotemporal traffic data sets, and our results show that the proposed LRTC-TNN model outperforms many state-of-the-art imputation models with missing rates/patterns. Moreover, the proposed model also outperforms other baseline models in extreme missing scenarios.
1. Introduction
Spatiotemporal traffic data are important but frequently incomplete, especially under realistic non-random patterns. The paper proposes a domain-informed low-rank tensor completion model using truncated nuclear norm minimization and evaluates it across diverse missing scenarios.
- Missing traffic data undermine intelligent transportation applications and can result from sensor malfunctioning, communication failure, or maintenance.
- Non-random missingness, including data lost continuously for several hours or days, is more realistic and challenging than random missingness.
- Low-rank methods exploit higher-order correlations and dependencies, while traffic tensors preserve daily patterns across location, day, and time of day.
- Convex nuclear norm minimization may inadequately approximate rank because it simultaneously minimizes all singular values.
- LRTC-TNN defines a tensor truncated nuclear norm and uses a universal rate parameter to flexibly control truncation across all tensor modes.
- Across four traffic data sets, LRTC-TNN outperforms state-of-the-art imputation models across missing rates and patterns, including a 70% missing-rate case.
2. Methodology
The methodology formulates spatiotemporal traffic imputation as low-rank tensor completion and replaces convex nuclear-norm minimization with a tensor truncated nuclear norm controlled by a universal truncation rate. Auxiliary variables and ADMM yield tractable iterative subproblems, with generalized singular-value thresholding providing optimal or suboptimal updates.
- Low-Rank Tensor Completion: LRTC models a partially observed third-order traffic tensor by seeking a recovered tensor consistent with observed entries under a low-rank assumption.The tensor dimensions correspond to spatial location, day, and time interval; PΩ projects onto observed entries.
- Low-Rank Tensor Completion: Because tensor rank minimization is NP-hard, the model replaces rank with weighted nuclear-norm minimization as a convex relaxation.The nuclear norm sums singular values across tensor unfoldings, with nonnegative mode weights.
- Truncated Nuclear Norm: The matrix TNN excludes the largest r singular values and minimizes only the remaining singular values, preserving major components while shrinking smaller ones.Singular values are ordered σ1 ≥ σ2 ≥ ···, and the first r do not contribute to the TNN.
- Truncated Nuclear Norm: The proposed multiple tensor TNN applies truncation to every tensor unfolding, with one universal rate parameter θ automatically controlling truncation across all d modes.Each mode uses a truncation rank determined from θ and the dimensions of the other modes, while αk weight the unfolding TNNs.
- Optimization Formulation: An auxiliary tensor M links the observed tensor to mode-specific variables Xk, converting the TNN completion formulation into a tractable constrained problem.M retains observation information and broadcasts it to Xk, while the Xk variables carry the mode-wise TNN penalties.
- Solution Algorithms: ADMM solves the constrained model iteratively through three subproblems, using auxiliary dual-update variables and singular-value thresholding for the nonconvex updates.The generalized thresholding leaves the first r singular values unchanged and applies [σ−α/ρ]+ to the remainder; global optimality is not guaranteed for nonconvex subproblems.
3. Model Implementation
The implementation converts raw traffic data into a location-by-day-by-time tensor, applies LRTC-TNN to recover the complete tensor, and fills missing entries.
- Missing-entry recovery: The recovered tensor is used to fill the original missing traffic observations.This completes the pipeline from structured raw data to imputed entries.
- Data structuring: The pipeline first adapts raw spatiotemporal traffic data to a tensor structure using a specified rule.The assumed third-order dimensions correspond to spatial location, day, and time interval.
- Tensor imputation: LRTC-TNN imputes the incomplete tensor through iterative variable updates defined by the model equations.The algorithm initializes variables and updates X, M, and T across iterations.
4. Experiments
Experiments on four real-world traffic tensors evaluate LRTC-TNN against matrix factorization, tensor factorization, and standard LRTC baselines under random and non-random missingness. LRTC-TNN generally performs best, including under heavy missing rates, although temporal factorization leads on one random-missing data set.
- Data sets: Experiments use four publicly available real-world data sets with location/sensor×day×time of day tensor structure.The data can also be organized as location/sensor×time matrices by stacking the time dimension.
- Baselines: The comparison includes temporal matrix factorization, Bayesian tensor factorization, and nuclear-norm low-rank tensor completion baselines.Baselines include BTMF, TRMF, BGCP, BATF, and HaLRTC.
- Evaluation: Evaluation masks entries and computes MAPE and RMSE against their actual ground-truth values.Random missing and correlated non-random missing patterns are tested, with the latter described as more challenging.
- Overall results: LRTC-TNN clearly outperforms other baselines across diverse random- and non-random-missing scenarios with varying missing rates.Both missing pattern and missing rate directly affect the MAPE/RMSE values of all models.
- Data-set differences: For data sets G, H, and S, LRTC-TNN consistently performs significantly better, while BTMF and TRMF lead for random missingness on Birmingham parking data.The paper attributes the Birmingham result to strong temporal patterns and the value of AR/VAR temporal dynamics.
- LRTC comparison: LRTC-TNN consistently achieves much lower MAPE/RMSE than HaLRTC, whose performance becomes less stable as missing rates increase.The comparison supports using truncated rather than standard nuclear-norm minimization for retaining dominant tensor patterns.
- Heavy missingness: At high missing rates of 50%, 60%, and 70%, LRTC-TNN obtains the lowest MAPE/RMSE in most cases and remains robust when HaLRTC becomes unstable.The experiments compare LRTC-TNN with BTMF, BGCP, and HaLRTC under both missing patterns.
- Extreme missingness: With 70% non-random missingness, LRTC-TNN achieves very high accuracy on all four data sets using only 30% input.Figure 3 visualizes selected corrupted and recovered time series.
5. Conclusion and Future Directions
The paper concludes that LRTC-TNN consistently outperforms state-of-the-art imputation models across four traffic datasets and two missingness patterns. Future work includes richer tensor rank approximations, side information and smoothness priors, and alternative nonconvex surrogates.
- Conclusion: LRTC-TNN consistently outperforms state-of-the-art imputation models on four real-world traffic datasets under random and non-random missing patterns.The model uses a nonconvex truncated nuclear norm within low-rank tensor completion.
- Conclusion: The tensor representation’s additional day dimension supports modeling low-rank traffic patterns across different temporal scales.This comparison further verifies a strong and unique low-rank property in traffic time series data.
- Future Directions: Adding spatial and temporal smoothness priors could incorporate local consistency and side information beyond the underlying low-rank tensor.Suggested terms include spatial Laplacian, temporal Toeplitz, and total-variation regularization.
- Future Directions: Schatten p-norms with 0 < p < 1 may provide better rank surrogates than the nuclear norm, but their nonconvex optimization is harder than TNN minimization.The paper notes that the Schatten p-norm approaches rank as p approaches 0 and equals the nuclear norm at p = 1.
- Future Directions: Weighted nuclear-norm minimization could account for differences between singular values, but its additional weights are challenging to tune for each dataset.This alternative produces a more general nonconvex formulation.
- Future Directions: Future rank-approximation work should address heterogeneous sensor, time-of-day, and day dimensions rather than using the same αk across all unfoldings.The paper identifies alternative tensor rank approximations as a potential research direction.