THESIS
2017
viii, 48 pages : illustrations ; 30 cm
Abstract
Tensor data are used widely in real-world applications, especially in completing the missing
entries in partially observed multilinear data. However, most tensor problems are NP-hard, and
low-rank tensor completion is much more difficult than low-rank matrix completion. In this
paper, we propose a time and space-efficient low-rank tensor completion algorithm by using
the scaled latent nuclear norm for regularization and the Frank-Wolfe (FW) algorithm for optimization.
We show that all the steps can be performed efficiently. In particular, Frank-Wolfe's
linear subproblem has a closed-form solution which can be obtained by rank-one SVD. By using
power method, it only includes matrix and vector multiplications to obtain rank-one SVD,
which are efficient especially when the tensor i...[
Read more ]
Tensor data are used widely in real-world applications, especially in completing the missing
entries in partially observed multilinear data. However, most tensor problems are NP-hard, and
low-rank tensor completion is much more difficult than low-rank matrix completion. In this
paper, we propose a time and space-efficient low-rank tensor completion algorithm by using
the scaled latent nuclear norm for regularization and the Frank-Wolfe (FW) algorithm for optimization.
We show that all the steps can be performed efficiently. In particular, Frank-Wolfe's
linear subproblem has a closed-form solution which can be obtained by rank-one SVD. By using
power method, it only includes matrix and vector multiplications to obtain rank-one SVD,
which are efficient especially when the tensor is sparse. It is also very efficient to search for
the best step size, where there is a simple closed-form solution. Moreover, by utilizing sparsity
of the observed tensor, we only need to maintain sparse tensor entries and a set of small
basis matrices to further reduce the time and space requirements. To alleviate the memory problem
caused by maintaining all the bases, we also propose a basis reduction process to reduce
the number of bases. Experimental results show that the proposed algorithm is more accurate,
much faster and more scalable than the state-of-the-art.
Post a Comment