Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
add comment

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
Very neat! Thanks a lot. –  Grönwall Sep 14 '10 at 11:33
add comment

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$.

share|improve this answer
1  
Did you read that Grönwall is looking for a monotone function h. –  Someone Sep 10 '10 at 12:14
    
As if there existed any monotone functions from $[1,N]$ to $[1,N]$ other than $x$ and $N+1-x$. Certainly, something else was meant (say, $g(h)$ should really be $h(g)$), but I'm too lazy to strain my mind-reading abilities. –  fedja Sep 10 '10 at 12:34
    
Sorry about the typo. –  Grönwall Sep 10 '10 at 12:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.