0
$\begingroup$

I am implementing an algorithm from a paper titled "Adaptive Multi-Trace Carving Based on Dynamic Programming." Specifically, this algorithm requires solving the following: $$ y[n] = \max_{k \in [0, N)} \{ x[k] \cdot h[n - k] \} $$ In this equation，x[n] and h[n] are known, and y[n] needs to be computed for n from 0 to N. This operation resembles convolution, except that it uses the MAX operation instead of SUM.

Is there any way to compute y[n] in O(NlogN) time complexity?

Any insights would be appreciated.

Improve this question
$\endgroup$
1
  • $\begingroup$ Taking logarithm turns this formula into an actual convolution in the max-plus tropical semiring. I'm not sure if it'd help to speed up things though. $\endgroup$
    – Max Alekseyev
    Commented Oct 29 at 15:19

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .