3
$\begingroup$

What is the objective function for CP (CANDECOMP/PARAFAC) tensor decomposition?

The decomposition tries to decompose a tensor $Z$ to $Z \approx \sum_{l=1}^L \lambda_l a_l \circ b_l \circ c_l $, where $\lambda_l \in \mathbb{R}_+$. Does it mean that the objective function is squared error as in SVD? That is, is the corresponding optimization problem as below

$$\min_{\lambda,a,b,c: \|a_l\|=\|b_l\|=\|c_l\|=1, \lambda_l \ge 0} \sum_i \sum_j \sum_k (Z_{ijk} -\sum_{l=1}^L \lambda_l a_{li} \circ b_{lj} \circ c_{lk} )^2$$

Typically the objective is the squared $L_2$ distance for decomposition, but I just want to make sure.

$\endgroup$
3
$\begingroup$

$a_l$, $b_l$, and $c_l$ should be replaced by $a_{li}$, $b_{lj}$, and $c_{lk}$, respectively. The norm constraints and $\lambda$ in min and cost function can be dropped, i.e., $\min\limits_{a_k,b_k,c_k}$ is okay (unconstrained optimization). There are several matlab tooklboxes that compute CP decomposition (e.g., tensorlab.net)

$\endgroup$
  • $\begingroup$ I can see now that my indices is messed up. I will fix it. Thanks for mentioning it! How is it that the constraints can be dropped? Does it not mess up the uniqueness of decomposition? Would you please elaborate a bit? $\endgroup$ – user25004 Sep 20 '16 at 19:04
  • $\begingroup$ One more thing: I suppose that $\lambda$-s are not known. In this case $\lambda$-s should also be under $\min$. $\endgroup$ – Ignat Domanov Sep 20 '16 at 19:12
  • $\begingroup$ @ Ignat. Fixed! Thanks! So the constraints would be okay? $\endgroup$ – user25004 Sep 20 '16 at 19:14
  • 1
    $\begingroup$ $\lambda $ and the norm constraints in min can be dropped because $\lambda$ can be moved inside $a\circ b\circ c$, e.g. $(\lambda a)\circ b\circ c$. In other words, $a$, $b$, $c$ can be recovered only up to scalars $\alpha$, $\beta$, and $\gamma$ such that $\alpha\beta\gamma=1$ (indeed, $a\circ b\circ c=\alpha a\circ \beta b \circ \gamma c$) $\endgroup$ – Ignat Domanov Sep 20 '16 at 19:18
  • 1
    $\begingroup$ Uniqueness of CP decomposition means uniqueness up to permutation of rank-$1$ terms, so moving constants in/out rank-$1$ terms does not affect uniqueness. $\endgroup$ – Ignat Domanov Sep 20 '16 at 19:24
2
$\begingroup$

The article you link to is also titled Tensor Rank Decomposition:

[T]he tensor rank decomposition is sometimes historically referred to as PARAFAC or CANDECOMP.

When the number of terms $r$ is minimal in the above expression, then $r$ is called the rank of the tensor, and the decomposition is often referred to as a (tensor) rank decomposition, minimal CP decomposition, or Canonical Polyadic Decomposition (CPD).

The objective function for an (exact) decomposition as a sum of rank one tensors is not about an approximating sum, but rather about minimizing how many rank one tensors are needed to give an exact summation. Thus the objective function here is a discrete function, counting the number of terms used.

Of course $n^2$ such tensors always suffice for an $n\times n$ matrix (or indeed $n$ will suffice), but in the "tensor rank" problem we want to know how few will suffice.

$\endgroup$
  • $\begingroup$ I see. So you are saying that since the decomposition is exact the recovery error is zero, and it does not matter with which norm we measure it. It still remains zero. Then the question would be how about a rank "L" CP, for a fixed rank $L$. Then the decomposition would not be exact, right. I am wondering if we have such a thing, such as in SVD? $\endgroup$ – user25004 Sep 20 '16 at 19:01
  • 1
    $\begingroup$ @user25004 Such a thing called higher-order SVD. But it is quite different from the CP decomposition. The optimization problem in your question may not have a solution (so called divergent components) $\endgroup$ – Ignat Domanov Sep 20 '16 at 19:27
  • 1
    $\begingroup$ Yes, you can certainly pose the problem, for various matrix or tensor norms, asking the "best approximation" by a sum of fixed $k \lt r $ rank one tensors. The SVD answers one version of this for matrices. $\endgroup$ – hardmath Sep 20 '16 at 19:31
  • $\begingroup$ @Ignat Are you saying the CP decomposition is always considered an exact decomposition? And if we need up to a number $K$, we need to go for higher-order SVD instead of CP? This would imply that the choice of the objective would not matter at all then? Is that what you are trying to say? $\endgroup$ – user25004 Sep 20 '16 at 19:49
  • 1
    $\begingroup$ Uniqueness makes sense only for the exact CP decomposition. If you start from the exact CP decomposition and add noise, then the rank of the noisy tensor significantly increases (typical rank), so you can consider only approximation by a rank-L decomposition. To my knowledge, there are no results on uniqueness of the approximation, but in practice, one of course computes it with a hope that if a tensor had a unique (exact) decomposition, and if the noise was sufficiently small, then the rank-L approximation will be close to the actual "true" CP-decomposition. $\endgroup$ – Ignat Domanov Sep 20 '16 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.