Efficiently Decodable Compressed Sensing by List-Recoverable Codes and Recursion
Efficiently Decodable Compressed Sensing by List-Recoverable Codes and Recursion
复制标题
通过列表可恢复代码和递归有效解码压缩感知
DOI：
10.4230/lipics.stacs.2012.230
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
A. Rudra
中科院分区：
文献类型：
--
作者：
H. Ngo;E. Porat;A. Rudra
我们提出了两种递归技术，用于构建可以在亚线性时间内“解码”的压缩感测方案。第一个技术基于所研究的代码组成方法，称为代码串联，其中“外部”代码具有强大的列表可恢复性属性。该技术仅使用一个层次的递归，并严格使用列表恢复的力量。第二个递归技术在概念上是相似的，并且具有多个递归水平。使用这些技术获得以下压缩感测结果：
- 强烈明确有效地可解码的L_1/L_1压缩传感矩阵：我们提出具有O（d^2log^2 N）测量值的强烈明确（“适用”）压缩感测测量矩阵，该测量可以输出接近最佳的D-Sparse近似值。 poly（d log n）。
- 非负信号的近乎最佳的有效解释的L_1/L_1压缩传感矩阵：我们提出两个随机构造（“所有”）压缩传感矩阵，具有接近最佳的测量值：o（d log n loglog_d n）和o__d loglog_d n）和o__ {m，s}（d^{1+1/s} log n（log^（m）n）^s），对于任何整数参数s，m> = 1。这两种构造都可以在时间poly（d log n）的非阴性信号的最佳D-SPARSE近似值附近输出。
据我们所知，任何结果都没有由文献中的现有结果主导。
We present two recursive techniques to construct compressed sensing schemes that can be "decoded" in sub-linear time. The first technique is based on the well studied code composition method called code concatenation where the "outer" code has strong list recoverability properties. This technique uses only one level of recursion and critically uses the power of list recovery. The second recursive technique is conceptually similar, and has multiple recursion levels. The following compressed sensing results are obtained using these techniques:
- Strongly explicit efficiently decodable l_1/l_1 compressed sensing matrices: We present a strongly explicit ("for all") compressed sensing measurement matrix with O(d^2log^2 n) measurements that can output near-optimal d-sparse approximations in time poly(d log n).
- Near-optimal efficiently decodable l_1/l_1 compressed sensing matrices for non-negative signals: We present two randomized constructions of ("for all") compressed sensing matrices with near optimal number of measurements: O(d log n loglog_d n) and O_{m,s}(d^{1+1/s} log n (log^(m) n)^s), respectively, for any integer parameters s,m>=1. Both of these constructions can output near optimal d-sparse approximations for non-negative signals in time poly(d log n).
To the best of our knowledge, none of the results are dominated by existing results in the literature.