...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Information Theory, IEEE Transactions on >Sketching Sparse Matrices, Covariances, and Graphs via Tensor Products
【24h】

Sketching Sparse Matrices, Covariances, and Graphs via Tensor Products

机译：通过Tensor产品草绘稀疏矩阵，协方差和图

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

This paper considers the problem of recovering an unknown sparse p×p matrix X from an m×m matrix Y=AXB, where A and B are known m×p matrices with m≪p. The main result shows that there exist constructions of the sketching matrices A and B so that even if X has O(p) nonzeros, it can be recovered exactly and efficiently using a convex program as long as these nonzeros are not concentrated in any single row/column of X. Furthermore, it suffices for the size of Y (the sketch dimension) to scale as m = O(√(# nonzeros in X) × log p). The results also show that the recovery is robust and stable in the sense that if X is equal to a sparse matrix plus a perturbation, then the convex program we propose produces an approximation with accuracy proportional to the size of the perturbation. Unlike traditional results on sparse recovery, where the sensing matrix produces independent measurements, our sensing operator is highly constrained (it assumes a tensor product structure). Therefore, proving recovery guarantees require nonstandard techniques. Indeed, our approach relies on a novel result concerning tensor products of bipartite graphs, which may be of independent interest. This problem is motivated by the following application, among others. Consider a p×n data matrix D, consisting of n observations of p variables. Assume that the correlation matrix X:=DD is (approximately) sparse in the sense that each of the p variables is significantly correlated with only a few others. Our results show that these significant correlations can be detected even if we have access to only a sketch of the data S=AD with A ∈ R .
机译：本文考虑了从m×m矩阵Y = AXB中恢复未知的稀疏p×p矩阵X的问题，其中A和B是已知m×p的m×p矩阵。主要结果表明，存在素描矩阵A和B的构造，因此，即使X具有O（p）个非零值，只要这些非零值不集中在任何一行中，就可以使用凸程序准确而有效地对其进行恢复。 / X的列。此外，满足Y的大小（草图尺寸）可缩放为m = O（√（X中的＃个非零值）×log p）。结果还表明，从某种意义上说，如果X等于稀疏矩阵加扰动，则恢复是鲁棒且稳定的，那么我们提出的凸程序将产生近似值，其精度与扰动的大小成正比。与稀疏恢复的传统结果不同，传感矩阵产生独立的测量值，而我们的传感算子则受到严格限制（假定张量积结构）。因此，证明恢复保证需要非标准技术。确实，我们的方法依赖于有关二部图张量积的新颖结果，该结果可能是独立关注的。该问题是由以下应用引起的。考虑一个p×n数据矩阵D，它由p个变量的n个观测值组成。在p个变量中的每个变量仅与其他几个变量显着相关的意义上，假设相关矩阵X：= DD稀疏。我们的结果表明，即使我们仅访问具有A∈R的数据S = AD的草图，也可以检测到这些显着的相关性。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号