Matrix and Tensor Decompositions in Signal Processing. Gérard Favier

(Goulart et al. 2017) (Tan et al. 2013; Ran et al. 2016) Music types of music × frequencies × frequencies users × keywords × songs recordings × (audio) characteristics × segments (Panagakis et al. 2010) (Nanopoulos et al. 2010) (Benetos and Kotropoulos 2008) Bioinformatics medicine × targets × diseases (Wang et al. 2019)

      Recommendation systems can also use information about the users (age, nationality, geographic location, participation on social networks, etc.) and the items themselves (types of music, types of film, classes of hotels, etc.). This is called contextual information. Taking this additional information into account allows the relevance of the recommendations to be improved, at the cost of increasing the dimensionality and the complexity of the data representation model and, therefore, of the processing algorithms. This is why tensor approaches are so important for this type of application today. Note that, for recommendation systems, the data tensors are sparse. Consequently, some tags can be automatically generated by the system based on similarity metrics between items. This is, for example, the case for music recommendations based on the acoustic characteristics of songs (Nanopoulos et al. 2010). Personalized tag recommendations take into account the user’s profile, preferences, and interests. The system can also help the user select existing tags or create new ones (Rendle and Schmidt-Thieme 2010).

      The articles by Bobadilla et al. (2013) and Frolov and Oseledets (2017) present various recommendation systems with many bibliographical references. Operating according to a similar principle as recommendation systems, social network websites, such as Wikipedia, Facebook, or Twitter, allow different types of data to be exchanged and shared, content to be produced and connections to be established.

I.4. With what tensor decompositions?

      It is important to note that, for an Nth-order tensor

the number of elements is

and, assuming In = I for n ∈ 〈N〉, this number becomes IN, which induces an exponential increase with the tensor order N. This is called the curse of dimensionality (Oseledets and Tyrtyshnikov 2009). For big data tensors, tensor decompositions play a fundamental role in alleviating this curse of dimensionality, due to the fact that the number of parameters that characterize the decompositions is generally much smaller than the number of elements in the original tensor.

      We now introduce three basic decompositions: PARAFAC/CANDECOMP/CPD, TD and TT⁵. The first two are studied in depth in Chapter 5, whereas the third, briefly introduced in Chapter 3, will be considered in more detail in Volume 3.

Table I.3 gives the expression of the element

of a tensor

of order N and size I₁ × · • · × I_N, either real (

= ℝ) or complex (

= ℂ), for each of the three decompositions cited above. Their parametric complexity is compared in terms of the size of each matrix and tensor factor, assuming I_n = I and R_n = R for all n ∈ 〈N〉.

Figures I.1–I.3 show graphical representations of the PARAFAC model

^{I1×I2×I3×I4}. In the case of the PARAFAC model, we define

using its columns, for n ∈ {1, 2, 3}.

Figure I.1. Third-order PARAFAC model

      We can make a few remarks about each of these decompositions:

       – The PARAFAC decomposition (Harshman 1970), also known as CANDECOMP (Carroll and Chang 1970) or CPD (Hitchcock 1927), of a Nth-order tensor χ is a sum of R rank-one tensors, each defined as the outer product of one column from each of the N matrix factors A(n) ∈ In×R. When R is minimal, it is called the rank of the tensor. If the matrix factors satisfy certain conditions, this decomposition has the essential uniqueness property. See Figure I.1 for a third-order tensor (N = 3), and Chapter 5 for a detailed presentation.

Table I.3. Parametric complexity of the CPD, TD, and TT decompositions

Decompositions	Notation	Element xi1,··· ,iN
PARAFAC / CPD	[[A^(1), · · · , A^(N); R ]]
TD
TT
Decompositions	Parameters	Complexity
CPD	A^(n) ∈ ^In×R, ∀n ∈ 〈N〉