低秩稀疏矩阵恢复的快速非单调交替极小化方法

针对低秩稀疏矩阵恢复问题的一个非凸优化模型,本文提出了一种快速非单调交替极小化方法.主要思想是对低秩矩阵部分采用交替极小化方法,对稀疏矩阵部分采用非单调线搜索技术来分别进行迭代更新.非单调线搜索技术是将单步下降放宽为多步下降,从而提高了计算效率.文中还给出了新算法的收敛性分析.最后,通过数值实验的比较表明,矩阵恢复的非单调交替极小化方法比原单调类方法更有效.     

低秩矩阵优化若干新进展

低秩矩阵优化是一类含有秩极小或秩约束的矩阵优化问题,在统计与机器学习、信号与图像处理、通信与量子计算、系统识别与控制、经济与金融等众多学科领域有着广泛应用,是当前最优化及其相关领域的一个重点研究方向.然而,低秩矩阵优化是一个NP-难的非凸非光滑优化问题,其研究成果并非十分丰富,亟待进一步深入研究.主要从理论和算法两个方面总结和评述若干新结果,同时列出相关的重要文献,奉献给读者.     

用随机奇异值分解算法求解矩阵恢复问题

本文研究了大型低秩矩阵恢复问题.利用随机奇异值分解（RSVD）算法,对稀疏矩阵做奇异值分解.该算法与Lanczos方法相比,在误差精度一致的同时运算时间大大降低,且该算法对相对低秩矩阵也有效.     

用随机奇异值分解算法求解矩阵恢复问题（英文）

本文研究了大型低秩矩阵恢复问题.利用随机奇异值分解(RSVD)算法,对稀疏矩阵做奇异值分解.该算法与Lanczos方法相比,在误差精度一致的同时运算时间大大降低,且该算法对相对低秩矩阵也有效.     

基于改进的不动点迭代算法的低秩Gram矩阵的恢复

仿射限制条件下的低秩矩阵的恢复问题广泛地出现在控制、信号处理及系统识别等许多领域中.此问题可以凸松弛为带仿射限制条件的矩阵核范数的极小化问题.尽管后者能够转化为标准的半定规划问题求解,但是对于规模较大的矩阵其产生的计算量也很大.为此提出一种新的求解Gram矩阵核范数极小化问题的一阶算法-改进的不动点迭代算法(FPC-BB),并给出了算法的收敛性分析.算法以不动点迭代算法(FPC)中的算子分裂技术为基础,通过改进阈值算子Tv来求解低秩Gram矩阵的恢复问题.同时,还引入Barzilai-Borwein技术进行参数的选取,提高了算法的收敛速度.数值实验显示算法不仅能够很快地将低秩Gram矩阵精确地恢复出来,对于一些非低秩矩阵的恢复问题也能得出较好的结果.     

求解低秩矩阵恢复问题的非单调交替梯度方向法

低秩矩阵恢复问题作为一类在图像处理和信号数据分析等领域中都十分重要的问题已被广泛研究.本文在交替方向算法的框架下,应用非单调技术,提出一种求解低秩矩阵恢复问题的新算法.该算法在每一步迭代过程中,首先利用一步带有变步长梯度算法同时更新低秩部分的两块变量,然后采用非单调技术更新稀疏部分的变量.在一定的假设条件下,本文证明了...     

求解鲁棒主成分分析的新交替下降方向法

鲁棒主成分分析作为统计与数据科学领域的基本工具已被广泛研究,其核心原理是把观测数据分解成低秩部分和稀疏部分.本文基于鲁棒主成分分析的非凸模型,提出了一种新的基于梯度方法和非单调搜索技术的高斯型交替下降方向法.在新算法中,交替更新低秩部分和稀疏部分相关的变量,其中低秩部分的变量是利用一步带有精确步长的梯度下降法进行更新,...     

张量鲁棒主成分分析的增广拉格朗日交替方向方法

张量的鲁棒主成分分析是将未知的一个低秩张量与一个稀疏张量从已知的它们的和中分离出来.因为在计算机视觉与模式识别中有着广阔的应用前景,该问题在近期成为学者们的研究热点.本文提出了一种针对张量鲁棒主成分分析的新的模型,并给出交替方向极小化的求解算法,在求解过程中给出了两种秩的调整策略.针对低秩分量本文对其全部各阶展开矩阵进行低秩矩阵分解,针对稀疏分量采用软阈值收缩的策略.无论目标低秩张量为精确低秩或近似低秩,本文所提方法均可适用.本文对算法给出了一定程度上的收敛性分析,即算法迭代过程中产生的任意收敛点均满足KKT条件.如果目标低秩张量为精确低秩,当迭代终止时可对输出结果进行基于高阶奇异值分解的修正.针对人工数据和真实视频数据的数值实验表明,与同类型算法相比,本文所提方法可以得到更好的结果.     

基于非凸加权核范数的目标视频帧选取

主要研究的是基于监控视频的显著前景目标帧选取问题.首先利用非凸加权核范数进行低秩背景估计.然后使用Markov随机场对稀疏前景目标位置矩阵进行估计,并提取出前景目标.最后定义显著前景目标区域,根据连通域面积大小,采用阈值法判断当前帧是否为显著目标帧,并采用F值来验证该模型的准确率.结果显示,模型在Campus、Curtain、Escalator、Fountain、Hall、Lobby和Office这7个数据集上的F值均超过90%,说明该模型普遍具有较高的鲁棒性和准确性.     

大规模严格凸二次规划问题一个新算法

根据广义乘子法的思想,将具有等式约束和非负约束的凸二次规划问题转化只有非负约束的简单凸二次规划,通过简单凸二次规划来得到解等式约束一非负约束的凸二次规划新算法,新算法不用求逆矩阵,这样可充分保持矩阵的稀疏性,用来解大规模稀疏问题,数值结果表明：在微机４８６／３３上就能解较大规模的凸二次规划。     

去除稀疏和结构化噪声的交替方向增强拉格朗日算法

图像和视频去噪是数字图像处理的必要环节之一.为了去除图像和视频中广泛存在的稀疏噪声和结构化噪声,提出了一种分离低秩矩阵、稀疏矩阵和结构化矩阵的优化模型一主成分离群点追求.在交替方向最小化思想的基础上,利用增强拉格朗日乘子法求解主成分离群点追求模型,设计了求解模型的交替方向增强拉格朗日(ADAL)算法,加入了一种连续技术以提高算法的收敛速率.仿真实验结果表明,提出的模型和算法能够有效去除不同尺寸矩阵的不同比例的稀疏噪声和结构化噪声.     

处理噪声问题的泰勒展开交替最小化算法

为了处理图像、计算机视觉和生物信息等领域中广泛存在的稀疏大噪声和高斯噪声问题,提出了一种利用交替方向最小化思想求解主成分追求松弛模型的泰勒展开交替最小化算法(TEAM).采用推广泰勒展开和收缩算子等技术推导出低秩矩阵和稀疏大噪声矩阵的迭代方向矩阵,加入连续技术提高算法的收敛速率,设计出TEAM算法的求解步骤.实验中,将TEAM算法与该领域的顶级算法作分析对比.结果表明,TEAM算法时间优势明显,误差优势略好.     

压缩感知邻域中的带限制性等距常数（英文）

众所周知,带限制性等距常数是压缩感知领域中的核心概念.在压缩感知理论发展的十几年历史中,几乎所有的重要理论结果都与这个概念密切相关.此文主要是总结近十余年来带限制性等距常数的若干重要结果,特别是最佳上界的发现.我们首先表明许多具有最少行数的随机矩阵满足这个性质,而一些确定性矩阵也满足这个性质.但是与随机矩阵相比,确定性矩阵的行数要明显多.其次,我们给出了刻画l_1优化模型范数最小解与最稀疏解等价性的最佳带限制性等距常数,对于l_p(0p 1)优化模型也得到了类似结果.最后,我们延拓这些结果到低秩矩阵恢复以及在字典表示下具有稀疏信号恢复的情形.     

《数值计算与计算机应用》2020年第41卷第4期摘要

刘伟峰.高可扩展、高性能和高实用的稀疏矩阵计算研究进展与挑战[J].数值计算与计算机应用,2020,41(3):259-281.摘要:稀疏矩阵算法是超级计算领域的热点和难点研究内容之一.本文从高可扩展、高性能和高实用这三个角度,对过去30年来国内外稀疏矩阵计算的部分主要研究工作进行了综述.并配合在三个GPU上十余个稀疏BLAS算法的测试数据.     

脉冲噪声下图像去模糊非光滑非凸最小化问题的近端线性化最小化算法

去除脉冲噪声是图像复原中的重要任务之一.我们提出一类非光滑非凸模型来恢复模糊和脉冲噪声污染的图像,该模型具有灵活的先验信息引入机制,如盒子约束或低秩等.为了求解所提非凸问题,我们采用近端线性化最小化算法.对于算法中的子问题,我们运用交替方向乘子法.在目标函数满足Kurdyka-Lojasiewicz性质的假设下,我们证明所提算法的全局收敛性.数值实验表明,在主观和客观质量评价方面,我们的方法优于$\ell_{1}$TV和非凸TV模型.     

有界灰矩阵的非奇异性与秩

本文重新论述有界灰方阵的非奇异性判别问题,提出“条件非奇异”与“最大非奇异子元值域”的新概念,指出现有结果的局限性,给出了一些实用判据,并对灰逆阵的存在性条件与定义域作了研究.此外,本文又提出有界灰矩阵的“灰秩”的新概念与算法,建立了有界灰矩阵恒满秩、恒不满秩、条件满秩的判据。     

稀疏降维的近似凸壳覆盖一类分类器构造

针对高维数据集常常存在冗余和维数灾难,在其上直接构造覆盖模型难以充分反映数据分布信息的问题,提出一种基于稀疏降维近似凸壳覆盖模型.首先采用同伦算法求解稀疏表示中l_1优化问题,通过稀疏约束自动获取合理近邻数并构建图,再通过LPP(Locality Preserving Projections)来进行局部保持投影,进而实现对高维空间快速有效地降维,最后在低维空间通过构造近似凸壳覆盖实现一类分类.在UCI数据库,MNIST手写体数据库和MIT-CBCL人脸识别数据库上的实验结果证实了方法的有效性,与现有的一类分类算法相比,提出的覆盖模型具有更高的分类正确率.     

低秩表示实现鲁棒的CT和MR图像分割

由于图像中的噪声和复杂性,传统的图像分割方法并不总是能够捕捉到所有细节,即可能会忽略相邻像素的属性或者将图像的不同部分合并在一起.为了充分利用可用信息,利用低秩表示(LRR)和鲁棒主成分分析(RPCA)模型的优点,提出了一种新的图像分割方法,通过模糊c均值(FCM)方法对低秩亲和矩阵进行聚类来获得分割结果.在整个方法中,低秩分量是图像的主要信息,是通过求解RPCA模型获得的,而亲和矩阵表示全局结构,则是通过求解LRR模型获得的.在实验部分,使用计算机断层扫描(CT)图像分割来评估本文方法,结果显示在准确性和鲁棒性方面都有了显著改进.与现有一些算法相比,本文算法对异常值更加鲁棒,并尽可能地保留了图像的细节信息.     

基于新的Hessian近似矩阵的稀疏重构算法

一般来说,基于二次近似模型的优化算法具有良好的数值表现.然而,当基于二次近似模型的优化算法求解大规模优化问题时,若使用稠密矩阵近似目标函数在迭代点的Hessian矩阵,需要花费大量的计算成本和存储成本,因此设计Hessian矩阵合适的标量近似矩阵特别重要.对于正则化模型,利用最近三次迭代的信息,设计粗糙的标量矩阵,使用拟牛顿公式进行更新,结合近似最优梯度法的思想和梯度法的延迟策略,构造Hessian矩阵新的含有更多二阶信息的标量近似矩阵.结合非单调线搜索,提出基于新的Hessian近似矩阵的稀疏重构算法,并进行收敛性分析.实验结果表明,与经典稀疏重构算法算法相比,基于新的Hessian近似矩阵的稀疏重构算法在重构效果相似的情况下能较大地减少迭代次数和较快地重构信号.     

压缩感知和稀疏优化简介

介绍压缩感知和稀疏优化的基本概念、理论基础和算法概要. 压缩感知利用原始信号的稀疏性,从远少于信号元素个数的测量出发,通过求解稀疏优化问题来恢复完整的原始稀疏信号. 通过一个小例子展示这一过程,并以此说明压缩感知和稀疏优化的基本理念. 接着简要介绍用以保证l₁凸优化恢复稀疏信号的零空间性质和RIP条件. 最后介绍求解稀疏优化的几个经典算法.