1

I'm trying to find an efficient approach to minimising the sum of pseudo-huber penalty along a vector. Ideally I would like to be able to formulate this problem as a linear system of the form $\mathbf{Ax = b}$, which can be solved via the conjugate gradient method.

First let $h(x): \mathbb{R} \to\mathbb{R}$ be the psuedo-huber penalty

$h(x) = t^2 \left(\sqrt{1 + \left(\frac{x}{t}\right)^2} - 1 \right)$

which is smooth and convex. To find the minimum we take the first derivative and set it to zero

$\frac{\partial}{\partial x} h(x) = \frac{x}{\sqrt{1 + (\frac{x}{t})^2}} = 0 \; \therefore x = 0$

I wish to extend this to the case of vector input. Let $\| \mathbf{x} \|_{H}: \mathbb{R}^n \to \mathbb{R}$ be the pseudo-huber norm

$\| \mathbf{x} \|_{H} = \sum_{i=1}^n t^2 \sqrt{1 + \left(\frac{\mathbf{x_i}}{t}\right)^2} - t^2$

Since the psuedo-huber penalty is convex the sum should also be convex. So to find the minimum we take the same approach as before and set the first derivative to zero. The derivative of a summation can be written as the summation of derivatives:

$\frac{\partial}{\partial \mathbf x} \| \mathbf{x} \|_{H} = \sum_{i=1}^n \frac{\mathbf x_i}{\sqrt{1 + (\frac{\mathbf x_i}{t})^2}}$

Now we come to the real problem. Can one write $\frac{\partial}{\partial \mathbf x} \| \mathbf{x} \|_{H}$ in matrix notation? For example one might wish to minimise

$f(\mathbf x) = \| \mathbf{D x - s} \|_2^2 + \| \mathbf{x} \|_{H}$

Ideally we would like $\frac{\partial}{\partial \mathbf x} f(x) = 0$ to be of the form $\mathbf{Ax = b}$ so that we can solve it using the conjugate gradient method.

A more complete example would be:

$\min_{\mathbf{x}} \; g(\mathbf x) = \| \mathbf{D x - s} \|_2^2 + \| \mathbf{x} \|_{2} \\ \frac{\partial}{\partial \mathbf x} g(x) = 2(\mathbf{D x - s}) + 2 \mathbf x = 0 \\ (\mathbf D + \mathbf I)\mathbf x = \mathbf s$

Which is of the form $\mathbf{Ax = b}$.

Stephen Tierney
  • 135
  • From what you've written here, you're taking the derivative of a scalar, so that's zero. I think that what you want to do is apply the norm after you take "the derivative" so you should actually be looking at $\grad \mathbf{x}$, which should then be fairly easy to put into the form of a matrix equation. – postmortes Dec 20 '13 at 09:50
  • @postmortes if it is fairly easy for you then please write an answer. – Stephen Tierney Dec 20 '13 at 22:51
  • What do you mean by writing derivative to be zero in the form of $Ax=b$? – Shuchang Dec 21 '13 at 01:02
  • @Shuchang I have updated the question to be more specific. – Stephen Tierney Dec 21 '13 at 04:19

1 Answers1

1

First, unless I'm misunderstanding, the gradient of your multi-dimensional norm is actually $$\nabla h(x) = \sum_{i} \frac{x_i}{\sqrt{1+(x_i/t)^2}} dx_i,$$ i.e. is vector-valued with the $i$th component depending only on $x_i$. The Hessian is therefore diagonal and positive, and so $\|x\|_H$ is convex, as you claimed.

The gradient is not an affine function of $x$: you can check this by noting that $$\nabla h(x/2+\textbf{0}/2) \neq \frac{1}{2}\nabla h(x) + \frac{1}{2}\nabla h(\textbf{0}).$$ Therefore, there is simply no way you can express $\nabla h$ in the matrix form you seek. However, since $\|x\|_H$, and therefore $\|Dx - s\|_2^2 + \|x\|_H$, is convex, it is a excellent candidate for minimization using nonlinear optimization techniques, such as Newton's method (which you can implement using your Conjugate Gradients code, if you wish).

user7530
  • 49,280