2
$\begingroup$

Is there a way to compute $y = (I_p \otimes A \otimes I_r )x$ efficiently? Where $A \in {\rm I\!R}^{q\times q}$ and $x ∈ {\rm I\!R}^{pqr}$?

I know that for $y = (I_p\otimes A)x$ this can be written as $Y=AX$ where $y=\mathrm{vec}(Y)$ and $x=\mathrm{vec}(X)$, but what's the generalisation when $y = (I_p \otimes A \otimes I_r )x$?

$\endgroup$
  • $\begingroup$ Your notation is not clear. Well, in $y = (I_p\otimes A)x$, $x$ and $y$ are vectors, aren't they? So, what $X = \text{vec}(x) $ (or $Y = \text{vec}(y)$) means? If $x$ and $y$ are vectors then $X=x$ ($Y=y$) and $Y=AX$ is false. $\endgroup$ – Alex Silva Apr 5 at 8:34
  • $\begingroup$ @AlexSilva sorry mistyped, what I ment to write was that $x=\mathrm{vec}(X)$ $\endgroup$ – Turbotanten Apr 5 at 9:01
  • $\begingroup$ I think you can only rewrite as $Y = (A\otimes I_r)X$. $\endgroup$ – Alex Silva Apr 5 at 9:35
2
$\begingroup$

Yes. It is essentially $A\cdot [X]_{(2)}$, where $[X]_{(2)} \in \mathbb{R}^{q \times p\cdot r}$ is a rearrangement of $x$ such that the index $q$ varies along rows and the indices $p, r$ vary along columns. The result of the multiplication is $q \times p\cdot r$ which if you rearrange back properly should give you $y$.

Here is a patchy Matlab demo for the concept (can be made much more efficient I'm sure):

p = 2;r = 4;q = 3;
A = randn(q,q);
x = randn(p*q*r,1);
% here is your version
v1 = kron(kron(eye(p),A),eye(r))*x;

% rearrange X to q x rp
X = reshape(permute(reshape(x,[r,q,p]),[2,1,3]),q,r*p);
% actual multiplication: just of size q
V2 = A*X;
% rearrange back the reshult
V2 = ipermute(reshape(V2,q,r,p),[2,1,3]);
v2 = V2(:);

% it's the same
disp(norm(v1-v2))

One wouldn't implement it like that I guess, but it serves to show the concept.

$\endgroup$
  • $\begingroup$ Thanks, the code looks and is very efficient. I wonder how it could be improved further? $\endgroup$ – Turbotanten Apr 8 at 8:19
  • $\begingroup$ Try it out for you and do some benchmarks. It'll depend on your problem size. If the bottleneck is the actual multiplication then you're fine. I'm not exactly sure about the efficiency of the permutes/reshapes. $\endgroup$ – Florian Apr 8 at 8:57

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.