  We consider the problem of recovering a low-multilinear-rank tensor from a
small amount of linear measurements. We show that the Riemannian gradient
algorithm initialized by one step of iterative hard thresholding can
reconstruct an order-$d$ tensor of size $n\times\ldots\times n$ and multilinear
rank $(r,\ldots,r)$ with high probability from only $O(nr^2 + r^{d+1})$
measurements, assuming $d$ is a constant. This sampling complexity is optimal
in $n$, compared to existing results whose sampling complexities are all
unnecessarily large in $n$. The analysis relies on the tensor restricted
isometry property (TRIP) and the geometry of the manifold of all tensors with a
fixed multilinear rank. High computational efficiency of our algorithm is also
achieved by doing higher order singular value decomposition on intermediate
small tensors of size only $2r\times \ldots\times 2r$ rather than on tensors of
size $n\times \ldots\times n$ as usual.
