Graph regularized local self-representation for missing value imputation with applications to on-road traffic sensor data

Recovering missing values (MVs) from incomplete data is an important problem for many real-world applications. Previous research efforts toward solving MVs problem primarily exploit the global and/or local structure of data. In this work, we propose a novel MVs imputation method by combing sample self-representation strategy and underlying local linear structure of data in a uniformed framework. Specifically, the proposed method consists of the following steps. First, an existing method is applied to obtain the first-round estimation of MVs. Then, a graph, characterizing local proximity structure of data, is constructed based on imputed data. Next, a novel model coined as graph regularized local self-representation (GRLSR) is proposed by integrating two crucial elements: local self-representation and graph regularization. The former assumes each sample can be well represented (reconstructed) by linearly combining the neighboring samples while the latter further requires the neighboring samples should not deviate too much from each other after reconstruction. By doing so, MVs can be more accurately restored due to the joint imputation as well as local linear reconstruction. We also develop an effective alternating optimization algorithm to solve GRLSR model, thereby achieving final imputation. The convergence and computational complexity analysis of our method are also presented. To evaluate our method, extensive experiments are conducted on both traffic flow dataset and UCI benchmark datasets. The results demonstrate the effectiveness of our proposed method compared with a set of widely-used competing methods.