Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
up vote 3 down vote accepted

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.

share|improve this answer
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? – Stiefel Dec 6 '12 at 16:33
Of course you can. See the edit. – Arnold Neumaier Dec 6 '12 at 17:02
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! – Stiefel Dec 10 '12 at 13:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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