论文地址 ： https://arxiv.org/abs/1804.10366
文中的数学公式符号并不能很好的显示，采用普通字母代替，故带有一定的误差，建议数学公式的推导还是回归论文查看。
简介
卷积稀疏编码（CSC）已被广泛用于图像和信号处理中的平移不变字典的学习。然而，现有的方法的可扩展性是有限的。在本文中，我们使用的不是样本共享的字典来卷积，而是使用样本自适应字典，其中每个过滤器是从数据中学习的一组基本滤波器的线性组合。这种灵活性允许捕获大量依赖于样本的模式，这在处理大型或高维数据集时特别有用。在计算上，所得到的模型可以通过在线学习来进行有效地学习。在大型数据集上的实验结果表明，所提出的方法优于现有的CSC算法，可以显著减少的时间和空间复杂度。
1.序言
卷积稀疏编码目前已成功地应用在图像处理、信号处理和生物医学应用中。它与稀疏编码密切相关，但CSC的优点在于它的平移不变字典可以捕获信号和图像中常见的偏移局部模式。然后，每个数据样本由对应的代码卷积的字典中的一组滤波器的总和来表示。
传统的CSC算法在批处理模式下运行，采用O（NK^2P+NKP log p）时间和O（NKP）空间（其中n是样本数），k是滤波器的数目，p是维数。近年来，随着数据样本到达一定程度，样本的相关信息被压缩为小型的历史统计数据，并且模型被增量更新，已经提出了许多在线CSC算法拥有了更好的可扩展性。值得一提的是，最先进的OCSC算法具有更小的时间复杂度O（K^2P+KP log P）和空间复杂度O（K^2P）。
然而，OCSC的复杂性仍然依赖于K，并且不能与大量的过滤器一起使用。因此，可以捕获的局部图案的数量是有限的，并且可能导致性能过低的情况出现，尤其是在高维数据集上更为严重。此外，使用更多的滤波器也导致了大量昂贵的卷积运算。RigaMunTi和SiRONI提出用可分离滤波器来近似地对学习过的滤波器进行后处理，使得卷积变得相对不那么昂贵。然而，由于学习和后处理是两个独立的过程，因此得到的滤波器可能不是最优的。此外，随着新样本的到来，这些独立的过滤器无法在线更新。
CSC拓展的另一个方向是通过分布式计算（BotSekas＆TsisiKLIS，1997）。将数据和工作量分配到多台机器上，最近的共识CSC算法（ChoudHury等人，2017）可以处理更大型、更高维的数据集，例如视频、多光谱图像和光场图像。然而，关于CSC的计算需求只是通过共享运算平台解决，并没有真正地解决CSC的计算量问题。
在本篇论文中，我们提出了通过从数据中学习的一组小型基础滤波器的自适应组合来近似大型滤波器。虽然标准CSC字典由所有样本共享，但我们建议每个样本都有自己的“个人”字典来补偿使用这些在线卷积稀疏编码与样本自适应基滤波器而导致的灵活性降低的问题。以这种方式，表现效果可以保持相同，但参数数目却可以有效减少。计算上，这种结构还允许开发高效的在线学习算法。具体地，基础滤波器可以通过乘法器交替方向法（ADMM）更新（博伊德等人，2011），而代码和组合权重可以通过加速的近端算法来学习（姚等人，2017）。在各种数据集上的广泛的实验结果表明，这种SCSC算法在时间和空间上都具有不错的效果，并且优于现有的批处理、在线和分布式CSC算法。
论文的其余部分按如下方式组织。第2节简要回顾卷积稀疏编码。第3节描述了所提出的算法。实验结果在第4节中给出，最后一节给出了一些相关结论。
2.卷积稀疏编码综述 Review: Convolutional Sparse Coding
给定的样本{x1，……，xn}在R^P中，CSC学习一个移位不变字典D∈R^M×K，其中列{D(: , k)} 表示k个滤波器。每个样本xi都被编码为Zi∈R^P×K，kth列是用滤波器D（:，k）卷积的代码。字典和代码是通过解决最优化问题一起学习得到的：
当第一项测量信号出现重构误差时，D = {D :||D(:,k) ||2 ≤ 1, ∀k = 1, . . . , K}保证了滤波器的归一化，β＞0是控制Zi’s稀疏性的正则化参数。
在空间域中执行（1）中的卷积。这需要O（KPM）时间，而且价格昂贵。相比之下，最近的CSC方法在频域上进行卷积，其取O（KPlog p）时间（Mallat，1999），并且对于M和P的典型选择更快，让x˜i ≡ F(xi)，D˜(:,k) ≡ F(D(:,k))和Z˜ i(:,k) ≡ F(Zi(:,k))成为xi ,D(:,k) and Zi(:,k)傅立叶变换后的对应。代码和滤波器以块坐标下降交替方式更新，如下：
（2）和（3）都可以用乘法器交替方向法（ADMM）来求解（博伊德等人，2011）。随后，{Z˜ i}和D˜可以被转换回空间域，如Zi(:,k) = F^-1 (Z˜ i(:,k)) 和D(:,k)＝C(F^-1(D˜(:,k)))。注意，虽然Zi’s（在空域中）是稀疏的，但是FFT变换后的的Z˜i’s 不是。
在推理上，给定学习字典D，测试样本xij被重建为
∑K/k=1 D(:, k) ∗ Zj (:, k)，其中Zj是得到的编码。
2.1.可分离滤波器的后处理 Post-Processing for Separable Filters
由CSC获得的滤波器是不可分离的，随后的卷积可能是缓慢的。为了提高速度，它们可以通过可分离滤波器进行后处理和近似（RigaMaTi等人，2013；SiRONI等人，2015）。具体而言，学习的D是由SW近似的，其中S ∈ R^M×R包含R rank-1基础滤波器{S（：，1），…，S（：，R）}和W ∈ R^R×K包含组合权重。然而，这常常会导致性能低下。
2.2. 在线CSC Online CSC
在线CSC算法（OCSC）是最近提出的。在最后一次迭代中，给出了傅立叶变换的样本x˜t和字典D˜ t−1，得到了相应的{Z˜t, Ut}，如在（2）中得到的。下面的命题通过重新编写（3）使用较小的历史统计数据来更新D˜t 和Vt。
命题1：Vt可以通过求解优化问题得到：
问题（4）可以用ADMM来解决。总的空间复杂度仅为O（K^2P），与N无关。此外，Ht和Gt可以进行增量更新。
最近还提出了另外两个在线CSC的重新制定方案。Degraux提出的CSC方案通过在空间域上进行卷积，但速度较慢。Liu提出的CSC方案在频域中进行卷积，但需要昂贵的稀疏矩阵运算。
3.具有自适应字典的在线CSC Online CSC with Sample-Dependent Dictionary
虽然OCSC在样本大小N的情况下可以很好地扩展，但它的空间复杂度仍然取决于滤波器数量K的平方。 这限制了可以使用的过滤器数量，并且可能影响性能。 受2.1节中可分离滤波器的思想的启发，我们通过用R基础滤波器来近似K滤波器以实现更多滤波器的学习，其中R<K。 与通过后处理获得的可分离滤波器相比，我们建议在信号重建期间直接学习字典。此外，字典中的滤波器以样本自适应的方式从基本滤波器组合。
3.1. 问题描述 Problem Formulation
回想一下，每一个xi in（1）都是由∑K/k=1 D(:, k) ∗ Zj (:, k)表示。设t B∈R^M×R，其中列{B(:,r)}是基础滤波器。我们建议将xi表示为：
这是依赖于样本的。如图所示，这允许Wi’进行独立学习（第3.3节）。这也导致更多的自适应模式被捕获，从而获得更好的性能（第4.4节）。
卷积神经网络（CNN）最近研究了样本相关滤波器（Ja等人，2016）。从经验上看，这优于标准CNNs在单镜头学习，视频预测和图像去模糊这三个方面的表现。Jia使用专门设计的神经网络学习滤波器，不考虑CSC模型，而是将样本相关滤波器集成到CSC中。
该词典还可以通过微调来适应单个样本。然而，当K很大时，学习初始共享字典仍然很昂贵。此外，如将在第4.2节中所示，所提出的方法将优于经验的微调。
3.2. 学习方法 Learning
将（6）代入到CSC公式中（1），我们得到
由于B和Wi在（8）中耦合在一起，这使得优化问题变得困难。下面的命题将B和Wi解耦。所有的证明都在附录中。
为了简化符号，我们用W表示W’1或W’2。通过在{Wi}上施加上述结构中的任一个，得到以下的优化问题：
在对样本xj进行推算时，可以通过解决(10)来获得相对应的（Wj，Zj）。
3.3.在线学习算法解决（10）优化问题 Online Learning Algorithm for (10)
正如在第2.2节中，我们提出了一个更好的可扩展性的在线算法。在tth迭代中，考虑
设B˜(:, r) ≡ F(B(:, r))，其中B(:, r) ∈ R^M使用零填充为P维。
注意，通过重写上面的求和∑R/r=1 B(:, r) ∗( ∑K/k=1 Wi(r, k)Zi(: , k))，可以将卷积的数量从k减少到r。
下面的命题重写（11）并在频域中进行卷积。
命题3:问题(11)重写为：
空域基础滤波器可以将B˜还原为B(:,r) = C(F^-1 (B˜(:,r)))。
3.3.1. B˜ t的获取 OBTAINING B˜ t
从优化问题（12），可以通过求解子问题来获得B˜ t：
其中V˜是辅助变量，这与（3）的形式相同。因此，类似于（4），B˜t可以通过下方优化问题得到：
3.3.2.得到Wt和Zt OBTAINING Wt AND Zt
随着XT的到来，我们将基础滤波器固定到在最后一次迭代中学习的B˜t−1，并从优化问题（12）获得（Wt，Zt）：
在CSC文献中，可以看出ADMM也可以用于求解（16）。虽然（2）中CSC的代码更新子问题是凸的，但问题（16）是非凸的，并且对于ADMM的现有收敛结果不适用。
在本论文中，我们将使用非凸和不精确加速的近端梯度（NIAPG）算法（姚等人，2017）。这是最近的非凸问题的近似算法。由于（16）中W和Z的正则化器是独立的，所以两个块的近端步长W.R.T.可以分别执行：
如上方所示，这些单独的近端步骤可以很容易地计算。
3.3.3.算法完善 COMPLETE ALGORITHM
整个过程将被称为“采样相关卷积稀疏编码（SCSC）”，在算法1中示出。它的空间复杂度为H(t) 和G（t），是O（R^2P）。其每次迭代时间复杂度为O（RKP+RP logP），其中O（RKP）项采用的是梯度计算，O（RP log P）是由于FFT/inverse FFT。表1比较了它的复杂性与其他在线和分布式CSC算法的复杂性。由此可见，SCSC具有较低的时间和空间复杂度。
4.实验 Experiments
我们在多个数据集上进行实验（表2）。Fruit和City是在CSC文献中常用的两个小型的图像数据集。我们使用默认训练和测试分割。图像的预处理包括转换为灰度、特征标准化、局部对比度归一化和边缘渐变。这两个数据集很小，在后面的实验中，我们还将使用两个更大的数据集，CIFAR10（Krizhevsky & Hinton, 2009）和Flower（Nilsback & Zisserman, 2008）。随后我们将滤波器大小M设为11×11，以及正则化参数。
为了评估学习字典的有效性，我们将主要考虑图像重建的任务。重建的图像质量通过测试峰值信噪比（PAPYANN等人，2017）来评估：
其中X^j是测试集的X的重建。实验用不同的字典初始化重复五次。
4.1.W的选择：W1与W2 Choice of W : W`1 versus W`2
首先，我们研究命题2中W的选择。我们比较SCSC-L1，它使用W= W’1，而SCSC-L2，使用的是W＝W’2。实验是在Fruit和City数据集上进行的。滤波器K的数目设置为100。回看表1中的空间复杂度的结果，我们定义SCSC相对于OCSC的压缩比（使用相同的K）作为CR＝（K/R）^2。我们在{K／20，K／10，K／9，…，K／2，K}中改变R的值，同时相应的CR为{400, 100, 81，.…，1 }。
结果如图1所示。可以看出，SCSC-L1是非常差的。图2（a）示出了在城市测试样本XJ上由K＝100和R＝10通过SCSC-L1获得的权重WJ（其他数据集上的结果是相似的）。可以看出，由于“1范数”引起的稀疏性，它的大部分条目都是零。表达能力严重受限，因为通常只使用一个基础滤波器来近似原始滤波器。另一方面，由SCSC-L2学习的WJ是稠密的并且具有更多的非零项（图2（b））。在续集中，我们只关注SCSC-L2，这将简单地表示为SCSC。
4.2. 样本自适应字典Sample-Dependent Dictionary
在这个实验中，我们设置K＝100，并将SCSC与使用样本无关字典的下列算法进行比较：（i）SCSC（共享）：这是SCSC变体，其中所有Wi的In（5）都是相同的。其优化是基于交替最小化。（ii）通过张量分解（SET-TD）学习的可分离滤波器（SRONI等人，2015），这是基于后处理的（共享）字典，由OCSC学习的，如第2.1节所述；（iii）OCSC（王等人，2018）：最新的在线CSC算法。
结果如图3所示。可以看出，SCSC总是优于SCSC（共享）和SET-TD，当R＝10（对应于CR＝100）或以上时，SCSC优于OCSC。这表明使用依赖于样本的字典的优点。
接下来，我们与带精细调谐滤波器的OCSC进行比较，这也是样本自适应的。具体地，给定测试样本xj，我们首先从学习字典D获得（2）其代码Zj，然后通过使用新计算的Zj求解（3）来微调D。这是重复迭代的过程。我们设置OCSC的K等于SCSC的R，使这两种方法采取相同的空间复杂度（表1）。在SCSC中使用的K仍然是100。结果如图4所示。可以看出，虽然微调提高了OCSC的性能，但是这种产生样本自适应的滤波器的方法仍然比SCSC更差。
4.3.多滤波器学习 Learning with More Filters
召回SCSC允许使用更多的过滤器（即较大的K），因为其较低的时间和空间复杂度。在这一节中，我们证明了这可以发挥更好的性能。我们比较SCSC与最近两批和在线CSC方法，即基于切片的CSC（SBCSC）（PaPaun等人，2017）和OCSC。对于SCSC，我们设定R＝10为Fruit和City，R＝30为CIFAR-10和Flower。
图5显示了在不同K的测试PSNR。如图所示，较大的K总是对所有方法都有更好的性能。SCSC允许使用更大的K，因为它的内存占用小得多。例如，在CIFAR-10上，CR＝1024时K＝800；在Flower上，CR＝1600时K＝400。
4.4.与目前最新技术的比较 Comparison with the State-of-the-Art
首先，我们对Fruit和City的两个较小数据集进行实验，K = 100.我们为SCSC设置R = 10（即CR = 100）。 将其与批量CSC算法进行比较。
图6显示了与时钟时间的测试PSNR的收敛性。也证明了在线CSC算法收敛更快，相比于批量CSC方法具有更好的PSNR。在在线方法中，SCSC具有与OCSC类似的PSNR，但是收敛得更快，并且占用更少的存储（CR＝100）。
接下来，我们对两个大数据集CIFAR-10和Flower进行实验。所有的批处理CSC算法和两个在线CSC算法OCDL-Degraux和OCDL-Liu并不能处理这样大的数据集。因此，我们只比较SCSC与OCSC。在CIFAR-10上，我们设定K＝300，相应的SCSC的CR为100。在Flower上，SCSC的K值仍为300。然而，OCSC只能使用k＝50，因为它的内存占用太多多。图7显示了测试PSNR的收敛性。在这两种情况下，SCSC显著优于OCSC。
4.5.高维度数据 Higher-Dimensional Data
在这一节中，我们对具有大于两个维度的数据集进行实验。为了缓解大的内存问题Choudhury等人提出了分布式算法的使用。在这里，我们表明，SCSC可以在一台机器上有效地处理这些数据集。
实验在三个数据集（表3）中进行（CoudHury等人，2017）。视频数据集包含在机场记录的图像子序列。每个视频的长度为7，每个图像帧的大小为100×100。多光谱数据包含60×60块来自多光谱图像（覆盖31个波长）的真实世界物体和材料。光场数据包含60×60块在物体和场景上的光场图像。对于每个像素，光线是来自8×8不同的方向。（将滤波器的大小M设为11×11×11视频，11×11×31为多光谱，11×11×8×8为光场。
我们比较SCSC与OCSC和共识 CSC（CCSC）算法，K＝50。为了公平的比较，所有的方法只使用一台机器。我们不与批处理方法和两种在线方法（OCDL-Degraux和OCDL-Liu）进行比较，因为它们是不可扩展的（如在第4.4节中已经示出的）。
由于SCSC的内存占用小，我们在GTX 1080 TI GPU上运行这个实验。OCSC也在GPU上运行用于视频。然而，OCSC只能在CPU上运行多光谱和光场。CCSC在处理过程中需要访问所有的样本和代码，也只能在CPU 上运行。
结果如表4所示。值得一提的是，SCSC是唯一可以处理整个视频、多光谱和光场数据集在一台机器上的算法。相比之下，CCSC只能处理最多30个视频样本、40个多光谱样本和35个光场样本。OCSC可以处理整个视频和多光谱，但是在使用整个光场数据集的2天内不能收敛。再一次表明SCSC优于OCSC和CCSC。
至于收敛速度，SCSC是最快的。但是注意这只是作为参考，因为SCSC是在GPU上运行的，而其他的（除了视频上的OCSC）在CPU上运行。然而，这仍然表明SCSC的一个重要优点，即它的小内存占用可以受益于GPU的使用，而其他的算法则不能。
4.6.图像去噪与修复 Image Denoising and Inpainting
在以前的实验中，学习字典的优势是通过重建干净的图像来证明的。在这一节中，我们进一步研究学习字典在两个应用：图像去噪和修复。使用Choudhury等人提供的十个测试图像。在去噪中，我们加入零均值和方差为0.01的高斯噪声对图像进行测试（平均输入PSNR为10dB）。在修复中，我们将随机子样本的50%像素作为0（平均输入PSNR为912dB）。随后我们使用二进制权重矩阵来掩盖缺失像素的位置。我们使用在第4.4节中从水果中吸取的过滤器。将SCSC与（批）SBCSC和（在线）OCSC进行比较。结果如表5所示。可以看出，由SCSC获得的PSNR始终高于其他算法。这表明，在图像重建中产生高PSNR的字典在其他图像处理应用中也可以发挥更好的性能。
4.7. 求解（16）：niAPG与ADMM Solving (16): niAPG vs ADMM
最后，我们比较了ADMM和niAPG在求解子问题（16）中的性能。我们使用来自City的训练样本xi。实验用不同的（Wi，Zi）初始化重复五次。图8显示了（16）目标随时间的收敛性。可见，niAPG具有快速收敛性，而ADMM不能收敛。图9显示了
，它用迭代次数来衡量违反ADMM约束的情况。可以看出，违规不会达到零，这表明ADMM不收敛。
5.结论 Conclusion
在本文中，我们提出了一种新的CSC扩展，其中每个样本都有自己的样本自适应的字典，由一组小的共享基滤波器构成。使用在线学习，该模型可以有效地更新，具有低的时间和空间复杂度。对包括大图像数据集和高维数据集在内的各种数据集的广泛实验都证明了它的效率和可扩展性。
才学疏浅，欢迎评论指导