Big data analysis has become a crucial part of new emerging technologies such as the internet of things, cyber-physical analysis, deep learning, anomaly detection, etc. Among many other techniques, dimensionality reduction plays a key role in such analyses and facilitates feature selection and feature extraction. Randomized algorithms are efficient tools for handling big data tensors. They accelerate decomposing large-scale data tensors by reducing the computational complexity of deterministic algorithms and the communication among different levels of memory hierarchy, which is the main bottleneck in modern computing environments and architectures. In this article, we review recent advances in randomization for computation of Tucker decomposition and Higher Order SVD (HOSVD). We discuss random projection and sampling approaches, single-pass and multi-pass randomized algorithms and how to utilize them in the computation of the Tucker decomposition and the HOSVD. Simulations on synthetic and real datasets are provided to compare the performance of some of best and most promising algorithms.

Cross Tensor Approximation (CTA) is a generalization of Cross/skeleton matrix and CUR Matrix Approximation (CMA) and is a suitable tool for fast low-rank tensor approximation. It facilitates interpreting the underlying data tensors and decomposing/compressing tensors so that their structures, such as nonnegativity, smoothness, or sparsity, can be potentially preserved. This paper reviews and extends state-of-the-art deterministic and randomized algorithms for CTA with intuitive graphical illustrations. We discuss several possible generalizations of the CMA to tensors, including CTAs: based on fiber selection, slice-tube selection, and lateral-horizontal slice selection. The main focus is on the CTA algorithms using Tucker and tubal SVD (t-SVD) models while we provide references to other decompositions such as Tensor Train (TT), Hierarchical Tucker (HT), and Canonical Polyadic (CP) decompositions. We evaluate the performance of the CTA algorithms by extensive computer simulations to compress color and medical images and compare their performance.

Optimal rank selection is an important issue in tensor decomposition problems, especially for Tensor Train (TT) and Tensor Ring (TR) (also known as Tensor Chain) decompositions. In this paper, a new rank selection method for TR decomposition has been proposed for automatically finding near-optimal TR ranks, which result in a lower storage cost, especially for tensors with inexact TT or TR structures. In many of the existing approaches, TR ranks are determined in advance or by using truncated Singular Value Decomposition (t-SVD). There are also other approaches for selecting TR ranks adaptively. In our approach, the TR ranks are not determined in advance, but are increased gradually in each iteration until the model achieves a desired approximation accuracy. For this purpose, in each iteration, the sensitivity of the approximation error to each of the core tensors is measured and the core tensors with the highest sensitivity measures are selected and their sizes are increased. Simulation results confirmed that the proposed approach reduces the storage cost considerably and allows us to find optimal model in TR format, while preserving the desired accuracy of the approximation.

CANDECOMP/PARAFAC (CP) approximates multiway data by sum of rank-1 tensors. Unlike matrix decomposition, the procedure which estimates the best rank- $R$ tensor approximation through $R$ sequential best rank-1 approximations does not work for tensors, because the deflation does not always reduce the tensor rank. In this paper, we propose a novel deflation method for the problem. When one factor matrix of a rank- $R$ CP decomposition is of full column rank, the decomposition can be performed through $(R-1)$ rank-1 reductions. At each deflation stage, the residue tensor is constrained to have a reduced multilinear rank. For decomposition of order-3 tensors of size $R\times R\times R$ and rank- $R$ , estimation of one rank-1 tensor has a computational cost of ${\cal O}(R^{3})$ per iteration which is lower than the cost ${\cal O}(R^{4})$ of the ALS algorithm for the overall CP decomposition. The method can be extended to tracking one or a few rank-one tensors of slow changes, or inspect variations of common patterns in individual datasets.