  We derive a CUR-type factorization for tensors in the Tucker format based on
interpolatory decomposition, which we will denote as Higher Order Interpolatory
Decomposition (HOID). Given a tensor $\mathcal{X}$, the algorithm provides a
set of column vectors $\{ \mathbf{C}_n\}_{n=1}^d$ which are columns extracted
from the mode-$n$ tensor unfolding, along with a core tensor $\mathcal{G}$ and
together, they satisfy some error bounds. Compared to the Higher Order SVD
(HOSVD) algorithm, the HOID provides a decomposition that preserves certain
important features of the original tensor such as sparsity, non-negativity,
integer values, etc. Error bounds along with detailed estimates of
computational costs are provided. The algorithms proposed in this paper have
been validated against carefully chosen numerical examples which highlight the
favorable properties of the algorithms. Related methods for subset selection
proposed for matrix CUR decomposition, such as Discrete Empirical Interpolation
method (DEIM) and leverage score sampling, have also been extended to tensors
and are compared against our proposed algorithms.
