Landscape Analysis of Simultaneous Blind Deconvolution and Phase Retrieval via Structured Low-Rank Tensor Recovery

Xiao Liang, Zhen Qin, Zhihui Zhu, Shuang LiarXiv 2025 · DOI · arXiv

Introduction

In advanced imaging, researchers often encounter two distinct mathematical hurdles: Blind Deconvolution (BD) and Phase Retrieval (PR). Blind Deconvolution requires recovering both an unknown signal and an unknown blurring kernel from their convolution, while Phase Retrieval involves recovering a complex-valued signal from intensity measurements alone, where phase information is lost.

Solving these problems simultaneously—referred to as Blind Deconvolution and Phase Retrieval (BDPR)—is notoriously difficult. The problem is both ill-posed (admitting multiple solutions) and non-convex (the optimization landscape is prone to local minima). This paper provides the first rigorous geometric landscape analysis for BDPR by reformulating it as a structured low-rank tensor recovery problem.

Methodology: A Tensor Recovery Framework

The authors bridge the gap in theoretical understanding by modeling the BDPR data as a third-order tensor with a specific symmetry: $x \circ x \circ h$, where $x$ represents the signal and $h$ represents the kernel coefficient. This structured approach allows the problem to be treated through the lens of Structured Low-Rank Tensor Recovery.

Key Methodological Steps

  1. Tractable Surrogate: The authors analyze a "tensor sensing" surrogate that obeys the Tensor Restricted Isometry Property (TRIP), providing a mathematically manageable version of the complex sensing physics.
  2. Landscape Analysis: They characterize the critical points (peaks, valleys, and saddle points) of the optimization landscape, proving that the landscape is "benign" for this specific tensor structure.
  3. Riemannian Gradient Descent (RGD): The paper employs RGD, an algorithm that optimizes by "walking" along the surface of a manifold (a unit sphere) to find the global minimum.
  4. Spectral Initialization: To avoid poor starting points, a spectral method based on Singular Value Decomposition is used to initialize the algorithm in a region close to the true solution.

Key Insights and Theoretical Guarantees

The most significant discovery is that the optimization landscape for this $x \circ x \circ h$ structure is relatively benign. While saddle points exist, the authors demonstrate that first-order methods like gradient descent can reliably converge to the global optimum under mild conditions.

Furthermore, the authors prove that the error decreases linearly (exponentially fast relative to iterations) once the algorithm enters the neighborhood of the solution. In the presence of noise, the algorithm exhibits "graceful degradation," converging linearly to a noise floor proportional to the level of additive Gaussian noise.

Empirical Results and Validation

The theoretical framework was validated through extensive synthetic numerical experiments, including Gaussian tensor sensing and structured sensing simulations that mimic real-world phase imaging physics.

Sample Complexity and Phase Transitions

Success rate trials demonstrate a clear "phase transition" in performance. As the number of measurements $m$ increases, the probability of successful recovery jumps sharply from 0% to 100%. The results confirm that the required number of measurements scales linearly with the dimensions of the signal ($N$) and kernel ($K$), specifically $m \geq \Omega(N + K)$.

Success rate of recovery as a function of the number of measurements m, showing the phase transition from failure to success.

Convergence Rates

In noiseless scenarios, the RGD algorithm demonstrates remarkable efficiency. The loss function and estimation errors for both the signal $x$ and kernel $h$ drop to approximately $10^{-30}$ within 2,500 iterations, confirming the predicted linear convergence to the global optimum.

Convergence plots showing the loss function and estimation errors for signal and kernel decreasing linearly over iterations.

Conclusion and Future Work

This work provides a foundational theoretical "map" for the BDPR optimization landscape, proving that RGD can achieve linear convergence under the TRIP assumption. While the current analysis focuses on real-valued variables and assumes the sensing operator satisfies TRIP, future work aims to formally prove these properties for actual optical sensing operators and further explore the complexities of non-strict saddle points in global convergence scenarios.

Summary updated

Abstract

This paper presents a geometric analysis of the simultaneous blind deconvolution and phase retrieval (BDPR) problem via a structured low-rank tensor recovery framework. Due to the highly complicated structure of the associated sensing tensor, directly characterizing its optimization landscape is intractable. To address this, we introduce a tensor sensing problem as a tractable surrogate that preserves the essential structural features of the target low-rank tensor while enabling rigorous theoretical analysis. As a first step toward understanding this surrogate model, we study the corresponding population risk, which captures key aspects of the underlying low-rank tensor structure. We characterize the global landscape of the population risk on the unit sphere and show that Riemannian gradient descent (RGD) converges linearly under mild conditions. We then extend the analysis to the tensor sensing problem, establishing local geometric properties, proving convergence guarantees for RGD, and quantifying robustness under measurement noise. Our theoretical results are further supported by extensive numerical experiments. These findings offer foundational insights into the optimization landscape of the structured low-rank tensor recovery problem, which equivalently characterizes the original BDPR problem, thereby providing principled guidance for solving the original BDPR problem.
BibTeX
@misc{liang2025landscape,
  author = {Xiao Liang and Zhen Qin and Zhihui Zhu and Shuang Li},
  title = {{Landscape Analysis of Simultaneous Blind Deconvolution and Phase Retrieval via Structured Low-Rank Tensor Recovery}},
  year = {2025},
  eprint = {2509.10834},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2509.10834},
}
Figure