Is there a nonlinear solver similar to CGNR evaluating only $A^TAx$?

Question

First of all, I am quite new to this field and I excuse myself in advance for any stupid content in this question.

In the field of compressed sensing or deblurring I have a nonlinear optimization problem of the form

$\min R(x)$ s.t. $Ax-b<\epsilon$

Currently, I solve the optimization problem using the Langrangian form and the non-linear conjugated gradient method:

$f(x) = |Ax-b|^2 +\lambda R(x)$

with the gradient

$\nabla f(x) = 2A^TAx-A^Tb +\lambda \nabla R(x)$

$Ax$ and $A^Tx$ are expensive to evaluate since they contain a non-uniform FFT. However, I am able to evaluate $A^TAx$ quite fast on a cartesian grid by convolution with the point spread function of $A^TA$.

This way I am able to calculate the gradient fast, but for the line search of the nonlinear CG I still have to evaluate $Ax$ frequently. I am looking for a nonlinear method that only needs the evaluation of $A^TAx$.

In a first attempt, somehow similar to linear CGNR, I tried to minimize the residual of the normal equations by using the following (in the line search only):

$f2(x) = |A^TAx-A^Tb|^2 +\lambda R(x)$

Without $\lambda Rx$ this method obviously reduces to linear CGNR (with an unnecessary line-search).

The method seems to converge to a solution. However, it converges to a different solution than the nonlinear CG, since the constant value of $\lambda$ needs to be adapted .

So my questions are:

1) Is this total nonsense what I tried? ;-)

2) Is there something like a "nonlinear CGNR"?

3) Or some other suitable method that solves my nonlinear optimization problem using only $A^TA$?

4) What is the gradient of $f2x()$?

Answer 1

Your problem is equivalent to minimizing $f(x)=x^T(Bx-c)+\lambda R(x)~~~~$ where $B=A^TA$, and $c=2A^Tb~~$. The gradient is $g(x)=2Bx-c+\lambda\nabla R(x)$.

Thus if you precompute $c$, any gradient-based method with line search only needs multiplications with $B$.

[Edit] In the complex case, you have $f(x)=x^*Bx-Re~(x^*c)+\lambda R(x)~~~~~$ where $B=A^*A$, and $c=2A^*b~~$, and things are essentially as in the real case.