  In tensor completion, the latent nuclear norm is commonly used to induce
low-rank structure, while substantially failing to capture the global
information due to the utilization of unbalanced unfolding scheme. To overcome
this drawback, a new latent nuclear norm equipped with a more balanced
unfolding scheme is defined for low-rank regularizer. Moreover, the new latent
nuclear norm together with the Frank-Wolfe (FW) algorithm is developed as an
efficient completion method by utilizing the sparsity structure of observed
tensor. Specifically, both FW linear subproblem and line search only need to
access the observed entries, by which we can instead maintain the sparse
tensors and a set of small basis matrices during iteration. Most operations are
based on sparse tensors, and the closed-form solution of FW linear subproblem
can be obtained from rank-one SVD. We theoretically analyze the
space-complexity and time-complexity of the proposed method, and show that it
is much more efficient over other norm-based completion methods for
higher-order tensors. Extensive experimental results of visual-data inpainting
demonstrate that the proposed method is able to achieve state-of-the-art
performance at smaller costs of time and space, which is very meaningful for
the memory-limited equipment in practical applications.
