不動点への高速な単調近似を実現する写像の新構成法と信号処理工学への応用

一种实现不动点快速单调逼近的新映射构造方法及其在信号处理工程中的应用

• 批准号: 09J09539
• 负责人: 山岸 昌夫
• 金额: $ 1.73万
• 依托单位: Tokyo Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2009
• 资助国家: 日本
• 起止时间: 2009 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-09J09539/
• 关键词: 信号処理; 適応システム同定問題; 単調近似写像; 劣勾配射影; 近接点写像

信号処理は,オンライン機械学習問題や適応フィルタリング問題など,幅広い分野に応用されており,誤差に頑健で低い計算量を有し,安定かつ高速な収束性能をもつアルゴリズムが望まれている.頑健性には「非可微分凸関数や指数型凸関数の値を十分小さくする点を見つける問題」に定式化が有効であり,低計算量で安定した収束の実現には「単調近似写像(解集合の点を不動点とし,それ以外の点は必ず解集合へ近づける写像)」の一つである劣勾配射影が有効である.しかし,劣勾配射影の収束は十分高速ではない.そこで,本研究は劣勾配射影と同程度の計算量で高速な収束を実現する単調近似写像を用いた高性能な信号処理アルゴリズムの構成を目的としている.今年度は,昨年度提案したAdaptive Proximal Forward-Backward Splitting(APFBS,「可微分凸関数と非可微分凸関数の和の最小化問題」の解集合への単調近似写像である前方後方分離型近接点写像を用いた適応システム同定問題の解法の設計原理)の応用を行った.APFBSの枠組みにHuber functionを導入する事で,インパルス性雑音に対する頑健性を有した適応システム同定問題の解法を提案している.これは,Benestyらが提案しているRVSS-NLMSの拡張となっており,RVSS-NLMSに比べ高い推定精度を実現している.さらに,「非可微分凸関数の和の最小化問題」の解集合への単調近似写像であるDouglas-Rachford splitting写像を用いた適応システム同定問題の解法を提案した.この解法は,非可微分凸関数の和を目的関数として扱う事のできる初めての適応システム同定問題の解法である.特に,複数の制約集合の指示関数(制約集合上で0,それ以外で無限大の値をとる関数)の和を目的関数として用いる事で,制約に対する忠実性を厳密に実現できる.適切に目的関数を選ぶ事で,APFBSに匹敵する性能を実現できることを確認している.また,Alternating Direction Method of Multipliers(ADMM,「非可微分凸関数の和の最小化問題」の逐次最小化原理)の計算時間削減法の提案を行った.ADMMの更新は補助問題の解法により構成される.信号処理への応用では,この補助問題に非線形反復解法が必要となることが多く,1回の更新に多大な計算時間を要していた.そこで,ADMMに現れる補助問題を「閉じた解を持つ特別な補助問題」に置き換えても,ADMMと同等の収束性能が実現できることを明らかにしている.また,提案法が計算時間をADMMの21-77%程度に削減できることを数値的に確認している.

Signal Processing: Mechanical learning problem: Adaptive learning problem: Amplitude separation problem: Application problem: Error problem: Low computation cost: Stability problem: High speed beam performance problem: High performance problem: Amplitude separation problem: Application problem: Low computation cost: Stability problem: High performance problem: High performance. For robustness, the problem of "non-differentiable convex number and exponential convex number have very small values" is formulated, and the problem of low computational complexity is stable. However, the problem of "single-tone approximate image writing (solution set points have fixed points, and other points must have solution set close to image writing)" is formulated. The light beam is very high speed. In this paper, we aim to improve the performance of signal processing and the structure of image processing system. Adaptive Proximal Forward-Backward Splitting (APFBS,"Minimizing the Sum of Differentiable Convex Numbers and Non-Differentiable Convex Numbers," A Design Principle for Solving Uniformly Adjusted Approximation Problem of Solution Set,"A Design Principle for Solving Uniformly Adjusted Approximation Problem of Front and Rear Separated Near-Contact Image Writing," A Design Principle for Solving Uniformly Determined Problem of Solution Set,"A Design Principle for Solving Uniformly Adjusted Approximation Problem of Solution Set," A Design Principle for Solving Uniformly Adjusted Approximation Problem of Solution Set,"A Design Principle for Solving Uniformly Adjusted Approximation Problem of Solution Set," A Design Principle for Solving Uniformly Adjusted Approximation Problem of Solution Set,"A Design Principle for Uniformly Adjusted Approximation Problem of Solution Set," A Design Principle for Solving Uniformly Adjusted Approximation Problem of Solution Set," A Design Principle for Uniformly Adjusted Approximation Problem of Solution Set," A Design Principle for Uniformly Adjusted Approximation Problem of Solution Set," A Design Principle for Uniformly Adjusted Approximation Problem of Solution Set," A Design Principle for A solution to the problem of robustness of the system is proposed. In contrast, Benesty's proposal to improve the accuracy of RVSS-NLMS estimation was implemented in RVSS-NLMS. In this paper, we propose a solution to the problem of minimizing the sum of non-differentiable convex relations by solving the set problem and the uniform approximation problem by using Douglas-Rachford splitting. The solution of this problem is: the sum of nondifferentiable convex relations and objective relations. In particular, the indicator relations of a plurality of constraint sets (the relations of infinite values outside the constraint set are 0) and the sum of the objective relations are closely related to the fidelity of the constraint set. APFBS performance is verified by selecting the appropriate target number. A proposal for a computational time reduction method for Alternating Direction Method of Multipliers (ADMM, Principle of Successive Minimization of the Sum of Nondifferentiable Convex Relations). Signal processing is not only useful, but also necessary for solving non-linear iterative problems. In this case, ADMM presents a subsidy problem called "closed solution to special subsidy problem." In this case, ADMM presents equivalent bundle performance. The proposed method reduces the calculation time of ADMM by 21 - 77%.

项目成果

Two improvements of the fast iterative shrinkage/thresholding algorithm--- Overrelaxation and weak convergence

快速迭代收缩/阈值算法的两个改进——过度松弛和弱收敛

• 发表时间: 2011
• 作者: M.Yamagishi;I.Yamada
• 通讯作者: I.Yamada

Acceleration of adaptive proximal forward-backward splitting method for sparse system identification

稀疏系统辨识的自适应近端前向后向分裂法加速

• 发表时间: 2010
• 作者: M.Yamagishi;M.Yukawa;I.Yamada
• 通讯作者: I.Yamada

Two variants of alternating direction method of multipliers without inner iterations and their application to image super-resolution

无内迭代乘法器交替方向法的两种变体及其在图像超分辨率中的应用

• 发表时间: 2012
• 作者: Masao Yamagishi;Shunsuke Ono;Isao Yamada
• 通讯作者: Isao Yamada

L1ノルムのMoreau envelopeを用いたスパースシステムの適応同定法に関する一考察

L1范数莫罗包络的稀疏系统自适应辨识方法研究

• 发表时间: 2011
• 作者: 山本誉之;山岸昌夫;山田功
• 通讯作者: 山田功

Fixed-Point Algorithms for Inverse Problems in Science and Engineering

• DOI: 10.1007/978-1-4419-9569-8
• 发表时间: 2011-06
• 作者: Heinz H. Bauschke;R. Burachik;P. Combettes;V. Elser;D. R. Luke;Henry Wolkowicz