Deterministic fast and stable phase retrieval in multiple dimensions
0
🛸
Sign in to get full access
Overview
- This paper presents a new algorithm for solving the multidimensional phase retrieval problem in polynomial arithmetic complexity without any prior information.
- The algorithm is guaranteed to succeed for a large class of objects, called "Schwarz objects," and can solve the problem in O(N log(N)) operations for Fourier measurements with cardinality N.
- The authors also introduce a simple and well-conditioned diagonal operator that can transform any phase retrieval instance into one that can be solved by their method.
Plain English Explanation
The paper introduces a new algorithm that can solve a problem called "multidimensional phase retrieval" without needing any prior information about the object being studied. This problem is important in fields like optics, astronomy, and medical imaging, where you need to reconstruct an object from measurements of the intensity (or brightness) of its light, but not the phase (or direction) of the light waves.
The new algorithm is guaranteed to work for a broad class of objects, called "Schwarz objects," and can solve the problem very efficiently, taking only a small number of computational steps (O(N log(N))) for the type of measurements commonly used (Fourier measurements with cardinality N).
The authors also provide a simple way to transform any phase retrieval problem into one that their algorithm can solve. This is useful because phase retrieval problems can be tricky to work with, and this transformation makes them much easier to handle.
Technical Explanation
The authors present a new phase retrieval algorithm that is guaranteed to solve the multidimensional phase retrieval problem in polynomial arithmetic complexity without any prior information about the object being studied. The algorithm is shown to successfully terminate in O(N log(N)) operations for Fourier measurements with cardinality N.
The method works by posing the phase retrieval problem as a multiplicative Cousin problem from complex analysis, constructing an approximate solution using a modified integral from the Schwarz problem, and then refining this approximate solution to an exact solution using standard optimization techniques.
The authors further introduce a diagonal operator that can transform any feasible phase retrieval instance into one that is solved by their algorithm. This operator is easy to calculate and well-conditioned, making it a useful tool for practical applications.
The paper includes numerical experiments demonstrating the algorithm's performance and its superiority to existing methods, as well as an analysis of its robustness to Gaussian noise.
Critical Analysis
The authors make a strong case for the effectiveness of their phase retrieval algorithm, providing both theoretical guarantees and empirical evidence of its performance. However, the paper does not explore the limitations of the "Schwarz object" assumption, which may restrict the applicability of the method in certain real-world scenarios.
Additionally, while the diagonal operator is a useful tool, it would be helpful to better understand the range of phase retrieval instances that can be transformed by this operator and the potential impact of this transformation on the overall performance of the algorithm.
Further research could also investigate the algorithm's behavior under different types of noise or measurement errors, as well as its performance on larger-scale problems or more diverse datasets.
Conclusion
This paper presents a significant advancement in the field of phase retrieval, offering a new algorithm that is guaranteed to solve the multidimensional problem in polynomial time without any prior information. The method's efficiency and robustness, as well as the introduction of a useful diagonal operator, make it a promising approach for a wide range of applications in optics, imaging, and beyond.
This summary was produced with help from an AI and may contain inaccuracies - check out the links to read the original source documents!
Related Papers
🛸
0
Deterministic fast and stable phase retrieval in multiple dimensions
Cole Brabec, Sivan Trajtenberg-Mills, Luca Daniel, Dirk Englund
We present the first phase retrieval algorithm guaranteed to solve the multidimensional phase retrieval problem in polynomial arithmetic complexity without prior information. The method successfully terminates in O(N log(N)) operations for Fourier measurements with cardinality N. The algorithm is guaranteed to succeed for a large class of objects, which we term Schwarz objects. We further present an easy-to-calculate and well-conditioned diagonal operator that transforms any feasible phase-retrieval instance into one that is solved by our method. We derive our method by combining techniques from classical complex analysis, algebraic topology, and modern numerical analysis. Concretely, we pose the phase retrieval problem as a multiplicative Cousin problem, construct an approximate solution using a modified integral used for the Schwarz problem, and refine the approximate solution to an exact solution via standard optimization methods. We present numerical experimentation demonstrating our algorithm's performance and its superiority to existing method. Finally, we demonstrate that our method is robust against Gaussian noise.
Read more7/2/2024
0
Low Complexity Regularized Phase Retrieval
Jean-Jacques Godeme, Jalal Fadili
In this paper, we study the phase retrieval problem in the situation where the vector to be recovered has an a priori structure that can encoded into a regularization term. This regularizer is intended to promote solutions conforming to some notion of simplicity or low complexity. We investigate both noiseless recovery and stability to noise and provide a very general and unified analysis framework that goes far beyond the sparse phase retrieval mostly considered in the literature. In the noiseless case we provide sufficient conditions under which exact recovery, up to global sign change, is possible. For Gaussian measurement maps, we also provide a sample complexity bound for exact recovery. This bound depends on the Gaussian width of the descent cone at the soughtafter vector which is a geometric measure of the complexity of the latter. In the noisy case, we consider both the constrained (Mozorov) and penalized (Tikhonov) formulations. We provide sufficient conditions for stable recovery and prove linear convergence for sufficiently small noise. For Gaussian measurements, we again give a sample complexity bound for linear convergence to hold with high probability. This bound scales linearly in the intrinsic dimension of the sought-after vector but only logarithmically in the ambient dimension.
Read more7/24/2024
0
Stable Phase Retrieval with Mirror Descent
Jean-Jacques Godeme, Jalal Fadili, Claude Amra, Myriam Zerrad
In this paper, we aim to reconstruct an n-dimensional real vector from m phaseless measurements corrupted by an additive noise. We extend the noiseless framework developed in [15], based on mirror descent (or Bregman gradient descent), to deal with noisy measurements and prove that the procedure is stable to (small enough) additive noise. In the deterministic case, we show that mirror descent converges to a critical point of the phase retrieval problem, and if the algorithm is well initialized and the noise is small enough, the critical point is near the true vector up to a global sign change. When the measurements are i.i.d Gaussian and the signal-to-noise ratio is large enough, we provide global convergence guarantees that ensure that with high probability, mirror descent converges to a global minimizer near the true vector (up to a global sign change), as soon as the number of measurements m is large enough. The sample complexity bound can be improved if a spectral method is used to provide a good initial guess. We complement our theoretical study with several numerical results showing that mirror descent is both a computationally and statistically efficient scheme to solve the phase retrieval problem.
Read more6/21/2024
0
Align-Free Multi-Plane Phase Retrieval
Jiabao Wang, Yang Wu, Jun Wang, Ni Chen
The multi-plane phase retrieval method provides a budget-friendly and effective way to perform phase imaging, yet it often encounters alignment challenges due to shifts along the optical axis in experiments. Traditional methods, such as employing beamsplitters instead of mechanical stage movements or adjusting focus using tunable light sources, add complexity to the setup required for multi-plane phase retrieval. Attempts to address these issues computationally face difficulties due to the variable impact of diffraction, which renders conventional homography techniques inadequate. In our research, we introduce a novel Adaptive Cascade Calibrated (ACC) strategy for multi-plane phase retrieval that overcomes misalignment issues. This technique detects feature points within the refocused sample space and calculates the transformation matrix for neighboring planes on-the-fly to digitally adjust measurements, facilitating alignment-free multi-plane phase retrieval. This approach not only avoids the need for complex and expensive optical hardware but also simplifies the imaging setup, reducing overall costs. The effectiveness of our method is validated through simulations and real-world optical experiments.
Read more5/1/2024