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

• 学术论文 • 上一篇    下一篇

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

马梦瑶1, 赖晓平1, 孟海龙2   

  1. 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-yao1, LAI Xiao-ping1, MENG Hai-long2   

  1. 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

摘要: 约束二维有限脉冲响应(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

中图分类号: