Error analysis of approximating Fourier transforms
$begingroup$
Consider the problem of computing the Fourier transform of a function, $f(x).$ $$ hat{f}(k) = int_{-infty}^{infty} dx~ f(x)~ e^{i k x} .$$
Suppose I want to approximate this transform by a discrete, truncated version,
$$ hat{F}_{Delta, ~L}(k) = sum_{n = -L}^L Delta~ f(Delta n)~ e^{i k Delta n} .$$
I want the approximation to work with error $epsilon$ in some interval $[0, k_{max}]$,
$$sup_{k in [0, k_{max}]} ~| hat{f}(k) - hat{F}_{Delta, ~L}(k) | leq epsilon $$
What values of $Delta$, $L$ should I choose to achieve this error. The answer will obviously depend on the properties of $hat{f}(k)$, like how fast it decays. I have seen this done for specific functions but haven't seen any general rigorous result. Since this seems to be a problem with many practical applications it seems unlikely that no one has worked it out. Are there any rigorous results known for this general case ?
fourier-analysis fourier-transform approximation-theory approximate-integration
asked Jan 18 at 8:14
biryanibiryani
268413
$endgroup$
add a comment |
$begingroup$
Consider the problem of computing the Fourier transform of a function, $f(x).$ $$ hat{f}(k) = int_{-infty}^{infty} dx~ f(x)~ e^{i k x} .$$
Suppose I want to approximate this transform by a discrete, truncated version,
$$ hat{F}_{Delta, ~L}(k) = sum_{n = -L}^L Delta~ f(Delta n)~ e^{i k Delta n} .$$
I want the approximation to work with error $epsilon$ in some interval $[0, k_{max}]$,
$$sup_{k in [0, k_{max}]} ~| hat{f}(k) - hat{F}_{Delta, ~L}(k) | leq epsilon $$
What values of $Delta$, $L$ should I choose to achieve this error. The answer will obviously depend on the properties of $hat{f}(k)$, like how fast it decays. I have seen this done for specific functions but haven't seen any general rigorous result. Since this seems to be a problem with many practical applications it seems unlikely that no one has worked it out. Are there any rigorous results known for this general case ?
fourier-analysis fourier-transform approximation-theory approximate-integration
asked Jan 18 at 8:14
biryanibiryani
268413
$endgroup$
add a comment |
$begingroup$
Consider the problem of computing the Fourier transform of a function, $f(x).$ $$ hat{f}(k) = int_{-infty}^{infty} dx~ f(x)~ e^{i k x} .$$
Suppose I want to approximate this transform by a discrete, truncated version,
$$ hat{F}_{Delta, ~L}(k) = sum_{n = -L}^L Delta~ f(Delta n)~ e^{i k Delta n} .$$
I want the approximation to work with error $epsilon$ in some interval $[0, k_{max}]$,
$$sup_{k in [0, k_{max}]} ~| hat{f}(k) - hat{F}_{Delta, ~L}(k) | leq epsilon $$
What values of $Delta$, $L$ should I choose to achieve this error. The answer will obviously depend on the properties of $hat{f}(k)$, like how fast it decays. I have seen this done for specific functions but haven't seen any general rigorous result. Since this seems to be a problem with many practical applications it seems unlikely that no one has worked it out. Are there any rigorous results known for this general case ?
fourier-analysis fourier-transform approximation-theory approximate-integration
asked Jan 18 at 8:14
biryanibiryani
268413
$endgroup$
Consider the problem of computing the Fourier transform of a function, $f(x).$ $$ hat{f}(k) = int_{-infty}^{infty} dx~ f(x)~ e^{i k x} .$$
Suppose I want to approximate this transform by a discrete, truncated version,
$$ hat{F}_{Delta, ~L}(k) = sum_{n = -L}^L Delta~ f(Delta n)~ e^{i k Delta n} .$$
I want the approximation to work with error $epsilon$ in some interval $[0, k_{max}]$,
$$sup_{k in [0, k_{max}]} ~| hat{f}(k) - hat{F}_{Delta, ~L}(k) | leq epsilon $$
What values of $Delta$, $L$ should I choose to achieve this error. The answer will obviously depend on the properties of $hat{f}(k)$, like how fast it decays. I have seen this done for specific functions but haven't seen any general rigorous result. Since this seems to be a problem with many practical applications it seems unlikely that no one has worked it out. Are there any rigorous results known for this general case ?
fourier-analysis fourier-transform approximation-theory approximate-integration
fourier-analysis fourier-transform approximation-theory approximate-integration
asked Jan 18 at 8:14
biryanibiryani
268413
asked Jan 18 at 8:14
biryanibiryani
268413
asked Jan 18 at 8:14
biryanibiryani
268413
asked Jan 18 at 8:14
biryanibiryani
268413
asked Jan 18 at 8:14
biryanibiryani
268413
268413
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
If you assume that $f in L^1$, then approximations are not so terrible because $hat{f}$ is uniformly continuous, with $|hat{f}|_{infty}le |f|_{1}$. So, for $epsilon > 0$, there exists $R > 0$ large enough such that
$$
left|hat{f}(k)-frac{1}{sqrt{2pi}}int_{-R}^{R}f(x)e^{-ikx}dxright| \
le frac{1}{sqrt{2pi}}int_{|u|ge R}|f(u)|du < frac{epsilon}{2},;;; kinmathbb{R}.
$$
So the Fourier transform is uniformly approximated by the truncated Fourier series integral on $[-R,R]$. Then you can approximate the Fourier integral over $[-R,R]$ by a discrete sum
$$
hat{f}(k)approxsum_{n=-N}^{N-1}frac{1}{sqrt{2pi}}int_{Rn/N}^{R(n+1)/N}f(x)dxe^{-ikRn/N}.
$$
I'm not sure if that's the type of approximation you want or not.
answered Jan 20 at 0:38
DisintegratingByPartsDisintegratingByParts
60.5k42681
$endgroup$
$begingroup$
So you assume $f$ is continuous ($f(x)=e^{-x^2}(1 - 1_{xin mathbb{Q}})$)
$endgroup$
– reuns
Jan 20 at 2:24
$begingroup$
This is the kind of approximation I use. The question is how does $epsilon$ depend on $R$ and $N$.
$endgroup$
– biryani
Jan 21 at 10:39
add a comment |
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3077962%2ferror-analysis-of-approximating-fourier-transforms%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
If you assume that $f in L^1$, then approximations are not so terrible because $hat{f}$ is uniformly continuous, with $|hat{f}|_{infty}le |f|_{1}$. So, for $epsilon > 0$, there exists $R > 0$ large enough such that
$$
left|hat{f}(k)-frac{1}{sqrt{2pi}}int_{-R}^{R}f(x)e^{-ikx}dxright| \
le frac{1}{sqrt{2pi}}int_{|u|ge R}|f(u)|du < frac{epsilon}{2},;;; kinmathbb{R}.
$$
So the Fourier transform is uniformly approximated by the truncated Fourier series integral on $[-R,R]$. Then you can approximate the Fourier integral over $[-R,R]$ by a discrete sum
$$
hat{f}(k)approxsum_{n=-N}^{N-1}frac{1}{sqrt{2pi}}int_{Rn/N}^{R(n+1)/N}f(x)dxe^{-ikRn/N}.
$$
I'm not sure if that's the type of approximation you want or not.
answered Jan 20 at 0:38
DisintegratingByPartsDisintegratingByParts
60.5k42681
$endgroup$
$begingroup$
So you assume $f$ is continuous ($f(x)=e^{-x^2}(1 - 1_{xin mathbb{Q}})$)
$endgroup$
– reuns
Jan 20 at 2:24
$begingroup$
This is the kind of approximation I use. The question is how does $epsilon$ depend on $R$ and $N$.
$endgroup$
– biryani
Jan 21 at 10:39
add a comment |
$begingroup$
If you assume that $f in L^1$, then approximations are not so terrible because $hat{f}$ is uniformly continuous, with $|hat{f}|_{infty}le |f|_{1}$. So, for $epsilon > 0$, there exists $R > 0$ large enough such that
$$
left|hat{f}(k)-frac{1}{sqrt{2pi}}int_{-R}^{R}f(x)e^{-ikx}dxright| \
le frac{1}{sqrt{2pi}}int_{|u|ge R}|f(u)|du < frac{epsilon}{2},;;; kinmathbb{R}.
$$
So the Fourier transform is uniformly approximated by the truncated Fourier series integral on $[-R,R]$. Then you can approximate the Fourier integral over $[-R,R]$ by a discrete sum
$$
hat{f}(k)approxsum_{n=-N}^{N-1}frac{1}{sqrt{2pi}}int_{Rn/N}^{R(n+1)/N}f(x)dxe^{-ikRn/N}.
$$
I'm not sure if that's the type of approximation you want or not.
answered Jan 20 at 0:38
DisintegratingByPartsDisintegratingByParts
60.5k42681
$endgroup$
$begingroup$
So you assume $f$ is continuous ($f(x)=e^{-x^2}(1 - 1_{xin mathbb{Q}})$)
$endgroup$
– reuns
Jan 20 at 2:24
$begingroup$
This is the kind of approximation I use. The question is how does $epsilon$ depend on $R$ and $N$.
$endgroup$
– biryani
Jan 21 at 10:39
add a comment |
$begingroup$
If you assume that $f in L^1$, then approximations are not so terrible because $hat{f}$ is uniformly continuous, with $|hat{f}|_{infty}le |f|_{1}$. So, for $epsilon > 0$, there exists $R > 0$ large enough such that
$$
left|hat{f}(k)-frac{1}{sqrt{2pi}}int_{-R}^{R}f(x)e^{-ikx}dxright| \
le frac{1}{sqrt{2pi}}int_{|u|ge R}|f(u)|du < frac{epsilon}{2},;;; kinmathbb{R}.
$$
So the Fourier transform is uniformly approximated by the truncated Fourier series integral on $[-R,R]$. Then you can approximate the Fourier integral over $[-R,R]$ by a discrete sum
$$
hat{f}(k)approxsum_{n=-N}^{N-1}frac{1}{sqrt{2pi}}int_{Rn/N}^{R(n+1)/N}f(x)dxe^{-ikRn/N}.
$$
I'm not sure if that's the type of approximation you want or not.
answered Jan 20 at 0:38
DisintegratingByPartsDisintegratingByParts
60.5k42681
$endgroup$
If you assume that $f in L^1$, then approximations are not so terrible because $hat{f}$ is uniformly continuous, with $|hat{f}|_{infty}le |f|_{1}$. So, for $epsilon > 0$, there exists $R > 0$ large enough such that
$$
left|hat{f}(k)-frac{1}{sqrt{2pi}}int_{-R}^{R}f(x)e^{-ikx}dxright| \
le frac{1}{sqrt{2pi}}int_{|u|ge R}|f(u)|du < frac{epsilon}{2},;;; kinmathbb{R}.
$$
So the Fourier transform is uniformly approximated by the truncated Fourier series integral on $[-R,R]$. Then you can approximate the Fourier integral over $[-R,R]$ by a discrete sum
$$
hat{f}(k)approxsum_{n=-N}^{N-1}frac{1}{sqrt{2pi}}int_{Rn/N}^{R(n+1)/N}f(x)dxe^{-ikRn/N}.
$$
I'm not sure if that's the type of approximation you want or not.
answered Jan 20 at 0:38
DisintegratingByPartsDisintegratingByParts
60.5k42681
answered Jan 20 at 0:38
DisintegratingByPartsDisintegratingByParts
60.5k42681
answered Jan 20 at 0:38
DisintegratingByPartsDisintegratingByParts
60.5k42681
answered Jan 20 at 0:38
DisintegratingByPartsDisintegratingByParts
60.5k42681
60.5k42681
$begingroup$
So you assume $f$ is continuous ($f(x)=e^{-x^2}(1 - 1_{xin mathbb{Q}})$)
$endgroup$
– reuns
Jan 20 at 2:24
$begingroup$
This is the kind of approximation I use. The question is how does $epsilon$ depend on $R$ and $N$.
$endgroup$
– biryani
Jan 21 at 10:39
add a comment |
$begingroup$
So you assume $f$ is continuous ($f(x)=e^{-x^2}(1 - 1_{xin mathbb{Q}})$)
$endgroup$
– reuns
Jan 20 at 2:24
$begingroup$
This is the kind of approximation I use. The question is how does $epsilon$ depend on $R$ and $N$.
$endgroup$
– biryani
Jan 21 at 10:39
$begingroup$
So you assume $f$ is continuous ($f(x)=e^{-x^2}(1 - 1_{xin mathbb{Q}})$)
$endgroup$
– reuns
Jan 20 at 2:24
$begingroup$
So you assume $f$ is continuous ($f(x)=e^{-x^2}(1 - 1_{xin mathbb{Q}})$)
$endgroup$
– reuns
Jan 20 at 2:24
$begingroup$
This is the kind of approximation I use. The question is how does $epsilon$ depend on $R$ and $N$.
$endgroup$
– biryani
Jan 21 at 10:39
$begingroup$
This is the kind of approximation I use. The question is how does $epsilon$ depend on $R$ and $N$.
$endgroup$
– biryani
Jan 21 at 10:39
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3077962%2ferror-analysis-of-approximating-fourier-transforms%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
