10
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • $\begingroup$ Did you mean to ask "Are there arguments from complexity theory that should dampen my expectations?" twice? $\endgroup$
    – user5810
    Dec 21, 2010 at 10:45
  • 3
    $\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, 2010 at 10:53
  • 3
    $\begingroup$ *whistles* That's a lot of parameters for each basis function... $\endgroup$
    – J. M. isn't a mathematician
    Dec 21, 2010 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, 2010 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, 2010 at 17:46

3 Answers 3

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ I'm probably being dense, but exactly how does double-exponential quadrature figure into David's problem? $\endgroup$
    – J. M. isn't a mathematician
    Dec 21, 2010 at 11:26
  • $\begingroup$ "Do there exist good numerical techniques" $\endgroup$
    – user5810
    Dec 21, 2010 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. isn't a mathematician
    Dec 21, 2010 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, 2010 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, 2010 at 0:26
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks...you've got me reading Ben Green's Montreal notes now. $\endgroup$
    – David Feldman
    Dec 21, 2010 at 21:38
1
$\begingroup$

Please search the literature for Chirplets. I remember reading articles published in IEEE journals 15+ years ago that describe the following method: Given a function/signal $f$, first calculate the STFT of $f$, then isolate the visible line segments on the graph of the spectrogram by treshholding. There are different ways to isolate line segments, e.g., apply Ridgelet transform or Radon transform to the spectrogram. Each line segment corresponds to a chirp. Roughly speaking, the linear combination of the chirps with the $n$-highest coefficients gives a (nonlinear) $n$-term approximation to $f$.

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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