MUSIC for multidimensional spectral estimation: stability and super-resolution

Abstract

This paper presents a performance analysis of the MUltiple SIgnal Classification (MUSIC) algorithm applied on $D$ dimensional single-snapshot spectral estimation while $s$ true frequencies are located on the continuum of a bounded domain. Inspired by the matrix pencil form, we construct a D-fold Hankel matrix from the measurements and exploit its Vandermonde decomposition in the noiseless case. MUSIC amounts to identifying a noise subspace, evaluating a noise-space correlation function, and localizing frequencies by searching the $s$ smallest local minima of the noise-space correlation function. In the noiseless case, $(2s{)}^D$ measurements guarantee an exact reconstruction by MUSIC as the noise-space correlation function vanishes exactly at true frequencies. When noise exists, we provide an explicit estimate on the perturbation of the noise-space correlation function in terms of noise level, dimension $D$, the minimum separation among frequencies, the maximum and minimum amplitudes while frequencies are separated by two Rayleigh Length (RL) at each direction. As a by-product the maximum and minimum non-zero singular values of the multidimensional Vandermonde matrix whose nodes are on the unit sphere are estimated under a gap condition of the nodes. Under the 2-RL separation condition, if noise is i.i.d. gaussian, we show that perturbation of the noise-space correlation function decays like $\sqrt{\log (\#(\mathbf{N}))/\#(\mathbf{N})}$ as the sample size $\#(\mathbf{N})$ increases. When the separation among frequencies drops below 2 RL, our numerical experiments show that the noise tolerance of MUSIC obeys a power law with the minimum separation of frequencies.

To appear in IEEE Transactions on Signal Processing

References in corpus (2)

• The recoverability limit for superresolution via sparsity
• Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices

Cited by in corpus (9)

• A multifrequency MUSIC algorithm for locating small inhomogeneities in inverse scattering
• Mathematical Theory of Computational Resolution Limit in Multi-dimensions
• Adaptive Superresolution in Deconvolution of Sparse Peaks
• Robust multifrequency imaging with MUSIC
• Algorithmic Foundations for the Diffraction Limit
• Stable Super-Resolution of Images: A Theoretical Study
• Spectral Compressed Sensing via Projected Gradient Descent
• An auto-parameter denoising method for nuclear magnetic resonance spectroscopy based on low-rank Hankel matrix
• Conditioning of restricted Fourier matrices and super-resolution of MUSIC