3
$\begingroup$

I have a secret $n$-dimensional vector $\mathbb{s} \in \mathbb{Z}^n$. I don't know $\mathbb{s}$; my goal is to estimate $\mathbb{s}$. I do have an oracle for the function $f_\mathbb{s} : \mathbb{Z}^n \to \mathbb{Z}$, defined by

$$f_\mathbb{s}(\mathbb{x}) = \mathbb{s} \cdot \mathbb{x}$$

(the dot-product of $\mathbb{s}$ and $\mathbb{x}$). Also, I know that $\mathbb{s}$ is smooth, in some sense: $\mathbb{s}_i$ varies slowly as a function of $i$. I'm open to reasonable ways to formalize that, but one formulation is that we can assume that $||\mathbb{s}'||_2$ is very small, where $\mathbb{s}'$ is the vector of first-order discrete derivatives, namely,

$$\mathbb{s}'_i = \mathbb{s}_{i+1} - \mathbb{s}_i.$$

The goal is to estimate/approximate $\mathbb{s}$: i.e., to output a vector $\mathbb{t}$ such that $||\mathbb{t}-\mathbb{s}||_2$ is small.

One can recover $\mathbb{s}$ exactly given $n$ queries to $f$, by using linear algebra (even without needing the smoothness constraint). But given knowledge that $\mathbb{s}$ is smooth, is there a more efficient way to estimate $\mathbb{s}$, using fewer queries?

In other words, the algorithm task is as follows:

Input: $n$, an oracle for $f_\mathbb{s}$, an upper bound on $||\mathbb{s}'||_2$
Output: $t \in \mathbb{Z}^n$ such that $||\mathbb{t}-\mathbb{s}||_2$ is small

In my application, $n$ is large (say, around 10,000) but $\mathbb{s}$ is very smooth, so I'm hoping it might be possible to estimate $\mathbb{s}$ with many fewer than $n$ queries. It would be fine to assume we are working over $\mathbb{R}^n$ if that's easier. In practice I have $\mathbb{s} \in \{0,1,\dots,255\}^n$. I'm not wedded to this exact definition of smoothness or of approximation of $\mathbb{s}$ (e.g., some sparsity constraint or other norm might also be a reasonable formulation).

Are there any techniques for this type of problem?

$\endgroup$
  • 3
    $\begingroup$ Well, there's the trivial approach of "divide the domain into regions and assume s is constant on each region". ​ That can probably be improved by at the end, dropping that assumption and using some interpolation method. ​ ​ $\endgroup$ – user6973 Jan 14 '16 at 22:17
  • $\begingroup$ Fourier series of 'smooth' function is 'sparse'. Let the fourier series be given by $f = \mathcal{F}s$ ($\mathcal{F}$ the fourier matrix). A oracle on $f$ can be easily maped to a oracle on $s$ (Using $\mathcal{F}$). Since $f$ is sparse, one could use many available techniques in the area of compressed sensing to obtain the sparse signal back. ( ecs.umass.edu/~mduarte/images/IDEA-ICASSP06.pdf ).If this serves your goal, I can write the above as a whole answer below. $\endgroup$ – Vivek Bagaria Jan 16 '16 at 6:59
  • $\begingroup$ @bagaria, neat! That sounds like it would be a great answer. Thank you. $\endgroup$ – D.W. Jan 17 '16 at 1:09

Your Answer

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

Browse other questions tagged or ask your own question.