Numerical Algorithms For Low Rank Tensor Recovery

With the rapid development of modern information technology, high-dimensional da-ta with more complex structures such as face images, surveillance videos and multispectralimages are becoming very ubiquitous across many areas of science and engineering. Be-sides, these data often sufer from the problem of deficiency and loss, or being corruptedwith noise or outliers. Thus, how to recover these data accurately and fast has become is ahot topic in machine learning, data mining, pattern recognition, and computer vision.In recent years, the inverse problem of recovering a low rank tensor, as an extension ofsparse recovery problem from the low dimensional space (matrix space) to the high dimen-sional space (tensor space), has come into use and show its potential value of applications.However, due to the complexity of the multi-way data analysis, the research on this top-ic is still limited. This thesis has made some research of modeling, algorithm designingand algorithm analysis for low rank tensor recovery. The author’s major contributions areoutlined as follows:1. We consider the multilinear-rank of a tensor as a sparsity measure, and adapt oper-ator splitting technique and convex relaxation technique to transform the original probleminto a convex, unconstrained optimization problem. A fixed point iterative method is pro-posed to solve the resulting problem. We also prove the convergence of the method undersome assumptions. By using a continuation technique, we propose a fast and robust algo-rithm for solving the tensor completion problem, which is called FP-LRTC (Fixed Pointfor Low n-Rank Tensor Completion). Our numerical results on randomly generated andreal tensor completion problems demonstrate that this algorithm is efective, especially for“easy” problems.2. The variable splitting technique and convex relaxation technique are used to trans-form the low multilinear-rank tensor recovery problem into a tractable constrained opti-mization problem. Considering the favorable structure of the problem, we develop a split-ting augmented Lagrangian method to solve the resulting problem. The proposed algorithmis easily implemented and its convergence can be proved under some conditions. Some pre-liminary numerical results on randomly generated and real completion problems show thatthe proposed algorithm is very efective and robust for tackling the low multilinear-ranktensor completion problem.