Guarantees of Augmented Trace Norm Models in Tensor Recovery

This paper studies the recovery guarantees of the models of minimizing $\mathrm{\parallel }\mathcal{X}{\mathrm{\parallel }}_{\ast }+\frac{1}{2\alpha }\mathrm{\parallel }\mathcal{X}{\mathrm{\parallel }}_F^2$ where $\mathcal{X}$ is a tensor and $\mathrm{\parallel }\mathcal{X}{\mathrm{\parallel }}_{\ast }$ and $\mathrm{\parallel }\mathcal{X}{\mathrm{\parallel }}_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 $\mathrm{\parallel }\mathcal{X}{\mathrm{\parallel }}_{\ast }$ 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 ${\mathcal{X}}^0$, minimizing $\mathrm{\parallel }\mathcal{X}{\mathrm{\parallel }}_{\ast }+\frac{1}{2\alpha }\mathrm{\parallel }\mathcal{X}{\mathrm{\parallel }}_F^2$ returns the same solution as minimizing $\mathrm{\parallel }\mathcal{X}{\mathrm{\parallel }}_{\ast }$ almost whenever $\alpha \ge 10\underset{i}{}\mathrm{\parallel }{X}_{(i)}^0{\mathrm{\parallel }}_2$.