Minimum norm estimation 2D matrix variable


(zhengchen) #1

Hi,

I just started to learn CVX today. I have a minimum norm problem but the variable is 2D matrix instead of a vector in the example of CVX. I tried with the following code and it took “forever” without any error or warning displayed in matlab. Is it because the matrix is too big or just the way I use CVX was wrong?

%% CODE %%
m = size(M,2); % M is a 50250 matrix
n = size(G,2); % G is a 50
3000 matrix
cvx_begin
variables J(n,m) gamma % J is a 2503000 matrix, gamma is a positive number
minimize(norm(M-G
J,2)+gamma.*norm(J,2))
subject to
gamma >0 % I can also give a range like 0<gamma<10
cvx_end
%% CODE %%

This problem is very similar to the example ( An optimal trade-off curve) in the quick start. The differences are 1) the second norm in my case is L2 instead of L1. 2) I have 2D matrix as the variable instead of x(n) in the example.

In this example you defined a range for “gamma” and the final solution is found by plotting the trade-off curve. This for me sounds like the so called “L-curve” technique. My question is would it be possible that I define gamma as a variable (the range of gamma could be defined in subject to as a constrain instead of a list of certain values) and CVX will deal with two variables (J(n,m) and gamma) and find the optimal gamma? In this way, I would expect a optimized way to find gamma.

I also tried to set gamma as a certain number like 0.01 and the code was running without any indication and nothing happened after 30 minutes. Could you please help on this issues. Thank you very much.

Best regards,
Zhengchen


(Mark L. Stone) #2

This is a large, taxing SDP model (because it uses the matrix 2-norm). Note that the matrix 2-norm is very different than the vector 2-norm, which would not give rise to an SDP. If you waited long enough for CVX to finish processing the model as written, which has gamma as a CVX variable, you would receive a CVX error message, because the objective function is not convex.

If you set gamma to a non-negative value and don’t declare it to be a CVX variable, then the model should be accepted if CVX ever finishes processing it. If you try smaller versions of this problem, CVX ought to be able to complete its model formulation and hopefully the solver solve it. Alternatively, if you used, for instance, the frobenius (‘fro’) norm instead of the 2-norm, this model would be much faster for CVX to formulate and a solver to solve. In all cases, you can not declare gamma to be a CVX variable. I will leave it up to you to determine which norm(s) you really want.