Recovering low-rank tensor from limited coefficients in any ortho-normal basis using tensor-singular value decomposition

Tensor singular value decomposition (t-SVD) provides a novel way to decompose a tensor. It has been employed mostly in recovering missing tensor entries from the observed tensor entries. The problem of applying t-SVD to recover tensors from limited coefficients in any given ortho-normal basis is addressed. We prove that an n × n × n₃ tensor with tubal-rank r can be efficiently reconstructed by minimising its tubal nuclear norm from its O(rn₃n log²(n₃n)) randomly sampled coefficients w.r.t any given ortho-normal basis. In our proof, we extend the matrix coherent conditions to tensor coherent conditions. We first prove the theorem belonging to the case of Fourier-type basis under certain coherent conditions. Then, we prove that our results hold for any ortho-normal basis meeting the conditions. Our work covers the existing t-SVD-based tensor completion problem as a special case. We conduct numerical experiments on random tensors and dynamic magnetic resonance images (d-MRI) to demonstrate the performance of the proposed methods.