Higher-order singular value decomposition

In multilinear algebra, the higher-order singular value decomposition (HOSVD) of a tensor is a specific orthogonal Tucker decomposition. It may be regarded as one generalization of the matrix singular value decomposition. The HOSVD has applications in computer graphics, machine learning, scientific computing, and signal processing. Some key ingredients of the HOSVD can be traced as far back as F. L. Hitchcock in 1928, but it was L. R. Tucker who developed for third-order tensors the general Tucker decomposition in the 1960s, including the HOSVD. The HOSVD as decomposition in its own right was further advocated by L. De Lathauwer et al. in 2000. In multilinear algebra, the higher-order singular value decomposition (HOSVD) of a tensor is a specific orthogonal Tucker decomposition. It may be regarded as one generalization of the matrix singular value decomposition. The HOSVD has applications in computer graphics, machine learning, scientific computing, and signal processing. Some key ingredients of the HOSVD can be traced as far back as F. L. Hitchcock in 1928, but it was L. R. Tucker who developed for third-order tensors the general Tucker decomposition in the 1960s, including the HOSVD. The HOSVD as decomposition in its own right was further advocated by L. De Lathauwer et al. in 2000. As the HOSVD was studied in many scientific fields, it is sometimes historically referred to as multilinear singular value decomposition, m-mode SVD, or cube SVD, and sometimes it is incorrectly identified with a Tucker decomposition. For the purpose of this article, the abstract tensor A {displaystyle {mathcal {A}}} is assumed to be given in coordinates with respect to some basis as a multidimensional array, also denoted by A {displaystyle {mathcal {A}}} , in F n 1 × n 2 × ⋯ × n d {displaystyle F^{n_{1} imes n_{2} imes cdots imes n_{d}}} , where d is the order of the tensor and F {displaystyle F} is either R {displaystyle mathbb {R} } or C {displaystyle mathbb {C} } . Let U k ∈ F n k × n k {displaystyle U_{k}in F^{n_{k} imes n_{k}}} be a unitary matrix containing a basis of the left singular vectors of the standard factor-k flattening A ( k ) {displaystyle {mathcal {A}}_{(k)}} of A {displaystyle {mathcal {A}}} such that the jth column u j k {displaystyle mathbf {u} _{j}^{k}} of U k {displaystyle U_{k}} corresponds to the jth largest singular value of A ( k ) {displaystyle {mathcal {A}}_{(k)}} . Observe that the factor matrix U k {displaystyle U_{k}} does not depend on the particular freedom of choice in the definition of the standard factor-k flattening. By the properties of the multilinear multiplication, we have As in the case of the compact singular value decomposition of a matrix, it is also possible to consider a compact HOSVD, which is very useful in applications. Assume that U k ∈ F n k × r k {displaystyle U_{k}in F^{n_{k} imes r_{k}}} is a matrix with unitary columns containing a basis of the left singular vectors corresponding to the nonzero singular values of the standard factor-k flattening A ( k ) {displaystyle {mathcal {A}}_{(k)}} of A {displaystyle {mathcal {A}}} . Let the columns of U k {displaystyle U_{k}} be sorted such that the jth column u j k {displaystyle mathbf {u} _{j}^{k}} of U k {displaystyle U_{k}} corresponds to the jth largest nonzero singular value of A ( k ) {displaystyle {mathcal {A}}_{(k)}} . Since the columns of U k {displaystyle U_{k}} form a basis for the image of A ( k ) {displaystyle {mathcal {A}}_{(k)}} , we have The tuple ( r 1 , r 2 , … , r d ) ∈ N d {displaystyle (r_{1},r_{2},ldots ,r_{d})in mathbb {N} ^{d}} where r k := r a n k ( A ( k ) ) {displaystyle r_{k}:=mathrm {rank} ({mathcal {A}}_{(k)})} is called the multilinear rank of A {displaystyle {mathcal {A}}} . By definition, every tensor has a unique multilinear rank, and its components are bounded by 0 ≤ r k ≤ n k {displaystyle 0leq r_{k}leq n_{k}} . Not all tuples in N d {displaystyle mathbb {N} ^{d}} are multilinear ranks. In particular, it is known that r k ≤ ∏ j ≠ k r j { extstyle r_{k}leq prod _{j eq k}r_{j}} must hold.