What is the name of this Knapsack-like problem?

Question

I am looking for the name of the following problem:

Imagine having a function $f(t)$, which basically resembles the maximum weight from the Knapsack problem for each t (although for what I try to do I just want to be close to f(t) don't have to stay below). Now I have a set of other functions $g_i(t)$, which are basically the items I would like to store in my backpack. With my $g_i(t)$ I would like to come as close to $f(t)$ as possible at each time t and I can shift my $g_i(t)$ along the x-axis. I tried to come up with a problem formulation:

$$min \space \space z = \mid\int_a^b f(t) - \sum_{i=1}^n g_i^{'}(t) x_i\,dt \mid$$

$x_i \in \{0, 1\}$, I think those are not really necessary as I could also choose $\tau_i > b$ instead of $x_i = 0$
$g_i^{'} = g_i(t-\tau_i)$, here $\tau_i$ is the shift on the x-axis. \

I don't need a solution for the problem, I just can't find its name and hence no literature to refer to. So if anyone knows a name or sth that is close I would really appreciate some hints.

Thank you very much

Answer 1

If you want to be as close to $f$ as possible, you should probably minimize $\int |f(t) - \sum_i g_i(t-\tau_i)| dt $, or for technical ease, $$I(\{\tau_i, \cdots ,\tau_n\})=\int |f(t) - \sum_i g_i(t-\tau_i)|^2 dt $$ I will treat the question as if this is what you meant. If not, please let me know and I will erase this answer. Also, note that you can extend the integration bounds to $[-\infty, \infty]$ without limiting the generality.

This now becomes a minimization problem in $\{\tau_1,\cdots ,\tau_n\}$, that is you are looking for a specific set of $\{\tau^{*}_1,\cdots ,\tau^{*}_n\}$ that minimize $I$, i.e. ${\partial I \over \partial \tau_i} =0 $ And can be solved numerically by a variety of methods, e.g. Gradient Descent. For a useful representation, I suggest using the spectral theorem to rewrite the problem in frequency space, noting that Parseval's theorem gives us: $$ I=\int \mathcal{F}(f(t) - \sum_i g_i(t-\tau_i)) \mathcal{F}(f(t) - \sum_i g_i(t-\tau_i))^* d\omega$$ The beauty of this is that to Fourier transform a time shifted function, just multiply by a phase, hence: $$\mathcal{F}(f(t) - \sum_i g_i(t-\tau_i)) = \hat f - \sum_i e^{i\omega \tau_i}\hat g_i$$ and now $$I= \int (\hat f - \sum_i e^{i\omega \tau_i}\hat g_i)(\hat f^* - \sum_i e^{-i\omega \tau_i}\hat g^*_i)d\omega $$ or $$I= \int (\hat f \hat f^* - \sum_i e^{i\omega \tau_i}\hat g_i \hat f ^* - \sum_i e^{-i\omega \tau_i}\hat g^{*}_i \hat f + \sum_{ij} e^{i \omega (\tau_i -\tau_j)} \hat g_j \hat g^{*}_i)d\omega $$ Where the $\tau_i$ dependence is explicit.