低秩稀疏矩阵优化问题的模型与算法

低秩稀疏矩阵优化问题是一类带有组合性质的非凸非光滑优化问题.由于零模与秩函数的重要性和特殊性,这类NP-难矩阵优化问题的模型与算法研究在过去十几年里取得了长足发展。本文从稀疏矩阵优化问题、低秩矩阵优化问题、低秩加稀疏矩阵优化问题、以及低秩张量优化问题四个方面来综述其研究现状;其中,对稀疏矩阵优化问题,主要以稀疏逆协方差矩阵估计和列稀疏矩阵优化问题为典例进行概述,而对低秩矩阵优化问题,主要从凸松弛和因子分解法两个角度来概述秩约束优化和秩(正则)极小化问题的模型与算法研究。最后,总结了低秩稀疏矩阵优化研究中的一些关键与挑战问题,并提出了一些可以探讨的问题。     

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

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

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

低秩矩阵恢复问题作为一类在图像处理和信号数据分析等领域中都十分重要的问题已被广泛研究.本文在交替方向算法的框架下,应用非单调技术,提出一种求解低秩矩阵恢复问题的新算法.该算法在每一步迭代过程中,首先利用一步带有变步长梯度算法同时更新低秩部分的两块变量,然后采用非单调技术更新稀疏部分的变量.在一定的假设条件下,本文证明了新算法的全局收敛性.最后通过解决随机低秩矩阵恢复问题和视频前景背景分离的实例验证新算法的有效性,同时也显示非单调技术极大改善了算法的效率.     

低秩矩阵恢复的混合型增广拉格朗日乘子算法CSCD

1引言低秩矩阵恢复问题,又称为鲁棒主成分分析问题或稀疏低秩矩阵分解问题,是指在较少的观测值的基础上恢复出原始矩阵.该问题来源于许多领域,如协同过滤[1,2,3],机器学习[4],图片对齐[5],信号处理[6]和量子态层析成像[7]等等.在文献[8,9,10]中,低秩矩阵恢复问题可以看作是将向量的稀疏表示推广到低秩矩阵的情形,也就是说当矩阵中某些元素严重缺失时,自动识别出损坏的元素并恢复原始矩阵[11].     

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

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

求解结构矩阵低秩逼近的交替投影方法

结构矩阵低秩逼近在图像压缩、计算机代数和语音编码中有广泛应用.首先给出了几类结构矩阵的投影公式,再利用交替投影方法计算结构矩阵低秩逼近问题.数值试验表明新方法是可行的.     

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

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

近似秩函数的一阶导数和二阶导数

矩阵秩优化的光滑函数方法依赖矩阵秩的光滑近似.光滑函数方法涉及光滑近似秩函数的一、二阶导数.因此给出一个具体的近似秩函数的一、二阶导数的计算公式.     

求解无约束优化问题的一个秩一适定方法

在本文中,我们给出一个求解无约束优化问题的秩一适定方法,该方法具有下述较好性质:校正矩阵是对称正定的;在适当条件下,对非凸函数拥有全局收敛性.我们还给出数值检验结果.     

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

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

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

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

Fuzzy矩阵Schein秩的计算复杂性

本文讨论Fuzzy矩阵Schein秩的计算复杂性问题,证明了它是一个"NP-完全问题".首先,刻画了交可分解的Puzzy关系的交分解解集.然后,从Fuzzy关系的交分解与广义分解之间的关系出发,给出了Fuzzy关系广义分解的算法.最后,从Fuzzy关系广义分解的角度来讨论Fuzzy矩阵的Schein秩.指出它与色数问题之间的关系,即Fuzzy矩阵的Schein秩等于由它生成的简单图的色数,从而证明了计算Fuzzy矩阵的Schein秩是一个"NP-完全问题".     

一种改进的求解矩阵补全问题的原始-对偶算法

低秩矩阵补全问题作为一类在机器学习和图像处理等信息科学领域中都十分重要的问题已被广泛研究.一阶原始-对偶算法是求解该问题的经典算法之一.然而实际应用中处理的数据往往是大规模的.针对大规模矩阵补全问题,本文在原始-对偶算法的框架下,应用变步长校正技术,提出了一种改进的求解矩阵补全问题的原始-对偶算法.该算法在每一步迭代过程中,首先利用原始-对偶算法对原始变量和对偶变量进行更新,然后采用变步长校正技术对这两块变量进行进一步的校正更新.在一定的假设条件下,证明了新算法的全局收敛性.最后通过求解随机低秩矩阵补全问题及图像修复的实例验证新算法的有效性.     

数据缺损矩阵低秩分解的正则化方法

数据缺损下矩阵低秩逼近问题出现在许多数据处理分析与应用领域. 由于极高的元素缺损率,数据缺损下的矩阵低秩逼近呈现很大的不适定性, 因而寻求有效的数值算法是一个具有挑战性的课题. 本文系统完整地综述了作者近期在这方面的一些研究进展, 给出了基本模型问题的不适定性理论分析, 提出了两种新颖的正则化方法: 元素约束正则化和引导正则化, 分别适用于中等程度的数据缺损和高度元素缺损的矩阵低秩逼近. 本文同时也介绍了相应快速有效的数值算法. 在一些实际的大规模数值例子中, 这些新的正则化算法均表现出比现有其他方法都好的数值特性.     

对矩阵的秩的讨论

1.说明矩阵的秩与向量组的秩的联系。2.不采用矩阵分块法来证明“左(右)乘列(行)满秩阵,矩阵的秩不变”的结论,以此体现关于可逆阵的秩的结论向行(列)满秩阵的推广,以及借行(列)满秩阵的转置将非方阵问题转化为方阵问题的处理方法。     

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

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

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

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

矩阵优化扰动性分析的若干进展

由于近年来实际问题特别是大数据应用的发展,矩阵优化问题越来越得到优化研究者,甚至是其他领域的研究者的高度关注,成为热点问题.优化问题的扰动性分析是优化理论研究的基础与核心,为包括算法设计在内的优化研究提供重要的理论基础.由于矩阵优化问题的非多面体性,使得相应扰动分析理论的研究本质上与经典的多面体优化问题(非线性规划)不同.结合文献[1,2],简要介绍矩阵优化扰动性分析方面取得的若干最新进展.     

基于受限等距性质的矩阵低秩稀疏逼近误差界

正1引言假设D∈R~(m×n)为实际观测到的高维数据矩阵,则从高维空间中估计一低维子空间的问题,称为矩阵低秩逼近,即估计一低秩矩阵A,使得D与A∈R~(m×n)之间的误差E=D-A最小化,该问题表示如下min‖E‖~2_F=‖D-A‖~2_F s.t.rank(A)≤r,其中r《min(m,n).求解矩阵低秩逼近问题最著名的方法是主成分分析法(Principal components analysis,PCA)[8,14,15],PCA在误差||E||_F较小的情况下,利用奇异值分解     

高维因子模型及其在统计机器学习中的应用

本文综述近年来因子模型研究的最新进展及其在统计机器学习中的应用.因子模型通过较少的因子实现降维,并为协方差矩阵提供了一种低秩加稀疏的结构,不仅受到高维数据分析领域的关注,也被广泛应用于计量经济学、数量金融学、基因组学、神经科学和图像处理等许多科学、工程及人文社科领域的研究中.本文系统阐述利用主成分分析方法提取潜在因子、估计因子载荷、异质结构与整体协方差矩阵的统计推断方法,这套方法被证明可以有效应对当前大数据所表现出的高维性、强相关性、厚尾性和异质性等重大挑战;另外,还重点介绍了高维因子模型在处理协方差矩阵估计、模型选择和多重检验等高维统计学习问题中的作用;最后,通过几个应用实例说明因子模型与现代机器学习问题之间的密切联系,其中包括当下流行的网络分析和低秩矩阵还原等.