计算机科学 ›› 2021, Vol. 48 ›› Issue (8): 66-71.doi: 10.11896/jsjkx.200900055

• 数据库&大数据&数据科学* • 上一篇    下一篇

基于耦合随机投影的张量填充方法

杨宏鑫, 宋宝燕, 刘婷婷, 杜岳峰, 李晓光   

  1. 辽宁大学信息学院 沈阳110036
  • 收稿日期:2020-09-07 修回日期:2020-11-17 发布日期:2021-08-10
  • 通讯作者: 李晓光(xgli@lnu.edu.cn)
  • 基金资助:
    国家自然科学基金(U1811261)

Tensor Completion Method Based on Coupled Random Projection

YANG Hong-xin, SONG Bao-yan, LIU Ting-ting, DU Yue-feng, LI Xiao-guang   

  1. School of Information,Liaoning University,Shenyang 110036,China
  • Received:2020-09-07 Revised:2020-11-17 Published:2021-08-10
  • About author:YANG Hong-xin,born in 1990,postgra-duate,Ph.D,lecturer,is a member of China Computer Federation.His main research interests include image processing and matrix analysis.(yanghongxin@lnu.edu.cn)LI Xiao-guang,born in 1973,postgra-duate,Ph.D,professor,Ph.D supervisor,is a member of China Computer Federation.His main research interests include data mining,machine learning and graph data analysis.
  • Supported by:
    National Natural Science Foundation of China(U1811261).

摘要: 现代信号处理中,越来越多的领域都需要存储和分析规模大、维度高、结构复杂的数据。张量作为向量和矩阵的高阶推广,在保证原始数据内在关系的前提下,可以更为直观地表示大规模数据的结构性。张量填充作为张量分析的一个重要分支,目前已被广泛应用于协同过滤、图像恢复、数据挖掘等领域。张量填充指从被噪声污染或存在数据缺失的张量中恢复出原始张量的手段,文中着眼于当前张量填充技术中时间复杂度较高的缺点,提出了基于耦合随机投影的张量填充方法。该方法的核心包括两个部分:耦合张量分解以及随机投影矩阵。通过随机投影矩阵,文中将原始高维张量投影到低维空间内生成替代张量,同时在低维空间内实现张量填充,进而提高算法的执行效率。同时,所提算法还利用耦合张量分解将填充后的低维张量映射到高维空间,从而实现原始张量的重构。最后,通过实验分析了所提算法的有效性和高效性。

关键词: 张量, 张量填充, 耦合随机投影, 耦合张量分解, 随机投影矩阵

Abstract: In modern signal processing,the date with large scale,high dimension and complex structure need to be stored and analyzed in more and more fields.Tensors,as a high-order extension of vectors and matrices,can more intuitively represent the structure of high-dimensional data while maintaining the inherent relationship of the original data.Tensor completion plays an important role in recovering the original tensor from the noisy or missing tensor,which can be considered as an important branch of tensor and has been widely used in collaborative filtering,image restoration,data mining and other fields.This paper focuses on the drawbacks of high time complexity in the current tensor completion technology,and proposes a new method based on coupled random projection.The essential point of the proposed method consists of two parts:coupled tensor decomposition (CPD) and random projection matrix (RPM).Through the RPM,the original high-dimensional tensor is projected into the low-dimensional space to generate alternative tensor,and the tensor completion is realized in the low-dimensional space,and thus the efficiency of our method can be improved.Then,the CPD is used to realize the reconstruction of the original tensor by mapping the completed low-dimensional tensor into the high-dimensional space.Finally,the experiments are used to analyze the effectiveness and efficiency of the proposed method.

Key words: Tensors, Tensor completion, Coupled random projection, Coupled tensor decomposition, Random projection matrix

中图分类号: 

  • TP311
[1]ZHANG Y.Improved Sample Image Inpainting Algorithm Based on Image Structure Tensor[J].Journal of Chongqing University of Technology(Natural Science),2020,34(3):145-151.
[2]XIE Q,ZHANG Y,MENG D Y.Survey on Tensor SparsityMeasure[J].Journal of Chongqing University of Posts and Tele-communications(Natural Science Edition),2019,31(3):340-347.
[3]RENNIE D M,SREBRO N.Fast Maximum Margin Matrix Factorization for Collaborative Prediction[C]//Proceedings of International Conference on Machine Learning.2005:713-719.
[4]CANRAL R S,TORRE F D,COSTCIRA J P,et al.MatrixCompletion for Multi-Lable Image Classification[C]//Procee-dings of Neural Information Processing Systems.2011:120-128.
[5]KOLDA T,BADER B.Tensor decompositions and applications[J].SIAM Review,2009,51 (3):455-500.
[6]CHEN D B,YANG X M.Block-coded Video Deblocking Based on Low-rank Tensor Recovery[J].Computer Science,2016,43(9):280-283.
[7]LIU J,YE J,et al.Tensor completion for estimating missing va-lues in visual data[C]// Proceedings of IEEE International Conference on Computer Vision.2009:2114-2121.
[8]LIU J,MUSIALSKI P,WONKA P,et al.Tensor completion for estimating missing values in visual data[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35 (1):208-220.
[9]GANDY S,RECHT B,YAMADA I.Tensor completion andlow-n-rank tensor recovery via convex optimization[J].Inverse Problems,2011,27(2):025010.
[10]ACAR E,DUNLAVY D M,KOLDA T G,et al.Scalable tensor factorizations for incomplete data[J].Chemometrics and Intelligent Laboratory Systems,2011,106(1):41-56.
[11]XU Y,HAO R,YIN W,et al.Parallel matrix factorization for low-rank tensor completion[J].Inverse Problems and Imaging,2015,9(2):601-624.
[12]SILVA C D,HERRMANN F J.Optimization on the Hierarchical Tucker manifold-Applications to tensor completion[J].Li-near Algebra and Its Applications,2015,481:131-173.
[13]BIGONI D,ENGSIG-KARUP A P,MARZOUK Y M.Spectral tensor-train decomposition[J].Mathematics,2014,38(4):2405-2439.
[14]XU Z,YAN F,QI Y.Bayesian Nonparametric Models for Multiway Data Analysis[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2015,37(2):475-487.
[15]FENG Y L,SUN W J.A Matrix Completion method based on Fast Random Projection[J].Computer Applications and Software,2019(9):106-110.
[16]ARRIAGA R I,RUTTER D,CAKMAK M,et al.Visual Categorization with Random Projection[J].Neural Computation,2015,27(10):2132-2147.
[17]YOST D.The Johnson-Lindenstrauss space[J].Extracta Mathe-maticae,2007,12(2):185-192.
[1] 水泽农, 张星宇, 沙朝锋. 基于最优输运和k-近邻的离群文档检测[J]. 计算机科学, 2021, 48(7): 105-111.
[2] 桑春艳, 胥文, 贾朝龙, 文俊浩. 社交网络中基于注意力机制的网络舆情事件演化趋势预测[J]. 计算机科学, 2021, 48(7): 118-123.
[3] 赵敏, 刘惊雷. 基于高斯场和自适应图正则的半监督聚类[J]. 计算机科学, 2021, 48(7): 137-144.
[4] 吴成凤, 蔡莉, 李劲, 梁宇. 基于多源位置数据的居民出行频繁模式挖掘[J]. 计算机科学, 2021, 48(7): 155-163.
[5] 刘聃, 郭绍忠, 郝江伟, 许瑾晨. 基于SIMD扩展部件的长向量超越函数实现方法[J]. 计算机科学, 2021, 48(6): 26-33.
[6] 刘蕴涵, 沙朝锋, 牛军钰. 基于Stack Overflow的数据库相关主题分析[J]. 计算机科学, 2021, 48(6): 48-56.
[7] 朱润泽, 秦小麟, 刘嘉琛. 基于查询对象的路网Skyline查询中Why-not问题的研究[J]. 计算机科学, 2021, 48(6): 57-62.
[8] 郭文, 尹童灵, 张天柱, 徐常胜. 时间一致性保持的多任务稀疏深度表达视觉跟踪[J]. 计算机科学, 2021, 48(6): 110-117.
[9] 刘小龙, 韩芳, 王直杰. 基于知识表示的联合问答模型[J]. 计算机科学, 2021, 48(6): 241-245.
[10] 陈艳, 陈佳晴, 陈星. 基于层次标签的机器学习流程组装[J]. 计算机科学, 2021, 48(6A): 306-312.
[11] 刘嘉琪, 刘贝丽, 彭韬, 段江, 康立, 陈智. 基于区块链的音频版权存证模型[J]. 计算机科学, 2021, 48(6A): 438-442.
[12] 唐飞, 陈云龙, 冯卓. 基于区块链和代理重加密的电子处方共享方案[J]. 计算机科学, 2021, 48(6A): 498-503.
[13] 王晓敏, 苏静, 姚兵. 基于格思想的图结构相似问题的算法[J]. 计算机科学, 2021, 48(6A): 543-551.
[14] 程学林, 杨小虎, 卓崇魁. 基于组织架构的数据权限控制模型研究与实现[J]. 计算机科学, 2021, 48(6A): 558-562.
[15] 黄双芹, 刘英博, 黄向生. 模型驱动开发工具的自动化测试技术研究[J]. 计算机科学, 2021, 48(6A): 568-571.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 .
[2] 杨羽琦,章国安,金喜龙. 车载自组织网络中基于车辆密度的双簇头路由协议[J]. 计算机科学, 2018, 45(4): 126 -130 .
[3] 李昊阳,符云清. 基于标签聚类与项目主题的协同过滤推荐算法[J]. 计算机科学, 2018, 45(4): 247 -251 .
[4] 王振武,吕小华,韩晓辉. 基于四叉树分割的地形LOD技术综述[J]. 计算机科学, 2018, 45(4): 34 -45 .
[5] 张小华, 黄波. 基于Bayes-MeTiS网格划分的3D几何重构[J]. 计算机科学, 2018, 45(6): 265 -269 .
[6] 刘菁华, 陈婧. 一种基于平面运动视差不变性的立体视频整帧丢失重建技术[J]. 计算机科学, 2018, 45(6): 270 -274 .
[7] 李姗姗,陈莉,张永新,袁娅婷. 基于RPCA的图像模糊边缘检测算法[J]. 计算机科学, 2018, 45(5): 273 -279 .
[8] 李月,王芳. 基于NVM的存储安全综述[J]. 计算机科学, 2018, 45(7): 53 -60 .
[9] 罗建桢,蔡君,刘燕,赵慧民. 一种基于内容流行度和社团重要度的ICN缓存与替换策略[J]. 计算机科学, 2018, 45(7): 116 -121 .
[10] 刘枭, 王晓国. 基于概率图的银行电信诈骗检测方法[J]. 计算机科学, 2018, 45(7): 122 -128 .