  We study the problem of learning a tensor from a set of linear measurements.
A prominent methodology for this problem is based on a generalization of trace
norm regularization, which has been used extensively for learning low rank
matrices, to the tensor setting. In this paper, we highlight some limitations
of this approach and propose an alternative convex relaxation on the Euclidean
ball. We then describe a technique to solve the associated regularization
problem, which builds upon the alternating direction method of multipliers.
Experiments on one synthetic dataset and two real datasets indicate that the
proposed method improves significantly over tensor trace norm regularization in
terms of estimation error, while remaining computationally tractable.
