投审稿平台


投稿指南
下载专区
地  址:北京市海淀区中关村科学院
南路6号中国科学院计算所342号 [地图]
《计算机辅助设计与图形学学报》编辑部
邮政编码:100190
电  话:010-62562491
          010-62600342
订阅信息
ISSN      1003-9775
CN        11-2925/TP
邮发代号:82-456
单    价:80.00元
全年订价:960.00元
在线期刊

基于随机奇异值分解的快速矩阵补全算法及其应用

冯 栩1,2), 李可欣1,2), 喻文健1,2)*, 黎耀航3)
1) (清华信息科学与技术国家实验室(筹) 北京 100084)2) (清华大学计算机科学与技术系 北京 100084)3) (Department of Computer Science, Old Dominion University, Norfolk VA 23529 USA)
分类号: TP391.41
出版年,卷(期):页码: 2017 , 29 ( 12 ): 2343-2348 冯栩
摘要: 为了在保证结果精度的情况下加快运算速度, 改进了矩阵补全的代表性算法——奇异值门限(SVT)算法. 首先对于输入矩阵进行规整化处理, 之后在每一步的迭代中使用奇异值分解算法对矩阵进行恢复. 由于每个迭代步中奇异值分解的计算量很大, 文中借鉴随机矩阵奇异值分解算法, 提出使用块克雷洛夫迭代近似奇异值分解算法和子空间复用技术的快速SVT算法. 使用彩色图像和电影评分矩阵对算法进行实验的结果表明, 快速SVT算法在不影响图像恢复和评分数据预测效果的同时显著地缩短了计算时间; 在图像恢复和电影评分预测的实验中, 分别取得了高达7.1倍和3.2倍的加速比.
关键词: 矩阵补全; 奇异值分解; 奇异值门限算法; 随机矩阵算法; 图像恢复; 推荐系统; 子空间复用
Fast Matrix Completion Algorithm Based on Randomized Singular Value Decomposition and its Applications
Feng Xu1,2), Li Kexin1,2), Yu Wenjian1,2)*, and Li Yaohang3)
1) (Tsinghua National Laboratory for Information Science and Technology, Tsinghua University, Beijing 100084)2) (Department of Computer Science and Technology, Tsinghua University, Beijing 100084)3) (Department of Computer Science, Old Dominion University, Norfolk VA 23529 USA)
abstract: The purpose of this work is to accelerate the singular value thresholding (SVT) algorithm, which is a representative algorithm of matrix completion, while preserving the accuracy. The algorithm first normalizes the input matrix, then uses singular value decomposition (SVD) to complete the matrix. Because in each iteration step of the SVT algorithm the SVD of the data matrix is computed, the overall computational time of the SVT algorithm is significant. In this paper, based on the recent results on randomized SVD algorithms we propose an improved SVT algorithm. It utilizes the block Krylov iteration scheme for computing approximate SVD to replace the standard SVD, and is based on a technique of recycling the range subspace. As the result, the proposed algorithm reduces the runtime of SVT algorithm remarkably. Our algorithm is tested for the problems of recovering color images and estimating film ratings. And, it is compared with the SVT algorithms using the standard SVD and a fast truncated SVD, respectively. The experimental results show that the proposed techniques largely accelerate the SVT algorithm. The speedup ratio is up to 7.1 and 3.2 for the image recovery problem and the film-rating estimation problem, respectively.
keyword: matrix completion; singular value decomposition; singular value thresholding algorithm; randomized
 
Copyright © 2004《计算机辅助设计与图形学学报》版权所有
电话:010-62600342 传真:010-62562491
E_mail:jcad@ict.ac.cn