Sparse Phase Retrieval with Redundant Dictionary via $\ell_q (0

Haiye Huo, Li Xiao

TL;DR

This paper provides the theoretical "rules of the road" for recovering signals that are sparse in redundant dictionaries from magnitude-only measurements using $\ell_q$ minimization ($0 < q \le 1$). By generalizing the Null Space Property (NSP) and the Strong Dictionary Restricted Isometry Property (S-DRIP), the authors prove that we can achieve exact and stable signal reconstruction under broader conditions than previously established.

What Problem Does This Paper Address?

Phase retrieval is a classic challenge in fields like optics, X-ray crystallography, and quantum mechanics. The goal is to reconstruct a signal when you can only measure its magnitude, losing all phase information. To make this problem tractable, researchers often assume the signal is "sparse"—meaning it can be represented by only a few non-zero coefficients.

However, most standard theories assume signals are sparse in a simple orthonormal basis. In reality, many signals (like radar images) are sparse in redundant dictionaries (or frames), which are collections of vectors that over-complete the space. Furthermore, while $\ell_1$ minimization is the standard tool for sparse recovery, $\ell_q$ minimization (where $q < 1$) is known to be more efficient, requiring fewer measurements. The catch? $\ell_q$ is non-convex and mathematically much harder to analyze. This paper bridges that gap by providing the necessary theoretical guarantees for using $\ell_q$ models with redundant dictionaries.

Methods

The authors focus on the $\ell_q$-analysis model, which seeks to minimize the $\ell_q$ norm of the signal's representation in a redundant dictionary $D$, subject to the measured magnitude constraints.

Their approach is purely theoretical, involving two main mathematical frameworks:

  1. Null Space Property (NSP): They derive new variants of the NSP that serve as necessary and sufficient conditions for exact recovery in noiseless scenarios, covering both real and complex signal spaces.
  2. Strong Dictionary Restricted Isometry Property (S-DRIP): For noisy scenarios, they analyze the S-DRIP—a condition on the measurement matrix that ensures stable recovery.

The novelty lies in extending these concepts from the standard $\ell_1$ case to the non-convex $\ell_q$ case and specifically tailoring them to redundant dictionaries rather than simple bases.

Datasets

This is a theoretical mathematics paper and does not utilize empirical datasets or benchmarks. The "results" are mathematical theorems and proofs rather than experimental data.

Key Insights and Ideas

  • Filling the "Gap" in S-DRIP: A major "aha moment" in the paper is the derivation of S-DRIP conditions for an order $tk$ where $0 < t < 4/3$. Previous research on $\ell_q$ models only covered cases where $t \ge 2$. This new result significantly broadens the range of measurement matrices known to guarantee stable recovery.
  • The Advantage of $q < 1$: The paper reinforces the idea that moving from $q=1$ (convex) to $q < 1$ (non-convex) isn't just a mathematical curiosity; it practically reduces the number of measurements required for successful reconstruction, provided the NSP or S-DRIP conditions are met.
  • Unifying Theory: The authors show that their $\ell_q$ results naturally "collapse" back into established $\ell_1$ theories when $q$ is set to 1, providing a unified theoretical framework for sparse phase retrieval.

Key Results

  • Exact Recovery (Theorems 3.1 & 3.2): The authors established the first necessary and sufficient NSP conditions for the $\ell_q$-analysis model in both real and complex fields. If a measurement matrix satisfies these NSP variants, the signal can be perfectly reconstructed (up to a global phase) in the absence of noise.
  • Stable Recovery (Theorem 4.1): In the presence of noise ($\epsilon$), the authors proved that the reconstruction error is bounded: $$\min \{\| \hat{x} - x_0 \|_2, \| \hat{x} + x_0 \|_2\} \le c_1\epsilon + c_2 \frac{\sigma_k(D^*x_0)_q}{k^{1/q - 1/2}}$$ This formula shows that the error stays small as long as the noise is low and the signal is "nearly" $k$-sparse in the dictionary.

Limitations and Future Work

  • Complex Field S-DRIP: While the NSP results cover both real and complex signals, the S-DRIP results for stable recovery are currently limited to the real number field. The authors identify extending these stability results to the complex field as a primary goal for future research.
  • Algorithmic Implementation: This paper focuses on the existence and uniqueness of solutions (the "what" and "when"). It does not propose a specific new algorithm (the "how") to solve the non-convex optimization problem, noting that efficient solvers for the $\ell_q$-analysis model are still a fertile ground for study.

Summary updated

Abstract

Sparse phase retrieval with redundant dictionary is to reconstruct the signals of interest that are (nearly) sparse in a redundant dictionary or frame from the phaseless measurements via the optimization models. Gao [7] presented conditions on the measurement matrix, called null space property (NSP) and strong dictionary restricted isometry property (S-DRIP), for exact and stable recovery of dictionary-$k$-sparse signals via the $\ell_1$-analysis model for sparse phase retrieval with redundant dictionary, respectively, where, in particularly, the S-DRIP of order $tk$ with $t&gt;1$ was derived. In this paper, motivated by many advantages of the $\ell_q$ minimization with $0
BibTeX
@misc{huo2025sparse,
  author = {Haiye Huo and Li Xiao},
  title = {{Sparse Phase Retrieval with Redundant Dictionary via $\textbackslash\{\}ell\_q (0}},
  year = {2025},
  eprint = {2506.04576},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2506.04576},
}
Figure