核范数随机矩阵求解新方法及其RPCA应用  

A New Method for Solving Nuclear Norm with Random Matrix and Its Application in Robust Principal Component Analysis

作　　者：王臻 杨敏[1] 

机构地区：[1]南京邮电大学自动化学院,江苏南京210023

出　　处：《计算机技术与发展》2017年第12期71-76,共6页Computer Technology and Development

基　　金：国家自然科学基金资助项目(61271234)

摘　　要：RPCA(稳健主成分分析)从原始观测数据中恢复低秩成分和稀疏成分。RPCA常用交替方向法迭代求解,算法的效率取决于核范数优化求解,即SVD分解。而RPCA在计算机视觉应用中,图像和视频等巨大的数据量为大规模数据SVD分解带来了很大困难。采用随机矩阵算法对SVD分解进行改进,分别为计数缩略算法、标准随机k-SVD算法和快速随机k-SVD算法。主要是对原有大规模数据矩阵进行降维随机采样,使用随机投影算法得到原数据矩阵的一个近似,对这个近似矩阵进行QR分解,得到对应的酉矩阵。对酉矩阵进行相关操作,得到与原矩阵SVD相似的结果。算法的时间效率和存储空间得到极大改善。基于单张图像和视频前景检测等仿真实验,表明所提方法大大提高了RPCA迭代优化求解的效率。RPCA （Robust Principal Component Analysis） recovers spazse and low rank components from the original observation data. It commonly uses ADM （ Alternate Direction Method） for iterative solving,the efficiency of which depends on the nuclear norm optimiza- tion solution, that is SVD. The application of RPCA in computer vision,large amounts of data from images and video make it difficult for large-scale data SVD. Therefore, a random matrix algorithm is adopted to improve the SVD,respectively the algorithm of count sketch, the prototype randomized k -SVD and the faster randomized k -SVD. Its main idea is to reduce the size of the original large-scale data matrix and sample randomly. Using the random projection algorithm to obtain an approximation of the original matrix, and operating QR decomposition of this approximate matrix, the unitary matrix corresponding to it is obtained, and then the results which is similar to the SVD can be achieved through correlated operation of unitary matrix. The time and space of the algorithm have been greatly optimized. Simulation based on single image and video foreground detection shows that the proposed method can greatly improve the efficiency of RPCA iterative optimization.

关 键 词：稳健主成分分析 交替方向法 标准随机k—SVD 快速随机k—SVD 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]