Matrix Least Square problem with constraints taking forever


(Debdipta Goswami) #1

Hello,

I am trying to solve a matrix least square problem with constraints. The problem looks like
minimise ||Y1-Y2*P|| (Frobenius norm)

subject to P(i,j)>=0 for all i,j
row sum of P is 1.

Now P is a huge (say 2000 x 2000) matrix, and Y1 and Y2 both are about (25 x 2000) real valued matrix. The CVX is taking forever to even form the problem before passing it to the chosen solver (Gurobi for instance). Is there any way to speed up this front-end overhead here, like reformatting the problem somehow? Thanks in advance.


(Michael C. Grant) #2

Since you haven’t posted the actual CVX model code, we can’t say. But I’m afraid the answer is likely no. You’ll have to bypass CVX and call the solvers directly if you need better performance. But in fact, this particular problem is better suited for a good old fashioned gradient descent anyway.


(Erling D.Andersen) #3

Shameless advertisement coming.

Solving it using the MOSEK optimization toolbox for MATLAB should be possible. And quite quickly I would expect.


(Michael C. Grant) #4

That’s great! I’d still be curious to see the original poster’s CVX model, though. It’s somewhat surprising that the formulation time would be expensive. It’s possible, certainly, but I wonder if there are unnecessary for loops.

Regardless, I’m glad to hear that MOSEK can handle it.


(Debdipta Goswami) #5

Thanks everyone. The cvx code is the following:

cvx_begin
variable Papprox_temp(mxmy,mxmy);
minimize norm(Psi1-PsiPapprox_temp, ‘fro’);
subject to
for i=1:mx
my
for j=1:mx*my
Papprox_temp(i,j)>= 0;
end
end

for i=1:mx*my
sum(Papprox_temp(i,:))==1;
end
cvx_end


(Michael C. Grant) #6

Yes, just as I suspected!

Those for loops are the cause of your problem. Replace the first set of for loops with just

P_approx_temp >= 0

And replace the second for loop with

sum(Papprox_temp) == 1


(Mark L. Stone) #7

I believe that should be
sum(Papprox_temp,2) == 1

BTW, even if you wanted column sums, in which case sum(Papprox_temp) == 1 would (usually) work, it’s better to explicitly specify sum(Papprox_temp,1) == 1 , otherwise, MATLAB will sum across the row if the program is ever run with matrix having one row (don’t ask me how I know, ha ha, although it has nothing to do with CVX).


(Michael C. Grant) #8

Thanks for the correction, Mark!


(Debdipta Goswami) #9

Thanks everyone. After reformulating the constraints the problem is solved by Gurobi in reasonable time with CVX front-end.