Recovery analysis of damped spectrally sparse signals and its relation to MUSIC
Recovery analysis of damped spectrally sparse signals and its relation to MUSIC
复制标题
DOI：
10.1093/imaiai/iaaa024
复制
发表时间：
2018-06
期刊：
影响因子：
--
通讯作者：
S. Li;H. Mansour;M. Wakin
中科院分区：
文献类型：
--
作者：
S. Li;H. Mansour;M. Wakin
估计频谱稀疏信号中的频率和阻尼因子的经典方法之一是 MUSIC 算法，该算法利用自相关矩阵的低秩结构。低秩矩阵最近在具有部分观测的优化算法中也受到了相当大的关注，并且核范数最小化（NNM）已被广泛用作低秩矩阵恢复问题的秩最小化的流行启发式。另一方面，研究表明，NNM 可以被视为原子范数最小化 (ANM) 的特例，它在解决线谱估计问题方面取得了巨大成功。然而，据我们所知，许多现有工作中考虑的通用ANM（而不是NNM）只能处理无阻尼正弦曲线中的频率估计。在这项工作中，我们的目标是填补这一空白并处理阻尼谱稀疏信号恢复问题。特别是，受 ANM 中使用的对偶分析的启发，我们对经典 MUSIC 算法提供了一种新颖的基于优化的视角，并提出了一种谱估计算法，该算法涉及搜索与某个 NNM 问题相对应的对偶多项式的峰值，并且我们证明该算法实际上等同于 MUSIC 本身。在此联系的基础上，我们还将经典的 MUSIC 算法扩展到丢失数据的情况。我们为我们提出的算法提供精确的恢复保证，并量化样本复杂性如何依赖于真实的光谱参数。特别是，我们为联合稀疏信号的低秩矩阵恢复提供了特定于参数的恢复界限，而不是像现有文献中那样使用某些不相干属性。仿真结果还表明，所提出的算法在阻尼指数的频率估计方面显着优于一些相关的现有方法（例如ANM）。
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.