Generalized Notions of Sparsity and Restricted Isometry Property. Part II: Applications
Generalized Notions of Sparsity and Restricted Isometry Property. Part II: Applications
复制标题
稀疏性和受限等距性质的广义概念。
DOI：
10.1007/s00041-020-09809-8
复制
发表时间：
2021
影响因子：
1.2
通讯作者：
Lee, Kiryung
中科院分区：
文献类型：
--
作者：
Junge, Marius;Lee, Kiryung
限制等距特性（RIP）为稀疏信号提供了一种近等距映射。结构随机矩阵的RIP对压缩测量的降维和恢复起着关键作用。在另一篇论文中，我们建立了广义稀疏模型上群结构测量算子的RIP的统一理论。本文将进一步讨论推广结果与传统理论的优缺点。我们首先证明了扩展RIP理论能够在规范稀疏模型的各种松弛上优化样本复杂度。同时，广义稀疏性模型不再被描述为子空间的并。因此稀疏度不是次加性的。这就导致了两倍稀疏度的RIP并不意味着在稀疏度模型与自身的闵可夫斯基差上的RIP，而闵可夫斯基差对于降维至关重要。我们证明了群结构测量算子对非次加性模型提供了具有加性畸变的类rip性质。这个较弱的结果对于像位置敏感散列这样的应用程序很有用。此外，我们还提出了具有随机符号的群结构测量可以在任何类似于高斯测量的集合上进行近等距素描。最后，通过Lebesgue支持度测度和Sobolev半形给出的实例，推导了理论的无限维推广。
Restricted isometry property (RIP) provides a near isometric map for sparse signals. RIP of structured random matrices has played a key role for dimensionality reduction and recovery from compressive measurements. In a companion paper, we have developed a unified theory for RIP of group structured measurement operators on generalized sparsity models. The implication of the extended result will be further discussed in this paper in terms of its pros and cons over the conventional theory. We first show that the extended RIP theory enables the optimization of sample complexity over various relaxations of the canonical sparsity model. Meanwhile, the generalized sparsity model is no longer described as a union of subspaces. Thus the sparsity level is not sub-additive. This incurs that RIP of double the sparsity level does not imply RIP on the Minkowski difference of the sparsity model with itself, which is crucial for dimensionality reduction. We show that a group structured measurement operator provides an RIP-like property with additive distortion for non-sub-additive models. This weaker result can be useful for applications like locality-sensitive hashing. Moreover, we also present that the group structured measurements with random sign enables near isometric sketching on any set similar to the Gaussian measurements. Lastly, an extension of theory to infinite dimension is derived and illustrated over selected examples given by Lebesgue measure of support and Sobolev seminorms.
登录
查看更多内容
影响因子：
3
作者：
Adcock, Ben;Hansen, Anders C.
通讯作者：
Hansen, Anders C.
影响因子：
2.3
作者：
M. Junge;Q. Zeng
通讯作者：
M. Junge;Q. Zeng
Khhinchine 不等式中的最佳常数
影响因子：
0.8
作者：
U. Haagerup
通讯作者：
U. Haagerup
Banach空间中Bernstein-Jackson型不等式与算子的紧度
DOI：
10.5802/aif.1020
发表时间：
1985
期刊：
Annales de l'Institut Fourier
影响因子：
--
作者：
B. Carl
通讯作者：
B. Carl
Marcinkiewicz 型离散化定理
影响因子：
2.7
作者：
V. Temlyakov;V. Temlyakov
通讯作者：
V. Temlyakov