In tensor factorization, the core tensor and its entries provide the level of interaction between the factor matrices and their components. Standard tensor factorizations use a single and unsupervised core to achieve this objective. However, the presence of heterogeneous data may induce different structure for subsets of them. To address this issue, we propose a double core tensor factorization (DCOT), where the core tensor is given by the superposition of global and subset specific local cores. DCOT preserves structural properties of the heterogeneous datasets, such as joint structure within subsets and idiosyncratic structures across different subsets (e.g. such subsets may correspond to presoecified groups). Further, in order to characterize the underlying joint-manifold drawn from the model factors, we propose two new structural regularization schemes: (1) a Nystro¨m multilinear graph embedding regularization on the factor matrices to characterize their underlying manifold determined by them, and (2) an orthogonal total variation regularization, on individual factor matrices of the tensor to encourage uniqueness of the factorization. A fast and efficient sketch based alternating minimization algorithm is suggested for DCOT factorization. The performance of DCOT and its Nystro¨m version (called DCOT-N) are illustrated on clustering, tensor completion, and foreground-background separation in surveillance video applications.