A sharp analysis of Root-MUSIC: locations of correct and extraneous roots

Technical Summary: A Sharp Analysis of Root-MUSIC: Locations of Correct and Extraneous Roots

Problem Statement
Root-MUSIC is a prominent spectral estimation algorithm used to recover unknown signal frequencies $\{\theta_k\}_{k=1}^s$ from noisy temporal samples. The method constructs a high-degree polynomial, $P$, based on an estimated signal subspace, and identifies the signal frequencies by locating the roots of a perturbed polynomial, $\tilde{P}$, that lie closest to the complex unit circle.

While previous works [20, 14] have provided asymptotic expectation formulas for the perturbation of the "correct" roots (those corresponding to the true frequencies), they relied on an implicit assumption: that the root selection criterion (choosing the $s$ roots closest to the unit circle) does not inadvertently select "extraneous" roots. Extraneous roots are those unrelated to the true signal parameters. A critical gap in the literature is the lack of rigorous, non-asymptotic guarantees ensuring that noise does not push an extraneous root closer to the unit circle than a perturbed correct root, which would lead to estimation failure. Furthermore, existing bounds often fail to explicitly quantify the dependence of frequency error on fundamental model parameters such as the number of sensors ($m$) and noise variance.

Methodology
This paper addresses these gaps through a geometric and analytic perturbation analysis of the Root-MUSIC polynomial. The authors analyze the relationship between the noiseless polynomial $P$ (derived from the true subspace $U$) and the perturbed polynomial $\tilde{P}$ (derived from an estimated subspace $\tilde{U}$).

The core methodology relies on:

1. Subspace Error Metric: The analysis is framed in terms of the subspace error $\rho = \|UU^* - \tilde{U}\tilde{U}^*\|_2$, which measures the distance between the true and estimated signal subspaces.
2. Separation Condition: The results assume a minimum separation between signal frequencies, $\Delta := \min_{j \neq k} d(\theta_j, \theta_k) \geq 2\pi\beta/m$, for a sufficiently large constant $\beta \geq 4$.
3. Rouché's Theorem: To locate the roots of $\tilde{P}$, the authors employ Rouché's theorem. This requires establishing tight lower bounds for $|P(z)|$ and upper bounds for the perturbation $|P(z) - \tilde{P}(z)|$ in specific neighborhoods of the true roots.
4. Geometric Analysis of Roots: The authors utilize the reflection symmetry of the Root-MUSIC polynomial (roots come in pairs $w, 1/w$) and analyze the polynomial's behavior in annuli and wedges around the unit circle. They demonstrate that while correct roots are double roots of $P$ (and thus sensitive to perturbation), the specific structure of the Root-MUSIC polynomial allows for "hidden cancellations" in the perturbation term near the correct roots.

Key Contributions
The paper makes two primary contributions, summarized in Theorem 3.1:

1. Exclusion of Extraneous Roots: The authors prove that under the stated separation and noise conditions, the perturbed polynomial $\tilde{P}$ possesses exactly $s$ roots (modulo reflection) within a specific annulus of thickness proportional to $1/m$ around the unit circle. Crucially, all other roots (extraneous roots) lie strictly outside this annulus. This rigorously confirms that the Root-MUSIC algorithm, which selects the $s$ roots closest to the unit circle, will invariably select the perturbed correct roots and never an extraneous root. This resolves the pathological scenario depicted in Figure 1 of the paper.

2. Sharp, Non-Asymptotic Error Bounds: The paper derives an explicit, non-asymptotic upper bound for the frequency estimation error. Specifically, for each correct root $w_k = e^{i\theta_k}$, the estimated root $\tilde{w}_k$ satisfies:
   $$\max_k |e^{i\theta_k} - \tilde{w}_k| \leq \frac{R}{m} \|UU^* - \tilde{U}\tilde{U}^*\|_2$$
   where $R$ is an absolute constant. This bound is "sharp" in that it scales linearly with the subspace error and includes a $1/m$ factor, which is a significant improvement over standard perturbation theory for double roots (which typically suggests a square-root dependence on the error).

Results and Applications
The abstract result is specialized to three common noise models, as summarized in Table 1 of the paper:

• Single-Snapshot (Deterministic Noise): Frequency error scales as $\lesssim \|\eta\|_p / m^{1+1/p}$.
• Single-Snapshot (Gaussian Noise): Frequency error scales as $\lesssim \sigma \sqrt{\log(m)} / m^{3/2}$.
• Multi-Snapshot (Gaussian Noise): Frequency error scales as $\lesssim \sigma / (m\sqrt{n})$, where $n$ is the number of snapshots.

A notable finding in the multi-snapshot model is the explicit $1/m$ decay factor. This indicates that increasing the number of sensors ($m$) provides a significant advantage in estimation accuracy, even if the noise-to-signal ratio remains fixed. The paper notes that these rates match the minimax optimal rates derived in prior work [25, 10] (up to logarithmic factors), establishing Root-MUSIC as an optimal algorithm for signals with sufficiently separated frequencies.

Significance and Claims
The authors claim that the first contribution—proving that Root-MUSIC does not select perturbed extraneous roots under natural assumptions—is a novel result. Previously, the success of the algorithm in the presence of noise relied on the unproven assumption that extraneous roots remain far from the unit circle.

The second contribution provides a unified, transparent error bound that explicitly highlights the scaling with model parameters. The authors emphasize that the $1/m$ factor in the error bound is a distinctive feature of Root-MUSIC (and related MUSIC variants like Gradient-MUSIC) that is not present in all spectral estimation theories. This factor implies that utilizing additional measurements (increasing $m$) yields increasingly accurate frequency estimates without requiring higher-quality individual samples.

The paper concludes that numerical simulations confirm both the theoretical error rates and the geometric property that the closest extraneous root lies at a distance of order $1/m$ from the annulus containing the correct roots, validating the sharpness of the derived bounds. The analysis is theoretical, and while it suggests that the algorithm is robust, the authors do not advocate for Root-MUSIC over other methods but rather provide a rigorous theoretical foundation for its performance.