The problem described here is algorithmic. We are given "black box access" to a map $f:R^d\to R^d$. By this we mean that one may query the value of $f(v)$ for an arbitrary $v\in R^d$.
We assume that there is a symmetric $d\times d$ matrix $T$ with spectral norm $\|T\|_{\rm sp}\leq 1$ such that: $$\forall v\in R^d : |Tv - f(v)|\leq \epsilon|v|,$$ where $|\cdot|$ denotes the Euclidean norm.
Problem: Given $k\in N$, find a $C=C(d,k,\epsilon)$ that is as small as possible such that the following holds. There exists an efficient algorithm that queries the values of $f(v)$ for at most $k$ different vectors and outputs a symmetric matrix $S$ with $$\|S-T\|_{sp}\leq C\epsilon.$$
Ideally, I would like $C>0$ to be independent of $d$.
Inneficient solution with $k\gg 2^d$ and $C\approx 1$: Let ${SYM}_d $ be the vector space consisting of all $d\times d$ symmetric matrices. Notice that:
$$T \in \bigcap_{w,v\in S^{d-1}}(S\in SYM_d : {\langle w,Tv\rangle\in [\langle w,f(v)\rangle-\epsilon,\langle w,f(v)\rangle+\epsilon]})$$ where $S^{d-1}$ is the ($d-1$)-dimensional sphere and $\langle \cdot,\cdot\cdot\rangle$ is the standard inner product. By replacing the sphere with a fine enough finite mesh, one may approximate the above intersection by a polytope in $SYM_d$ with diameter $\leq 2 \epsilon$ where $T$ lies. Any matrix $S$ in that polytope satisfies $\|T-S\|_{\rm sp}\leq 2\epsilon$.
Efficient solution with $C=d$. Compute $f(e_i)$ for each vector in the canonical basis. Let $S$ map $e_i$ to $f(e_i)$. Let $S_0$ map $e_i$ to $f(e_i)$; this is $d\epsilon$-close to $T$. Now take $S = (S_0 + S_0^*)/2$.
Can one do better? I am guessing this might be a known problem, but I could not find any references.
