PCDL的计算复杂度分析

在本章中，K代表卷积核数量，J代表图像数量，L代表补零后的图像维度。式（7－12）中的卷积核更新是通过在每个频率索引位置上的5个矩阵—向量积来完成的。由于变量重排后，每个小矩阵的大小为J×K，所以全部L频率上对应的计算代价是O（JKL）。下面继续分析式（7－12）所需要的预处理开销。

利用FFT计算的复杂度为O（JKLlogL）。当只需返回奇异值时，计算一个J×K矩阵的SVD的复杂度是O（JKmin（K，J））［215，216］。因此，式（7－12）所需的全部预处理复杂度为O（JKL（logL＋min（K，J）））；而当使用式（7－22）时，由于只计算1%的低频位置上的SVD，该部分开销降低了99%。由于算法7－1中的内循环次数为S，这些预处理计算开销是平摊到每一次内循环迭代上的。将式（7－12）自身的计算复杂度O（JKL），与采用式（7－21）的预处理开销计算在一起，每次卷积核更新时的总计算复杂度为O（JKL［1＋（min（K，J）＋logL）／S］）；而利用式（7－22）构造预条件矩阵时，总开销则为O（JKL［1＋logL／S］）。

表7－1中给出了本章所提出的PCDL算法与其他几个已有算法的计算复杂度比较。

图7－1　PCDL随迭代展现出的数值性质变化

（a）～（d）第1、5、10、15次迭代时的谱半径（每个子图右侧放大显示中，红线标记1%的频谱带宽，而绿点标记出所选出的谱半径）；（e）使用与不使用预条件处理时，的条件数(www.xing528.com)

表7－1　PCDL与已有算法的计算复杂度比较

续表

注：K为卷积核数量，J为图像数量，L为补零后的图像维度，S为滤波器子问题迭代次数，U为并行计算单元数量，N为图像分块处理数量。