Guarantees of Augmented Trace Norm Models in Tensor Recovery / 1670

*Ziqiang Shi, Jiqing Han, Tieran Zheng, Ji Li*

This paper studies the recovery guarantees of the models of minimizing ||X||_{∗} + 1/2a ||X||^{2}_{F} where X is a tensor and ||X||_{∗} and ||X||_{F} are the trace and Frobenius norm of respectively. We show that they can efficiently recover low-rank tensors. In particular, they enjoy exact guarantees similar to those known for minimizing ||X||_{∗} under the conditions on the sensing operator such as its null-space property, restricted isometry property, or spherical section property. To recover a low-rank tensor X^{0}, minimizing ||X||_{∗} + 1/2a ||X||^{2}_{F} returns the same solution as minimizing ||X||_{∗} almost whenever α ≥ 10max ||X^{0}_{(i)}||_{2}.