L1 norm minimization- too slow in CVX

1

I would like to minimize the objective function |Ax -b|_1 (i.e., L1 norm of an error). The matrix A models the forward projection (sampled Radon transform) of a CT scanner, x is an image, and b is the measured Radon transform. A is not orthogonal. Its size is 46080 x 16384, and it is sparse. The following is the CVX code

cvx_begin
variable xk(npix*npix);
minimize(norm(A*xk-b, 1));
cvx_end

CVX has taken about 8 hours to run this, and next I will need to add constraints. I would like to use TFOCS instead, if that’s faster. Please can you suggest how to put this problem in one of the standard forms that TFOCS requires? Thank you.

2

The presence of A in the norm suggests passing to the dual. Assuming x \ge 0, the dual is
$$\begin{split} \min_\theta & b’ \theta \ \mbox{s.t.} & A’\theta \ge 0 \ & ||\theta||_\infty \leq 1 \end{split}$$
which can be approximated by tfocs_SCD using small \mu.

3

I agree with the answer about dualizing but an optimizer like MOSEK will do that automatically.

Did you try other optimizers e.g. MOSEK?

4

Thank you nv. I am new to optimization, and I need to follow this up. Did you mean “max” instead of “min” in the dual form? If not, I don’t understand! Second, if I use the dual, how will I get the optimal solution x of my primal problem? I appreciate your patience!

5

Actually, you do not take the dual yourself; tfocs SCD does that for you. In effect you will want to solve \tfrac{1}{2}\mu^2\|x\|_2^2+\|Ax-b\|_1. Unfortunately we don’t have the resources here to provide a lot of TFOCS tutorial help. It is definitely a more difficult to use piece of software.

6

Indeed, CVX automatically solves the dual problem if doing so is more efficient. I second Erling’s suggestion to try other solvers, like MOSEK.

7

Got it. Thank you very much, mgc and Erling.

8

Yes, the correct objective is max_\theta -b’\theta. For the primal solution you need to check which of the A’\theta >= 0 inequalities are active at the solution. As mcg pointed, you can use tfocs_SCD directly.