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!



Finding an optimal monotone function?
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).


