矩阵填充的子空间逼近法

本文提出了一种矩阵填充的子空间逼近法.该算法以奇异值分解的子空间逼近为基础,运用二次规划技术产生子空间中最接近的可行矩阵,从而获得较好的可行矩阵.该算法通过阈值的奇异值个数逐步减少达到子空间的降秩,最后得到最优低秩矩阵.本文证明了在一定条件下子空间逼近法是收敛的.通过与增广Lagrange乘子算法和正交秩1矩阵逼近法进行随机实验对比,本文所提方法在CPU时间和低秩性上均更有效.     

OPAST子空间跟踪数据压缩半盲多用户检测

基于子空间方法的最小均方误差半盲多用户检测的计算核心是对信号子空间的特征值与特征向量的同时跟踪.仅跟踪计算信号子空间特征向量的子空间跟踪算法不能直接应用于这种检测方法.利用数据压缩技术,提出一种只需跟踪计算信号子空间正交规范基的自适应数据压缩半盲多用户检测.将著名的正交投影逼近子空间跟踪(OPAST)算法应用于这种数据压缩半盲多用户检测,发现OPAST算法具有自然的数据压缩结构,在几乎不增加运算量的情况下即可实现数据压缩半盲多用户检测.仿真实验表明:基于OPAST算法的数据压缩半盲多用户检测具有良好的检测性能.     

一种求解特征值问题的广义共轭梯度算法

本文基于阻尼块反幂法与子空间投影算法设计了一种求解特征值问题的广义共轭梯度算法,同时也实现了相应的计算软件包.然后对算法和计算过程进行一系列的优化来提高算法的稳定性、计算效率和并行可扩展性,使得本文的算法适合在并行计算环境下求解大规模稀疏矩阵的特征值.所形成的软件包不依赖于矩阵和向量的具体结构,可以应用于任意的矩阵向量结构.针对几种典型矩阵的测试结果表明,本文的算法和软件包不但具有良好的数值稳定性和可扩展性,同时相比于SLEPc软件包中的LOBPCG (locally optimal block preconditioned conjugate gradient)和Jacobi-Davidson解法器有2至6倍的效率提升.软件包的网址是https://github.com/pase2017/GCGE-1.0.     

简化全局GMRES算法的扩张及收缩

简化的全局GMRES算法作为求解多右端项线性方程组的方法之一,与标准的全局GMRES算法相比,需要较少的计算量,但对应的重启动方法由于矩阵Krylov子空间维数的限制,收敛会较慢.基于调和Ritz矩阵,提出了简化全局GMRES的扩张及收缩算法.数值实验结果表明,新提出的扩张及收缩算法比标准的全局GMRES算法更为快速高效.     

直觉模糊矩阵幂序列的收敛准则

首先,给出直觉模糊矩阵幂的隶属度和非隶属度的表达形式.其次,定义直觉模糊矩阵的最小正周期数和收敛指数,得到单增的直觉模糊矩阵幂序列是收敛的结论.最后,给出直觉模糊矩阵幂序列收敛的两个充分条件.     

关于幂法的注记

本文对幂法求矩阵主特征值及特征向量存在不完善之处给出了理论分析及计算实例.目前一些“计算方法”书中关于幂法初始向量 x~0选得不当(即 α_1=0)时,给出的计算收敛情况的结论,是不完全的,该文对此做了较深入的分析.     

一类自适应广义交替方向乘子法

广义交替方向乘子法是求解凸优化问题的有效算法.当实际问题中子问题难以求解时,可以采用在子问题中添加邻近项的方法处理,邻近矩阵正定时,算法收敛,然而这也会使迭代步长较小.最新研究表明,邻近矩阵可以有一定的不正定性.本文在基于不定邻近项的广义交替方向乘子法框架下,提出一种自适应的广义交替方向乘子法,动态地选择邻近矩阵,增大迭代步长.在一些较弱的假设下,证明了算法的全局收敛性.我们进行一些初等数值实验,验证了算法的有效性.     

基于均值的Toeplitz矩阵填充的子空间算法

本文提出一种基于均值的Toeplitz矩阵填充的子空间算法.通过在左奇异向量空间中对已知元素的最小二乘逼近,形成了新的可行矩阵;并利用对角线上的均值化使得迭代后的矩阵保持Toeplitz结构,从而减少了奇异向量空间的分解时间.理论上,证明了在一定条件下该算法收敛于一个低秩的Toeplitz矩阵.通过不同已知率的矩阵填充数值实验展示了Toeplitz矩阵填充的新算法比阈值增广Lagrange乘子算法在时间上和精度上更有效.     

含高次逆幂的矩阵方程对称解的双迭代算法

本文研究了在控制理论和随机滤波等领域中遇到的一类含高次逆幂的矩阵方程的等价矩阵方程对称解的数值计算问题.采用牛顿算法求等价矩阵方程的对称解,并采用修正共轭梯度法求由牛顿算法每一步迭代计算导出的线性矩阵方程的对称解或者对称最小二乘解,建立了求这类矩阵方程对称解的双迭代算法,数值算例验证了双迭代算法是有效的.     

简化正交归一约束的自适应噪声子空间估计算法

为避免MUSIC算法的特征分解过程,提出一种噪声子空间的自适应估计算法,能够估计整个噪声子空间.该算法基于正交归一化约束的最小均方(LMS)算法,但对正交归一约束过程进行了简化,较之显式正交归一化约束的LMS算法,简化了运算过程,适合实时计算与工程实现.噪声子空间估计以迭代的方式进行,适合应用于运动信号源的跟踪.仿真结果显示算法具有很好的空间谱估计性能和DOA跟踪性能.     

Restoration of images based on subspace optimization accelerating augmented Lagrangian approach

We propose a new fast algorithm for solving a TV-based image restoration problem. Our approach is based on merging subspace optimization methods into an augmented Lagrangian method. The proposed algorithm can be seen as a variant of the ALM (Augmented Lagrangian Method), and the convergence properties are analyzed from a DRS (Douglas-Rachford splitting) viewpoint. Experiments on a set of image restoration benchmark problems show that the proposed algorithm is a strong contender for the current state of the art methods.     

一类线性约束矩阵不等式及其最小二乘问题

本文主要考虑一类线性矩阵不等式及其最小二乘问题,它等价于相应的矩阵不等式最小非负偏差问题.之前相关文献提出了求解该类最小非负偏差问题的迭代方法,但该方法在每步迭代过程中需要精确求解一个约束最小二乘子问题,因此对规模较大的问题,整个迭代过程需要耗费巨大的计算量.为了提高计算效率,本文在现有算法的基础上,提出了一类修正迭代方法.该方法在每步迭代过程中利用有限步的矩阵型LSQR方法求解一个低维矩阵Krylov子空间上的约束最小二乘子问题,降低了整个迭代所需的计算量.进一步运用投影定理以及相关的矩阵分析方法证明了该修正算法的收敛性,最后通过数值例子验证了本文的理论结果以及算法的有效性.     

A finite-element capacitance matrix method for exterior Helmholtz problems

Summary. We introduce an algorithm for the efficient numerical solution of exterior boundary value problems for the Helmholtz equation. The problem is reformulated as an equivalent one on a bounded domain using an exact non-local boundary condition on a circular artificial boundary. An FFT-based fast Helmholtz solver is then derived for a finite-element discretization on an annular domain. The exterior problem for domains of general shape are treated using an imbedding or capacitance matrix method. The imbedding is achieved in such a way that the resulting capacitance matrix has a favorable spectral distribution leading to mesh independent convergence rates when Krylov subspace methods are used to solve the capacitance matrix equation. Received May 2, 1995     

The modified natural power method for principal component computation

A modified version of the natural power method (NP) for fast estimation and tracking of the principal eigenvectors of a vector sequence is Presented. It is an extension of the natural power method because it is a solution to obtain the principal eigenvectors and not only for tracking of the principal subspace. As compared with some power-based methods such as Oja method, the projection approximation subspace tracking (PAST) method, and the novel information criterion (NIC) method, the modified natural power method (MNP) has the fastest convergence rate and can be easily implemented with only O(np) flops of computation at each iteration, where n is the dimension of the vector sequence and p is the dimension of the principal subspace or the number of the principal eigenvectors. Furthermore, it is guaranteed to be globally and exponentially convergent in contrast with some non-power-based methods such as MALASE and OPERA. Selected from Journal of Fudan University (Natural Science), 2004, 43(3): 275–284     

Computation of matrix functions with deflated restarting

A deflated restarting Krylov subspace method for approximating a function of a matrix times a vector is proposed. In contrast to other Krylov subspace methods, the performance of the method in this paper is better. We further show that the deflating algorithm inherits the superlinear convergence property of its unrestarted counterpart for the entire function and present the results of numerical experiments.     

Splitting and linearizing augmented Lagrangian algorithm for subspace recovery from corrupted observations

Given a set of corrupted data drawn from a union of multiple subspace, the subspace recovery problem is to segment the data into their respective subspace and to correct the possible noise simultaneously. Recently, it is discovered that the task can be characterized, both theoretically and numerically, by solving a matrix nuclear-norm and a ?_2,1-mixed norm involved convex minimization problems. The minimization model actually has separable structure in both the objective function and constraint; it thus falls into the framework of the augmented Lagrangian alternating direction approach. In this paper, we propose and investigate an augmented Lagrangian algorithm. We split the augmented Lagrangian function and minimize the subproblems alternatively with one variable by fixing the other one. Moreover, we linearize the subproblem and add a proximal point term to easily derive the closed-form solutions. Global convergence of the proposed algorithm is established under some technical conditions. Extensive experiments on the simulated and the real data verify that the proposed method is very effective and faster than the sate-of-the-art algorithm LRR.     

预条件广义极小残余新算法

研究Krylov子空间广义极小残余算法(GMRES(m))的基本理论，给出GMRES(m)算法透代求解所满足的代数方程组．深入探讨算法的收敛性与方程组系数矩阵的密切关系，提出一种改进GMRES(m)算法收敛性的新的预条件方法，并作出相关论证．     

Projected Landweber iteration for matrix completion

Recovering an unknown low-rank or approximately low-rank matrix from a sampling set of its entries is known as the matrix completion problem. In this paper, a nonlinear constrained quadratic program problem concerning the matrix completion is obtained. A new algorithm named the projected Landweber iteration (PLW) is proposed, and the convergence is proved strictly. Numerical results show that the proposed algorithm can be fast and efficient under suitable prior conditions of the unknown low-rank matrix.     

线性等式约束优化的既约预条件共轭梯度路径法

采用既约预条件共轭梯度路径结合非单调技术解线性等式约束的非线性优化问题.基于广义消去法将原问题转化为等式约束矩阵的零空间中的一个无约束优化问题,通过一个增广系统获得既约预条件方程,并构造共轭梯度路径解二次模型,从而获得搜索方向和迭代步长.基于共轭梯度路径的良好性质,在合理的假设条件下,证明了算法不仅具有整体收敛性,而且保持快速的超线性收敛速率.进一步,数值计算表明了算法的可行性和有效性.