  One of the classical approaches for estimating the frequencies and damping
factors in a spectrally sparse signal is the MUSIC algorithm, which exploits
the low-rank structure of an autocorrelation matrix. Low-rank matrices have
also received considerable attention recently in the context of optimization
algorithms with partial observations, and nuclear norm minimization (NNM) has
been widely used as a popular heuristic of rank minimization for low-rank
matrix recovery problems. On the other hand, it has been shown that NNM can be
viewed as a special case of atomic norm minimization (ANM), which has achieved
great success in solving line spectrum estimation problems. However, as far as
we know, the general ANM (not NNM) considered in many existing works can only
handle frequency estimation in undamped sinusoids. In this work, we aim to fill
this gap and deal with damped spectrally sparse signal recovery problems. In
particular, inspired by the dual analysis used in ANM, we offer a novel
optimization-based perspective on the classical MUSIC algorithm and propose an
algorithm for spectral estimation that involves searching for the peaks of the
dual polynomial corresponding to a certain NNM problem, and we show that this
algorithm is in fact equivalent to MUSIC itself. Building on this connection,
we also extend the classical MUSIC algorithm to the missing data case. We
provide exact recovery guarantees for our proposed algorithms and quantify how
the sample complexity depends on the true spectral parameters. In particular,
we provide a parameter-specific recovery bound for low-rank matrix recovery of
jointly sparse signals rather than use certain incoherence properties as in
existing literature. Simulation results also indicate that the proposed
algorithms significantly outperform some relevant existing methods (e.g., ANM)
in frequency estimation of damped exponentials.
