Coding for a Single Sparse Inverse Problem
Coding for a Single Sparse Inverse Problem
复制标题
DOI：
10.1109/isit.2018.8437459
复制
发表时间：
2018-06
期刊：
影响因子：
--
通讯作者：
Yaoqing Yang;P. Grover;S. Kar
中科院分区：
文献类型：
--
作者：
Yaoqing Yang;P. Grover;S. Kar
我们提出了一种编码计算技术，用于使求解单个稀疏线性逆问题的幂迭代方法对擦除型噪声具有鲁棒性。我们观察到，对于稀疏逆问题，具有密集生成矩阵的代码会显着增加存储成本。因此，我们建议使用稀疏生成矩阵对功率迭代计算进行编码。令人惊讶的是，尽管具有稀疏生成矩阵的代码的纠错能力很差，但我们通过理论分析和模拟表明，只要使用我们称为“替代解码”的新解码算法，这些代码足以实现与无噪声功率迭代几乎相同的收敛速度。
We propose a coded computing technique for making the power-iteration method of solving a single sparse linear inverse problem robust to erasure-type noise. We observe that for sparse inverse problems, codes with dense generator matrices can significantly increase storage costs. Thus, we propose coding the power-iteration computation using sparse generator matrices. Surprisingly, despite the poor error-correction ability of codes with sparse generator matrices, we show through both theoretical analysis and simulations that these codes are sufficient to achieve almost the same convergence rate as noiseless power iterations, provided that a new decoding algorithm that we call “substitute decoding” is used.