摘要
为实现稳健的稀疏–低秩矩阵分解,本文首次引入矩阵的S1/2范数以诱导矩阵的低秩性来构建新模型,并在ADMM算法框架下设计了高效的交替阈值迭代算法.该算法采用增广Lagrange乘子技术,在迭代过程中交替更新低秩矩阵和稀疏矩阵.由于这两个矩阵的最优更新具有显式形式,算法整体的计算精度和时间代价得以控制.大量的数值模拟实验说明:相较于目前最好的不精确ALM算法,交替阈值迭代算法的迭代次数与时间代价大幅降低,对噪声更为稳健,分解出的低秩矩阵的秩与稀疏矩阵的稀疏度更接近于真实值.在对监控视频进行背景建模这一实际问题中,交替阈值迭代算法得到的背景矩阵更为低秩,更符合问题先验,且时间代价相较于不精确ALM算法降幅高达一个数量级,这说明新模型与算法能有效解决相关实际问题.
This paper introduces the S1/2-norm for matrices to induce their lower rank, based on which a new model for robust sparse and low-rank matrix decomposition is proposed. To the best of our knowledge, this is the first time that the S1/2-norm for matrices is used to characterize the low-rank property. Inspired by the alternating direction method of multipliers, we propose a computationally efficient algorithm, the alternating threshold iterarive algorithm, for the new model. The proposed Mgorithm adopts the augmented Lagrange multiplier technique and iteratively updates both the low-rank and sparse components in explicit form, making the global computation accuracy and time cost controllable. Numerous numerical simulation experiments are presented to show that the new algorithm requires much less computation time to obtain a more robust decomposition. In additiong the rank of the low-rank component and sparsity of the obtained compared with those of the state-of-the-art algorithm, inexact sparse matrix are much closer to their true values ALM, in solving these problems. When applied to a background modeling application for surveillance video, the new algorithm recovers the background matrix with a lower rank, which is sort of consistent with the prior while modeling, while the time cost is only 10% of that of the inexact ALM algorithm. All these findings confirm that the new model and algorithm can solve practical problems more effectively and efficiently.
出处
《中国科学：信息科学》
CSCD
2013年第6期733-748,共16页
Scientia Sinica(Informationis)
基金
国家自然科学基金(批准号:61075054
60975036
11171272)
国家重点基础研究发展计划(973计划)(批准号:2013CB329404)资助项目
关键词
S1
2范数
稀疏-低秩矩阵分解
快速稳健
交替阈值迭代
S1/2-norm, sparse and low-rank matrix decomposition, efficient and robust, alternative thresholdingiteration
