Multidimensional Harmonic Retrieval via Coupled Canonical Polyadic Decomposition—Part II: Algorithm and Multirate Sampling

In Part I of this paper, we have presented a link between multidimensional harmonic retrieval (MHR) and the recently proposed coupled canonical polyadic decomposition (CPD), which implies new uniqueness conditions for MHR that are more relaxed than the existing results based on a Vandermonde constrained CPD. In Part II, we explain that the coupled CPD also provides a computational framework for MHR. In particular, we present an algebraic method for MHR based on simultaneous matrix diagonalization that is guaranteed to find the exact solution in the noiseless case, under conditions discussed in Part I. Since the simultaneous matrix diagonalization method reduces the MHR problem into an eigenvalue problem, the proposed algorithm can be interpreted as an MHR generalization of the classical ESPRIT method for one-dimensional harmonic retrieval. We also demonstrate that the presented coupled CPD framework for MHR can algebraically support multirate sampling. We develop an efficient implementation which has about the same computational complexity for single-rate and multirate sampling. Numerical experiments demonstrate that by simultaneously exploiting the harmonic structure in all dimensions and making use of multirate sampling, the coupled CPD framework for MHR can lead to an improved performance compared to the conventional Vandermonde constrained CPD approaches.