We study the problem of estimating a rank-one matrix from Gaussian observations where different blocks of the matrix are observed under different noise levels. This problem is motivated by applications in clustering and community detection where latent variables can be partitioned into a fixed number of known groups (e.g., users and items) and the blocks of the matrix correspond to different types of pairwise interactions (e.g., user-user, user-item, or item-item interactions). In the setting where the number of blocks is fixed while the number of variables tends to infinity, we prove asymptotically exact formulas for the minimum mean-squared error in estimating both the matrix and the latent variables. These formulas describe the weak recovery thresholds for the problem and reveal invariance properties with respect to certain scalings of the noise variance. We also derive an approximate message passing algorithm and a gradient descent algorithm and show empirically that these algorithms achieve the information-theoretic limits in certain regimes.


翻译:我们研究从高斯观察中估计一等矩阵的问题,在不同的噪音水平下观察到矩阵的不同区块。这个问题的起因是群集和社区探测应用,潜伏变量可以分成固定数目的已知组群(如用户和项目),矩阵的区块与不同类型的对称互动(如用户-用户、用户-项目或项目-项目互动)相对应。在确定区块数目而变量数趋向无限的设置中,我们证明在估计矩阵和潜在变量时,对最小平均差错的公式不那么精确。这些公式描述了问题的回收阈值薄弱,并揭示了噪音差异的某些尺度的不变化性。我们还得出了一种大致的信息传递算法和梯度下位算法,并用经验显示这些算法在某些制度中达到了信息-理论限度。

0
下载
关闭预览

相关内容

【WWW2021】双曲图卷积网络的协同过滤
专知会员服务
39+阅读 · 2021年3月26日
专知会员服务
27+阅读 · 2021年2月17日
最新《图理论》笔记书,98页pdf
专知会员服务
74+阅读 · 2020年12月27日
专知会员服务
42+阅读 · 2020年12月18日
专知会员服务
50+阅读 · 2020年12月14日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
已删除
将门创投
7+阅读 · 2019年10月10日
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【论文】图上的表示学习综述
机器学习研究会
14+阅读 · 2017年9月24日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年8月24日
Signal Detection in Degree Corrected ERGMs
Arxiv
0+阅读 · 2021年8月20日
Arxiv
3+阅读 · 2018年10月18日
Arxiv
4+阅读 · 2018年3月14日
VIP会员
相关VIP内容
相关资讯
已删除
将门创投
7+阅读 · 2019年10月10日
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【论文】图上的表示学习综述
机器学习研究会
14+阅读 · 2017年9月24日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员