  Fourier domain structured low-rank matrix priors are emerging as powerful
alternatives to traditional image recovery methods such as total variation and
wavelet regularization. These priors specify that a convolutional structured
matrix, i.e., Toeplitz, Hankel, or their multi-level generalizations, built
from Fourier data of the image should be low-rank. The main challenge in
applying these schemes to large-scale problems is the computational complexity
and memory demand resulting from lifting the image data to a large scale
matrix. We introduce a fast and memory efficient approach called the Generic
Iterative Reweighted Annihilation Filter (GIRAF) algorithm that exploits the
convolutional structure of the lifted matrix to work in the original un-lifted
domain, thus considerably reducing the complexity. Our experiments on the
recovery of images from undersampled Fourier measurements show that the
resulting algorithm is considerably faster than previously proposed algorithms,
and can accommodate much larger problem sizes than previously studied.
