A Convex Optimization Algorithm for Compressed Sensing in a Complex Domain: The Complex-Valued Split Bregman Method

Kai Xiong, Guanghui Zhao, Guangming Shi, Yingbin Wang2019 · DOI

TL;DR

This paper introduces the Complex-Valued Split Bregman Method (CV-SBM), a novel algorithm for compressed sensing (CS) in complex domains. CV-SBM directly handles complex-valued signals and phase information, outperforming existing methods in reconstruction accuracy and computational efficiency, especially for large-scale applications.

What Problem Does This Paper Address?

Compressed sensing (CS) is a powerful technique for reconstructing sparse signals from fewer measurements than traditionally required. While CS has been widely applied, most existing algorithms are designed for real-valued signals. Many real-world signals, such as those in radar and wireless communications, are inherently complex-valued and contain crucial phase information. Existing methods that attempt to handle complex signals often do so by converting them to a real domain, which can be computationally expensive and may lead to loss of phase information, degrading reconstruction quality. This paper addresses the need for a direct, efficient, and accurate CS reconstruction method for complex-valued signals that preserves phase information.

Methods

The core contribution is the development of the Complex-Valued Split Bregman Method (CV-SBM). This method is a generalization of the well-established Split Bregman Method (SBM) into the complex domain. Key aspects include:

  • Complex-Valued Bregman Distance (CV-BD): The authors define a new Bregman distance that operates directly on complex numbers, allowing for the direct measurement of closeness in complex spaces.
  • Complex-Valued Bregman Iteration (CV-BI): This is the iterative engine of the proposed method. It's designed to solve optimization problems with convex regularization terms in the complex domain, leveraging Wirtinger calculus for gradient computations. The convergence of CV-BI is theoretically analyzed.
  • Variable Separation Technique: To simplify the iterative process and avoid reliance on external algorithms (a limitation of the original CV-BI), CV-SBM employs a variable separation technique, similar to the original SBM. This allows for efficient, alternating minimization steps.
  • Direct Complex Domain Processing: Unlike previous approaches that convert complex signals to real ones (doubling the data size and computational cost), CV-SBM operates entirely within the complex domain, preserving phase information and reducing computational overhead.

Datasets

Not discussed in the paper. The paper uses synthetic data generated for experiments and real data from ISAR imaging.

Key Insights and Ideas

  • Phase Matters: The paper strongly emphasizes that phase information in complex signals is critical for accurate reconstruction. Methods that ignore or distort this information (like complex-to-real transformations) inherently limit performance.
  • Direct Complex Optimization is Superior: By developing CV-BD and CV-BI, the authors show that directly optimizing in the complex domain is not only theoretically sound but also practically beneficial, leading to better accuracy and efficiency.
  • Split Bregman's Adaptability: The Split Bregman framework, known for its versatility with different regularization terms (like L1 and TV), proves to be adaptable to the complex domain, offering a unified approach.
  • Computational Efficiency Gains: The complex-to-real transformation used in existing methods (like RV-SBM) is a significant bottleneck. CV-SBM's direct approach bypasses this, leading to substantial speedups, especially for large signals.

Key Results

  • Improved Reconstruction Accuracy: In synthetic experiments with complex-valued sparse signals, CV-SBM consistently recovered more accurate points compared to OMP, CAMP, and M-lasso. For example, in one test, CV-SBM achieved 10 and 15 well-recovered points in the real and imaginary parts, respectively, outperforming other methods.
  • Superior ISAR Imaging: When applied to real ISAR imaging data, CV-SBM produced clearer images with stronger scatterers and significantly suppressed outliers compared to RD, a previous CS method, and RV-SBM.
  • Robustness to Noise: CV-SBM demonstrates good robustness against measurement noise, with its Mean Squared Error (MSE) decreasing as Signal-to-Noise Ratio (SNR) increases. It achieved the lowest MSE among tested algorithms at higher SNRs.
  • Efficiency for Large-Scale Problems: For large signal dimensions (n=512), CV-SBM significantly reduced MSE (up to 26.7% lower) and computational time (up to 28.8% less) compared to RV-SBM across various SNR levels. This is attributed to avoiding the complex-to-real transformation.
  • Scalability: Figure 5 shows that CV-SBM's CPU time scales favorably with signal dimension compared to other methods, becoming more competitive and eventually faster than RV-SBM at larger scales.

Limitations and Future Work

  • Convex Regularization: The current CV-SBM is designed for convex regularization problems. The authors suggest that a significant goal for future work is to apply CV-SBM to more complicated regularization problems, as CV-BI and CV-SBM are theoretically capable of handling any convex optimization problem.
  • Comparison with CAMP: While CV-SBM shows great potential and is competitive with CAMP, the paper notes that CAMP has a specific design for L1-norm problems, and CV-SBM's inclusion of an inverse operator makes it slightly slower in some cases. However, the gap is small, and CV-SBM has potential to exceed CAMP.
  • Further Algorithm Exploration: The paper mentions that CV-BI requires the help of other algorithms for specific regularizations, and while CV-SBM simplifies this, further exploration into more complex regularization scenarios is warranted.

Summary updated

BibTeX
@misc{xiong2019convex,
  author = {Kai Xiong and Guanghui Zhao and Guangming Shi and Yingbin Wang},
  title = {{A Convex Optimization Algorithm for Compressed Sensing in a Complex Domain: The Complex-Valued Split Bregman Method}},
  year = {2019},
  doi = {10.3390/s19204540},
}
Figure