Sparsity Order Estimation From a Single Compressed Observation Vector

In this paper, the problem of estimating the unknown degree of sparsity from compressive measurements without the need to carry out a sparse recovery step is investigated. While the sparsity order can be directly inferred from the effective rank of the observation matrix in the multiple snapshot case, this appears to be impossible in the more challenging single snapshot case. It is shown that specially designed measurement matrices allow to rearrange the measurement vector into a matrix such that its effective rank coincides with the effective sparsity order. In fact, it is proven that matrices that are composed of a Khatri-Rao product of smaller matrices generate measurements that allow to infer the sparsity order. Moreover, if some samples are used more than once, one of the matrices needs to be Vandermonde. These structural constraints reduce the degrees of freedom in choosing the measurement matrix, which may incur in a degradation in the achievable coherence. Thus, this paper also addresses suitable choices of the measurement matrices. In particular, Khatri-Rao and Vandermonde matrices are analyzed in terms of their coherence and a new design for Vandermonde matrices that achieves a low coherence is proposed.