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()$?


1 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.

  • $\begingroup$ Thank you, this is a good solution. Now I am trying to do the same thing in complex space. In this case I can't factor out $x^H$ that easily, since $(x^HA^Hb)^H \neq x^HA^Hb$. Any idea? $\endgroup$
    – Stiefel
    Dec 6, 2012 at 16:33
  • $\begingroup$ Of course you can. See the edit. $\endgroup$ Dec 6, 2012 at 17:02
  • $\begingroup$ Stupid me, the $Re(x^*c)$ is a scalar product and a cheap operation in my case. So there is obviously no need to factor out $x^*$. Thank you, I should have seen this myself! $\endgroup$
    – Stiefel
    Dec 10, 2012 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.