# Perform matrix-vector multiplicacion using quadratic form

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

• 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. – tom Mar 6 '14 at 20:27
• 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 – user38568 Mar 6 '14 at 20:38

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

• 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. – user38568 Mar 6 '14 at 21:12
• 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)$ – tom Mar 6 '14 at 21:14