没有合适的资源?快使用搜索试试~ 我知道了~
FFTLasso:傅里叶域中的大规模LASSO
,(1)17160FFTLasso:傅里叶域中的大规模LASSO0Adel Bibi,Hani Itani,Bernard Ghanem,沙特阿拉伯科技大学(KAUST)0adel.bibi@kaust.edu.sa, hmi10@mail.aub.edu, bernard.ghanem@kaust.edu.sa0摘要0本文重新审视了LASSO稀疏表示问题,该问题已在各种不同领域进行了研究和应用,包括信号处理、信息理论、计算机视觉和机器学习。在视觉社区中,它在许多重要应用中得到了应用,包括人脸识别、跟踪、超分辨率、图像去噪等等。尽管在高效稀疏算法方面取得了进展,但解决大规模的LASSO问题仍然是一个挑战。为了避免这个困难,人们倾向于对问题进行降采样和子采样(例如通过降维)以保持一个可管理的LASSO大小,但通常会损失解的准确性。本文提出了一种新颖的循环重构LASSO方法,将问题提升到更高的维度,从而可以高效地应用ADMM算法来处理其对偶形式。由于这种提升,所有的优化变量都只使用基本的逐元素操作进行更新,其中计算开销最大的是一维FFT。这样,就不需要线性系统求解器或矩阵-向量乘法。由于FFTLasso方法中的所有操作都是逐元素的,子问题是完全独立的,可以轻松地进行并行化(例如在GPU上)。通过对合成数据、真实数据和人脸识别任务进行广泛的实验证明了FFTLasso的吸引人的计算性能,表明FFTLasso比最先进的求解器具有更好的可扩展性。01. 引言0本文主要研究高效解决流行的LASSO问题,定义如下:0min c } Ac ´ b }2 2looooomon0f p cq0` λ } c } 1loom0g p cq0其中 A P R m ˆ n 是稀疏字典,λ是一个正参数,用于权衡稀疏性和数据拟合的准确性。问题(1)是强凸但非0平滑。问题(1)描述了计算机视觉和机器学习中的许多应用,包括(但不限于)人脸识别[32, 28, 33],人脸对齐[25,24],跟踪[20, 35, 37, 38, 15, 36, 3],超分辨率[34,27],卷积稀疏编码[6, 14,17],图像修复[30],稀疏子空间聚类[11,10],图像去模糊[2, 16, 26]等等。0在许多应用中(例如人脸识别和人脸对齐),解决问题(1)对于一个非常大的过完备字典 A(例如当 m,n > 10^5 时)是很重要的。在人脸识别、人脸对齐和跟踪中,A的每个大小为 m 的列是一个矢量化的图像或图像块,n是训练样本的数量。在某些特定的人脸识别和跟踪模型中,训练样本的数量甚至更大。例如,在[35, 32, 20]中,身份矩阵 I_m 与原始字典连接在一起(即 n = n +m),以处理部分遮挡,但代价是解决一个更大的LASSO问题。此外,在稀疏子空间聚类[10,23]中,数据点的维度(m)通常非常大,任务是将高维数据聚类成一组较低维度的子空间。其他应用,如超分辨率[34],往往具有大量从自然图像生成的字典元素(n)。此外,A还可以具有特定的结构,可以用于更快的求解。例如,在图像去噪/恢复[2, 16]和修复[30,26]中,A通常基于2D卷积算子/核,因此,结果是一个具有循环块的块循环矩阵(BCCB)或具有循环块的块Toeplitz矩阵(BTTB),其中每个矩阵以不同的方式处理边界条件。在这些情况下,A P R n ˆ n。0是方形的,n是卷积核或滤波器中像素的数量。当同时使用多个卷积核或滤波器时,矩阵 A变得更加“肥”,如在卷积稀疏编码中[6, 14, 17]。0解决大规模 A 的问题(特别是当 m很大时)通常直接与特定应用的性能提升相关联。这个想法已经在人脸识别[28,25]中得到明确提出和讨论。尽管有这个收益,由于其显著的计算负担,这些大规模LASSO问题往往无法解决。相反,qΨk`1 “ Apρkζ ´ cq ´ b.k`1projℓ8,λpAJΨk`1 ` ck{ρkq.c update: ck`1 “ ck ` ρkpAJΨk`1 ´ ζk`1q).ρk`1 “ γρkend17170算法1:用于解决问题(1)的PL-ADMM0输入:b,A,c,“0n,z“0n,Ψ“0m,λ,u1,γą 1 输出:c 当未收敛时执行0c update: 解 p 2 A J A ` u k I n q c k ` 1 “ 2A J b ´ Ψ k ` u k z k z update: z k ` 1 “软阈值 p c k ` 1 ` Ψ k { u k q . Ψ update: Ψ k `1 “ Ψ k ` u k p c k ` 1 ´ z k ` 1 q u k ` 1 “γu k end0A的列往往会被下采样或子采样到可由现有LASSO求解器处理的大小。例如,在许多稀疏跟踪器中,构成 A列的跟踪目标模板被大幅下采样(例如原始补丁大小的25-50倍)[20]。这种策略在速度和准确性之间存在权衡。至于解决问题(1)的技术,文献中存在许多方法,并在这个领域取得了重大进展。出于计算原因,只有一阶LASSO技术对于大规模问题才有兴趣。在这些技术中,使用增广Lagrange方法(ALM)进行优化的方法往往是最高效的[32, 28,33]。在本文中,我们通过首先提升问题(1),然后使用一种类型的ALM在傅里叶域中优化其对偶形式来扩展这种类型的LASSO求解器,特别是交替方向乘子法(ADMM)。这样就不需要解决许多大型线性系统,并且可以使用更简单的操作,即1DFFT和逐元素向量乘积。与最先进的求解器相比,每个ADMM迭代在提升域中的计算复杂度更低,而且非常容易并行化,因为可以利用硬件加速(即简单的GPU实现)。0数学符号。我们使用粗体小写字母和粗体大写字母表示向量和矩阵,分别。I n 是大小为 n ˆ n 的单位矩阵。运算符 d表示逐元素乘积,向量 x 的FFT表示为 ˆ x ,F表示归一化的离散Fouri- er变换(DFT)矩阵。上标 ˚ 和 H表示复共轭和共轭转置操作。最后,循环卷积运算符表示为˚ 。02. 相关工作0LASSO求解器通常是一阶或二阶方法[31,33]。一阶方法通常基于局部线性逼近,最多具有线性局部误差。例子不仅限于近端点[22],并行坐标下降[5],迭代收缩阈值方法(ISTA和FISTA)[1, 7, 22]。多项式方法0算法2:用于解决问题(4)的DL-ADMM0输入:b,A,c,“0n,ζ“0n,Ψ“0m,λ,ρ1,γą 1 输出:c 当未收敛时执行0Ψ update: 解 p ρ k AAJ ` 10也是一阶的。它们包括ADMM,可以应用于问题(1),我们称之为原始LASSO(PL-ADMM)。由于LASSO的凸性,ADMM也可以应用于问题(1)的对偶问题,我们称之为对偶LASSO(DL-ADMM)。至于二阶方法,它们通常计算成本高,包括原始-对偶内点方法[29]。由于一阶方法在计算复杂度和收敛速度方面非常有吸引力,我们简要讨论一些一阶方法来解决问题(1)。问题(1)是两个函数的求和,一个是光滑的,另一个是非光滑的。解决这个问题的一类流行方法使用迭代软阈值(ISTA和FISTA)[1, 7]。由于光滑部分 fp c q是梯度Lipschitz连续的,可以用二次函数将其限制,并找到一系列解 c k ,通过最小化上界收敛到全局最优解:0c_k ` 1 - arg min_c f(p_c_k) + p(c -c_k)q0` 102L_f}c - c_k}^2 + λg(p_c), (2)0其中L_f≥0是f(p_c)的梯度Lipschitz常数(A^JA的最大特征值)。问题(2)有一个闭合形式的解(ℓ1范数的近端算子):0c_k ` 1 - soft(c_k - L_f�f(p_c_k), L_fλ�) (3)0迭代软阈值方法具有次线性收敛速度。一般来说,对于将L_f取为1/α_k的问题,它变成了一般的近端点方法和加速近端梯度方法(APG)。尽管每次迭代的计算复杂度较低,但这两种方法在迭代次数方面收敛较慢[22]。问题(1)可以使用坐标下降法来解决,该方法在每次迭代中更新稀疏编码c的一个条目。更新有一个闭合形式[31]。然而,总体上计算效率低下,因为该方法在每次迭代中需要访问A的一列,其中元素索引只能在GPU上部分并行化[9, 31]。17180问题(1)可以通过直接将ADMM应用于其原始形式来解决,从而得到PL-ADMM,或者将其应用于其对偶形式,从而得到DL-ADMM。对于PL-ADMM,原始-对偶更新步骤在算法(1)中显示。重要的是要注意,PL-ADMM的瓶颈在于c的更新,因为它必须解决一个nˆn的正定线性系统。软p.q运算符是标准的软阈值函数。在这里,每次迭代的复杂度最多为O(p*n^3)*O(p*m*n)。DL-ADMM优化问题(1)的对偶形式。请注意,由于LASSO是凸的并且满足Slater条件,对偶间隙为零,原始和对偶形式导致相同的解。问题(1)的对偶形式可以很容易地表示为:0min Ψ1/4}Ψ}^2 + ΨJb s.t.}AJΨ}8≤λ (4)0DL-ADMM的原始-对偶更新在算法(2)中显示,其中ρk≥0是一个权衡系数,c是原始变量1。类似地,DL-ADMM的瓶颈是解决一个mˆmPD线性系统。每次迭代的复杂度最多为O(p*m^3)*O(p*m*n)。更新ζ很直观,因为它只需要在ℓ8球上进行简单的投影。现在很明显,字典的形状决定了哪种方法(PL-ADMMvs.DL-ADMM)在计算上最有效。换句话说,如果A是高而瘦的(即m>n),则使用PL-ADMM来解决LASSO更可取,而如果A是胖的(即m
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 保险服务门店新年工作计划PPT.pptx
- 车辆安全工作计划PPT.pptx
- ipqc工作总结PPT.pptx
- 车间员工上半年工作总结PPT.pptx
- 保险公司员工的工作总结PPT.pptx
- 报价工作总结PPT.pptx
- 冲压车间实习工作总结PPT.pptx
- ktv周工作总结PPT.pptx
- 保育院总务工作计划PPT.pptx
- xx年度现代教育技术工作总结PPT.pptx
- 出纳的年终总结PPT.pptx
- 贝贝班班级工作计划PPT.pptx
- 变电值班员技术个人工作总结PPT.pptx
- 大学生读书活动策划书PPT.pptx
- 财务出纳月工作总结PPT.pptx
- 大学生“三支一扶”服务期满工作总结(2)PPT.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功