Call a function of the following form a beep: $e^{-(\frac{x-\alpha}{\beta})^2}\sin(\rho x+\theta)$. Given a real-valued function $f\in L^2(R)$ and a number $n$, I'm interested in the approximating $f$ as closely as possible by a linear combination of $n$ beeps.

Does this particular type of non-linear regression problem have a literature?

Do there exist good numerical techniques (perhaps after relaxing "best possible" in some controlled way) for solving this fitting problem?

Improving an approximation sufficiently near the optimal one seems relatively straightforward, but first getting near the optimal approximation seems to involve some manner of combinatorial search. Are there arguments from complexity theory that should dampen my expectations?

Are there theoretical results concerning how the error should vary with $n$ (perhaps with $f$ subject to some hypothesis, e.g. compact support or smoothness)?

Does the self-dual nature of the problem help in any way?

Finally, I'm interested in anything I can learn along these lines, so feel free to tell me if you think I haven't quite asked the right question.

  • $\begingroup$ Did you mean to ask "Are there arguments from complexity theory that should dampen my expectations?" twice? $\endgroup$ – user5810 Dec 21 '10 at 10:45
  • 2
    $\begingroup$ Sorry if I missed the obvious, but what is the significant difference to usual Wavelet analysis? Isn't your beep a variant of a windowed Fourier transform with a Gaussian window? $\endgroup$ – Tim van Beek Dec 21 '10 at 10:53
  • 2
    $\begingroup$ *whistles* That's a lot of parameters for each basis function... $\endgroup$ – J. M. is not a mathematician Dec 21 '10 at 11:28
  • 1
    $\begingroup$ If you want some info on the theoretical side, the keyword is 'wave packet' and what you are looking for is a 'wave packet decomposition' $\endgroup$ – Piero D'Ancona Dec 21 '10 at 14:24
  • 1
    $\begingroup$ @Ricky Fixed now, thanks. @Tim I'm just a pure mathematician who's wandered into this, so I crave your patience (of you all). But it seems to me that wavelet analysis is great if I first pick a linearly independent set of beeps and then I want to know the best coefficients. That's a linear problem. I don't see how wavelet analysis helps me pick the beeps to solve my non-linear optimization problem. @Piero Thanks for keywords, they help immensely. $\endgroup$ – David Feldman Dec 21 '10 at 17:46

Yes, http://en.wikipedia.org/wiki/Matching_pursuit#References

Yes, http://en.wikipedia.org/wiki/Tanh-sinh_quadrature

No, I don't think so.

Yes, http://en.wikipedia.org/wiki/Matching_pursuit#Properties

Yes, it gives an inner product.

No, I don't think so.

  • $\begingroup$ I'm probably being dense, but exactly how does double-exponential quadrature figure into David's problem? $\endgroup$ – J. M. is not a mathematician Dec 21 '10 at 11:26
  • $\begingroup$ "Do there exist good numerical techniques" $\endgroup$ – user5810 Dec 21 '10 at 11:40
  • $\begingroup$ Well, yes; his is a fitting problem, while DE solves the problem of approximately integrating an improper integral. $\endgroup$ – J. M. is not a mathematician Dec 21 '10 at 12:20
  • $\begingroup$ I gather from this exchange that tanh-sinh was meant merely as joke at the expense of my ellipsis, now eliminated. Ah, MO humor. Or am I missing something? Thanks for the pointer to matching pursuit, another keyword that I didn't have before! $\endgroup$ – David Feldman Dec 21 '10 at 17:53
  • $\begingroup$ tanh-sinh is the in general most accurate way to compute the inner products for the type of matching pursuit I'm recommending. $\endgroup$ – user5810 Dec 22 '10 at 0:26

It may not help you, but I would recommend typing "quadratic Fourier analysis" into Google. That will give you links to a number of discussions of what is quite a big theme in additive combinatorics. However, the flavour of the problem on the real line is fairly different, so I don't think the results in additive combinatorics will directly answer the questions you have -- but they might just suggest one or two ideas.

  • $\begingroup$ Thanks...you've got me reading Ben Green's Montreal notes now. $\endgroup$ – David Feldman Dec 21 '10 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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