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

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.

share|improve this question
    
Did you mean to ask "Are there arguments from complexity theory that should dampen my expectations?" twice? –  Ricky Demer Dec 21 '10 at 10:45
2  
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? –  Tim van Beek Dec 21 '10 at 10:53
2  
*whistles* That's a lot of parameters for each basis function... –  J. M. Dec 21 '10 at 11:28
1  
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' –  Piero D'Ancona Dec 21 '10 at 14:24
1  
@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. –  David Feldman Dec 21 '10 at 17:46

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
I'm probably being dense, but exactly how does double-exponential quadrature figure into David's problem? –  J. M. Dec 21 '10 at 11:26
    
"Do there exist good numerical techniques" –  Ricky Demer Dec 21 '10 at 11:40
    
Well, yes; his is a fitting problem, while DE solves the problem of approximately integrating an improper integral. –  J. M. Dec 21 '10 at 12:20
    
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! –  David Feldman Dec 21 '10 at 17:53
    
tanh-sinh is the in general most accurate way to compute the inner products for the type of matching pursuit I'm recommending. –  Ricky Demer 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.

share|improve this answer
    
Thanks...you've got me reading Ben Green's Montreal notes now. –  David Feldman Dec 21 '10 at 21:38

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.