<p>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</p>

<p>$$f_\mathbb{s}(\mathbb{x}) = \mathbb{s} \cdot \mathbb{x}$$</p>

<p>(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,</p>

<p>$$\mathbb{s}'_i = \mathbb{s}_{i+1} - \mathbb{s}_i.$$</p>

<p>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.</p>

<p>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?</p>

<p>In other words, the algorithm task is as follows:</p>

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

<p>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).</p>

<p>Are there any techniques for this type of problem?</p>

CC BY-SA 3.0
2016-01-16T06:59:58.113Z
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. ( http://www.ecs.umass.edu/~mduarte/images/IDEA-ICASSP06.pdf ).If this serves your goal, I can write the above as a whole answer below.
Vivek Bagaria
CC BY-SA 3.0
2016-01-17T01:09:57.393Z
@bagaria, neat!  That sounds like it would be a great answer.  Thank you.
D.W.
<it.information-theory><lg.learning><query-complexity><approximation><compressed-sensing>
Estimate smooth vector, from dot-product queries
D.W.
# Estimate smooth vector, from dot-product queries

(Asked by: username_0 on 2016-01-14)

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?

**Tags:** it.information-theory, lg.learning, query-complexity, approximation, compressed-sensing
> **Comments:**
> **username_1**: 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. ( http://www.ecs.umass.edu/~mduarte/images/IDEA-ICASSP06.pdf ).If this serves your goal, I can write the above as a whole answer below.  
> **username_0**: @bagaria, neat!  That sounds like it would be a great answer.  Thank you.  

---

## 0 answers

