Almost-sure identifiability of multidimensional harmonic retrieval

Two-dimensional (2-D) and, more generally, multidimensional harmonic retrie val is of interest in a variety of applications, including transmitter loca lization and joint time and frequency offset estimation in wireless communi cations. The associated identifiability problem is key in understanding the fundamental limitations of parametric methods in terms of the number of ha rmonies that can be resolved for a given sample size. Consider a mixture of 2-D exponentials, each parameterized by amplitude, phase, and decay rate p lus frequency in each dimension. Suppose that I equispaced samples are take n along one dimension and, likewise, J along the other dimension. We prove that if the number of exponentials is less than or equal to roughly IJ/4, t hen, assuming sampling at the Nyquist rate or above, the parameterization i s almost surely identifiable. This is significant because the best previous ly known achievable bound was roughly (I + J) / 2. For example, consider I = J = 32; our result yields 256 versus 32 identifiable exponentials. We als o generalize the result to N dimensions, proving that the number of exponen tials that can be resolved is proportional to total sample size.