4
$\begingroup$

The best known algorithm(s) for matrix multiplication of $n$-dimensional matrices take $O(n^{2.37})$ time. However, that's for matrices with totally independent contents. When the two matrices are related to each other in some known way, it's sometimes possible to get a speedup. For example, computing $U \cdot V$ is quite easy if you're promised that $V = U^{-1}$.

I was wondering if knowing $V = U^\dagger$, i.e. that $V$ is the conjugate transpose of $U$, allowed for asymptotically faster matrix multiplication.

Can the special case $U \cdot U^\dagger$ be computed asymptotically more quickly than the general case $U \cdot V$?

$\endgroup$
4
$\begingroup$

It's not faster (asymptotically). You can reduce general matrix multiplication down to three "adjoint-squarings".

Suppose we're given an adjoint-squaring function $\mathfrak{F}$ where $\mathfrak{F}(M) = M \cdot M^\dagger$. Consider that:

$\mathfrak{F}(A + B) = (A+B) \cdot (A+B)^\dagger = AA^\dagger + BB^\dagger + A B^\dagger + B A^\dagger$

$\mathfrak{F}(A - B) = AA^\dagger + BB^\dagger - A B^\dagger - B A^\dagger$

$\mathfrak{F}(A + i B) = AA^\dagger + BB^\dagger - i A B^\dagger + i B A^\dagger$

Thinking in terms of the basis $[x, y, z, t] \rightarrow x AA^\dagger + y BB^\dagger + z A B^\dagger + t B A^\dagger$, those three adjoint-squarings give us $p=[1, 1, 1, 1]$ and $q=[1,1,-1,-1]$ and $r=[1,1,-i,i]$ respectively. From that we want to recover the product $[0,0,1,0] \rightarrow AB^\dagger$. A bit of work will show that the linear combination $\frac{1-i}{4}p - \frac{1+i}{4}q + \frac{i}{2} r$ is exactly what we need.

Therefore we can compute the product $U \cdot V$ via $\mathfrak{F}$ by evaluating:

$$U \cdot V = \frac{1-i}{4} \mathfrak{F}(U + V^\dagger) - \frac{1+i}{4} \mathfrak{F}(U - V^\dagger) + \frac{i}{2} \mathfrak{F}(U + i V^\dagger)$$

Since the most expensive step of this reduction is the adjoint-squaring (it's certainly not the adding, conjugating, transposing, subtracting, or scaling), and the adjoint-squaring function $\mathfrak{F}$ is only used a constant number of times (3 times), general multiplication is no more asymptotically expensive than adjoint-squaring.

(Related: Is matrix squaring asymptotically faster? Nope. With a much simpler proof.)

$\endgroup$
  • $\begingroup$ Is this an answer you post claiming it is correct, or do you want feedback as to whether it is correct? (Just checking your intentions, I have not read the answer.) $\endgroup$ – Raphael Jan 19 '16 at 15:13
  • 1
    $\begingroup$ @Raphael It should be correct. I figured it out as part self-answering another question, realized it should be separate, and split it off. $\endgroup$ – Craig Gidney Jan 19 '16 at 16:04

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.