Generalized Notions of Sparsity and Restricted Isometry Property. Part II: Applications

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.