5
$\begingroup$

I have left maths world a few years ago and doing Machine learning nowadays. But In one of the paper I am reading, the author just writes (well slightly different wording/ notation)

$H$ is positive definite so $H^{-1}v$ = arg min$_t \{ t^\top H t - v^\top t \}$

and quite honestly I have no idea why this is the case.

Help would be nice thanks!

$\endgroup$

3 Answers 3

4
$\begingroup$

Either you are quoting the author incorrectly, or the author is wrong. Observe that $t^\top Ht-v^\top t=\left\|H^{1/2}t-\frac12H^{-1/2}v\right\|_F^2-\left\|\frac12H^{-1/2}v\right\|_F^2$. Since the second term is constant, the objective function is minimised when $H^{1/2}t-\frac12H^{-1/2}v=0$. Hence the (unique) minimiser is $t=\frac12H^{-1}v$ rather than $t=H^{-1}v$.

In particular, when $H,v,t$ are real numbers and $v=H=1$, the objective function is $f(t)=t^\top Ht-v^\top t=t^2-t$. Its critical point (the value of $t$ at which $f'(t)=0$) is $t=\frac12=\frac12H^{-1}v$, not $t=1=H^{-1}v$.

$\endgroup$
1
  • $\begingroup$ The author was quoting another paper and he wasn't even using the method because other method is faster so it's not too surprising that the statement is wrong (I double checked that I didn't make mistake copying the identity down. I don't have the access to the original paper so I won't find out who made the initial mistake :P $\endgroup$
    – Jack Yoon
    Commented Jul 12, 2022 at 11:00
3
$\begingroup$

I think you should have $\frac{1}{2}$ in front of $t^THt$. But the reason is that the gradient of the function $f(t) = t^THt - t^Tv$

$$\nabla_t(t^THt - t^Tv) = (H+H^T)t-v = 2Ht-v$$

This is by linearity and for the bi-linear part see for example here. For a critical point we get $\frac{1}{2}H^{-1}v$. This is a local minimum because the Hessian is actually $H$ and it's positive definite. To see that it's a global minimum notice that for any direction $t$ (a unit vector) the function $f(st), s\in{[0, \infty)}$ tends to infinity. This is because

$$f(st) = s^2 t^THt - s t^Tv = s(s t^THt - t^Tv) > s,$$

when $s>\frac{ t^Tv}{t^THt}$. By C-S we have $t^Tv \leq |t||v| = |v|$ and $|t^THt|$ is bounded by the largest eigenvalue of $H$, so outside a big enough ball $f$ will be larger than in the critical point.

$\endgroup$
2
$\begingroup$

The minimum of $t^THt−v^T t$ is attained when the first order derivative is zero, i.e.

$2 Ht −v = 0$

in other words

$t = \frac 1 2 H^{-1} v$

so a factor of $\frac{1}{2}$ is missing.

$\endgroup$
0

You must log in to answer this question.

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