Canoni
cal Polyadi
c De
composition (CPD) of a third-order tensor is a minimal de
composition into a sum of rank-1 tensors. We find new mild deterministi
c conditions for the uniqueness of individual rank-1 tensors in CPD and present an algorithm to re
cover them. We
call the algorithm “algebrai
c” be
cause it relies only on standard linear algebra. It does not involve more advan
ced pro
cedures than the
computation of the null spa
ce of a matrix and eigen/singular value de
composition. Simulations indi
cate that the new
conditions for uniqueness and the working assumptions for the algorithm hold for a randomly generated
class="mathmlsrc">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×J×Kclass="mathContainer hidden">class="mathCode"> tensor of rank
class="mathmlsrc">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≥2class="mathContainer hidden">class="mathCode"> if
R is bounded as
class="mathmlsrc">le="View the MathML 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">cript>
le="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">cript>class="mathContainer hidden">class="mathCode"> at
least for the dimensions that we have tested. This improves upon the famous Kruskal bound for uniqueness
class="mathmlsrc">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−2)/2class="mathContainer hidden">class="mathCode"> as soon as
class="mathmlsrc">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≥3class="mathContainer hidden">class="mathCode">.
In the particular case class="mathmlsrc">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=Kclass="mathContainer hidden">class="mathCode">, the new bound above is equivalent to the bound class="mathmlsrc">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−1)(J−1)class="mathContainer hidden">class="mathCode"> 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 class="mathmlsrc">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−1)≤I(I−1)J(J−1)/2class="mathContainer hidden">class="mathCode"> (implying that class="mathmlsrc">le="View the MathML 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">cript>
le="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">cript>class="mathContainer hidden">class="mathCode">). 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 class="mathmlsrc">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≤24class="mathContainer hidden">class="mathCode">, our algorithm can recover the rank-1 tensors in the CPD up to class="mathmlsrc">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−1)(J−1)class="mathContainer hidden">class="mathCode">.