How to build a Fourier matrix?

How would I build a Fourier matrix in Matlab? Intuitively what is this matrix telling me and is there a difference between a Fourier matrix for a vector signal (x) vs. a Fourier matrix for an image (I) signal? My intuition is that it doesn't matter and that the matrix simply holds the frequencies I wish to capture. For example:

y = Fx,

where F is the Fourier matrix, x is a sparse vector and y are my signals. x could stand for my vectorized image, say x = I(:)

so far I have

F = dftmtx(numel(I))

Is this right?

p.s. Are there different names used to refer to this Fourier Matrix?

Thank you

Answer 1

[Bjorn Gustavsson]

Yes, it is right. F would be a 1-D Fourier matrix. A Fourier coefficient is the inner product between the signal and the corresponding Fourier waveform:

fftX_n = exp(-1i*pi*n*(0:length(f))/length(f))*f(:)

(if I got the parenthesises and signs right) So you can simply stack all of the Fourier base-functions, line by line into a Fourier matrix and calculate all the Fourier components in one matrix multiplication. This is for a 1-D dft, to calculate a 2-D you'd either have to do it step-wise column by column and then row by row - or use the powerful ':' operator matlab has and build a larger 2-D Fourier matrix. But why bother, there are fft2 and ifft2 functions?

[Valentin]

Thank you - I just need the Fourier matrix. If I understood you correctly, this Fourier matrix remains the same for a 2D Fourier transform.

If I'm calculating the DFT using F (but in my case I'm not) than I would use the fft2.

[Bjorn Gustavsson]

Not exactly the same. You have to take into account that the image is 2-D. This is the 2-D dft-matrix for 8-by-8 images:

function DFTMTX2D = TwoDdftmtx(d)
% only for 8-by-8 d
DFTMTX = dftmtx(8);
DFTMTX2D = zeros(8^2*[1,1]);
for i1 = 1:8,
  for i2 = 1:8,
    DFTMTX2D(8*(i1-1)+[1:8],8*(i2-1)+[1:8]) = DFTMTX*DFTMTX(i1,i2);
  end
end

Then you get the DFT like this:

DFTMTX2D = TwoDdftmtx(d);
ftD = 0*d;
ftD(:) = DFTMTX2D*d(:);

[Matt J]

If F is a 1D dft matrix then the 2D dft matrix can also be obtained as

 DFTMTX2D = kron(F,F);

Answer 2

[Matt J]

If the whole motivation for this thread is that MATLAB's fft2() can't handle sparse input images, then I would recommend implementing it this way for an NxN image

    F=fft(eye(N)); %or dftmtx if you have the correct Toolbox

    fft2d = F*Image*F.';

As I commented here, you can also do this as

    fft2d = kron(F,F)*Image(:);

but this will be much slower and more memory-consuming.

[Matt J]

For still further optimization, it would probably be better to do

fft2d= fft(F*Image, [],2);

The reason is that F*Image is not sparse even if 'Image' is sparse. Therefore, it becomes possible (and more efficient) to use fft() again for part of the computation.

[Matt J]

Even better, build F to be sparse and to include only columns that will be used

    F=speye(N);
    idx=any(Image,2);
    F(:,idx)=fft(full(F(:,idx)));

    fft2d= fft(F*Image, [],2);

This would really only be good for sparse Images with lots of all-zero rows.

[Valentin]

@Matt Thanks for your posts. I am just reading through the answers. I'm learning about compressed sensing. My motivation is to do a test that measures an "incoherence property" between a sensing matrix (Phi) and a representation matrix (Psi). The literature states one option for the representation matrix is the Fourier matrix. My data is a 2D image that I subsample randomly and then I reconstruct using compressed sensing (and matrix completion)

[SwishSwisher]

This is very helpful Matt! Thank you.

Answer 3

[Robert Kim]

You can get both cos and sin part of Fourier basis. If you need the complex number, just remove the real, and imag parts. But if really need to use this for FFT purpose, just try matlab function "fft".

sigLen = 2;

AC_t = 0.001:0.001:sigLen;

AC = ones(sigLen/0.001, 1);
for n = 1:4
y = exp(2^n*i*pi/sigLen*AC_t)';
AC = [AC real(y) imag(y)];
end

figure
plot(AC_t, AC)

ylim([-1.2 1.2])