• 论文 • 上一篇    下一篇

核范数和谱范数下广义Sylvester方程最小二乘问题的有效算法

李姣芬1, 宋丹丹1, 李涛1, 黎稳2   

  1. 1. 桂林电子科技大学数学与计算科学学院, 广西高校数据分析与计算重点实验室, 桂林 541004;
    2. 华南师范大学数学科学学院, 广州 510631
  • 收稿日期:2015-12-22 出版日期:2017-05-15 发布日期:2017-07-18
  • 基金资助:

    国家自然科学基金资助项目(11561015,11671158),广西自然科学基金资助项目(2016GXNSFAA380074,2016GXNSFFA380009).

李姣芬, 宋丹丹, 李涛, 黎稳. 核范数和谱范数下广义Sylvester方程最小二乘问题的有效算法[J]. 计算数学, 2017, 39(2): 129-150.

Li Jiaofen, Song Dandan, Li Tao, Li Wen. AN EFFICIENT METHOD FOR SOLVING GENERALIZED SYLVERSTER EQUATION MINIMIZATION PROBLEM UNDER THE NUCLEAR AND SPECTRAL NORM[J]. Mathematica Numerica Sinica, 2017, 39(2): 129-150.

AN EFFICIENT METHOD FOR SOLVING GENERALIZED SYLVERSTER EQUATION MINIMIZATION PROBLEM UNDER THE NUCLEAR AND SPECTRAL NORM

Li Jiaofen1, Song Dandan1, Li Tao1, Li Wen2   

  1. 1. School of Mathematics and Computational Science, Guangxi Colleges and Universities Key Laboratory of Data Analysis and Computation, Guilin University of Electronic Technology, Guilin 541004, China;
    2. School of Mathematical Sciences, South China Normal University, Guangzhou 510631, China
  • Received:2015-12-22 Online:2017-05-15 Published:2017-07-18
本文从数值角度讨论Schatten q-范数下的广义Sylvester方程约束最小二乘问题
minXS||∑i=1NAiXBi-C||q
其中S为闭凸约束集合,Schatten q-范数定义为||M||qq=∑i=1nσiqM),其中σiMM∈Rn×n的奇异值.该问题的几类特殊情形在图像处理、控制论等领域有广泛的应用.q=2即Frobenius范数下该问题已被充分研究,故本文着重讨论q=1,+∞,即核范数和谱范数下该问题的数值求解.采用的数值方法是非精确标准容易执行的部分非精确交替方向法,并结合奇异值阈值算法,Moreau-Yosida正则化算法,谱投影算法和LSQR算法等求解相应子问题.给出算法的收敛性证明,并用数值算例验证其高效可行性.
In this paper,we are concerned with the following generalized Sylvester equation least squares problem of the form
minXS||∑i=1NAiXBi-C||q,
,where||.||stands for the Schatten q-norm,which defined as||M||qq=∑i=1nσiq(M) and σi(M)(i=1,...,n) be the singular values of M∈Rn×n,S be the closed convex set.Some special types of this problem can be applied in image processing and control theory.An inexact version of alternating direction method (ADM) with truly implementable inexactness criteria is proposed for solving this problem under the nuclear norm and spectrum norm,namely q=1,+∞,combining with the Singular Value Threshold algorithm,Moreau-Yosida regularization algorithm,Spectral Projection algorithm and LSQR algorithm to deal with the generated subproblems.Numerical experiments are performed to illustrate the feasibility and efficiency of the proposed algorithm with randomly generated data.

MR(2010)主题分类: 

()
[1] Lei Y, Liao A P. A minimal residual algorithm for the inconsistent matrix equation AXB=C over symmetric matrices[J]. Applied Mathematics and Computation, 2007, 188:499-513.

[2] Li J F, Hu X Y, Zhang L. Numerical solutions of AXB=C for centrosymmetric matrix X under a specified submatrix constraint[J]. Numerical Linear Algebra with Application, 2011, 18:857-873.

[3] Peng Y X, Hu X Y, Zhang L. An iteration method for the symmetric solutions and the optimal approximation solution of the matrix equation AXB=C[J]. Applied Mathematics and Computation, 2005, 160:763-777.

[4] Qiu Y Y, Zhang Z Y, Lu J F. Matrix iterative solutions to then least squares problem of BXAT=F with some linear constraints[J]. Applied Mathematics and Computation, 2007, 185:284-300.

[5] Ding F, Chen T W. On iterative solutions of general coupled matrix equations[J]. SIAM Joural on Control and Optimization, 2006, 44:2269-2284.

[6] Bouhamidi A, Jbilou K, Raydan M. Convex constrained optimization for large-scale generalized Sylvester equations[J]. Computational Optimization and Applications, 2011, 48:233-253.

[7] Bouhamidi A, Enkhbat R, Jbilou K. Conditional gradient Tikhonov method for a convex optimization problem in image restoration[J]. Journal of Computational and Applied Mathematics, 2014, 255:580-592.

[8] Birgin E G, Martinezand J M, Raydan M. Inexact Spectral Projected Gradient methods on convex sets[J]. SIMA Journal on Numerical Analysis, 2003, 23:539-559.

[9] Escalante R, Raydan M. Dykstra's algorithm for constrained least-squares rectangular matrix problems[J]. Computers Mathematics with Applications, 1998, 6:73-79.

[10] Li J F, Hu X Y, Zhang L. Dykstra's algorithm for constrained least-squares doubly symmetric matrix problems[J]. Theoretical Computer Science, 2010, 411:2818-2826.

[11] Yang J F. Yuan X M. Linearized augmented lagrangian and alternating direction methods for nuclear norm minimization[J]. Mathematics of Computation, 2012, 82:301-329.

[12] Xiao Y H, Jin Z F. An alternating direction method for linear-constrained matrix nuclear norm minimization[J]. Numerical Linear Algebra with Application, 2012, 19:541-554.

[13] Li Q N. Alternating direction method for a class of constrained matrix approximation problems[J]. Pacific Journal of Optimization, 2012, 8:765-778.

[14] Boyd S, Parikh N, Chu E, Peleato B, Eckstein J. Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers[J]. Foundations and Trends in Machine Learning, 2011, 3:1-122.

[15] Boley D. Local linear convergence of ADMM on quadratic or linear programs[J]. SIAM Joural on Control and Optimization, 2013, 23:2183-2207.

[16] Han D R, Yuan X M. Local linear convergence of the alternating direction method of multipliers for quadratic programs[J]. SIAM Journal on Numerical Analysis, 2013, 51:3446-3457.

[17] He B S, Yang H, Wang S L. Alternating directions method with self-adaptive penalty parameters for monotone variational inequalities[J]. Journal of Optimization Theory and Applizations, 2000, 106:337-356.

[18] Michael NG K, Wang F, Yuan X M. Inexact alternating direction methods for image recovery[J]. SIAM Journal on Scientific Computing, 2011, 33:1643-1668.

[19] Birgin E G, Mart'?nez J M, Raydan M. Nonmonotone spectral projected gradient methods on convex sets[J]. SIAM Journal on Optimization, 2000, 10:1196-1211.

[20] Paige C C, Saunders A. LSQR:An algorithm for sparse linear equations and sparse least squares[J]. ACM Transactions on Mathematmal Software, 1982, 8:43-71.

[21] Peng Z Y. Solutions of symmetry-constrained least-squares problems[J]. Numerical Linear Algebra with Applications, 2008, 15:373-389.

[22] Li S K, Huang T Z. LSQR iterative method for generalized coupled Sylvester matrix equations[J]. Applied Mathematical Modelling, 2012, 36:3545-3554.

[23] Goldstein T, O'onoghue B, Setzer S, Baraniuk R. Fast alternating direction optimization methods[J], SIAM Journal on Imaging Sciences. 2014, 7:1588-1623.
[1] 李丽丹, 张立卫, 张宏伟. 一类不可微二次规划逆问题[J]. 计算数学, 2021, 43(2): 227-240.
[2] 蔡文银, 徐玲玲. 核范数和谱范数下广义Sylvester方程最小二乘问题的一类改进算法[J]. 计算数学, 2018, 40(4): 387-401.
[3] 温朝涛, 陈小山. 矩阵极分解新的数值方法[J]. 计算数学, 2017, 39(1): 23-32.
[4] 陈小山,黎稳. 关于矩阵方程X+A~*X~(-1)A=P的解及其扰动分析[J]. 计算数学, 2005, 27(3): 303-310.
阅读次数
全文


摘要