  In this paper, we propose an efficient numerical scheme for solving some
large scale ill-posed linear inverse problems arising from image restoration.
In order to accelerate the computation, two different hidden structures are
exploited. First, the coefficient matrix is approximated as the sum of a small
number of Kronecker products. This procedure not only introduces one more level
of parallelism into the computation but also enables the usage of
computationally intensive matrix-matrix multiplications in the subsequent
optimization procedure. We then derive the corresponding Tikhonov regularized
minimization model and extend the fast iterative shrinkage-thresholding
algorithm (FISTA) to solve the resulting optimization problem. Since the
matrices appearing in the Kronecker product approximation are all structured
matrices (Toeplitz, Hankel, etc.), we can further exploit their fast
matrix-vector multiplication algorithms at each iteration. The proposed
algorithm is thus called structured fast iterative shrinkage-thresholding
algorithm (sFISTA). In particular, we show that the approximation error
introduced by sFISTA is well under control and sFISTA can reach the same image
restoration accuracy level as FISTA. Finally, both the theoretical complexity
analysis and some numerical results are provided to demonstrate the efficiency
of sFISTA.
