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

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

-
I think there may be some typos here as well as some ambiguous terminology: (1) you use "dimension" in two different senses within the very same statement (#1). (2) In statement 3 it looks like you want to estimate $f^{-1}$, not $f$. As far as properties of $f$ go, is there any possibility that $f(s)$ can be incorrectly evaluated? If not, this is not a statistical problem and it has a mathematical answer that is trivial to obtain. If so, what can you tell us about the nature of these errors? –  whuber Feb 23 '12 at 17:58
might be helpful: models.kvl.dk/~pih/parafac/chap2parafac.htm –  Dov Feb 23 '12 at 21:01
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.