Estimating a linear function mapping from n-dim to 1-dim [closed]

Question

I'm coming from a computer science domain with an estimation problem that I'm trying to address. My background isn't statistics, so I apologize if the terminology is bad.

I've been reading various topics related to model estimation, but the area seems enormous. So, I'll describe the problem below, and it would be extremely helpful to get pointers to specific areas that are relevant to avoid wading through dozens more wikipedia pages :).

1. Consider a $d$-dimensional space $S$ with dimensions $N_1 \times N_2 \times \dots \times N_d$. Any point $s \in S$ is specified by a tuple $(n_1, n_2, \dots, n_d)$ with $d$ zero-based indices $n_k \in [0, N_k-1]$.

2. There exists a 1-1 function $f: S \rightarrow \mathbb{N}$ that maps a multi-dimensional point in $S$ to a single natural number.

3. The problem I am trying to approach is related to estimating $f$, that is: given $S$, the range of $f(S)$, and $p \in f(S)$, estimate the point $s \in S$ such that $f(s)=p$.

4. (edit): I forgot to mention: The space can be probed to construct a training set. That is, training data can be acquired by evaluating $f(s)$. However, computing $f(s)$ is very expensive, so the goal is to estimate $f$ with as few evaluations as possible.

So, in the end the goal is to estimate the inverse of $f$. There are some assumptions about $f$, perhaps the most important is that it is linear. There are other properties, too, if they might be relevant please ask.

Thanks! Noah

Answer 1

One relevant area is principal components analysis. It only applies if $f$ is linear, but from what you say this is the case. The first principal component might be just what you want.

@whuber asks good questions in his comments. You need to think through at some point what statistical variation there is in $S$ and how to incorporate that into your model when you look at different candidates for $f$, but I suspect something along the lines of PCA and the literature around it will get you in the right direction.