Numerical computing the rank of a matrix is a fundamental problem in scientific computation. The data sets generated by Internet often correspond to the analysis of high-dimensional sparse matrices. Notwithstanding the recent advances in the promotion of traditional singular value decomposition (SVD), an efficient estimation algorithm for rank of a high-dimensional sparse matrix is still lacked. Inspired by the controllability theory of complex networks, we converted the rank of a matrix into max-matching computing. Then we established a fast rank estimation algorithm by using cavity method, a powerful approximate technique for computing the max-matching, to estimate the rank of a sparse matrix. In the merit of its natural low complexity of cavity method, we showed that the rank of a high-dimensional sparse matrix can be estimated in a much faster way than SVD with high accuracy. Our method offers an efficient pathway to fast estimate the rank of the high-dimensional sparse matrix, when the time cost of computing the rank by SVD is unacceptable.


翻译:计算矩阵的等级是科学计算中的一个基本问题。 互联网生成的数据集往往与高维稀释矩阵的分析相对应。 尽管最近在推广传统单值分解(SVD)方面有所进步,但高维稀释矩阵的等级仍然缺乏有效的估计算法。 在复杂网络的可控性理论的启发下,我们将矩阵的等级转换为最大匹配计算。 然后,我们通过使用洞穴法建立了快速级估测算法,这是计算最大匹配率的有力近似技术,用来估计稀散矩阵的等级。 由于这种方法的自然复杂性较低,我们显示高维度稀释矩阵的等级可以比高精度SVD更快地估计。 我们的方法提供了一种高效的途径,可以快速估计高维稀释矩阵的等级,而SVD计算等级的时间成本是不可接受的。

0
下载
关闭预览

相关内容

【硬核书】矩阵代数基础,248页pdf
专知会员服务
83+阅读 · 2021年12月9日
Python编程基础,121页ppt
专知会员服务
48+阅读 · 2021年1月1日
【经典书】C语言傻瓜式入门(第二版),411页pdf
专知会员服务
51+阅读 · 2020年8月16日
论文浅尝 | 一种可解释的语义匹配复值网络
开放知识图谱
6+阅读 · 2019年6月25日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【推荐】GAN架构入门综述(资源汇总)
机器学习研究会
10+阅读 · 2017年9月3日
【推荐】TensorFlow手把手CNN实践指南
机器学习研究会
5+阅读 · 2017年8月17日
Arxiv
0+阅读 · 2021年12月23日
Arxiv
3+阅读 · 2018年10月18日
Arxiv
4+阅读 · 2018年3月14日
VIP会员
相关资讯
论文浅尝 | 一种可解释的语义匹配复值网络
开放知识图谱
6+阅读 · 2019年6月25日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【推荐】GAN架构入门综述(资源汇总)
机器学习研究会
10+阅读 · 2017年9月3日
【推荐】TensorFlow手把手CNN实践指南
机器学习研究会
5+阅读 · 2017年8月17日
Top
微信扫码咨询专知VIP会员