Content deleted Content added
No edit summary |
|||
| (36 intermediate revisions by 4 users not shown) | |||
Line 1:
{{Short description|Tensor decomposition}}
In [[multilinear algebra]], the '''higher-order singular value decomposition''' ('''HOSVD''') is a misnomer.
* ''rank-𝑅'' decomposition and * orthonormal subspaces for These properties are not realized within a single algorithm for higher-order tensors, but are instead [[Lieven De Lathauwer |De Lathauwer]] ''et al.''<ref name=":2">{{Cite journal|last1=De Lathauwer|first1=L.|last2=De Moor|first2=B.|last3=Vandewalle|first3=J.|date=2000-01-01|title=On the Best Rank-1 and Rank-(R1 ,R2 ,. . .,RN) Approximation of Higher-Order Tensors|journal=SIAM Journal on Matrix Analysis and Applications|volume=21|issue=4|pages=1324–1342|doi=10.1137/S0895479898346995|issn=0895-4798|citeseerx=10.1.1.102.9135}}</ref><ref name="
|author=M. A. O. Vasilescu, D. Terzopoulos
|title=Multilinear Analysis of Image Ensembles: TensorFaces
|book-title=Proc. 7th European Conference on Computer Vision (ECCV'02)
|___location=Copenhagen, Denmark
|year=2002
|url= https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=67eb22ae0baf86af77188fc0ab27edacf07a9140}}</ref><ref name=Vasilescu2003/><ref name=":Vasilescu2005">{{cite conference
|author=M. A. O. Vasilescu, D. Terzopoulos
|title=Multilinear Independent Component Analysis
|book-title=Proc. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR’05)
|___location=San Diego, CA
|year=2005}}</ref> introduced algorithmic clarity. Vasilescu and Terzopoulos<ref name=":Vasilescu2002"/><ref name=":Vasilescu2005"/>
introduced the '''M-mode SVD''', which is the classic algorithm that is currently referred in the literature as the '''Tucker''' or the '''HOSVD'''. The Tucker approach and De Lathauwer’s implementation are both sequential and rely on iterative procedures such as gradient descent or the power method. By contrast, the M-mode SVD provides a closed-form solution that can be executed sequentially and is well-suited for parallel computation.
: This misattribution has had lasting impact on the scholarly record, obscuring the original source of a widely adopted algorithm, and complicating efforts to trace its development, reproduce results, and recognizing the respective contributions of different research efforts.
The term '''M-mode SVD''' accurately reflects the algorithm employed. It captures the actual computation, a set of SVDs on mode-flattenings without making assumptions about the structure of the core tensor or implying a rank decomposition.
Robust and L1-norm-based variants of this decomposition framework have since been proposed.<ref name="robustHOSVD">{{Cite journal|last1=Godfarb|first1=Donald|last2=Zhiwei|first2=Qin|title=Robust low-rank tensor recovery: Models and algorithms|journal=SIAM Journal on Matrix Analysis and Applications|volume=35|number=1|pages=225–253|date=2014|doi=10.1137/130905010|arxiv=1311.6182|s2cid=1051205}}</ref><ref name="l1tucker">{{cite journal|last1=Chachlakis|first1=Dimitris G.|last2=Prater-Bennette|first2=Ashley|last3=Markopoulos|first3=Panos P.|title=L1-norm Tucker Tensor Decomposition|journal=IEEE Access|date=22 November 2019|volume=7|pages=178454–178465|doi=10.1109/ACCESS.2019.2955134|doi-access=free|arxiv=1904.06455|bibcode=2019IEEEA...7q8454C}}</ref><ref name="l1tucker3">{{cite journal|last1=Markopoulos|first1=Panos P.|last2=Chachlakis|first2=Dimitris G.|last3=Papalexakis|first3=Evangelos|title=The Exact Solution to Rank-1 L1-Norm TUCKER2 Decomposition|journal=IEEE Signal Processing Letters|volume=25|issue=4|date=April 2018|pages=511–515|doi=10.1109/LSP.2018.2790901|arxiv=1710.11306|bibcode=2018ISPL...25..511M|s2cid=3693326}}</ref><ref name="l1tucker2">{{cite book|last1=Markopoulos|first1=Panos P.|last2=Chachlakis|first2=Dimitris G.|last3=Prater-Bennette|first3=Ashley|title=2018 IEEE Global Conference on Signal and Information Processing (GlobalSIP) |chapter=L1-Norm Higher-Order Singular-Value Decomposition |date=21 February 2019|pages=1353–1357|doi=10.1109/GlobalSIP.2018.8646385|isbn=978-1-7281-1295-4|s2cid=67874182}}</ref>
Line 12 ⟶ 29:
For the purpose of this article, the abstract tensor <math>\mathcal{A}</math> is assumed to be given in coordinates with respect to some basis as a [[Tensor#As multidimensional arrays|M-way array]], also denoted by <math>\mathcal{A}\in\mathbb{C}^{I_1 \times I_2 \cdots \times \cdots I_m \cdots\times I_M}</math>, where ''M'' is the number of modes and the order of the tensor. <math>\mathbb{C}</math> is the complex numbers and it includes both the real numbers <math>\mathbb{R}</math> and the pure imaginary numbers.
Let <math>\mathcal{A}_{[m]}\in\mathbb{C}^{I_m \times (I_1 I_2 \cdots I_{m-1} I_{m+1} \cdots I_M)}</math> denote the [[Tensor reshaping#Mode-m Flattening / Mode-m Matrixization|
}</math> combined. Let <math>{\bf U}_m \in \mathbb{C}^{I_m \times I_m}</math>be a [[unitary matrix]] containing a basis of the left singular vectors of the <math>\mathcal{A}_{[m]}</math> such that the ''j''th column <math>\mathbf{u}_j</math> of <math>{\bf U}_m</math> corresponds to the ''j''th largest singular value of <math>\mathcal{A}_{[m]}</math>. Observe that the '''mode/factor matrix''' <math>{\bf U}_m</math> does not depend on the particular on the specific definition of the mode ''m'' flattening. By the properties of the [[multilinear multiplication]], we have<math display="block">\begin{array}{rcl} \mathcal{A}
&=& \mathcal{A}\times ({\bf I}, {\bf I}, \ldots, {\bf I}) \\
&=& \mathcal{A} \times ({\bf U}_1 {\bf U}_1^H, {\bf U}_2 {\bf U}_2^H, \ldots, {\bf U}_M {\bf U}_M^H) \\
&=& \left(\mathcal{A} \times ({\bf U}_1^H, {\bf U}_2^H, \ldots, {\bf U}_M^H) \right) \times ({\bf U}_1, {\bf U}_2, \ldots, {\bf U}_M),
\end{array}</math>where <math>\cdot^H</math> denotes the [[conjugate transpose]]. The second equality is because the <math>{\bf U}_m</math>'s are unitary matrices. Define now the '''core tensor'''<math display="block">\mathcal{S} := \mathcal{A} \times ({\bf U}_1^H, {\bf U}_2^H, \ldots, {\bf U}_M^H).</math>Then, the M-mode SVD(HOSVD)<ref name=":2" /> of <math>\mathcal{A}</math> is the decomposition<math display="block">\mathcal{A} = \mathcal{S}\times ({\bf U}_1, {\bf U}_2, \ldots, {\bf U}_M).</math> The above construction shows that every tensor has a M-mode SVD(HOSVD).
== Compact M-mode SVD (HOSVD) ==
As in the case of the [[Singular value decomposition#Compact SVD|compact singular value decomposition]] of a matrix, where the rows and columns corresponding to vanishing singular values are dropped, it is also possible to consider a '''compact
Assume that <math>{\bf U}_m \in \mathbb{C}^{I_m \times R_m}</math> is a matrix with unitary columns containing a basis of the left singular vectors corresponding to the nonzero singular values of the standard factor-''m'' flattening <math>\mathcal{A}_{[m]}</math> of <math>\mathcal{A}</math>. Let the columns of <math>{\bf U}_m</math> be sorted such that the <math>r_m</math> th column <math>{\bf u}_{r_m}</math> of <math>{\bf U}_m</math> corresponds to the ''<math>r_m</math>''th largest nonzero singular value of <math>\mathcal{A}_{[m]}</math>. Since the columns of <math>{\bf U}_m</math> form a basis for the image of <math>\mathcal{A}_{[m]}</math>, we have<math display="block">\mathcal{A}_{[m]} = {\bf U}_m {\bf U}_m^H \mathcal{A}_{[m]} = \bigl( \mathcal{A} \times_m ({\bf U}_m {\bf U}_m^H) \bigr)_{[m]},</math>where the first equality is due to the properties of [[Projection (linear algebra)|orthogonal projections]] (in the Hermitian inner product) and the last equality is due to the properties of multilinear multiplication. As flattenings are bijective maps and the above formula is valid for all <math>m=1,2,\ldots,m,\ldots,M</math>, we find as before that<math display="block">\begin{array}{rcl}
Line 32 ⟶ 50:
The '''multilinear rank'''<ref name=":0" /> of <math>\mathcal{A}</math> is denoted with rank-<math>(R_1, R_2, \ldots, R_M) </math>. The multilinear rank is a tuple in <math>\mathbb{N}^M</math> where <math>R_m := \mathrm{rank}( \mathcal{A}_{[m]} )</math>. Not all tuples in <math>\mathbb{N}^M</math> are multilinear ranks.<ref name=":3">{{Cite journal|last1=Carlini|first1=Enrico|last2=Kleppe|first2=Johannes|title=Ranks derived from multilinear maps|journal=Journal of Pure and Applied Algebra|volume=215|issue=8|pages=1999–2004|doi=10.1016/j.jpaa.2010.11.010|year=2011|doi-access=free}}</ref> The multilinear ranks are bounded by <math>1 \le R_m \le I_m</math> and it satisfy the constraint <math display="inline">R_m \le \prod_{i \ne m} R_i</math> must hold.<ref name=":3" />
The compact M-mode SVD(HOSVD) is a rank-revealing decomposition in the sense that the dimensions of its core tensor correspond with the components of the multilinear rank of the tensor.
== Interpretation ==
The following geometric interpretation is valid for both the full and compact M-mode SVD(HOSVD). Let <math>(R_1, R_2, \ldots, R_M)</math> be the multilinear rank of the tensor <math>\mathcal{A}</math>. Since <math>\mathcal{S} \in {\mathbb C}^{R_1 \times R_2 \times \cdots \times R_M}</math> is a multidimensional array, we can expand it as follows<math display="block">\mathcal{S} = \sum_{r_1=1}^{R_1} \sum_{r_2=1}^{R_2} \cdots \sum_{r_M=1}^{R_M} s_{r_1,r_2,\ldots,r_M} \mathbf{e}_{r_1} \otimes \mathbf{e}_{r_2} \otimes \cdots \otimes \mathbf{e}_{r_M},</math>where <math>\mathbf{e}_{r_m}</math> is the <math>r_m</math>th standard basis vector of <math>{\mathbb C}^{I_m}</math>. By definition of the multilinear multiplication, it holds that<math display="block">\mathcal{A} = \sum_{r_1=1}^{R_1} \sum_{r_2=1}^{R_2} \cdots \sum_{r_M=1}^{R_M} s_{r_1,r_2,\ldots,r_M}
\mathbf{u}_{r_1} \otimes \mathbf{u}_{r_2} \otimes \cdots \otimes \mathbf{u}_{r_M},</math>where the <math>\mathbf{u}_{r_m}</math> are the columns of <math>{\bf U}_m \in {\mathbb C}^{I_m \times R_m}</math>. It is easy to verify that <math>B = \{ \mathbf{u}_{r_1} \otimes \mathbf{u}_{r_2} \otimes \cdots \otimes \mathbf{u}_{r_M} \}_{r_1,r_2,\ldots,r_M}</math> is an orthonormal set of tensors. This means that the M-mode SVD(HOSVD) can be interpreted as a way to express the tensor <math>\mathcal{A}</math> with respect to a specifically chosen orthonormal basis <math>B</math> with the coefficients given as the multidimensional array <math>\mathcal{S}</math>.
== Computation ==
Line 42 ⟶ 60:
=== Classic computation ===
While De Lathauwer et al. clarified Tucker’s
=== M-mode SVD (also referred to as HOSVD or Tucker)===
What is commonly referred to as the HOSVD or Tucker was developed by [[Vasilescu]] and [[Demetri Terzopoulos|Terzopoulos]] under
the name M-mode SVD.<ref name=":Vasilescu2002"
* For <math>m=1,\ldots,M</math>, do the following:
# Construct the mode-''m'' flattening <math>\mathcal{A}_{[m]}</math>;
#
* Compute the core tensor <math>\mathcal{S}</math> via the [[mode-k multiplication|mode-m product]] <br/><math> \mathcal{S} = \mathcal{A} \times_1 {\bf U}_1^H \times_2 {\bf U}_2^H \ldots \times_m {\bf U}_m^H \ldots \times_M {\bf U}_M^H</math>
=== Interlacing computation ===
A strategy that is significantly faster when some or all <math>R_m \ll I_m </math> consists of interlacing the computation of the core tensor and the factor matrices, as follows:<ref name=Vasilescu2003>{{cite conference
A strategy that is significantly faster when some or all <math>R_m \ll I_m </math> consists of interlacing the computation of the core tensor and the factor matrices, as follows:<ref name=":4">{{Cite journal|last1=Vannieuwenhoven|first1=N.|last2=Vandebril|first2=R.|last3=Meerbergen|first3=K.|date=2012-01-01|title=A New Truncation Strategy for the Higher-Order Singular Value Decomposition|journal=SIAM Journal on Scientific Computing|volume=34|issue=2|pages=A1027–A1052|doi=10.1137/110836067|bibcode=2012SJSC...34A1027V |s2cid=15318433 |issn=1064-8275|url=https://lirias.kuleuven.be/handle/123456789/337210}}</ref><ref name=":5">{{Cite book|title=Tensor Spaces and Numerical Tensor Calculus {{!}} SpringerLink|volume = 42|last=Hackbusch|first=Wolfgang|language=en-gb|doi=10.1007/978-3-642-28027-6|series = Springer Series in Computational Mathematics|year = 2012|isbn = 978-3-642-28026-9| s2cid=117253621 }}</ref><ref name=":fist_hosvd">{{Cite conference|last1=Cobb|first1=Benjamin|last2=Kolla|first2=Hemanth|last3=Phipps|first3=Eric|last4=Çatalyürek|first4=Ümit V.|date=2022|title=FIST-HOSVD: Fused in-Place Sequentially Truncated Higher Order Singular Value Decomposition|conference=Platform for Advanced Scientific Computing(PASC) |language=en|isbn=9781450394109|doi=10.1145/3539781.3539798|doi-access=free}}</ref>▼
|title=Multilinear Subspace Analysis for Image Ensembles
|last1=Vasilescu
|first1=M.A.O.
|last2=Terzopoulos
|first2=D.
|book-title=Proc. Computer Vision and Pattern Recognition Conf. (CVPR '03)
|volume=2
|___location=Madison, WI
|year=2003
▲
* Set <math>\mathcal{A}^0 = \mathcal{A}</math>;
Line 72 ⟶ 100:
A simple idea for trying to solve this optimization problem is to truncate the (compact) SVD in step 2 of either the classic or the interlaced computation. A '''classically''' '''truncated M-mode SVD/HOSVD''' is obtained by replacing step 2 in the classic computation by
* Compute a rank-<math>\bar R_m </math> truncated SVD <math>\mathcal{A}_{[m]} \approx U_m \Sigma_m V^T_m </math>, and store the top <math>\bar R_m </math> left singular vectors <math>U_m \in F^{I_m \times \bar R_m}</math>;
while a '''sequentially truncated M-mode SVD (HOSVD)''' (or '''successively truncated M-mode SVD
* Compute a rank-<math>\bar R_m </math> truncated SVD <math>\mathcal{A}_{[m]}^{m-1} \approx U_m \Sigma_m V^T_m </math>, and store the top <math>\bar R_m </math> left singular vectors <math>U_m \in F^{I_m \times \bar R_m}</math>. Unfortunately, truncation does not result in an optimal solution for the best low multilinear rank optimization problem,.<ref name=":2" /><ref name=
== Applications ==
Line 86 ⟶ 114:
It is also used in [[tensor product model transformation]]-based controller design.<ref name="Baranyi042">{{cite journal|author=P. Baranyi|date=April 2004|title=TP model transformation as a way to LMI based controller design|journal=IEEE Transactions on Industrial Electronics|volume=51|pages=387–400|doi=10.1109/tie.2003.822037|number=2|s2cid=7957799}}</ref><ref name="compind2">{{cite journal|author1=P. Baranyi|author2=D. Tikk|author3=Y. Yam|author4=R. J. Patton|year=2003|title=From Differential Equations to PDC Controller Design via Numerical Transformation|journal=Computers in Industry|volume=51|issue=3|pages=281–297|doi=10.1016/s0166-3615(03)00058-7}}</ref>
The concept of M-mode SVD (HOSVD) was carried over to functions by Baranyi and Yam via the [[TP model transformation]].<ref name="Baranyi042" /><ref name="compind2" /> This extension led to the definition of the
M-mode SVD (HOSVD) was proposed to be applied to multi-
== Robust L1-norm variant ==
L1-Tucker is the [[Lp space|L1-norm]]-based, [[Robust statistics|robust]] variant of [[Tucker decomposition]].<ref name="l1tucker"/><ref name="l1tucker3"/> L1-HOSVD is the analogous of M-mode SVD(HOSVD) for the solution to L1-Tucker.<ref name="l1tucker"/><ref name="l1tucker2"/>
== References ==
<references />
{{DEFAULTSORT:
[[Category:Multilinear algebra]]
[[Category:Tensors]]
| |||