Tensors (loosely called 'higher-dimensional matrices') provide a richer and more natural representation for many large data sets than 'flat' matrices. Often, these tensors are structured and this fact can be exploited to decompose these tensors into compact and sophisticated multilinear models. Using these models, large data sets can be handled efficiently. The computation of a decomposition of a very large data set (so called Big Data), however, is hard due to the curse of dimensionality. In this Ph.D. research we will develop new compressed sensing type algorithms to alleviate and even remove this burden, and we will develop new applications for large and computationally challenging data sets in data analysis and signal processing.