  Two approximation algorithms are proposed for $\ell_1$-regularized sparse
rank-1 approximation to higher-order tensors. The algorithms are based on
multilinear relaxation and sparsification, which are easily implemented and
well scalable. In particular, the second one scales linearly with the size of
the input tensor. Based on a careful estimation of the $\ell_1$-regularized
sparsification, theoretical approximation lower bounds are derived. Our
theoretical results also suggest an explicit way of choosing the regularization
parameters. Numerical examples are provided to verify the proposed algorithms.
