Breaking the curse of dimensionality using decompositions of incomplete tensors: Tensor-based scientiļ¬c computing in big data analysis

Nico Vervliet, Otto Debals, Laurent Sorber, Lieven De Lathauwer


Tensors, or multiway arrays of numerical values, and their decompositions are common in domains like signal processing, data analysis and chemometrics. Being higher-order generalizations of vectors and matrices, tensors are often large-scale as their number of entries scales exponentially in the order. The computational and memory-related challenges created by this exponential dependence are referred to as the curse of dimensionality. In this chapter, we show that using a decomposition instead of the tensor can alleviate or even break this curse. Moreover, by sampling few entries, incomplete tensors can be used to alleviate or break the curse for the computation of these decompositions as well. We illustrate this for the canonical polyadic decomposition, and discuss similar concepts such as tensor trains and cross approximation, which are often used in scientific computing and quantum information theory. These concepts can be translated to a signal processing context, as is illustrated for multidimensional harmonic retrieval. In a materials science application, the melting temperature of an alloy is modeled using a low-rank CPD and we show that, using incomplete tensors, the curse is broken as the ninth-order tensor, which has \({\cal O}(10^{18})\) entries, is decomposed using only \(10^5\) samples.

Code description

We demonstrate how incomplete tensors can be used using two case studies: multidimensional harmonic retrieval and modeling the melting point of a complex alloy. In this package, we provide the data and code to reproduce the resultspresented in the paper. The code has been updated to work with Tensorlab 3.0 and a new visualization technique has been included for the melting temperature dataset.


N. Vervliet, O. Debals, L. Sorber, and L. De Lathauwer, "Breaking the curse of dimensionality using decompositions of incomplete tensors: Tensor-based scientific computing in big data analysis," IEEE Signal Processing Magazine, vol. 31, no. 5, pp. 71-79, Sep. 2014.

Download code

This repository can be cited as:
S. Hendrikx, M. Boussé, N. Vervliet, M. Vandecappelle, R. Kenis, and L. De Lathauwer, Tensorlab⁺, Available online, Version of Dec 2022 downloaded from