二维FIR滤波器约束最小二乘设计的最大分划松弛ADMM算法

doi:10.3969/j.issn.0372-2112.2020.03.013

电子学报 ›› 2020, Vol. 48 ›› Issue (3): 510-517.DOI: 10.3969/j.issn.0372-2112.2020.03.013

二维FIR滤波器约束最小二乘设计的最大分划松弛ADMM算法

马梦瑶¹, 赖晓平¹, 孟海龙²

1. 杭州电子科技大学自动化学院, 浙江杭州 310018;
2. 齐鲁工业大学(山东省科学院)数学与统计学院, 山东济南 250353

收稿日期:2019-06-03 修回日期:2019-10-13 出版日期:2020-03-25 发布日期:2020-03-25
通讯作者: 赖晓平
作者简介:马梦瑶 女,1992年生于河北石家庄,现为杭州电子科技大学自动化学院研究生.研究方向为数字滤波器优化设计.E-mail:mmynice123@163.com;孟海龙 男,1988年生于山东济宁,现为齐鲁工业大学(山东省科学院)讲师.主要研究方向为数字滤波器优化设计.E-mail:hl.meng@foxmail.com
基金资助:
国家自然科学基金（No.61573123，No.U1909209，No.U1509205）

A Maximally Split and Relaxed ADMM for Constrained Least-Squares Design of Two-Dimensional FIR Filters

MA Meng-yao¹, LAI Xiao-ping¹, MENG Hai-long²

1. School of Automation, Hangzhou Dianzi University, Hangzhou, Zhejiang 310018, China;
2. School of Mathematics and Statistics, Qilu University of Technology(Shandong Academy of Sciences), Jinan, Shandong 250353, China

Received:2019-06-03 Revised:2019-10-13 Online:2020-03-25 Published:2020-03-25

摘要/Abstract

摘要： 约束二维有限脉冲响应（Finite Impulse Response，FIR）滤波器，现有设计算法计算复杂度高.针对二维FIR滤波器的约束最小二乘设计，本文应用交替方向乘子法（Alternating Direction Method of Multipliers，ADMM），研究其并行优化方法.通过模型的最大分划，并采用一种松弛技术，提出一个具有高度并行结构的最大分划松弛ADMM算法，分析了算法的计算复杂度，讨论了算法的收敛性，并给出了算法的参数设置方法.实验表明，最大分划松弛ADMM比非松弛的最大分划ADMM收敛快很多；与现有算法相比，提高了计算效率.GPU加速实验中获得的大加速比，表明了所提算法的高度并行性和可扩展性，在图像处理、计算机视觉、模式识别及机器学习等领域有广阔的应用前景.

关键词: 滤波器设计, 多维信号处理, 优化方法, 约束最小二乘, 交替方向乘子法, 计算复杂度, 收敛性分析

Abstract: For constrained two-dimensional (2-D) finite impulse response (FIR) filters,the computational complexity of the existing design algorithms is very high.Based on the alternating direction method of multipliers (ADMM),the parallel optimization of constrained least-squares (CLS) 2-D FIR filters was studied.By maximally splitting the problem into univariate subproblems and utilizing a relaxation technique,a maximally split and relaxed ADMM with a highly parallel computing architecture was proposed.The computational complexity and convergence of the algorithm were analyzed,and a practical scheme for selection of the algorithm parameters was provided.Experimental results show that the proposed maximally split and relaxed ADMM converges much faster than the maximally split unrelaxed ADMM.Compared with existing algorithms,the computational efficiency of the proposed algorithm is improved.The large acceleration ratios obtained by GPU demonstrate the high parallelism and scalability of the proposed algorithm,which is very valuable for applications of the algorithm in image processing,computer vision,pattern recognition and machine learning.

Key words: filter design, multi-dimensional signal processing, optimization method, constrained least-squares, alternating direction method of multipliers, computational complexity, convergence analysis

中图分类号:

TN79

马梦瑶, 赖晓平, 孟海龙. 二维FIR滤波器约束最小二乘设计的最大分划松弛ADMM算法[J]. 电子学报, 2020, 48(3): 510-517.

MA Meng-yao, LAI Xiao-ping, MENG Hai-long. A Maximally Split and Relaxed ADMM for Constrained Least-Squares Design of Two-Dimensional FIR Filters[J]. Acta Electronica Sinica, 2020, 48(3): 510-517.

参考文献

[1] AGGARWAL A,KUMAR M,RAWAT T K.Design of two-dimensional FIR filters with quadrantally symmetric properties using the 2D L₁-method[J].IET Signal Processing,2019,13(3):262-272.
[2] ARAVENA J L,GU G.Weighted least mean square design of 2-D FIR digital filters:the general case[J].IEEE Transactions on Signal Processing,1996,44(10):2568-2578.
[3] CAPIZZI G, SCIUTO G L.A novel 2-D FIR filter design methodology based on a Gaussian-based approximation[J].IEEE Signal Processing Letters,2019,26(2):362-366.
[4] DHABAL S,VENKATESWARAN P.A novel accelerated artificial bee colony algorithm for optimal design of two dimensional FIR filter[J].Multidimensional Systems and Signal Processing,2017,28(2):471-493.
[5] DUMITRESCU B.Trigonometric polynomials positive on frequency domains and applications to 2-D FIR filter design[J].IEEE Transactions on Signal Processing,2006,54(11):4282-4292.
[6] HANNA M T.Weighted least squares design of two-dimensional zero-phase FIR filters in the continuous frequency domain[J]. IEEE Transactions on Circuits and Systems-II,1996,43(7):534-537.
[7] HONG X Y,LAI X P,ZHAO R J.Matrix-based algorithms for constrained least-squares and minimax designs of 2-D FIR filters[J].IEEE Transactions on Signal Processing,2013,64(14):3620-3631.
[8] HONG X Y,LAI X P,ZHAO R J.A fast design algorithm for elliptic-error and phase-error constrained LS 2-D FIR filters[J].Multidimensional Systems and Signal Processing,2016,27(2):477-491.
[9] LAI X P.Optimal design of nonlinear-phase FIR filters with prescribed phase error[J].IEEE Transactions on Signal Processing,2009,57(9):3399-3410.
[10] LAI X P,CHENG Y.A sequential constrained least-square approach to minimax design of 2-D FIR filters[J].IEEE Transactions on Circuits and Systems-II,2007,54(11):994-998.
[11] LANG M C,SELESNICK I W,BURRUS C S.Constrained least squares design of 2-D FIR filters[J].IEEE Transactions on Signal Processing,1996,44(5):1234-1241.
[12] LU W S.A unified approach for the design of 2-D digital filters via semidefinite programming[J].IEEE Transactions on Circuits and Systems-I,2002,49(6):814-826.
[13] LU W S,HINAMOTO T.Two-dimensional digital filters with sparse coefficients[J].Multidimensional Systems and Signal Processing,2011,22(1):173-189.
[14] WANG H,ZENG R,CHENG X M,JIAN Z H.An iterative technique for optimally designing a separable 2D FIR filter[J].IEEJ Transactions on Electrical and Electronic Engineering,2018,13(4):622-626.
[15] ZHAO R J,LAI X P.Efficient 2-D based algorithms for WLS design of 2-D FIR filters with arbitrary weighting functions[J].Multidimensional Systems and Signal Processing,2013,24(3):417-434.
[16] ZHAO R J,LAI X P,HONG X Y,LIN Z P.A matrix-based IRLS algorithm for the least l_p-norm design of 2-D FIR filters[J].Multidimensional Systems and Signal Processing,2019,30(1):1-15.
[17] ZHAO R J,LAI X P,LIN Z P.Weighted least squares design of 2-D FIR filters using a matrix-based generalized conjugate gradient method[J].Journal of the Franklin Institute,2016,353(8):1759-1780.
[18] ZHU W P,AHMAD M O,SWAMY M N S.A closed-form solution to the least-square design problem of 2-D linear-phase FIR filters[J].IEEE Transactions on Circuits and Systems-II,1997,44(12):1032-1039.
[19] ZHU W P,AHMAD M O,SWAMY M N S.A least-squares design approach for 2-D FIR filters with arbitrary frequency response[J].IEEE Transactions on Circuits and Systems-II,1999,46(8):1027-1034.
[20] CEVHER V,BECKER S,SCHMIDT M.Convex optimization for big data:scalable,randomized,and parallel algorithms for big data analytics[J].IEEE Signal Processing Magazine,2014,31(5):32-43.
[21] SLAVAKIS K,GIANNAKIS G B,MATEOS G.Modeling and optimization for big data analytics:(statistical) learning tools for our era of data deluge[J].IEEE Signal Processing Magazine,2014,31(5):18-31.
[22] BOYD S,PARIKH N,CHU E,et al.Distributed optimization and statistical learning via the alternating direction method of multipliers[J].Foundations and Trends^® in Machine Learning,2011,3(1):1-122.
[23] ROBINSON D P,TAPPENDEN R.A flexible ADMM algorithm for big data applications[J].Journal of Scientific Computing,2017,71(1):435-467.
[24] ALMEIDA M S,FIGUEIREDO M.Deconvolving images with unknown boundaries using the alternating direction method of multipliers[J].IEEE Transactions on Image Processing,2013,22(8):3074-3086.
[25] LIAVAS A P,SIDIROPOULOS N D.Parallel algorithms for constrained tensor factorization via alternating direction method of multipliers[J].IEEE Transactions on Signal Processing,2014,63(20):5450-5463.
[26] MAROS M,JALDEN J.ADMM for distributed dynamic beamforming[J].IEEE Transactions on Signal and Information Processing over Networks,2018,4(2):220-235.
[27] MINAEE S,WANG Y.An ADMM approach to masked signal decomposition using subspace representation[J].IEEE Transactions on Image Processing,2019,28(7):3192-3204.
[28] SOUTO N,DINIS R.MIMO detection and equalization for single-carrier systems using the alternating direction method of multipliers[J].IEEE Signal Processing Letters,2016,23(12):1751-1755.
[29] TANG B,LI J,LIANG J L.Alternating direction method of multipliers for radar waveform design in spectrally crowded environments[J].Signal Processing,2018,142:398-402.
[30] WANG W D,WANG J J,ZHANG Z L.Block-sparse signal recovery via e2/e1-2 minimisation method[J].IET Signal Processing,2018,12(4):422-430.
[31] YANG J T,LIN J R,SHI Q J,LI Q.An ADMM-based approach to robust array pattern synthesis[J].IEEE Signal Processing Letters,2019,26(6):898-902.
[32] ZHU Y P,DENG B W,JIANG A M,LIU X F,TANG Y B,YAO X.ADMM-based TDOA estimation[J].IEEE Communications Letters,2018,22(7):1406-1409.
[33] LAI X P,CAO J W,ZHAO R J,LIN Z P.A relaxed ADMM algorithm for WLS design of linear-phase 2D FIR filters[A].Proceedings of the 23rd International Conference on Digital Signal Processing[C].New York:IEEE,2018.1-5.
[34] LAI X P,CAO J W,HUANG X F,WANG T L,LIN Z P.A maximally split and relaxed ADMM for regularized extreme learning machines[J].IEEE Transactions on Neural Networks and Learning Systems,2019,DOI:10.1109/TNNLS.2019.2927385.

二维FIR滤波器约束最小二乘设计的最大分划松弛ADMM算法

A Maximally Split and Relaxed ADMM for Constrained Least-Squares Design of Two-Dimensional FIR Filters

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	王孟依, 陈振兴, 陈智慧. 基于三级LLR检测的广义零填充三模OFDM索引调制系统研究[J]. 电子学报, 2021, 49(7): 1291-1297.
[2]	杨仲平, 杨书宁, 周青松, 张剑云. 基于ADMM的低副瓣阵列区域聚焦照射[J]. 电子学报, 2021, 49(7): 1370-1378.
[3]	侯秀聪, 赖晓平, 曹九稳. 正则化超限学习机的最大分划广义交替方向乘子法[J]. 电子学报, 2021, 49(4): 625-630.
[4]	赖春露, 姚统, 王路. 低延迟有限冲激响应平坦数字微分器的优化设计[J]. 电子学报, 2021, 49(3): 477-483.
[5]	贾志豪, 孙君. 基于子图的边缘串行消息传递算法[J]. 电子学报, 2021, 49(11): 2146-2151.
[6]	张聪炫, 周仲凯, 陈震, 葛利跃, 黎明, 江少锋, 陈昊. 深度学习光流计算技术研究进展[J]. 电子学报, 2020, 48(9): 1841-1849.
[7]	王彪, 慕建君, 焦晓鹏, 王钟斐. 基于改进罚函数的LDPC码分层调度ADMM惩罚译码[J]. 电子学报, 2020, 48(4): 827-832.
[8]	蒋阳, 谢宗霖, 吴亚辉, 吴霞, 储夏. 一种低复杂度空间调制球形译码检测算法[J]. 电子学报, 2018, 46(12): 3008-3013.
[9]	贾正荣, 卢发兴, 吴玲. 基于函数逼近的未来空域窗瞄准点配置方法[J]. 电子学报, 2017, 45(8): 2031-2037.
[10]	宋华军, 刘芬, 陈海华, 张鹤. 一种基于改进PSO的随机最大似然算法[J]. 电子学报, 2017, 45(8): 1989-1994.
[11]	周伟, 孙玉宝, 刘青山, 吴敏. 运动目标检测的l₀群稀疏RPCA模型及其算法[J]. 电子学报, 2016, 44(3): 627-632.
[12]	易云飞, 董文永, 林晓东, 蔡永乐. 求解带软时间窗车辆路径问题的改进伊藤算法及其收敛性分析[J]. 电子学报, 2015, 43(4): 658-664.
[13]	孟超, 孙知信. 中心引力优化CFO算法研究[J]. 电子学报, 2013, 41(4): 698-703.
[14]	刘建军, 吴泽彬, 韦志辉, 肖亮, 孙乐. 基于约束非负矩阵分解的高光谱图像解混快速算法[J]. 电子学报, 2013, 41(3): 432-437.
[15]	金勇, 刘先省, 黄建国, 胡振涛. MIMO声纳方位估计子空间拟合快速算法[J]. 电子学报, 2013, 41(10): 1964-1968.