MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
what happens when say $f : v \mapsto \exp(v)$, that is, elementwise exponentiation? Also, is your matrix $T$ like a gradient of $f$? – Suvrit May 26 '11 at 13:08
I am assuming that f is close to a linear map, which rules out elementwise exponentiation. Presumably the derivative of f at any point is close to T, but (i) I am not assuming that f is differentiable, and (ii) even if it is, it is not entirely clear how this could be useful in my black box model. – – Roberto Imbuzeiro Oliveira May 26 '11 at 14:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.