STELLAR: Spatio-Temporal Tensor Completion via Low-Rankness and Smoothness of Difference Features for Traffic Data Imputation

Low-rank matrix/tensor completion methods have attracted growing interest in traffic data imputation. These approaches leverage the low-rank structure and spatio-temporal smoothness of traffic measurements. However, most existing methods model these properties separately and combine them in a linear manner. This simplification overlooks the interdependencies between low-rank structure and smoothness, potentially degrading imputation quality. To address this issue, we propose a method termed STELLAR (spatio-temporal tensor completion vialow-rankness and smoothness of difference features), which fuses global low-rankness and local spatio-temporal smoothness of traffic data in a unified manner. Specifically, we impose the nuclear norm on the difference features after three spatio-temporal difference transformations of the traffic tensor, thereby simultaneously quantifying the low-rankness and smoothness. This results in a convex formulation of STELLAR that is efficiently solved via the alternating direction method of multipliers (ADMM). We prove the global convergence of STELLAR to an optimal solution of the associated convex problem. Extensive experiments on real-world traffic datasets demonstrate that STELLAR outperforms many state-of-the-art methods while maintaining competitive computational efficiency. In particular, on the Seattle traffic dataset, STELLAR achieves up to an 11.1% reduction in root mean square error (RMSE) over the suboptimal baseline. The STELLAR code is available athttps://github.com/IAmEzreal/STELLAR.git