Ifft through Matrix multiplication

Question

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)

Answer 1

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.

Answer 2

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$