I'm working with non-linear optimization for imaging, such as MRI and CT.
Our problem is of the form $\|Ax-b \|_2^2+\lambda \|Wx\|_1$. $A$ is never formed explicitly, so we're limited to approaches that only use $Ax$ and $A^Hf$. Even so, these evaluations are quite expensive, whereas $Wx$ and $W^Tx$ are quite inexpensive to compute.
I've been using a non-linear conjugate gradient (NCG) for this problem, but my backtracking line search tends to fail as $A^H$ is not the exact conjugate transpose of $A$, but an approximation.
Ignoring the non-linear term and using the conjugate gradient on the normal equations, everything works beautifully, and so does the Split-Bregman algorithm. The latter is however something like an order of magnitude slower than the NCG.
I was wondering if anyone knew if an iterative solver that allowed for the gradient ($A^H(Ax-f)$ to be approximate?