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

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

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

 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.

-

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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 29, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9344913959503174, "perplexity_flag": "head"}