Creating huge fourier matrix

I need to minimize |FT^-1(Ax-B)| using lsqr. A is a huge matrix which I had to define using spalloc. Since fft() can't handle sparse matrix, I'm trying to perform the fourier transform via multiplication with fourier matrix

F=dftmtx(N)

in order to compute

 x=lsqr(F*A,fft(B))

However, N is too large so I can't create F. Is there any method to handle large fourier matrix? Thank you for the help.

Answer 1

[Matt J]

Note that | | FT^-1(Ax-B) | | = | | Ax-B | |. This can be seen from Parseval's theorem, or just from basic properties of orthogonal matrices. In other words, you can equivalently just do lsqr(A,B) or A\B and there is no need to actually implement the FT operator at all.

Note also that lsqr(P,Q) does not require that P be a matrix. In the documentation for lsqr, you will see that it can also be a function handle to a function that implements the operations P*x and P' * x.

[Matteo Cencini]

Thank you for your help. Actually I need to minimize |W*FT^-1(Ax-B)|, where W is a weighting vector and * denote pointwise multiplication, so I think I have to implement the FT operator.

[Matt J]

Then you should use a function handle, as I also suggested.

[Christine Tobler]

You could take a look at example 2 in the lsqr documentation for how to define a function handle input to lsqr.