Preserving injectivity under subgaussian mappings and its application to compressed sensing
Preserving injectivity under subgaussian mappings and its application to compressed sensing
复制标题
DOI：
10.1016/j.acha.2020.05.006
复制
发表时间：
2017-10
影响因子：
2.5
通讯作者：
P. Casazza;Xuemei Chen;Richard G. Lynch
中科院分区：
文献类型：
--
作者：
P. Casazza;Xuemei Chen;Richard G. Lynch
压缩感知领域已成为高维分析的主要工具，人们认识到，只要矢量位于低维结构中（通常是相对于基在大多数坐标中为零的矢量），就可以从相对很少的线性测量中恢复矢量。然而，在许多应用中，我们希望恢复相对于字典而不是基稀疏的向量。也就是说，我们假设向量是 d×n 矩阵 D 的至多 s 列的线性组合，其中 s 相对于 n 非常小，并且 D 的列形成一个（通常是过完备的）跨越集。在这个方向上，我们表明，当矩阵 D 在集合 S 上的范数上保持远离零的界限，并且由独立同分布的亚高斯行组成的提供的映射 Φ 的测量数量至少与相关集合 D S 的高斯宽度 w (D S) 的平方成正比时，那么组合 Φ D 也很有可能保持远离零的界限。作为一个具体的应用，我们发现在这种亚高斯映射下，s阶的零空间性质以高概率得到保留。因此，我们通过 ℓ 1-合成方法获得了字典稀疏信号的稳定恢复保证，仅需要 O (s log(n/s)) 随机测量和 D 上的最小条件，这补充了压缩感知文献。
The field of compressed sensing has become a major tool in high-dimensional analysis, with the realization that vectors can be recovered from relatively very few linear measurements as long as the vectors lie in a low-dimensional structure, typically the vectors that are zero in most coordinates with respect to a basis. However, there are many applications where we instead want to recover vectors that are sparse with respect to a dictionary rather than a basis. That is, we assume the vectors are linear combinations of at most s columns of a d× n matrix D, where s is very small relative to n and the columns of D form a (typically overcomplete) spanning set. In this direction, we show that as a matrix D stays bounded away from zero in norm on a set S and a provided map Φ comprised of iid subgaussian rows has number of measurements at least proportional to the square of w (D S), the Gaussian width of the related set D S, then with high probability the composition Φ D also stays bounded away from zero. As a specific application, we obtain that the null space property of order s is preserved under such subgaussian maps with high probability. Consequently, we obtain stable recovery guarantees for dictionary-sparse signals via the ℓ 1-synthesis method with only O (s log(n/s)) random measurements and a minimal condition on D, which complements the compressed sensing literature.