ANM-PhaseLift: Structured line spectrum estimation from quadratic measurements

Zhe Zhang, Zhi TianarXiv 2017

Abstract

PhaseLift is a noted convex optimization technique for phase retrieval that can recover a signal exactly from amplitude measurements only, with high probability. Conventional PhaseLift requires a relatively large number of samples that sometimes can be costly to acquire. This paper focuses on some practical applications where the signal of interest is composed of a few Vandermonde components, such as line spectra. A novel phase retrieval framework, namely ANM-PhaseLift, is developed that exploits the Vandermonde structure to alleviate the sampling requirements. Specifically, the atom set of amplitude-based quadratic measurements is identified, and atomic norm minimization (ANM) is introduced into PhaseLift to considerably reduce the number of measurements that are needed for accurate phase retrieval. The benefit of ANM-PhaseLift is particularly attractive in applications where the Vandermonde structure is presented, such as massive MIMO and radar imaging.

Introduction

In many scientific and engineering fields, such as X-ray crystallography, astronomy, and radar imaging, sensors can only record the intensity or magnitude of a signal, losing the phase information entirely. Recovering the original signal from these quadratic measurements is a notoriously difficult non-convex problem. While PhaseLift is a popular solution that "lifts" the problem into a higher-dimensional space to make it convex, it is often "data-hungry," requiring a large number of measurements ($M$) relative to the signal size ($N$) to guarantee success.

This paper addresses the challenge of performing phase retrieval more efficiently when the signal has a specific structure—specifically, when it is a line spectrum (a sum of a few complex sinusoids). This structure is common in applications like radar and massive MIMO communications.

Methodology

The authors introduce ANM-PhaseLift, which integrates two powerful optimization concepts:

  1. PhaseLift (Lifting): Instead of searching for a signal vector $x$, the algorithm searches for a matrix $X = xx^H$. This turns non-linear magnitude measurements into linear constraints on the matrix $X$.
  2. Atomic Norm Minimization (ANM): This is a "gridless" compressed sensing technique. Instead of assuming frequencies lie on a fixed grid, ANM uses the mathematical properties of Vandermonde matrices (via Toeplitz matrix structures) to find the sparsest set of frequencies in a continuous domain.

Because the combined problem is originally non-convex, the authors propose two ways to solve it: a BMI Reformulation (Bilinear Matrix Inequalities) which is highly accurate but iterative, and a Convex Reformulation which is a standard Semidefinite Program (SDP) that is computationally faster but slightly less accurate.

Experimental Results

The performance of ANM-PhaseLift was evaluated using Monte Carlo simulations with signals of $N=8$ dimensions and $L=2$ frequency components. The results demonstrate significant improvements in both sampling efficiency and estimation accuracy.

Successful recovery rate of x vs. number of samples M.

As illustrated in the recovery rate analysis, traditional PhaseLift requires nearly 30 samples to reach a 100% success rate for the test signal. In contrast, ANM-PhaseLift (BMI version) achieves the same success rate with only 15 to 18 samples, effectively halving the data requirement.

MSE of recovered frequency f vs. number of samples M.

In terms of frequency estimation accuracy, ANM-PhaseLift outperforms the baseline by several orders of magnitude. As the number of samples increases, the Mean Square Error (MSE) for ANM-PhaseLift drops to $10^{-15}$, while standard PhaseLift struggles to break $10^{-5}$ even with maximum samples. This highlights the benefit of the "gridless" approach, which avoids errors associated with off-grid frequencies.

Conclusion

ANM-PhaseLift provides a robust framework for phase retrieval by exploiting the inherent Vandermonde structure of line spectra. By combining lifting with atomic norm minimization, the method achieves high-fidelity signal recovery with significantly fewer measurements than traditional PhaseLift. While the computational complexity of Semidefinite Programming remains a consideration for large-scale applications, the reduction in required samples offers a major advantage in data-constrained environments. Future research will focus on establishing formal theoretical bounds for these sampling requirements and improving performance in high-noise scenarios.

Summary updated

Abstract

PhaseLift is a noted convex optimization technique for phase retrieval that can recover a signal exactly from amplitude measurements only, with high probability. Conventional PhaseLift requires a relatively large number of samples that sometimes can be costly to acquire. This paper focuses on some practical applications where the signal of interest is composed of a few Vandermonde components, such as line spectra. A novel phase retrieval framework, namely ANM-PhaseLift, is developed that exploits the Vandermonde structure to alleviate the sampling requirements. Specifically, the atom set of amplitude-based quadratic measurements is identified, and atomic norm minimization (ANM) is introduced into PhaseLift to considerably reduce the number of measurements that are needed for accurate phase retrieval. The benefit of ANM-PhaseLift is particularly attractive in applications where the Vandermonde structure is presented, such as massive MIMO and radar imaging.
BibTeX
@misc{zhang2017anm,
  author = {Zhe Zhang and Zhi Tian},
  title = {{ANM-PhaseLift: Structured line spectrum estimation from quadratic measurements}},
  year = {2017},
  eprint = {1808.01036},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1808.01036},
}
Figure