Guaranteed Nonconvex Factorization Approach for Tensor Train Recovery
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A Scalable Factorization Approach for High-Order Structured Tensor Recovery
Tensor decompositions, which represent an $N$-order tensor using approximately $N$ factors of much smaller dimensions, can significantly reduce the number of parameters. This is particularly beneficial for high-order ten…
Tensor DecompositionGeneralized Nonconvex Approach for Low-Tubal-Rank Tensor Recovery
The tensor-tensor product-induced tensor nuclear norm (t-TNN) (Lu et al., 2020) minimization for low-tubal-rank tensor recovery attracts broad attention recently. However, minimizing the t-TNN faces some drawbacks. For e…
Image InpaintingLow-Rank Matrix CompletionFasTer: Fast Tensor Completion with Nonconvex Regularization
Low-rank tensor completion problem aims to recover a tensor from limited observations, which has many real-world applications. Due to the easy optimization, the convex overlapping nuclear norm has been popularly used for…
Homotopy Analysis for Tensor PCA
Developing efficient and guaranteed nonconvex algorithms has been an important challenge in modern machine learning. Algorithms with good empirical performance such as stochastic gradient descent often lack theoretical g…
global-optimizationTensor p-shrinkage nuclear norm for low-rank tensor completion
In this paper, a new definition of tensor p-shrinkage nuclear norm (p-TNN) is proposed based on tensor singular value decomposition (t-SVD). In particular, it can be proved that p-TNN is a better approximation of the ten…