PaperlayerView exact revision on arXiv

Source-linked AI summary

Off-the-Grid Line Spectrum Denoising and Estimation with Multiple Measurement Vectors

Yuanxin Li, Yuejie Chi

arXiv:1408.2242v2cs.ITmath.NA

TL;DR

The paper studies recovery and denoising of multiple spectrally sparse signals sharing unknown continuous frequencies from partial and noisy observations. It develops atomic-norm and structured-covariance estimators with semidefinite-program formulations, deriving recovery and finite-sample guarantees and showing gains from more measurement vectors.

  • Problem

    The problem is recovering shared continuous-valued frequencies and associated signal ensembles from partial and noisy observations without relying on a fixed frequency grid.

  • Method

    The paper combines atomic norm minimization for signal recovery and denoising with structured covariance estimation for frequency recovery.

  • Results

    The methods have theoretical guarantees, including finite-sample covariance analysis, and numerical results demonstrate performance gains as the number of measurement vectors increases.

  • Takeaways & Limitations

    Multiple measurement vectors provide a joint-sparsity structure that supports continuous-frequency estimation and denoising without assuming grid-aligned frequencies.

Abstract

from arXiv · show

Compressed Sensing suggests that the required number of samples for reconstructing a signal can be greatly reduced if it is sparse in a known discrete basis, yet many real-world signals are sparse in a continuous dictionary. One example is the spectrally-sparse signal, which is composed of a small number of spectral atoms with arbitrary frequencies on the unit interval. In this paper we study the problem of line spectrum denoising and estimation with an ensemble of spectrally-sparse signals composed of the same set of continuous-valued frequencies from their partial and noisy observations. Two approaches are developed based on atomic norm minimization and structured covariance estimation, both of which can be solved efficiently via semidefinite programming. The first approach aims to estimate and denoise the set of signals from their partial and noisy observations via atomic norm minimization, and recover the frequencies via examining the dual polynomial of the convex program. We characterize the optimality condition of the proposed algorithm and derive the expected convergence rate for denoising, demonstrating the benefit of including multiple measurement vectors. The second approach aims to recover the population covariance matrix from the partially observed sample covariance matrix by motivating its low-rank Toeplitz structure without recovering the signal ensemble. Performance guarantee is derived with a finite number of measurement vectors. The frequencies can be recovered via conventional spectrum estimation methods such as MUSIC from the estimated covariance matrix. Finally, numerical examples are provided to validate the favorable performance of the proposed algorithms, with comparisons against several existing approaches.

I. INTRODUCTION

The paper addresses line-spectrum estimation and denoising for multiple signals sharing unknown continuous frequencies, extending sparse recovery beyond fixed-grid models. It develops atomic-norm and covariance-based approaches that exploit multiple measurement vectors and are solvable by semidefinite programming.

  • I. INTRODUCTION: Spectrally sparse signal ensembles contain a small number of sinusoids sharing frequencies, observed through potentially partial and noisy measurements.The goal is to recover both the signal ensemble and its corresponding frequencies.
  • I. INTRODUCTION: Fixed-basis compressed sensing suffers from basis mismatch when physical signals have continuous, unknown frequency parameters.Spectrally sparse signals may have arbitrary frequencies on the unit interval rather than frequencies restricted to a DFT grid.
  • I. INTRODUCTION: Multiple measurement vectors exploit a shared joint-sparsity pattern without requiring frequencies to lie exactly on a grid.This connects the proposed model to the continuous counterpart of the MMV compressed-sensing framework.
  • I. INTRODUCTION: The paper develops atomic-norm minimization and structured covariance estimation, both efficiently formulated as semidefinite programs.Frequencies are recovered from the atomic-norm dual polynomial or from estimated covariance matrices using methods such as MUSIC.
  • I. INTRODUCTION: Atomic-norm recovery targets the full signal ensemble but becomes computationally expensive when the number of measurement vectors is high.The covariance approach instead targets the covariance matrix when only the shared frequency set is needed.
  • I. INTRODUCTION: Under uncorrelated frequencies, the covariance matrix is Hermitian Toeplitz with rank equal to the number of distinct frequencies.The proposed covariance method estimates this structure from partial sample covariance information and then applies conventional spectrum estimation.

B. Atomic Norm of the MMV Model

The paper defines an atomic norm for MMV spectrally sparse ensembles and uses its semidefinite characterization for recovery and denoising from partial or noisy observations. The formulation handles continuous frequencies and supports efficient convex optimization.

  • B. Atomic Norm of the MMV Model: The MMV atomic set represents an ensemble atom using a continuous frequency f and a unit-norm coefficient vector b.The frequency ranges over [0,1), while b lies in C^L with ||b||_2 = 1.
  • B. Atomic Norm of the MMV Model: The atomic ℓ0 quantity describes the smallest number of MMV atoms needed to represent the signal ensemble.It is equivalent to a formulation involving a Hermitian Toeplitz matrix but is NP-hard to minimize directly.
  • B. Atomic Norm of the MMV Model: The atomic norm is introduced as a convex relaxation of the atomic ℓ0 quantity and generalizes the single-vector atomic norm.The single-vector formulation is recovered when L = 1.
  • B. Atomic Norm of the MMV Model: The MMV atomic norm has an equivalent semidefinite-program characterization, enabling efficient computation.This characterization is the computational basis for the proposed convex recovery procedures.
  • B. Atomic Norm of the MMV Model: Atomic-norm minimization is applied to partial noiseless recovery and full-observation denoising in additive white Gaussian noise.A regularization parameter controls the noisy-observation formulation.
  • B. Atomic Norm of the MMV Model: The theoretical analysis covers the noiseless partial-observation algorithm and full-observation denoising, while partial noisy observations are left for future work.The regularization parameter is described as carefully selected.

A. Signal Recovery from Partial Noiseless Observations

The section develops atomic-norm methods for recovering jointly spectrally sparse signals from partial noiseless observations, with frequency identification from a dual polynomial. Recovery is guaranteed under random sampling and frequency-separation conditions, while a Hankel formulation connects the approach to EMaC.

  • Atomic-norm formulation and frequency recovery: The atomic-norm program can be written as a semidefinite program and its dual polynomial identifies the frequencies at points where its norm equals one.After frequency identification, amplitudes are recovered through group sparsity minimization.
  • Optimality certification: A dual certificate with zero values outside the observed set and prescribed behavior on the frequency atoms certifies unique recovery.The certificate follows from strong duality between the primal and dual programs.
  • Recovery guarantees: Recovery succeeds with high probability when randomly sampled observations exceed a logarithmic-factor multiple of the information-theoretic lower bound Θ(rL), under frequency separation.The guarantee assumes uniformly sampled index pairs and independent random coefficient signs.
  • Recovery guarantees: The required average samples per measurement vector is on the order of r log n log r, similar to the single-vector case, while experiments show gains from additional vectors.The results motivate studying whether more measurement vectors can relax separation or sampling conditions.
  • Connections and scope: The Hankel reformulation views columns as a shared-frequency ensemble, while EMaC relaxes the formulation by dropping the Toeplitz constraint.When p = 1, the formulation is equivalent to the single-vector atomic-norm method, but its theoretical guarantee does not apply because vector signs are dependent.
  • Connections and scope: The Hankel-based formulation does not provide practical performance gains over the single-vector atomic-norm algorithm and is presented primarily for theoretical interest.The stated limitation is the dependence among signs within each vector.

B. Signal Denoising for MMV Model

The section applies atomic-norm minimization to denoise fully observed MMV signals in additive white Gaussian noise. Its expected error analysis shows that performance can improve with more measurement vectors, subject to coefficient-scaling conditions.

  • Denoising method: Atomic-norm denoising in AWGN uses an efficiently implementable optimization algorithm, with ADMM provided as a solution procedure.The noisy observations are modeled as Z = X⋆ + N.
  • Convergence analysis: The expected convergence rate is bounded under an AWGN model with a specified noise-scale condition.The bound is stated in Theorem 3.
  • Effect of measurement vectors: The per-measurement-vector MSE vanishes as L increases when the coefficient-matrix row norms are o(L).This condition is satisfied, for example, by a correlated signal ensemble described in the section.
  • Effect of measurement vectors: With unit-amplitude entries in the coefficient matrix, the per-measurement-vector MSE may not vanish as L increases, although numerical results show graceful decreases.The contrasting behavior depends on how the coefficient norms scale with the number of measurement vectors.

IV. STRUCTURED COVARIANCE ESTIMATION FOR MMV MODEL

The structured covariance approach estimates a low-rank PSD Hermitian Toeplitz covariance matrix from partial sample covariances instead of reconstructing the full signal ensemble. This reduces storage and enables frequency recovery through standard spectral estimators.

  • Covariance structure: Under uncorrelated frequency coefficients, the signal covariance is PSD Hermitian Toeplitz and has rank equal to the number of distinct frequencies.Thus spectral sparsity appears as low rank in the covariance matrix.
  • Computational considerations: The covariance formulation stores an m×m sample covariance rather than the mL observation matrix, reducing storage when m ≪ L and allowing online updates.This approach targets frequency recovery without reconstructing the signal ensemble.
  • Frequency recovery: Frequencies can be estimated from the recovered covariance or its first column using MUSIC or ESPRIT.The algorithm therefore focuses on covariance reconstruction rather than direct signal-ensemble recovery.
  • Structured covariance estimation: The method estimates the full covariance matrix from partial observations by fitting its observed submatrix to the partial sample covariance.The observation pattern is represented by a mask operator acting on rows and columns indexed by Ω.
  • Optimization: A trace-regularized convex relaxation replaces NP-hard rank minimization while preserving the PSD Hermitian Toeplitz structure.The resulting optimization can be solved efficiently with off-the-shelf semidefinite-program solvers.
  • Relation to prior methods: Compared with the correlation-aware grid-based method, the proposed formulation uses continuous frequency atoms rather than discretizing them over a grid.The cited numerical comparisons are carried out later in the paper.

B. Performance Guarantees with Finite Samples

The finite-sample analysis studies covariance estimation under Gaussian coefficient assumptions and deterministic observation patterns. It provides high-probability error guarantees and identifies sample-complexity regimes where the MSE vanishes.

  • Assumptions and theorem: Under Gaussian coefficients, the covariance estimator is analyzed using the effective rank reff(Σ) = Tr(Σ)/∥Σ∥, which is smaller than the exact rank r.The effective rank accommodates approximately sparse signals.
  • Finite-sample guarantee: With probability at least 1 − L^-1, the estimator satisfies the Theorem 4 error bound when its sampling condition holds.The guarantee additionally assumes that Ω is a complete sparse ruler so unobserved entries can be deduced from observed differences.
  • Finite-sample guarantee: For full observations, reliable covariance estimation requires L on the order of reff(Σ⋆)r log n ≤ r^2 log n measurement vectors.This requirement is smaller than the ambient dimension n.
  • Finite-sample guarantee: For a complete sparse ruler, the average per-entry MSE vanishes when L is on the order of reff(Σ⋆_Ω)r log n ≤ r^2 log n.The guarantee extends the stated sample-complexity regime to partial observations.

A. Atomic Norm Minimization (10) for MMV Model

The atomic-norm MMV experiments show that increasing the number of measurement vectors improves reconstruction, denoising, and frequency-estimation accuracy. Structured covariance estimation exhibits the same benefit for covariance and frequency recovery under partial observations.

  • Recovery from Partial Observations: Increasing L raises reconstruction success for a fixed sparsity level under the stated separation and sampling conditions.Experiments use n = 64, m = 32, and frequencies separated by ∆≥1/n; success means normalized reconstruction error below 10^-5.
  • Recovery from Partial Observations: With r = 10 and no noise, both L = 1 and L = 3 achieve perfect recovery, but L = 3 gives better dual-polynomial localization.The dual polynomial is examined as the frequency-recovery certificate.
  • Atomic-Norm Denoising: The per-measurement vector MSE decreases as L increases, demonstrating more accurate MMV denoising.The empirical trend matches the theoretical upper bound from Theorem 3, although the bound is not tight.
  • Atomic-Norm Denoising: As L increases, average frequency-estimation MSE approaches the CRB while the CRB approaches zero.The comparison averages frequency-estimation error over 500 Monte Carlo noise realizations with n = 14, r = 2, and σ = 0.3.
  • Structured Covariance Estimation: For structured covariance estimation, average normalized estimation error decreases with L at fixed sparsity, while frequency estimates improve as L increases.Covariance experiments use n = 64 and m = 15; frequency-estimation experiments use m = 8 and apply rootmusic with the true model order.

D. Comparisons Between Different Approaches

The comparisons evaluate frequency estimation as measurement vectors, frequency separation, samples per vector, noise, and observation patterns vary. Structured covariance estimation is strongest with few measurement vectors, while atomic norm minimization improves with larger ensembles; both outperform grid-based methods in reported experiments.

  • Phase transitions: The structured covariance approach achieves better phase transitions than atomic norm minimization as measurement vectors, separation, and samples per vector vary.Success rates increase with more measurement vectors for fixed separation, and larger L permits smaller separations at the same success rate.
  • Noiseless measurements: With n = 64 and L = 400, structured covariance estimation accurately locates all frequencies in both tested sample settings.The settings use m = 8 and m = 5 with r = 6; the comparison includes CS, correlation-aware estimation, atomic norm minimization, and structured covariance estimation.
  • Noiseless measurements: With n = 64 and L = 400, grid-based methods produce extra lattice frequencies, while atomic norm minimization misses one close frequency under insufficient samples per vector.The grid mismatch affects CS and correlation-aware methods, whereas the atomic norm failure occurs for closely spaced frequencies.
  • Average estimation error: Over 200 Monte Carlo trials, structured covariance estimation performs better when L is small, while atomic norm minimization improves dramatically once L is sufficiently large.Both proposed methods outperform grid-based approaches; when separation is violated, similar behavior is observed, but atomic norm minimization requires more measurement vectors to approach structured covariance performance.
  • Overview: The paper develops two semidefinite-programming approaches for partial and noisy observations of multiple signals sharing continuous-valued frequencies.Atomic norm minimization estimates and denoises the signal ensemble, whereas structured covariance estimation recovers a structured covariance matrix.

APPENDIX

The appendix establishes atomic-norm identities and optimality properties using positive semidefinite Toeplitz and Vandermonde structure. It also proves uniqueness through dual certificates.

  • Atomic-norm representation: A Toeplitz semidefinite representation is shown equivalent to the atomic norm through matching upper and lower bounds.The proof uses Vandermonde decomposition and positive semidefinite factors to establish equality.
  • Optimality: Any matrix satisfying the stated dual conditions is dual feasible, and strong duality makes the primal and dual solutions optimal.The proof explicitly concludes that the constructed primal solution and dual certificate are optimal.
  • Uniqueness: A competing optimal solution with support outside the true frequency set contradicts the dual certificate, proving uniqueness of the solution.The argument also uses independence of atoms sharing the same support.

C. Proof of Theorem 3

The proof bounds the expected dual norm of the noise by discretizing the frequency interval and controlling chi-squared tails. This bound yields an expected convergence rate for atomic norm denoising.

  • Proof strategy: The expected convergence rate of atomic norm denoising is reduced to bounding E[∥N∥∗].The proof analyzes the noise dual norm as the key quantity governing the denoising guarantee.
  • Dual-norm bound: The noise dual norm is controlled by bounding trigonometric terms over a finite frequency grid and extending the result across the interval.The argument invokes Bernstein’s theorem and a grid of size D.
  • Concentration: Chi-squared tail bounds, a union bound, and Chernoff estimates produce the required probabilistic control of the noise dual norm.The proof introduces a chi-squared variable with 2L degrees of freedom and selects D = 8πnL log n.
  • Conclusion: Setting the resulting bound as τ completes the convergence-rate proof for the atomic norm denoising algorithm.The bound uses α = 8πn log n in the final parameter choice.

D. Proof of Theorem 4

The proof of Theorem 4 combines nuclear-norm analysis with sample-covariance concentration and optimality inequalities. It considers the structured covariance estimator through tangent-space error decomposition.

  • Reformulation: The trace-norm formulation is treated as an equivalent nuclear-norm optimization problem for positive semidefinite matrices.This reformulation enables the subsequent low-rank matrix error analysis.
  • Error decomposition: The covariance estimation error is decomposed into a rank-at-most-2r tangent component and an orthogonal component.The proof denotes the tangent space by T and its orthogonal complement by T ⊥.
  • Regularization: A regularization parameter is selected using a concentration bound for Gaussian sample covariance matrices.The proof introduces a sample covariance concentration lemma and a constant C.
  • Error bound: Triangle inequalities and estimator optimality bound the structured covariance error in terms of the observed covariance discrepancy.The proof then separates the analysis into two cases.
  • Full observation: Under full observation, the analysis gives a Frobenius-norm error bound involving the regularization parameter λ.The supplied statement specifies ∥T(û − u⋆)∥F ≤ 16λ√… with the remaining expression omitted.

E. ADMM Implementation of (22)

The paper reformulates (22) for ADMM, derives its augmented-Lagrangian updates and closed-form solutions, and stops when primal and dual residuals meet preset tolerances.

  • (22) is reformulated to enable application of ADMM.
  • The reformulated problem is used to construct an augmented Lagrangian and derive ADMM update steps.
  • Closed-form solutions are available for the resulting ADMM updates.
  • The implementation defines conjugation, the matrix-to-vector mapping a = G(A), and the diagonal matrix Υ used in the updates.The mapping aggregates entries of A satisfying q − p + 1 = i, while Υ has diagonal entries Υi,i = 1.
  • Iterations continue until both primal and dual residuals satisfy preset tolerance levels.
Loading 1408.2242v2…