Duality of the convolution theorem in Fourier Domain
$begingroup$
Convolution in the time domain can be represented as a Hadamard (pointwise) product in the Frequency domain. Using the instructions specified at
https://in.mathworks.com/matlabcentral/answers/38066-difference-between-conv-ifft-fft-when-doing-convolution
I am able to obtain a convolution between two vectors both in the time and frequency domain. Now, I would like to do the reverse operation.
Suppose (Using Matlab/Octave notation)
$a=[1, 2, 3, 4]$ and $b=[7, 5, 3, 1]$; Then
$c = a.*b = [7, 10, 6, 4]$.
If I take a Fourier transform of this vector, I obtain
$c_{fft} = [34 + 0i, -2 - 2i, -2 + 0i, -2 + 2i]$.
Now, If I apply the duality property of convolution,
$c_{fft} = conv(FFT(a),FFT(b))$ should be true (as Hadamard multiplication in time domain is equivalent to convolution in Fourier domain). However, when I implement the same, I get the following:
$c_{fft} = [224 + 0i, 24 + 40i, -24 + 32i, -8 + 8i, -88 + 0i, -32 - 48i, 16 - 32i]$
Am I doing something wrong here? Help from domain specialists would be greatly appreciated.
fourier-transform hadamard-product
asked Jan 6 at 12:30
user3351526user3351526
11
$endgroup$
add a comment |
$begingroup$
Convolution in the time domain can be represented as a Hadamard (pointwise) product in the Frequency domain. Using the instructions specified at
https://in.mathworks.com/matlabcentral/answers/38066-difference-between-conv-ifft-fft-when-doing-convolution
I am able to obtain a convolution between two vectors both in the time and frequency domain. Now, I would like to do the reverse operation.
Suppose (Using Matlab/Octave notation)
$a=[1, 2, 3, 4]$ and $b=[7, 5, 3, 1]$; Then
$c = a.*b = [7, 10, 6, 4]$.
If I take a Fourier transform of this vector, I obtain
$c_{fft} = [34 + 0i, -2 - 2i, -2 + 0i, -2 + 2i]$.
Now, If I apply the duality property of convolution,
$c_{fft} = conv(FFT(a),FFT(b))$ should be true (as Hadamard multiplication in time domain is equivalent to convolution in Fourier domain). However, when I implement the same, I get the following:
$c_{fft} = [224 + 0i, 24 + 40i, -24 + 32i, -8 + 8i, -88 + 0i, -32 - 48i, 16 - 32i]$
Am I doing something wrong here? Help from domain specialists would be greatly appreciated.
fourier-transform hadamard-product
asked Jan 6 at 12:30
user3351526user3351526
11
$endgroup$
$begingroup$
The DFT implements cyclic convolution, not linear convolution. You need a minimum amount of zero padding for cyclic convolution to coincide with linear convolution. See chapter 9 of Orfanidis' book for details: ece.rutgers.edu/~orfanidi/intro2sp
$endgroup$
– Andy Walls
Jan 6 at 14:22
$begingroup$
Andy, that's why I added the link in my post indicating that fact. Using zero padding I am able to get the forward and inverse steps for convolution (in the time domain). Can you please share your thoughts as to how I would have to zero pad when doing the operations indicated above.
$endgroup$
– user3351526
Jan 6 at 18:49
$begingroup$
Well, your first $c_{fft}$ represents a cyclic convolution in the discrete frequency domain. No amount of zero padding added to $a$ and $b$ will change that as their FFTs will be non-zero in almost every bin. So, then for the other operations, your linear convolution of FFT(a) and FFT(b) will not match the circular convolution. Using the 'cconv()' function in MatLab, the circular convolution should come out properly though.
$endgroup$
– Andy Walls
Jan 6 at 23:22
$begingroup$
Andy, unfortunately I don't have Matlab. I was hoping a simple step-by-step explanation would be helpful not only for me but for others who may come here for this.
$endgroup$
– user3351526
Jan 7 at 11:06
add a comment |
$begingroup$
Convolution in the time domain can be represented as a Hadamard (pointwise) product in the Frequency domain. Using the instructions specified at
https://in.mathworks.com/matlabcentral/answers/38066-difference-between-conv-ifft-fft-when-doing-convolution
I am able to obtain a convolution between two vectors both in the time and frequency domain. Now, I would like to do the reverse operation.
Suppose (Using Matlab/Octave notation)
$a=[1, 2, 3, 4]$ and $b=[7, 5, 3, 1]$; Then
$c = a.*b = [7, 10, 6, 4]$.
If I take a Fourier transform of this vector, I obtain
$c_{fft} = [34 + 0i, -2 - 2i, -2 + 0i, -2 + 2i]$.
Now, If I apply the duality property of convolution,
$c_{fft} = conv(FFT(a),FFT(b))$ should be true (as Hadamard multiplication in time domain is equivalent to convolution in Fourier domain). However, when I implement the same, I get the following:
$c_{fft} = [224 + 0i, 24 + 40i, -24 + 32i, -8 + 8i, -88 + 0i, -32 - 48i, 16 - 32i]$
Am I doing something wrong here? Help from domain specialists would be greatly appreciated.
fourier-transform hadamard-product
asked Jan 6 at 12:30
user3351526user3351526
11
$endgroup$
Convolution in the time domain can be represented as a Hadamard (pointwise) product in the Frequency domain. Using the instructions specified at
https://in.mathworks.com/matlabcentral/answers/38066-difference-between-conv-ifft-fft-when-doing-convolution
I am able to obtain a convolution between two vectors both in the time and frequency domain. Now, I would like to do the reverse operation.
Suppose (Using Matlab/Octave notation)
$a=[1, 2, 3, 4]$ and $b=[7, 5, 3, 1]$; Then
$c = a.*b = [7, 10, 6, 4]$.
If I take a Fourier transform of this vector, I obtain
$c_{fft} = [34 + 0i, -2 - 2i, -2 + 0i, -2 + 2i]$.
Now, If I apply the duality property of convolution,
$c_{fft} = conv(FFT(a),FFT(b))$ should be true (as Hadamard multiplication in time domain is equivalent to convolution in Fourier domain). However, when I implement the same, I get the following:
$c_{fft} = [224 + 0i, 24 + 40i, -24 + 32i, -8 + 8i, -88 + 0i, -32 - 48i, 16 - 32i]$
Am I doing something wrong here? Help from domain specialists would be greatly appreciated.
fourier-transform hadamard-product
fourier-transform hadamard-product
asked Jan 6 at 12:30
user3351526user3351526
11
asked Jan 6 at 12:30
user3351526user3351526
11
asked Jan 6 at 12:30
user3351526user3351526
11
asked Jan 6 at 12:30
user3351526user3351526
11
asked Jan 6 at 12:30
user3351526user3351526
11
11
$begingroup$
The DFT implements cyclic convolution, not linear convolution. You need a minimum amount of zero padding for cyclic convolution to coincide with linear convolution. See chapter 9 of Orfanidis' book for details: ece.rutgers.edu/~orfanidi/intro2sp
$endgroup$
– Andy Walls
Jan 6 at 14:22
$begingroup$
Andy, that's why I added the link in my post indicating that fact. Using zero padding I am able to get the forward and inverse steps for convolution (in the time domain). Can you please share your thoughts as to how I would have to zero pad when doing the operations indicated above.
$endgroup$
– user3351526
Jan 6 at 18:49
$begingroup$
Well, your first $c_{fft}$ represents a cyclic convolution in the discrete frequency domain. No amount of zero padding added to $a$ and $b$ will change that as their FFTs will be non-zero in almost every bin. So, then for the other operations, your linear convolution of FFT(a) and FFT(b) will not match the circular convolution. Using the 'cconv()' function in MatLab, the circular convolution should come out properly though.
$endgroup$
– Andy Walls
Jan 6 at 23:22
$begingroup$
Andy, unfortunately I don't have Matlab. I was hoping a simple step-by-step explanation would be helpful not only for me but for others who may come here for this.
$endgroup$
– user3351526
Jan 7 at 11:06
add a comment |
$begingroup$
The DFT implements cyclic convolution, not linear convolution. You need a minimum amount of zero padding for cyclic convolution to coincide with linear convolution. See chapter 9 of Orfanidis' book for details: ece.rutgers.edu/~orfanidi/intro2sp
$endgroup$
– Andy Walls
Jan 6 at 14:22
$begingroup$
Andy, that's why I added the link in my post indicating that fact. Using zero padding I am able to get the forward and inverse steps for convolution (in the time domain). Can you please share your thoughts as to how I would have to zero pad when doing the operations indicated above.
$endgroup$
– user3351526
Jan 6 at 18:49
$begingroup$
Well, your first $c_{fft}$ represents a cyclic convolution in the discrete frequency domain. No amount of zero padding added to $a$ and $b$ will change that as their FFTs will be non-zero in almost every bin. So, then for the other operations, your linear convolution of FFT(a) and FFT(b) will not match the circular convolution. Using the 'cconv()' function in MatLab, the circular convolution should come out properly though.
$endgroup$
– Andy Walls
Jan 6 at 23:22
$begingroup$
Andy, unfortunately I don't have Matlab. I was hoping a simple step-by-step explanation would be helpful not only for me but for others who may come here for this.
$endgroup$
– user3351526
Jan 7 at 11:06
$begingroup$
The DFT implements cyclic convolution, not linear convolution. You need a minimum amount of zero padding for cyclic convolution to coincide with linear convolution. See chapter 9 of Orfanidis' book for details: ece.rutgers.edu/~orfanidi/intro2sp
$endgroup$
– Andy Walls
Jan 6 at 14:22
$begingroup$
The DFT implements cyclic convolution, not linear convolution. You need a minimum amount of zero padding for cyclic convolution to coincide with linear convolution. See chapter 9 of Orfanidis' book for details: ece.rutgers.edu/~orfanidi/intro2sp
$endgroup$
– Andy Walls
Jan 6 at 14:22
$begingroup$
Andy, that's why I added the link in my post indicating that fact. Using zero padding I am able to get the forward and inverse steps for convolution (in the time domain). Can you please share your thoughts as to how I would have to zero pad when doing the operations indicated above.
$endgroup$
– user3351526
Jan 6 at 18:49
$begingroup$
Andy, that's why I added the link in my post indicating that fact. Using zero padding I am able to get the forward and inverse steps for convolution (in the time domain). Can you please share your thoughts as to how I would have to zero pad when doing the operations indicated above.
$endgroup$
– user3351526
Jan 6 at 18:49
$begingroup$
Well, your first $c_{fft}$ represents a cyclic convolution in the discrete frequency domain. No amount of zero padding added to $a$ and $b$ will change that as their FFTs will be non-zero in almost every bin. So, then for the other operations, your linear convolution of FFT(a) and FFT(b) will not match the circular convolution. Using the 'cconv()' function in MatLab, the circular convolution should come out properly though.
$endgroup$
– Andy Walls
Jan 6 at 23:22
$begingroup$
Well, your first $c_{fft}$ represents a cyclic convolution in the discrete frequency domain. No amount of zero padding added to $a$ and $b$ will change that as their FFTs will be non-zero in almost every bin. So, then for the other operations, your linear convolution of FFT(a) and FFT(b) will not match the circular convolution. Using the 'cconv()' function in MatLab, the circular convolution should come out properly though.
$endgroup$
– Andy Walls
Jan 6 at 23:22
$begingroup$
Andy, unfortunately I don't have Matlab. I was hoping a simple step-by-step explanation would be helpful not only for me but for others who may come here for this.
$endgroup$
– user3351526
Jan 7 at 11:06
$begingroup$
Andy, unfortunately I don't have Matlab. I was hoping a simple step-by-step explanation would be helpful not only for me but for others who may come here for this.
$endgroup$
– user3351526
Jan 7 at 11:06
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
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%2f3063801%2fduality-of-the-convolution-theorem-in-fourier-domain%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3063801%2fduality-of-the-convolution-theorem-in-fourier-domain%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
$begingroup$
The DFT implements cyclic convolution, not linear convolution. You need a minimum amount of zero padding for cyclic convolution to coincide with linear convolution. See chapter 9 of Orfanidis' book for details: ece.rutgers.edu/~orfanidi/intro2sp
$endgroup$
– Andy Walls
Jan 6 at 14:22
$begingroup$
Andy, that's why I added the link in my post indicating that fact. Using zero padding I am able to get the forward and inverse steps for convolution (in the time domain). Can you please share your thoughts as to how I would have to zero pad when doing the operations indicated above.
$endgroup$
– user3351526
Jan 6 at 18:49
$begingroup$
Well, your first $c_{fft}$ represents a cyclic convolution in the discrete frequency domain. No amount of zero padding added to $a$ and $b$ will change that as their FFTs will be non-zero in almost every bin. So, then for the other operations, your linear convolution of FFT(a) and FFT(b) will not match the circular convolution. Using the 'cconv()' function in MatLab, the circular convolution should come out properly though.
$endgroup$
– Andy Walls
Jan 6 at 23:22
$begingroup$
Andy, unfortunately I don't have Matlab. I was hoping a simple step-by-step explanation would be helpful not only for me but for others who may come here for this.
$endgroup$
– user3351526
Jan 7 at 11:06