[BANANA] LA/Opt Seminar: Wed Sept 27

[Gene H Golub]

DATE: 	Wed, Sept 27
TIME: 	4:15 
ROOM:  	Gates 104 
SPEAKER:Ofer Levi 
FROM:  	Ben-Gurion University 
E-MAIL: levio at bgu.ac.il 
TITLE: Iterative solvers for non-uniform discrete Fourier inverse 
problems.

ABSTRACT: In this talk, I will present the non-uniform discrete Fourier 
inverse problem in 1D and 2D. Unlike the uniform case where the transform 
is orthogonal and the inverse problem can be solved directly in O(nLog(n)) 
complexity, non-uniform Fourier problems involve dense ill-conditioned 
linear systems with no general fast algorithms for matrix-vector 
multiplication. Iterative solvers for such systems can be impractical for 
big systems due to the O(n^2) complexity of the matrix-vector 
multiplications in each iteration where in practical problems n might be 
in the order of millions, for example the number of pixels in a digital 
image. Due to the computational challenges mentioned above, what is done 
in practice is solving the inverse non-uniform Fourier problem 
approximately by interpolating the Fourier coefficients to a uniform grid. 
I will show that for any non-uniform grid in the Fourier space and any 
dimension the operator matrix, A'A (the product of the transform matrix 
and its adjoint) has a Toeplitz or Block Toeplitz (in the higher 
dimensional case) structure so the normal equation of the inverse problem 
can be solved iteratively with a cost of O(nLog(n)) for each iteration 
using known super-fast algorithms for such structured matrices. Using this 
method makes the iterative solution feasible even for relatively big 
problems.


Coming Attractions: October is Tensor Decomposition Month. Watch this 
space!
-++**==--++**==--++**==--++**==--++**==--++**==--++**==
This message was posted through the Stanford campus mailing list
server.  If you wish to unsubscribe from this mailing list, send the
message body of "unsubscribe linear_algebra_optimization" to majordomo at lists.stanford.edu