# 2D FFT of Vector

I have a bunch of 8x8 images which have been vectorized and formed into a 64xN matrix, X. I'd like to take the 2D-FFT of each of these images without reshaping each column of X into an 8x8 image and using fft2.

Any suggestions? I've tried playing around with properties of kronecker products and vec() operations but haven't gotten anywhere.

• For questions like this, it is best to also tag the software environment you are working with so people can provide you with the most targeted solutions (MATLAB, R, C++...). – Sam Maloney Apr 25 '13 at 16:25
• So your matrix looks like this: $$\begin{array}{ccc}X_1(:,1) & \ldots & X_N(:,1)\\\vdots & \ddots & \vdots\\X_1(:,8) & \ldots & X_N(:,8)\end{array}$$ with $X_i$ the matrix of image $i$? – Matt L. Apr 25 '13 at 17:11
• @Matt Yes, this is correct. The second index runs to 64, but that isn't as important. – lp251 Apr 25 '13 at 17:42
• OK, but my elements $X_i(:,k)$ are 8-element vectors (the columns of the individual images), and there are 8 such vectors concatenated in each column of the total matrix, right? – Matt L. Apr 25 '13 at 19:08
• @Matt Yes, that is correct. – lp251 Apr 25 '13 at 19:09

Your matrix looks like this: $$\begin{array}{ccc}X_1(:,1) & \ldots & X_N(:,1)\\\vdots & \ddots & \vdots\\X_1(:,8) & \ldots & X_N(:,8)\end{array}$$ where $X_i,\; i=1,\ldots 64,$ are the $8\times 8$ image matrices. So $X_i(:,1)$ is the first column of the $i^{th}$ image (I'm using matlab/octave notation). You said you don't want to reshape each column and you've tried kronecker products etc., but I actually think that reshaping is the simplest solution to your problem. Look at the code:

$\tt Z=[];\\for\; i=1:N, Y=reshape(X(:,i),8,8); Z=[Z,fft2(Y)]; end$

$\tt N$ is the total number of images in matrix $\tt X$. $\tt Z$ is a $8\times 8N$ matrix containing the DFTs of all $N$ images. I think it won't get much simpler than that. If so, please let me know.

• This is definitely the simplest solution, but quite unattractive due to the problem size. Ideally I'd have an operation that I can apply directly to the 64xN matrix without any reshaping. – lp251 Apr 25 '13 at 20:23
• OK, but I don't think it's that huge a problem. It's only a loop over 64 submatrices. Anyway, that's all relative of course. If you come up with a simpler solution, please share it with us. – Matt L. Apr 25 '13 at 20:30
• I wasn't able to find any faster methods. For a little context, I was trying to accelerate a matrix-matrix product XY where X is diagonalized with 2D-FFTs (block circulant with circulant blocks) but Y has no structure to speak of. For the problem size I'm looking at, a dense multiply is faster than the reshape-fft2-reshape operations, even though the complexity order is higher. Such is Matlab. – lp251 May 4 '13 at 16:45

you could create a matrix that contains the Fourier basis set in the format that conforms to the vectorized version of your images and use this matrix to compute the fft2.

You can therefore get what you want with a simple matrix multiplication.