Matrix multiplication and conjugation

Question

Let $A,B \in \mathbb{C}^{n \times n}$ be given $A,B \neq 0$. Then I would like to know what

$$\inf_{V_1,...,V_d \in \mathbb{C}^{n \times n}} \left\lVert AB - \sum_{k=1}^{d} V_k B V_k^* \right\rVert$$ is, where $d$ is arbitrary.

So I would like to know, if we can say in general for two matrices, how much conjugation is contained in multiplying $A$ and $B$.

It is easy to get an upper bound: $V_1=A$ for $d \ge 1.$ This way, $$\inf_{V_1,...,V_d} \left\lVert AB - \sum_{k=1}^{d} V_k B V_k^* \right\rVert\le \left\lVert AB(1-A^*)\right\rVert. $$

Is there a way to get more elaborate bounds? Has this question been studied somewhere? What is the dependence on $d$? Does the approximation become better for $d$ large? By linear independence, it seems that making $d$ larger than $n^2$ does no longer improve things, but maybe it is enough to consider much smaller numbers $d$. I am curious. Thanks a lot

Answer 1

I don't yet know of an explicit method of computing your desired infimum (although I'm fairly convinced that an explicit method exists), but here is MATLAB code that computes it efficiently via semidefinite programming. For this code to work, you will need to install two (free) packages for MATLAB: CVX and QETLAB.

A = [1 2;3 4];
B = [5 1;3 1];

n = length(A);

cvx_begin sdp quiet
    cvx_precision best;
    variable Phi(n^2,n^2) hermitian

    minimize norm(A*B - ApplyMap(B,Phi),'fro')

    subject to
        Phi >= 0;
cvx_end

cvx_optval

You can of course replace $A$ and $B$ in the above code with any matrices of your choosing -- it can handle matrices of size up to $20 \times 20$ or so (and it returns a value of 10.3132 for the pair of matrices I chose above).

As mentioned in my earlier comment, the method of computation relies on observing that the map $\Phi(B) = \sum_{k=1}^d V_k B V_k^*$ is just an arbitrary completely positive map (when $d \geq n^2$), which can be optimized over by using the fact that they're isomorphic to the set of positive semidefinite matrices.

It's also worth noting that this remains a semidefinite program (and thus the above code still works) even if you replace norm(,'fro') with pretty much any other matrix norm, like the operator norm or trace norm. Also, if you want to know what the $\{V_k\}$ matrices are that attain the minimum, use the following code (after running the above code):

V = KrausOperators(Phi);

This will put the $\{V_k\}$ matrices in a cell array, so that V{1} is $V_1$, V{2} is $V_2$, and so on.