  In this work, a tensor completion problem is studied, which aims to perfectly
recover the tensor from partial observations. Existing theoretical guarantee
requires the involved transform to be orthogonal, which hinders its
applications. In this paper, jumping out of the constraints of isotropy or
self-adjointness, the theoretical guarantee of exact tensor completion with
arbitrary linear transforms is established. To that end, we define a new
tensor-tensor product, which leads us to a new definition of the tensor nuclear
norm. Equipped with these tools, an efficient algorithm based on alternating
direction of multipliers is designed to solve the transformed tensor completion
program and the theoretical bound is obtained. Our model and proof greatly
enhance the flexibility of tensor completion and extensive experiments validate
the superiority of the proposed method.
