• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Information Theory >Vanishingly Sparse Matrices and Expander Graphs, With Application to Compressed Sensing
【24h】

Vanishingly Sparse Matrices and Expander Graphs, With Application to Compressed Sensing

机译：稀疏的稀疏矩阵和扩展图在压缩感知中的应用

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

摘要

We revisit the probabilistic construction of sparse random matrices where each column has a fixed number of nonzeros whose row indices are drawn uniformly at random with replacement. These matrices have a one-to-one correspondence with the adjacency matrices of fixed left degree expander graphs. We present formulas for the expected cardinality of the set of neighbors for these graphs, and present tail bounds on the probability that this cardinality will be less than the expected value. Deducible from these bounds are similar bounds for the expansion of the graph which is of interest in many applications. These bounds are derived through a more detailed analysis of collisions in unions of sets. Key to this analysis is a novel dyadic splitting technique. The analysis led to the derivation of better order constants that allow for quantitative theorems on existence of lossless expander graphs and hence the sparse random matrices we consider and also quantitative compressed sensing sampling theorems when using sparse nonmean-zero measurement matrices.
机译：我们将重新研究稀疏随机矩阵的概率构造，其中每一列具有固定数量的非零值，其行索引通过替换均匀地随机绘制。这些矩阵与固定左度展开图的邻接矩阵一一对应。我们为这些图提供了一组邻居的期望基数的公式，并给出了该基数小于期望值的概率的尾限。从这些边界可得出用于图扩展的相似边界，这在许多应用中都令人关注。这些边界是通过对集合并集中的冲突进行更详细的分析得出的。该分析的关键是一种新颖的二元分割技术。该分析导致了更好的阶数常数的推导，该阶数常数允许对存在的无损展开图进行定量定理，因此可以考虑我们所考虑的稀疏随机矩阵，以及在使用稀疏非均值零测量矩阵时的定量压缩感知采样定理。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号