Canonical polyadic decomposition of third-order tensors: Relaxed uniqueness conditions and algebraic algorithm

详细信息    查看全文

• 作者：Ignat Domanov<sup>asup><sup> ; sup><sup>bsup><sup> ; sup><sup>ignat.domanov@kuleuven.be" class="auth_mail" title="E-mail the corresponding authorsup> ; Lieven De Lathauwer<sup>asup><sup> ; sup><sup>bsup><sup> ; sup><sup>lieven.delathauwer@kuleuven.be" class="auth_mail" title="E-mail the corresponding authorsup>
• 关键词：15A69 ; 15A23
• 刊名：Linear Algebra and its Applications
• 出版年：2017
• 出版时间：15 January 2017
• 年：2017
• 卷：513
• 期：Complete
• 页码：342-375
• 全文大小：655 K

文摘

Canonical Polyadic Decomposition (CPD) of a third-order tensor is a minimal decomposition into a sum of rank-1 tensors. We find new mild deterministic conditions for the uniqueness of individual rank-1 tensors in CPD and present an algorithm to recover them. We call the algorithm “algebraic” because it relies only on standard linear algebra. It does not involve more advanced procedures than the computation of the null space of a matrix and eigen/singular value decomposition. Simulations indicate that the new conditions for uniqueness and the working assumptions for the algorithm hold for a randomly generated <span id="mmlsi1" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951630492X&_mathId=si1.gif&_user=111111111&_pii=S002437951630492X&_rdoc=1&_issn=00243795&md5=f6de898797ba556d5fd0597b31bf6257" title="Click to view the MathML source">I&times;J&times;Kspan><span class="mathContainer hidden"><span class="mathCode">scroll">I&times;J&times;Kspan>span>span> tensor of rank <span id="mmlsi2" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951630492X&_mathId=si2.gif&_user=111111111&_pii=S002437951630492X&_rdoc=1&_issn=00243795&md5=4d7c74b65baff1cdf1ad2719b01fc739" title="Click to view the MathML source">R≥K≥J≥I≥2span><span class="mathContainer hidden"><span class="mathCode">scroll">R≥K≥J≥I≥2span>span>span> if R   is bounded as <span id="mmlsi3" class="mathmlsrc">source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951630492X&_mathId=si3.gif&_user=111111111&_pii=S002437951630492X&_rdoc=1&_issn=00243795&md5=46382bf2f5161f01eaf99696e8e05785">class="imgLazyJSB inlineImage" height="20" width="365" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S002437951630492X-si3.gif">script>style="vertical-align:bottom" width="365" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S002437951630492X-si3.gif">script><span class="mathContainer hidden"><span class="mathCode">scroll">R≤stretchy="false">(I+J+K&minus;2stretchy="false">)stretchy="false">/2+stretchy="false">(K&minus;sqrt>sup>stretchy="false">(I&minus;Jstretchy="false">)2sup>+4Ksqrt>stretchy="false">)stretchy="false">/2span>span>span> at least for the dimensions that we have tested. This improves upon the famous Kruskal bound for uniqueness <span id="mmlsi4" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951630492X&_mathId=si4.gif&_user=111111111&_pii=S002437951630492X&_rdoc=1&_issn=00243795&md5=c007a50703b1af83fb3b936dd195b12e" title="Click to view the MathML source">R≤(I+J+K&minus;2)/2span><span class="mathContainer hidden"><span class="mathCode">scroll">R≤stretchy="false">(I+J+K&minus;2stretchy="false">)stretchy="false">/2span>span>span> as soon as <span id="mmlsi5" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951630492X&_mathId=si5.gif&_user=111111111&_pii=S002437951630492X&_rdoc=1&_issn=00243795&md5=1c26b74db1d2f003d9a97fa282740de1" title="Click to view the MathML source">I≥3span><span class="mathContainer hidden"><span class="mathCode">scroll">I≥3span>span>span>.

sp0060">In the particular case <span id="mmlsi6" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951630492X&_mathId=si6.gif&_user=111111111&_pii=S002437951630492X&_rdoc=1&_issn=00243795&md5=ce7737c9ed7edde190c7645e4a21d2ec" title="Click to view the MathML source">R=Kspan><span class="mathContainer hidden"><span class="mathCode">scroll">R=Kspan>span>span>, the new bound above is equivalent to the bound <span id="mmlsi194" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951630492X&_mathId=si194.gif&_user=111111111&_pii=S002437951630492X&_rdoc=1&_issn=00243795&md5=d43df3f83f3ee7be3a942149e8bcf315" title="Click to view the MathML source">R≤(I&minus;1)(J&minus;1)span><span class="mathContainer hidden"><span class="mathCode">scroll">R≤stretchy="false">(I&minus;1stretchy="false">)stretchy="false">(J&minus;1stretchy="false">)span>span>span> which is known to be necessary and sufficient for the generic uniqueness of the CPD. An existing algebraic algorithm (based on simultaneous diagonalization of a set of matrices) computes the CPD under the more restrictive constraint <span id="mmlsi8" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951630492X&_mathId=si8.gif&_user=111111111&_pii=S002437951630492X&_rdoc=1&_issn=00243795&md5=fc633c849a1f3849b8e7eb69ba9e9b03" title="Click to view the MathML source">R(R&minus;1)≤I(I&minus;1)J(J&minus;1)/2span><span class="mathContainer hidden"><span class="mathCode">scroll">Rstretchy="false">(R&minus;1stretchy="false">)≤Istretchy="false">(I&minus;1stretchy="false">)Jstretchy="false">(J&minus;1stretchy="false">)stretchy="false">/2span>span>span> (implying that <span id="mmlsi9" class="mathmlsrc">source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951630492X&_mathId=si9.gif&_user=111111111&_pii=S002437951630492X&_rdoc=1&_issn=00243795&md5=2caf5463fa1b9b944ab5dd1f0871ed50">class="imgLazyJSB inlineImage" height="19" width="196" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S002437951630492X-si9.gif">script>style="vertical-align:bottom" width="196" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S002437951630492X-si9.gif">script><span class="mathContainer hidden"><span class="mathCode">scroll">R<stretchy="false">(J&minus;c>12c>stretchy="false">)stretchy="false">(I&minus;c>12c>stretchy="false">)stretchy="false">/sqrt>2sqrt>+1span>span>span>). We give an example of a low-dimensional but high-rank CPD that cannot be found by optimization-based algorithms in a reasonable amount of time while our approach takes less than a second. We demonstrate that, at least for <span id="mmlsi10" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951630492X&_mathId=si10.gif&_user=111111111&_pii=S002437951630492X&_rdoc=1&_issn=00243795&md5=486125734e02de25e433221b8d83af6f" title="Click to view the MathML source">R≤24span><span class="mathContainer hidden"><span class="mathCode">scroll">R≤24span>span>span>, our algorithm can recover the rank-1 tensors in the CPD up to <span id="mmlsi194" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S002437951630492X&_mathId=si194.gif&_user=111111111&_pii=S002437951630492X&_rdoc=1&_issn=00243795&md5=d43df3f83f3ee7be3a942149e8bcf315" title="Click to view the MathML source">R≤(I&minus;1)(J&minus;1)span><span class="mathContainer hidden"><span class="mathCode">scroll">R≤stretchy="false">(I&minus;1stretchy="false">)stretchy="false">(J&minus;1stretchy="false">)span>span>span>.