Guaranteed Nonconvex Factorization Approach for Tensor Train Recovery
Zhen Qin Michael B. Wakin Zhihui Zhu
In this paper, we provide the first convergence guarantee for the
factorization approach. Specifically, to avoid the scaling ambiguity and to
facilitate theoretical analysis, we optimize over the so-called left-orthogonal
TT format which enforces orthonormality among most of the factors. To ensure
the orthonormal structure, we utilize the Riemannian gradient descent (RGD) for
optimizing those factors over the Stiefel manifold. We first delve into the TT
factorization problem and establish the local linear convergence of RGD.
Notably, the rate of convergence only experiences a linear decline as the
tensor order increases. We then study the sensing problem that aims to recover
a TT format tensor from linear measurements. Assuming the sensing operator
satisfies the restricted isometry property (RIP), we show that with a proper
initialization, which could be obtained through spectral initialization, RGD
also converges to the ground-truth tensor at a linear rate. Furthermore, we
expand our analysis to encompass scenarios involving Gaussian noise in the
measurements. We prove that RGD can reliably recover the ground truth at a
linear rate, with the recovery error exhibiting only polynomial growth in
relation to the tensor order. We conduct various experiments to validate our
theoretical findings.