We give a new deterministic construction of integer sensing matrices that can be used for the recovery of integer-valued signals in compressed sensing. This is a family of $n \times d$ integer matrices, $d \geq n$, with bounded sup-norm and the property that no $\ell$ column vectors are linearly dependent, $\ell \leq n$. Further, if $\ell \leq o(\log n)$ then $d/n \to \infty$ as $n \to \infty$. Our construction comes from particular sets of difference vectors of point-sets in $\mathbb R^n$ that cannot be covered by few parallel hyperplanes. We construct examples of such sets on the $0, \pm 1$ grid and use them for the matrix construction. We also show a connection of our constructions to a simple version of the Tarski plank problem.
翻译:我们给出了可用于在压缩传感器中恢复整数值信号的整数感测矩阵的新确定性构造。 这是一个由 $ = time d$ 整数矩阵组成的组合, $ d \ geq n$, 配有 sups-norm 和没有 $ ell 列矢量的属性, $\ ell\ leq n$ 。 此外, 如果$\ leq o (\ log n) $ d/n \ to\ inty$, 以 $ \ 至\ inty$ 。 我们的构造来自 $\ mathbbl Rn$ 中特定的点位差数矢量矢量, 无法由几个平行的超平面覆盖。 我们用 $0 \ pm 1 的电网建这样的集示例, 并用于构建矩阵。 我们还展示了我们的构造与 Tarski plk 问题的简单版本的连接 。