Minimal Non-Uniform Sampling For Multi-Dimensional Period Identification
This paper addresses a fundamental question in the context of multi-dimensional periodicity. Namely, to distinguish between two N-dimensional periodic patterns, what is the least number of (possibly non-contiguous) samples that need to be observed? This question was only recently addressed for one-dimensional signals. This paper generalizes those results to N-dimensional signals. It will be shown that the optimal sampling pattern takes the form of sparse and uniformly separated bunches. Apart from new theoretical insights, this paper's results may provide the foundation for fast N-dimensional period recognition algorithms that use minimal number of samples.
© 2018 IEEE. This work was supported in parts by the ONR grants N00014-17-1-2732 and N00014-18-1-2390, the NSF grant CCF-1712633, and an Amazon post doctoral fellowship facilitated through the Information Science and Technology (IST) initiative at Caltech.