How to speed up CVX for sparse, low-rank matrix recovery

I want to solve \min_{\mathbf{X} \succeq 0}\textrm{Trace}(\mathbf{X}) +\lambda \|\mathbf{X}\|_1 subject to \mathbf{A}\textrm{vec}(\mathbf{X}) = \mathbf{y} using CVX. Here, \mathbf{X} \in \mathbb{R}^{n\times n}, \mathbf{A} \in \mathbb{R}^{n^2 \times m} and \textrm{vec}(\cdot) represents vectorization. Below is my code:

cvx_begin
variable X(n, n) semidefinite
minimize(trace(X) + lambda * sum(sum(abs(X))))
subject to
A * X(: ) == y
cvx_end

This runs very slowly for moderately large n, e.g. 100. I’m using SeDuMi, which the user guide recommends over SDTP3. Could you advise how to speed up my programme?

The screenshots attached show the output of the programme on n=84 and m=30. Any comments would be much appreciated!

Try the latest version of Mosek, currently 10.0.25,

To make sure you don’t wind up using Mosek 9.1.9 which is included with CVX 2.2:

First download latest Mosek and install under MATLAB. Make sure mosekdiag succeeds. Then reinstall CVX so it will find the new solver.

Either delete or rename the mosek directory under CVX (before reinstalling CVX)
or
cvx_solver shows all the versions of all the solvers available to CVX. Choose the Mosek 10.x version, which might be called something like Mosek_2, then use cvx_solver Mosek_2 to get that version, and you can save_prefs.

In any event, cvx_solver will show all the versions available to CVX.

1 Like

Thanks so much, Mark! I tried this out and the run time of the same experiment has reduced from 1000secs to 30secs. You are a lifesaver!

However, why does Mosek run so much faster than SeDuMi and SDPT3?

Would you expect TFOCS to run faster than Mosek on this problem?

Mosek is an actively developed commercial solver. SeDuMi and SDPT3? are non-commercial solvers whose development other than minor bug and compatibility fixes ended years or decades ago. In fact, SeDuMi’s developer died over 2 decades ago, although CVX developer @mcg and others did make some bug and compatibility fixes incorporated in the SeDuMi version included with CVX. I will defer to Mosek employees @Erling , @Michal_Adamaszek o @hfriberg to discuss further.

As for TFOCS vs. Mosek, I have no idea, but feel free to share your experience if you get TFCOS implementation in good shape (or maybe you don’t see the need now that you have used Mosek?). I don’t think TFCOS has been further developed for the better part of a decade. As you can see, TFOCS developer @Stephen_Becker just posted in your other thread TFOCS for mixed trace and $\ell_1$-norm minimization .

1 Like

@Mark_L_Stone nails it pretty well.

This

https://themosekblog.blogspot.com/2022/06/on-performance-improvement-of-semi.html

shows something about the improvements we made in the recent v10 which is definitely not in SeDuMi.

1 Like

If your problem is small enough to be run by MOSEK, then you should use MOSEK over TFOCS. TFOCS is best for really large problems: it takes many more iterations to converge, but each iteration has cheaper complexity (if you apply it to the right kind of problem). TFOCS can take advantage of fast multiplies for the linear constraints (sparse matrices, FFT/convolutions/blur, etc.). So, rule-of-thumb, if you have a giant problem and are OK with low-accuracy, then you could consider TFOCS; if it’s small enough to run quickly in MOSEK, then you shouldn’t worry about TFOCS (TFOCS wouldn’t give you much more accuracy except in rare cases).

2 Likes

I see, thanks so much Stephen. Your high-level clarification is really useful.

I see, thank you Mark. Yes, I think Mosek is sufficient for now. I’ll share results with you when I’ve constructed a solution using TFOCS.