Structured FISTA for image restoration
Structured FISTA for image restoration
复制标题
DOI：
10.1002/nla.2278
复制
发表时间：
2019-01
影响因子：
4.3
通讯作者：
Zixuan Chen;J. Nagy;Yuanzhe Xi;Bo Yu
中科院分区：
文献类型：
--
作者：
Zixuan Chen;J. Nagy;Yuanzhe Xi;Bo Yu
在本文中，我们提出了一种有效的数值方案来解决图像恢复中出现的一些大规模不适定线性逆问题。为了加速计算，利用了两种不同的隐藏结构。首先，将系数矩阵近似为少量克罗内克乘积之和。该过程不仅在计算中引入了多一级并行性，而且还允许在后续优化过程中使用计算密集型矩阵-矩阵乘法。然后，我们推导相应的 Tikhonov 正则化最小化模型，并扩展快速迭代收缩阈值算法（FISTA）来解决由此产生的优化问题。由于克罗内克乘积近似中出现的矩阵都是结构化矩阵（Toeplitz、Hankel 等），因此我们可以在每次迭代时进一步利用它们的快速矩阵向量乘法算法。因此，所提出的算法称为结构化 FISTA (sFISTA)。特别是，我们表明 sFISTA 引入的近似误差得到了很好的控制，并且 sFISTA 可以达到与 FISTA 相同的图像恢复精度水平。最后，提供了理论复杂性分析和一些数值结果来证明 sFISTA 的效率。
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. Because 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 FISTA (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.