Precise semidefinite programming formulation of atomic norm minimization for recovering d-dimensional (D ≥ 2) off-the-grid frequencies

Weiyu Xu, Jian-Feng Cai, Kumar Vijay Mishra, Myung Cho, Anton Kruger

TL;DR

This paper tackles the challenge of precisely recovering signals with sparse frequencies that don't align with standard sampling grids (off-the-grid frequencies) in multiple dimensions (d ≥ 2). The authors introduce novel semidefinite programming formulations that accurately capture the atomic norm minimization problem, extending previous work that was limited to one dimension. This advancement is crucial for more accurate signal recovery in various applications where signals are inherently multi-dimensional and their spectral components are not perfectly aligned with discrete sampling points.

What Problem Does This Paper Address?

Compressed sensing (CS) is a powerful technique for acquiring and compressing signals using fewer samples than traditional methods, by exploiting the signal's sparsity. A key challenge arises when the signal's sparse components (like frequencies) don't fall exactly on the discrete grid points of the sensing system. This "off-the-grid" problem leads to a "basis mismatch," where the signal appears less sparse than it truly is, hindering accurate recovery.

While atomic norm minimization has shown promise for recovering 1D off-the-grid sparse signals, extending this to higher dimensions (d ≥ 2) proved difficult. Previous attempts either used heuristic approximations or were not guaranteed to find the true atomic norm minimum. This paper addresses this open problem by providing precise semidefinite programming (SDP) formulations for atomic norm minimization in d-dimensional off-the-grid scenarios. This is vital for applications involving multi-dimensional signals, such as image processing or multi-channel sensor data, where frequencies can exist in complex, multi-dimensional spaces.

Methods

The core contribution of this paper lies in developing equivalent positive semidefinite programming (SDP) formulations for atomic norm minimization in d-dimensional (d ≥ 2) off-the-grid frequency recovery. The authors leverage the dual problem of atomic norm minimization. They then transform this dual problem into an SDP by utilizing theories related to positive trigonometric polynomials.

Specifically, they define a multi-variate trigonometric polynomial and its properties. By introducing a "sum-of-squares relaxation degree" vector, they construct a Hermitian matrix that captures the constraints of the dual problem. This allows them to formulate an SDP that approximates the atomic norm minimization. The paper also proposes a mechanism to check if the chosen relaxation degree is sufficient to achieve the true minimum atomic norm, ensuring the accuracy of the solution.

Datasets

Not discussed in the paper. The paper focuses on theoretical formulations and demonstrates its approach with simulated data in the numerical simulations section.

Key Insights and Ideas

  • Bridging the Dimensionality Gap: The most significant insight is the successful extension of precise atomic norm minimization from 1D to d-dimensional (d ≥ 2) off-the-grid frequency recovery. This overcomes a fundamental theoretical hurdle that prevented direct generalization.
  • Dual Problem as the Key: The paper highlights the power of working with the dual problem of atomic norm minimization. By reformulating the problem in its dual form, the authors find a path to an SDP formulation that was elusive when working directly with the primal problem.
  • The Role of Trigonometric Polynomials: The theoretical underpinnings of positive trigonometric polynomials are crucial for transforming the dual problem into a tractable SDP. This connection provides a rigorous mathematical framework for the proposed solution.
  • Checking for Optimality: The introduction of a mechanism to verify if the chosen relaxation degree is sufficient for achieving the minimum atomic norm is a practical and important contribution. It provides a way to ensure the accuracy of the SDP solution without relying on brute-force increases in complexity.

Key Results

The paper successfully proposes equivalent semidefinite programming formulations for atomic norm minimization for d-dimensional (d ≥ 2) off-the-grid frequencies. These formulations are shown to be applicable to arbitrary signal dimensions d > 2 and are extensible to noisy observations. The numerical simulations section demonstrates the effectiveness of the proposed dual polynomial approach for frequency localization in a 2D case, showing that the dual polynomial accurately identifies the true poles of the signal. The paper also indicates that a specific relaxation degree (m = (11,11) for a 2D case with n = (12,12)) was sufficient to achieve the minimum atomic norm, as verified by their checking mechanism.

Limitations and Future Work

  • Computational Complexity: While the paper provides precise SDP formulations, the computational complexity of these formulations can grow significantly with the signal dimension (d) and the chosen relaxation degree (m). The dimension of the PSD matrix Qo is (Π_{p=1}^d (m_p + 1)) × (Π_{p=1}^d (m_p + 1)), which can become very large.
  • Choosing the Relaxation Degree: While a mechanism to check for sufficiency is provided, determining the optimal or most efficient relaxation degree (m) for a given problem might still require some experimentation.
  • Future Work: The authors mention that their results are extensible to noisy observations, suggesting that further investigation into robust recovery in the presence of noise would be a valuable direction. Additionally, exploring more efficient computational methods for solving these high-dimensional SDPs would be beneficial for practical applications.

Summary updated

Abstract

Recent research in off-the-grid compressed sensing (CS) has demonstrated that, under certain conditions, one can successfully recover a spectrally sparse signal from a few time-domain samples even though the dictionary is continuous. In particular, atomic norm minimization was proposed in [1] to recover 1-dimensional spectrally sparse signal. However, in spite of existing research efforts [2], it was still an open problem how to formulate an equivalent positive semidefinite program for atomic norm minimization in recovering signals with d-dimensional (d ≥ 2) off-the-grid frequencies. In this paper, we settle this problem by proposing equivalent semidefinite programming formulations of atomic norm minimization to recover signals with d-dimensional (d ≥ 2) off-the-grid frequencies.
BibTeX
@inproceedings{xu2014precise,
  author = {Weiyu Xu and Jian-Feng Cai and Kumar Vijay Mishra and Myung Cho and Anton Kruger},
  title = {{Precise semidefinite programming formulation of atomic norm minimization for recovering d-dimensional (D ≥ 2) off-the-grid frequencies}},
  booktitle = {ITA},
  year = {2014},
  url = {https://openreview.net/forum?id=_ecj55yGrGx},
}
Figure