I have a 3-tensor $A = A_{ijk}$ with each dimension between 9 and 25 (roughly), and an integer $n > 0$. I would like the factor this tensor as

$$A_{ijk} = \sum_{0 \le \alpha \lt n} B_{\alpha i} C_{\alpha j} D_{\alpha k}$$

such that that $B$, $C$, and $D$ are optimally conditioned possibly rectangular matrices. I'm not sure whether optimally should mean max, sum, or product of $\operatorname{cond}(B)$, $\operatorname{cond}(C)$, $\operatorname{cond}(D)$.

Are there algorithms to do this? Software? I expect it's an NP-complete problem, but $A$ is fixed and I'm willing to spend quite a lot of compute time.

Clarification: As noted in the comments, I'm specifically interested in the overcomplete case $n > \operatorname{rank}(A)$, where more terms than necessary are used in order to improve the conditioning.

  • 1
    $\begingroup$ Looking at dx.doi.org/10.1137/07070111X, isn't this quite close to being a multilinear SVD problem, with $n$ being the tensor rank? Or is that something you've already tried? $\endgroup$ – Kirill Jun 5 '16 at 0:37
  • 1
    $\begingroup$ Nothing in that reference seems to match what I want, but also nothing in there has the exact name "multilinear SVD", so it's possible I missed it. Which algorithm were you referring to? The problem is that I want CP in their terminology, except that I want to set $n > \operatorname{rank}(A)$ to improve the conditioning of $B, C, D$. That case doesn't seem to be discussed. $\endgroup$ – Geoffrey Irving Jun 5 '16 at 4:19
  • 1
    $\begingroup$ I guess I meant "multilinear SVD" as just the general type of idea, not a specific decomposition–the question didn't mention it at all, so I wasn't sure. Your comment makes the question a lot clearer to me now (esp. $n>\mathrm{rank}(A)$), but I can't suggest anything. Their example on p.469 about rank-2 approximating rank-3 seemed to me to be close but in the other direction. $\endgroup$ – Kirill Jun 5 '16 at 4:53

Your Answer

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

Browse other questions tagged or ask your own question.