Huge Fourier matrix - MATLAB

Question

I need to create a Fourier matrix in order to apply it to a huge matrix that I needed to define as sparse using spalloc. I tried:

F=dftmtx(N);

but N is too large so I can't create it. Is there any way to solve this problem? Thank you for your help!

Answer 1

For each column, you can form a reduced DFT matrix by leaving out the entries that will multiply zeros. Something like

X = my_matrix;
c = column_index;

x = X(:,c);
N = length(x);
inds = find(x);
F = exp( -1j * 2*pi/N * (0:N-1)' * (inds-1) );
Xdft(:,c) = F * x(inds);

You'll have to iterate over the columns unless the zeros in the input matrix don't change column-to-column. However, the above still seems silly to me. I'd just pull off one column at a time and use fft().