# Ifft through Matrix multiplication

I am still new to MATLAB, so apologies if I sound lazy to you. I am attempting to model a transformation as a set of matrix operations. I start with a vector, up-sample it by $U$ (up-sampling rate), take its Fourier transform, apply a Low-pass filter, take Inverse Fourier transform and finally down-sample at a rate $D$, where $U \neq D$.

I want to do all these transformations as a set of matrix multiplication, and not use MATLAB's built-in commands. Up-sampling / Down-sampling is easy. And so is Low Pass Filtering. But I am stuck with fft and ifft. I could use dftmtx to generate the matrix that would perform the fft, but using a vector $1000$ samples long, and up-sampling it by $1000$ makes a very big array, so that matrix generated by dftmtx becomes memory constrained. I have looked the code for dftmtx which is simply fft(eye(n)), where $n$ is length of the vector to be transformed. I tried replacing eye(n) with speye(n), so as to reduce the matrix values, but it would not work this way too.

The second problem is I do not have any idea how to do ifft using a matrix multiplication. I understand this matrix will also be a very large matrix and become memory constrained. However, no search on any online resource has helped me so far.

Whereas doing the above mentioned transformations is easily done by MATLAB, I need the matrix version for my application.

Any guidance is appreciated.

My code in simplest for is

n=1000;% length of original code
a=randn(n,1)+j*randn(n,1); %initialise
U=1001; %up-sampling rate
u=zeros(n*U,n); %Blank up-sample matrix
%find indices for up-sampling
for i=1:N;
u(U*i-(U-1),i)=1;
end
ua=u*a; %up-sample a by rate of U
%Find Fourier transform
ft=dftmtx(length(ua));
fa=ft*ua;
%Designing LPF
lp=speye(length(fa)); %initialise
j=length(fa)/2-ceil(U/3):length(fa)/2+ceil(U/3); %define central region where high frequencies will be ignored
lp(j,j)=0; %ignore center values which have high frequency, render this region zero
lpa= lp*fa; %Low Pass Filter Up-sampled Fourier transformed sequence
%Inverse Fourier transform
ifa=ifft(lpa); %How to implement this as matrix multiplication so that we have ifa = ifft_matrix * lpa
%Down-sample
D=1000; %down-sample rate
j=length(ifa)/D;
d=zeros(j,length(ifa)); %Blank up-sample matrix %find indices for down-sampling code
for i=1:j
d(i,D*i-(D-1))=1;
end
da=d*ifa; %calculate the down-sampled matrix da with length 1001 (original code stretched by 1 sample)


## 2 Answers

You can alternatively create a DFT matrix in matlab using this code:

exp(-1j*2*pi* ((0:N-1)/N).' * (0:N-1))


And the IDFT matrix thus:

1/N * exp(1j*2*pi* ((0:N-1)/N).' * (0:N-1))


As the only difference betweenm DFT and IDFT is the sign and a scaling factor.

You could alternatively just do:

ifft(eye(N))


But this doesn't get around needing the full DFT matrix, and honestly I don't see an obvious way of perfoming a DFT by matrix multiplication without actually having the DFT matrix. Perhaps if you were writing your own code you could leverage the symmetry of the DFT matrix so you only needed half of it but I don't think this idea will get you anywhere in Matlab.

• Hi. This had seemed to be the first option I tried, but as I said, after up-sampling a vector of length 1000 by a factor of 1001 yields an up-scaled vector of length (1001000). MATLAB refuses to work on matrices of this size (ifft(eye(1001000)))=7465.5 GB and generating a matrix using the IDFT formula yileding a matrix requiring memory 14931 GB.So i guess this this is not a viable option. – Sal Jul 6 '18 at 3:42
• Can you explain why it needs to be performed as a matrix operation? Is it part of an optimisation routine? – kippertoffee Jul 6 '18 at 7:39
• Yes. I am trying to model the whole transformation for an optimisation requirement. Having matrices will help me find one generalised matrix that would perform all these transformations, and then optimise it accordingly. One possible avenue is tall vector, but then the operations are held back unless asked for. I am not sure how slow my simulation would become by using tall vectors. – Sal Jul 7 '18 at 6:29

The first part of the question remains to be answered, but a simple solution to second part is here. The trick is shared here https://dsp.stackexchange.com/a/36084/30997.

I found it to be very simple especially for calculating ifft by using fft, that is using $dftmtx$ in MATLAB. The matrix that would calculate the ifft of a given sequence $X$ in frequency domain is $iff=1/(m)*conj(f*(conj(X)))$

where $m$ is the length of the vector $X$. Multiplying the matrix $iff$ with $X$ is analogous to calculating the ifft of the Vector $X$