3
$\begingroup$

I'm researching the problem of solving the equation $A\mathbf{x}=\mathbf{b}$ with ill-conditioned matrices. We know that if we solve it directly, like $\mathbf{x}=\mathrm{inv}(A)\ast\mathbf{b}$, then the stronger the ill-conditioning of matrix $A$, the more any small error in $\mathbf{b}$ will be amplified. But what if we use regularization methods? For example, if we apply the Tikhonov regularization method, will we still reach the same conclusion?

What I mean is, if we use regularization methods, will we still find that the error in the solution increases as the ill-conditioning of matrix $A$ worsens?

$\endgroup$

1 Answer 1

5
$\begingroup$

There is a lot of research about this. I can recommend the books

  • Engl, Heinz Werner, Martin Hanke, and Andreas Neubauer. Regularization of inverse problems. Vol. 375. Springer Science & Business Media, 1996.
  • Hansen, Per Christian. Discrete inverse problems: insight and algorithms. Society for Industrial and Applied Mathematics, 2010.

The former works in Hilbert spaces while the latter in $\mathbb{R}^n$.

In short, Tikhonov regularization helps to keep the amplification of noise down, but at the expense of a bias. This can be quantified as follows:

If there is noisy data $b^\delta$ with $\|b-b^\delta\|\leq\delta$ and we define $$ x^\dagger = A^\dagger b $$ be the (idealized, unknown) true solution (where $A^\dagger$ denotes the pseudo-inverse of $A$ and we assume that $b$ in in the range of $A$) and $$ x_\alpha^\delta = \operatorname{argmin}_x \|Ax-b^\delta\|^2 + \alpha\|x\|^2 $$ be the regularized solution.

Then one can decompose the reconstruction error as $$ \|x_\alpha^\delta - x^\dagger\| \leq \|x_\alpha^\delta -x_\alpha\| + \|x_\alpha - x^\dagger\| $$ where $$ x_\alpha = \operatorname{argmin}_x \|Ax-b\|^2 + \alpha\|x\|^2. $$ We call $$ \|x_\alpha^\delta - x_\alpha\| $$ the data error, which is the error that is induced by the measurement error in $b$, and $$ \|x_\alpha-x^\dagger\| $$ the approximation error, which is due to the approximation of the (true but ill-posed) inversion of $A$.

The decomposition into data and approximation error is similar to the bias-variance decomposition in statistics (bias being the approximation error and variance coming from the data error).

The quantities $x_\alpha^\delta$ and $x_\alpha$ are given by $$ x_\alpha^\delta = R_\alpha b^\delta,\quad\text{and}\quad x_\alpha = R_\alpha b $$ where $$ R_\alpha = (A^*A + \alpha I)^{-1}A^* $$ ($A^*$ is the adjoint/transpose of $A$ and $I$ is the identity operator). This gives us for the data error $$ \|x_\alpha^\delta - x_\alpha\| \leq \|R_\alpha\|\|b^\delta - b\|\leq \|R_\alpha\|\delta. $$ For the approximation error we get $$ \|x_\alpha-x^\dagger\| = \|(R_\alpha - A^\dagger)b\| = \|(R_\alpha A - I)x^\dagger\|. $$ Since one can show that $$ \|R_\alpha\|\leq \tfrac1{2\sqrt{\alpha}} $$ and $$ \|(R_\alpha A - I)x^\dagger\| \to 0 \quad\text{for}\quad \alpha\to 0 $$ we get that the reconstruction error fulfills $$ \|x_\alpha^\delta - x^\dagger\| \to 0\quad\text{if}\quad \delta\to 0,\ \alpha\to 0,\ \text{and}\ \tfrac{\delta}{\sqrt{\alpha}}\to 0. $$

One can get quantitative estimates for the reconstruction error by assuming so called source conditions, e.g. that $x^\dagger$ is in the range of $A^*$. With this assumption one can estimate the approximation error and arrive at estimated of the type $$ \|x_\alpha^\delta\|\leq C_1\tfrac{\delta}{\sqrt{\alpha}} + C_2\sqrt{\alpha} $$ which shows that one get "best reconstruction" of one chooses $\alpha$ in the order of $\delta$.

The constants $C_1$ and $C_2$ do not depend on the condition number of $A$. To be more precise: $C_1$ is fully independent of $A$ (for Tikhonov regularization it is $1/2$), but $C_2$ depends on $A$ implicitly. For Tikhonov regularization one has $C_2 = \|w\|/2$ where $w$ is such that $x^\dagger = A^*w$ - but the condition of $A$ is not so important - it's more the norm of $A$.

$\endgroup$
2
  • $\begingroup$ Towards the end, did you mean to write that $\alpha$ has to be of the order of $\delta$? That bound is minimized when $C_1\frac{\delta}{\sqrt{\alpha}} = C_2 \sqrt{\alpha}$ by AM-GM, which means $\alpha = \frac{C_1}{C_2}\delta$. $\endgroup$ Commented Aug 15 at 17:05
  • $\begingroup$ Oh yes, thanks Federico! $\endgroup$
    – Dirk
    Commented Aug 16 at 6:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .