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.
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.
I agree with the answer about dualizing but an optimizer like MOSEK will do that automatically.
Did you try other optimizers e.g. MOSEK?
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!
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.
Indeed, CVX automatically solves the dual problem if doing so is more efficient. I second Erling’s suggestion to try other solvers, like MOSEK.
Got it. Thank you very much, mgc and Erling.
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.
