Provable Tensor Completion with Graph Information
Kaidong Wang Yao Wang Xiuwu Liao Shaojie Tang Can Yang Deyu Meng
Graphs, depicting the interrelations between variables, has been widely used
as effective side information for accurate data recovery in various
matrix/tensor recovery related applications. In this paper, we study the tensor
completion problem with graph information. Current research on
graph-regularized tensor completion tends to be task-specific, lacking
generality and systematic approaches. Furthermore, a recovery theory to ensure
performance remains absent. Moreover, these approaches overlook the dynamic
aspects of graphs, treating them as static akin to matrices, even though graphs
could exhibit dynamism in tensor-related scenarios. To confront these
challenges, we introduce a pioneering framework in this paper that
systematically formulates a novel model, theory, and algorithm for solving the
dynamic graph regularized tensor completion problem. For the model, we
establish a rigorous mathematical representation of the dynamic graph, based on
which we derive a new tensor-oriented graph smoothness regularization. By
integrating this regularization into a tensor decomposition model based on
transformed t-SVD, we develop a comprehensive model simultaneously capturing
the low-rank and similarity structure of the tensor. In terms of theory, we
showcase the alignment between the proposed graph smoothness regularization and
a weighted tensor nuclear norm. Subsequently, we establish assurances of
statistical consistency for our model, effectively bridging a gap in the
theoretical examination of the problem involving tensor recovery with graph
information. In terms of the algorithm, we develop a solution of high
effectiveness, accompanied by a guaranteed convergence, to address the
resulting model. To showcase the prowess of our proposed model in contrast to
established ones, we provide in-depth numerical experiments encompassing
synthetic data as well as real-world datasets.