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