SCAN-MUSIC: An efficient super-resolution algorithm for large-scale single snapshot line spectral estimation

Abstract We propose an efficient algorithm for reconstructing large-scale one-dimensional line spectra from their Fourier data in a bounded interval $$[-\Omega ,\Omega ]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>[</mml:mo> <mml:mo>-</mml:mo> <mml:mi>Ω</mml:mi> <mml:mo>,</mml:mo> <mml:mi>Ω</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> . While traditional subspace methods such as MUSIC achieve super-resolution for closely separated line spectra, their computational cost is high, particularly for large-scale ones. To address this issue, we proposed a scalable algorithm, termed SCAN-MUSIC, that scans the spectral domain using a fixed Gaussian window and then reconstructs the line spectra falling into the window at each time. For line spectra with cluster structure, we further refine the proposed algorithm using the annihilating filter technique. Both algorithms can significantly reduce the computational complexity of the standard MUSIC algorithm with a moderate loss of resolution. The algorithms are supplemented with theoretical analyses of error estimates, sampling complexity, computational complexity, and computational limit.