  Low rank tensor learning, such as tensor completion and multilinear multitask
learning, has received much attention in recent years. In this paper, we
propose higher order matching pursuit for low rank tensor learning problems
with a convex or a nonconvex cost function, which is a generalization of the
matching pursuit type methods. At each iteration, the main cost of the proposed
methods is only to compute a rank-one tensor, which can be done efficiently,
making the proposed methods scalable to large scale problems. Moreover, storing
the resulting rank-one tensors is of low storage requirement, which can help to
break the curse of dimensionality. The linear convergence rate of the proposed
methods is established in various circumstances. Along with the main methods,
we also provide a method of low computational complexity for approximately
computing the rank-one tensors, with provable approximation ratio, which helps
to improve the efficiency of the main methods and to analyze the convergence
rate. Experimental results on synthetic as well as real datasets verify the
efficiency and effectiveness of the proposed methods.
