Wrong output on bit string array input

1

My CVX code is:

[m n] = size(A);
cvx_begin
cvx_quiet(true)
variables t W1(m,m) W2(n,n);
minimize(t);
subject to
    [W1 A; A' W2] == semidefinite(m+n);
    diag(W1) <= t;
    diag(W2) <= t;
cvx_end

I tested it with the bit string representation of a given matrix, for space efficiency purposes. For example, the bit string representation of the matrix $$A=\left(\begin{array}{ccc} 1 & 1 & 1 & 1 \ 1 & 0 & 1 & 1 \ 0 & 1 & 0 & 1 \ 0 & 0 & 1 & 0\end{array} \right)$$ is the bit string Abit=1100101011011110, as obtained by the MATLAB function dec2bin. By reshaping the Abit using Abit=reshape(A,4,4), we obtain the bit string matrix that corresponds to A. Given Abit, my code returns cvx_optval=49.2819, but \gamma_2(A)=1.3301 and my code correctly returns this value for input A.

So, does this indicate a CVX deficiency on handling bit string arrays, or is there any modification that I can make to my code in order to handle such matrix representations?

I’m using CVX v.1.22 on MATLAB R2008b. I tried to switch on v2 but faced some strange errors and returned back to v1.22.

2

I think I have reproduced something at least equivalent in the essential respect to what you may have done, and was able to get the result of 49.2819.
A = [1 1 1 1;1 0 1 1;0 1 0 1;0 0 1 0]; AA = reshape(dec2bin(A),4,4);
then use double(AA) for A in your program above. This executes and results in cvx_optval = 49.2819. However

disp(double(AA))
49 49 49 49
49 48 49 49
48 49 48 49
48 48 49 48

I do get cvx_optval = 1.3301 when using the double precision matrix A.

I might also suggest not using quiet mode when you are trying to figure out what is going on.

3

Mark, thanks for your answer. But, I can’t understand what your point is. Do you mean that CVX make an inner conversion of bit string matrices to matrices with elements of type double? If it is the case, I can’t reduce the size of my test arrays like I did until then…

4

I don’t know exactly what you did, because you didn’t show us. I did show a way which reproduces your erroneous result. If you did something that essentially amounts to what I showed, then it is your “fault”, not CVX’s. Whatever you put in for the “A” in the CVX program, it needs to evaluate to the proper result in MATLAB, even leaving aside CVX.

If you are trying to reduce the memory requirement for A, perhaps you should use a sparse matrix representation. The method you used to save memory is obviously wrong.

5

Thanks again, Mark; I got you now. I did exactly what you did to reproduce my result. Thus, my method is wrong, as I suspected.

Surprisingly, MATLAB can do correct computations using bit string representations of (0,1)-matrices (with elements of type double. For example, consider the matrix A = [1 1 1 1;1 0 1 1;0 1 0 1;0 0 1 0] and the vector b=[1,1,0,1]'. For the linear system x=A\b, MATLAB returns the same result either using A and b, or their corresponding bit string representations, obtained by dec2bin.