Robust measurement design for detecting sparse signals: Equiangular uniform tight frames and grassmannian packings

Detecting a sparse signal in noise is fundamentally different from reconstructing a sparse signal, as the objective is to optimize a detection performance criterion rather than to find the sparsest signal that satisfies a linear observation equation. In this paper, we consider the design of low-dimensional (compressive) measurement matrices for detecting sparse signals in white Gaussian noise. We use a lexicographic optimization approach to maximize the worst-case signal-to-noise ratio (SNR). More specifically, we find an optimal solution for a k-sparse signal among optimal solutions subject to sparsity level k - 1. We show that for all sparse signals, columns of the optimal measurement matrix must form a uniform tight frame. For 2-sparse signals, the smallest angle among angles between element pairs of this frame must be maximized. In this case, the optimal solution matrix is an optimal Grassmannian packing. For k-sparse signals where k > 2, the largest angle among such angles must be as close to the maximum smallest angle as possible. We show that under certain conditions, columns of the optimal measurement matrix form an equiangular uniform tight frame. For this case, we derive an expression for the maximal SNR in the worst-case scenario, as a function of the signal dimension and the number of measurements.