Let $f$ and $g$ be two discrete signals. I want to find a monotone function h such that
$h=argmin_{h}\sum_{n\in[0,N]}{(f(n)-h(g(n)))^2}$
I don't really care about finding the global optimum, I just want a good fit. What would be a good representation of f to achieve that? Thanks!
Here is another try:
Assume w.l.o.g. that values of $g(n)$ are in increasing order, i.e. $g(0) \le g(1) \le \cdots\le g(n)$. Moreover, assume the first $n_1$ values in that sequence are equal, then the next $n_2$ values are equal, etc. and that there are $m$ distinct values i.e. $$g(0)=g(1)=\cdots=g(n_1-1) < g(n_1)=\cdots=g(n_1+n_2-1) < \cdots < g(n_1+\cdots+n_{m-1}) + \cdots g(n_1+\cdots+n_m-1).$$We have to decide the following $m$ values of $h$: $$h_k = h(g(k)), \quad k=1,2,\ldots m$$
Say we are looking for an increasing $h$ (you can look for a decreasing $h$ in a similar way and take the best of the two solutions). Denote by $H_r(t)$ the value of the solution of the problem limited to the first $r$ groups, where $t$ is an additional upper bound $t$ on the values taken by $h$, i.e. $$H_r(t) = \min_{h_1 \le h_2 \le \cdots \le h_r \le t} \quad \sum_{k=1}^r \quad \sum_{i=n_1+\cdots+n_{r-1}}^{n_1+\cdots+n_r-1} (f(i) - h_k)^2$$
When $r=1$, the value of $H_1(t)$ can now be easily computed: it is easy to check that the optimal $h_1$ is equal to the average $\bar{f_1}=\frac{1}{n_1}(f(0)+f(1)+ \ldots+ f(n_1-1))$ if it is less than $t$, and to $t$ otherwise, and that $$H_1(t)=constant + n_1 (\min (t-\bar{f_1},0))^2 .$$From that we can successively compute the values of $H_2(t)$, $H_3(t)$, etc. and end up with the final solution when $r=n$, using the recurrence $$H_{r}(t) = \min_{s \le t}\ H_{r-1}(s) + constant + n_s(s-\bar{f_r})^2$$ (this is similar to dynamic programming).
Edit: the answer below ignores the monotonicity constraint, and refers to a previous version of the problem with $g(h(n))$ instead of $h(g(n))$
You problem is completely separable: for each $k$, choose the value of $h(k)$ such that $g(h(k))$ is as close as possible to $f(k)$, a decision that is independent from the values of $h(n)$ for all other $n \neq k$. Each of these choices is made by simple inspection of the possible values for $g$.
