Near-optimal tensor recovery guarantees for transformed total variation minimization

Over the past three decades, total variation (TV) has successfully been applied in image processing, compressed sensing, and many other fields. Consider the problem of tensor recovery from compressed measurements with noise, TV minimization has been shown to provide good approximations to tensors such as hyperspectral image and videos, even if the measurements are far less than the ambient dimension. By combining the recently developed transformed L1 function with TV, this paper explores the transformed total variation (TTV) minimization for recovering a tensor X₀ ∈ C^Nd. Specifically, it is an extension of a recent work specially designed for two-dimensional image recovery, which has been shown to provide a robust recovery guarantee and outperform TV minimization in image recovery tasks. However, this extension is challenging because tensors have more complicated structures, leading that some algebraic tools designed for two-dimensional images are infeasible. Based on the restricted isometry property (RIP), we demonstrate that TTV minimization recovers X₀ from O(sdlog N^d) linear measurements, and an error bound composed of its best s-term approximation to its gradient tensor and noise level is derived, which is optimal up to a logarithmic factor log Nd. Furthermore, the restricted isometry condition is also improved compared with that of TV minimization.