Optimal High-order Tensor SVD via Tensor-Train Orthogonal Iteration.

Area of Science:

• Multivariate Statistics
• Numerical Analysis
• Machine Learning

Background:

• High-order tensor Singular Value Decomposition (SVD) is crucial for analyzing complex datasets.
• Existing methods may lack computational efficiency or theoretical guarantees for noisy tensor data.
• Estimating low-rank structures in tensors is a fundamental challenge in data science.

Purpose of the Study:

• To propose a computationally efficient algorithm for high-order tensor SVD.
• To develop a robust method for estimating low tensor-train rank structures from noisy tensor observations.
• To establish theoretical guarantees for the proposed algorithm's estimation error and optimality.

Main Methods:

• Development of the tensor-train orthogonal iteration (TTOI) algorithm.
• Initialization using TT-SVD and novel iterative backward/forward updates.
• Derivation of general upper bounds on estimation error using tensor matricization lemmas.
• Establishment of information-theoretic lower bounds for minimax optimality.

Main Results:

• The TTOI algorithm demonstrates computational efficiency.
• TTOI achieves theoretical guarantees on estimation error, matching information-theoretic lower bounds.
• The algorithm proves to be minimax optimal under the spiked tensor model.
• Successful application in estimating and reducing dimensions of high-order Markov processes and analyzing real-world data.

Conclusions:

• TTOI provides an efficient and theoretically sound framework for high-order tensor SVD.
• The algorithm's optimality and accuracy are validated through theoretical analysis and practical applications.
• The developed method offers a valuable tool for analyzing large-scale, high-dimensional tensor data.