Difference between log_det, sum_log, det_rootn, and geo_mean

1

This question stems from this post) in which I observed that depending on whether I used log_det, sum_log, det_rootn, or geo_mean, cvx returned different solutions. I just wanted to check whether I’m doing anything crazy before filing a bug report. I let K=M=4, let H = randn(K,M) + 1i*randn(K,M), and let P_ant=250. Then I run the following cvx program:

cvx_begin 
    variable Q(M,M,K) hermitian;

    expression expr
    for k=1:K
        expr(k) = real(1 + H(k,:)*Q(:,:,k)*H(k,:)');
        % had to use real() to eliminate a small(?) imaginary component
    end
    maximize "objective"

    for m = 1:M
        sum(Q(m,m,:)) <= P_ant;
    end
    
    for k = 1:K
        range = 1:K;
        notk = range(range~=k);
        for j = notk
            H(j,:)*Q(:,:,k)*H(j,:)' == 0;
        end
        Q(:,:,k) == hermitian_semidefinite(M);
    end
cvx_end

where “objective” can be one of the following:

sum_log(expr)
geo_mean(expr)
log_det(diag(expr))
det_rootn(diag(expr))

When using either log_det(diag(expr)) or det_rootn(diag(expr)), I believe the answer is correct (at least, the objective is never less than a simpler, non-optimal method I use for comparison). However, when using sum_log(expr) or geo_mean(expr), the entries of expr are nearly the same (i.e. expr(1)=expr(2)=…, which is unexpected), and the objective (sum(expr)) is sometimes less than that of the simple comparison method.

I’ve found the same results in cvx-1.2 and cvx-2.0beta. The confusing thing to me is that geo_mean() is exactly equivalent to det_rootn(diag()), and sum_log() is exactly equivalent to log_det(diag()). And when maximizing over these objectives, I believe they should all be equivalent. It’s strange that the two functions that use diag() have the same behavior… am I doing something wrong?

2

Well, there is definitely no point whatsoever using log_det and sum_log. These are actually implemented using det_rootn and geo_mean, respectively, so I am not surprised they achieve the same results. The rest is interesting, however, thank you for submitting this. I will investigate…

3

Thanks again for submitting this bug report. I’ll post an update when I complete the diagnosis, but for now, I think that the bug is somehow related to the use of the expression statement.

UPDATE

Actually, I’ve located the exact problem. After the first for loop, expr is a 1\times 4 vector. geo_mean is not processing this row vector properly. However, if you ensure that geo_mean sees a column vector, it works properly. For instance, if you change your for loop as follows, it works as expected:

for k=1:K
    expr(k,1) = real(1 + H(k,:)*Q(:,:,k)*H(k,:)');
    % had to use real() to eliminate a small(?) imaginary component
end

This is certainly a bug, and I am going to fix it promptly and issue a rapid update. Thank you for finding this! I’ll leave the rest of my answer up since there are some tricks there you might find useful anyway.

END UPDATE

If you change the expression expr to variable expr(K), and you change the assignments to expr(k) to equality constraint, the difference between the two problems goes away. Here’s the relevant excerpt of the modified model:

    variable expr(K);
    for k=1:K
        expr(k) == real(1 + H(k,:)*Q(:,:,k)*H(k,:)');
    end

Now it’s actually important to note that in this case, whether you use geo_mean(expr) or det_rootn(diag(expr)) is irrelevant, because CVX actually can tell when a the argument to det_rootn is exactly/structurally diagonal, and converts it to a call to geo_mean automatically. Note that CVX can’t deduce that a matrix should be diagonal at the solution—but it can do so in this case, because its input is diag(expr), which means the off-diagonal elements are identically zero.

I also tried cleaning up your model a bit. I created a new variable R(K,K) that is set equal to all of your H-Q products. By declaring this variable to be diagonal, I encapsulated your equality constraints naturally. The objective just becomes det_rootn(R). I also did a few more tricks to tighten up the model. Here’s the result:

cvx_begin 
    variable Q(M,M,K) hermitian;
    variable R(K,K) diagonal;
    Q == hermitian_semidefinite([M,M,K]);
    diag(sum(Q,3)) <= P_ant;
    for k = 1:K
        for j = 1:K,
            R(k,j) == real(H(j,:)*Q(:,:,k)*H(j,:)');
        end
    end
    maximize(det_rootn(R));
cvx_end

This model also produces the same result as yours, again no matter whether I use geo_mean(diag(R)) or det_rootn(R) as the objective. Furthermore, both of my modified models avoid the weird issues you were seeing with the geo_mean case.

So I think you have identified a bug in expression handling, and I thank you for that! In the meanwhile, I think this change in your model will give you consistent results. Let me know what you think.

4

Great, thanks for the detailed response. Glad I hit on something relevant!