1
$\begingroup$

I have a quadratic from, $v^{T}Hv +q^Tv+c$, where neither the $H$, $q$ and $c$ are given implicity. The whole expression is very complicated, but it is quadratic form. $H$ is simetric.

The question is: how can I build an procedure that return $Hv$, that use only evaluation of the above quadratic form or at least from the form $v^THv$?.

The trivial way would be using combinations of canonical vector, that will return the entries of the matrix $H$ one-by-one, but this is not scalable method, since I am expecting to deal with dimensions more than $10000 \times 10000$. Is there a better way?.

The ultimate goal is to solve the problem of minimizing the quadratic form using the conjugate gradient algorithm. That is why I need a procedure that perform the kernel $Hv$.

Any advice, would be greatly appreciated. Thanks in advance.

$\endgroup$
  • $\begingroup$ How complicated is your expression? Aren't you able to differentiate it? Or you can do it numerically, since central difference scheme is exact for quadratic function. $\endgroup$ – tom Mar 6 '14 at 20:27
  • $\begingroup$ I am able to differentiate it respect to some scaling factor, i.e. changing $v$ for $tv$ and deriving respect to $t$. But at the end, I always get an scalar quantity. Central difference scheme $\endgroup$ – user38568 Mar 6 '14 at 20:38
1
$\begingroup$

Denote $Q(v) = Q(v_1,\dots,v_n) = \frac1{2}v^T H v + q^T v + c$ where $v = (v_1,\dots,v_n)$.

Fix some $v$ for which you want to calculate $Hv$

Function $f(x) = Q(x,v_2,\dots,v_n)$ is quadratic function and $f'(x) = \frac{\partial Q}{\partial v_1}(x,v_2,\dots,v_n) = (Hv+q)_1$, by $(Hv+q)_1$ I mean first component of $Hv+q$.

Now we use fact, that central difference scheme is exact for quadratic function: $$ \frac{\partial Q}{\partial v_1}(x,v_2,\dots,v_n) = f'(x) = \frac{f(x+h)-f(x-h)}{2h} = \frac{ Q(x+h,v_2,\dots,v_n) - Q(x-h,v_2,\dots,v_n)}{2h} $$ $h$ is arbitrary.

This gives us final answer: $$ (Hv + q)_i = \frac{ Q(v+ e_i) - Q(v-e_i) }{2} $$

But this is still quite costly. Because evaluating quadratic form and matrix-vector multiplication is both $O(n^2)$ but my suggested method which is $O(n^3)$

$\endgroup$
  • $\begingroup$ It is still $O(n^3)$ but it is far better than the trivial way that I was stucked. The use of central difference scheme was a great idea. Thanks you very much. $\endgroup$ – user38568 Mar 6 '14 at 21:12
  • $\begingroup$ I think that there is no way to do better than $O(n^3)$ if the only thing you can do is to evaluate $Q(v)$ $\endgroup$ – tom Mar 6 '14 at 21:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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