Mathematica Eterna
Open Access

A Generalization of Polarization Formula and Its Application in Phase Retrieval

Zhitao Zhuang^1* and Guochang Wu^{2 *}Correspondence: Zhitao Zhuang, College of Mathematics and Statistics, North China University of Water Resources and Electric Power, Zhengzhou 450011, P.R. China, Email:

Author info »

Introduction

The aim of phase retrieval is to recover signal x from its intensity measurements where forms a frame of C^d. Since for any with the best reconstruction of x is up to a unimodular constant. Phase retrieval arises in many areas of engineering and applied physics, including X-ray crystallography [1-8], optics [9], and computational biology [10-13]. In fact, it is difficult to solve the phase retrieval problem if one only knows the intensity measurements. One way to overcome this issue is to collect more prior information of the signal x [11]. Another way is to take more additional measurements. We only mention two different methods of the second way. The PhaseLift algorithm is proposed by Candès et al. with the lift technique of semi-definite programming [6]. Polarization method using structured measurements is proposed by Alexeev et al. [2]. Natural nonconvex algorithms often work remarkably well in practice, but lack clear theoretical explanations, therefore Sun et al. give a geometric analysis of phase retrieval [14]. Recently, phase retrieval in infinite dimensional space also attracts great attentions. Reconstruction of a bandlimited real-valued function f from unsigned intensity measurements is considered [8]. Unlike the finite dimensional case, phase retrieval in infinite dimensional Hilbert space is never uniformly stable [4]. Therefore, Alaifari et al. proposed a new paradigm for stable phase retrieval by considering the problem of reconstructing signal up to a phase factor that is not global [1].

In this paper, the frame theory is used to obtain some polarization identities. At first, we briefly introduce some definitions and notations. Let H denotes a separable Hilbert space with the inner product and J be a countable index set.

Definition 1.1. A sequence of elements in H is a frame for H if there exists constants A, B > 0 such that

The constants A, B are called lower and upper frame bounds for the frame. A frame is A-tight, if A=B. If A =B=1, it is called a Parseval frame.

Frame theory not only provides an effective analysis method for signal processing, but also offers a reconstruction method. We call a dual frame of if it is a frame for H and satisfying

The dual frame always exists but generally not unique. Since is also a frame, the function f has the expression as well. For special case, if is an A-tight frame, then is a dual frame. And if is a Parseval frame, it is a dual frame of itself.

Since the complex field C is closely related to the Euclidean space R², the frame theory in R² can be rewritten with respect to complex numbers. Explicitly, any complex number Z=X+IY can be considered as a bidimensional vector (x, y). Therefore, for any two complex numbers z1 and z2, the real part is an inner product of the vectors with respect to them. Without confusion, we call the collection is a frame for C if its corresponding collection of vectors is a frame for R². And the frame reconstruction formula can be rewritten as

where {z˜k }k∈J is the dual frame of {zk }k∈ J. Some polarization identities and examples are given in Section 2. We discuss the applications of polarization identities in (affine) phase retrieval problem in Section 3.

Polarization Formulas

In this section, we show some polarization identities that are deduced from frame theory in C. The classical polarization identity in functional analysis becomes a special case.

Lemma 2.1. Suppose is a frame for C with dual frame

Proof. We expand the modulus:

Taking summation over k and applying reconstruction formula (1.2) to the expansion, we get the desired result.

Above lemma can be generalized to any Hilbert space to get a polarization identity with similar proof.

Theorem 2.1. Suppose is a frame for C with dual frame . Then for any two elements f, g in a Hilbert space H, we have

By imposing some constraints to the frames, we can get some compact results. For instance, if is an equal norm frame that is for some constant c > 0 and all k ∈ J, then we have

Furthermore, if we require then

Even more, if is an A-tight frame, then the expression is not related to dual frame in form. Explicitly, we have

All the above polarization identities can be generalized to sesquilinear form. We only show the last one in the following.

Theorem 2.2. Let W be a complex vector space, S a sesquilinear form on W, and q the quadratic form generated by S. Suppose is an A-tight equal norm frame for W with Then we have

This theorem is easy to prove. From the theorem of Jordan and Von Neumann, we know that a norm on a vector space is generated by an inner product if and only if the parallelogram is satisfied. If this is so then the inner product is given by (2.7). In fact, one can prove that the inner product is also given by any frame in Theorem 2.1.

One important thing is whether an equal norm tight frame exists. The answer is positive and explicit constructions are given in finite frames: theory and applications [7] and reference therein. In the rest of this section, we consider the frame that consists of Nth roots of unity.

Lemma 2.2. Let for N ≥ 3, then is an equal norm tight frame for R² with frame bound N/2 and satisfy

Proof. For any f = (x, y)∈R² with norm there exists an angle θ such that Then we have

where the equation is used in the last equation.

By the frame properties we have

As mentioned before, there is an equivalent formula corresponding to complex field C. Explicitly, for any complex number z, we have

where Taking in Lemma 2.1 and Theorem 2.1, we get the following two corollaries.

Corollary 2.1. Take for N ≥ 3. Then for any

Corollary 2.2. Let H be a complex Hilbert space and for N ≥ 3. Then for any f, g ∈ H,

Taking N = 3 in Corollary 2.1, we get the polarization identity stated [2]. The classical polarization formula in functional analysis is a special case of Corollary 2.2 with N = 4, that is

Consequently, the above corollaries can be viewed as a generalization of the canonical polarization formula.

The frames consisted of Nth roots of unity play an important role in above discussion. Since it’s not very efficient in phase retrieval when N is large, reduction of elements in frame is needed. In fact, three elements of the Nth roots are enough for recovering the inner product. Let k₁,k₂,k₃ be any three different integers in the set {0,1,...,N −1}. Then must form a frame for C. If there exists a dual frame satisfying

Then we get a reconstruction formula

In fact, if we write since the reconstruction formula holds if and only if it holds for f =1 and f=i by linearity of innerproduct, the equations (2.8) and (2.9) are equivalent to the matrix equation XA = B, where

If A is invertible, the matrix equation has a unique solution and the corresponding dual frame satisfy (2.8) and (2.9). By simple computation, we have

det A=

Since k1, k2, k3 are different from each other in the set {0,1,...,N −1}. the determinant of matrix A is not zero.

Combing the above discussion, we have the following conclusion:

Theorem 2.3. Suppose k1, k2, k3 are three different integers from each other in the set {0,1,...,N −1}. Then, the collection forms a frame of C with a dual frame satisfying (2.8) and (2.9).

Example 2.1. The Nth roots of unity are 1, i, −1, −i when N = 4. By Theorem 2.3, we can find four frames of C and their corresponding dual frames, which are listed in Table 1. As a result, we can get four polarization identities by formula (2.3). The first one is given by

The others can be written out similarly.

If we continue to reduce the number of elements in a frame to two, then the new frame should be a basis of C and have no redundancy. Therefore, the restriction is no longer hold. However, we still can recover the innerproduct by the following theorem whose proof is similar to Theorem 2.3.

Theorem 2.4. Taking out two numbers k₁ ,k₂ from the set {0,1,...,N −1} with if N is odd and if N is even, then we have that the set forms a frame with dual frame which is given by

Example 2.2. The Nth roots of unity are when N=3. By Theorem 2.4, we get three frames and their dual frames, which are listed in Table 2. As a result, we can get three polarization identities by Theorem 2.1. The first one is given by

The others can be written out similarly.

In Example 2.2, the expression of polarization identity is not likely to become easier than Example 2.1. However, in phase retrieval, since the original intensity measurements ∥f ∥² , ∥g∥² are known generally, only two additional measurements are needed in order to recover relative phase.

Applications To Phase Retrieval

In this section, we apply the polarization identities to phase retrieval problem. The key ingredient is to add new measurements in order to gain the relative phase.

By leveraging the ideas of Alexeev et al. [2] and Bandeira et al. [3], we can implement polarization algorithms in phase retrieval problem with the help of polarization identities that are given in Section 2. Suppose the intensity measurements are known, the key point to recover signal x with polarization method is to compute the relative phase using where is a frame of C. If and the relative phase between is defined by

Since can be considered as an innerproduct in C, it can be computed by Lemma 2.1. If for every i∈ J , we can get the relative phase of two adjacent points, or relative phase of two points with is fixed. Then the signal x can be recovered up to a global phase factor. In graph theory terms, if the graph with vertex and edges x is a circle or star, then we can recover x . However, in general situation, there is a mask orthogonal to the signal x i.e., Therefore the relative phases can’t propagate across this vertex. The authors of Alexeev et al. [2] propose to design full spark frame and expander graph to overcome this shortage.

In this section, we focus on phase retrieval simulations with masked Fourier measurements, which are obtained by measuring the Fourier power spectrum of signals with adding mask. In order to have a high probability recovery, the mask is chosen randomly with Gaussian distribution.

Let denote the complex sinusoid Then the discrete Fourier transform is defined by

Suppose the Fourier intensity measurements are known, additional measurements are needed to recover the relative phase. Taking then we have

Accordingly, we need N additional vectors for computing every relative phase Since where one has

If all intensity measurements then we need N + 1 masks to recover x . By Theorem 2.3, one can reduce the number of total masks to four. When the intensity measurements are known, one can continue to reduce the amount of masks to three by Theorem 2.4. For instance, we can take the masks as in Example 2.2, and then the total masks are Comparing with the masks in Candes et al. [5], the same amount of masks are used.

We demonstrate the performance of polarization method with different frames and their duals in phase retrieval problem. Given a random signal, we add white Gaussian noise with different noise level to the intensity measurements such that the signal noise ratio (SNR) changes from 13 to 40 with step length 3. The effects of recovering the original signal with different frames are shown in Table 3, where correspond to N-th roots of unity frames, the first frame in Table 1 and Table 2 respectively. Observing Table 3, we find that the polarization method also have denoising effects due to the least square method that is used in the reconstruction process. For different frames, it seems that the effects have not much difference. However, for large N, we can still recover the signal when erasures occur in intensity measurements.

Table 1: Four frames and their dual frames.

Table 2: Three frames and their dual frames.

Table 3: Effects of different frames with different noise level measured by decibel.

Affine phase retrieval introduced in Gao et al. [10] has an exact reconstruction but not up to a unimodular constant. Explicitly, we consider recovering signal from the absolute values of the affine linear measurements

where and H = C or R. Let and, by vector augmentation, we set

Then the measurements can be written as One can prove easily that (A,b) is affine phase retrievable if A and A˜ are both full spark. Generally, the polarization method is hardly used to high dimension data due to its high computation complexity. However, because of the exact reconstruction of affine phase retrieval, this can be implemented by affine phase retrieval in one dimension iteratively. As a simulation, the polarization method is used to reconstruct the cameraman image from its power spectrum with SNR=20. This is implemented by reconstruction column by column in one dimension. Finally, we get the reconstructed image with SNR=17.9, which is illustrated in Figure 1.

Figure 1: The left is the original image, right is the reconstruction image from intensity measurements with SNR=20.

Conclusion

By the advantage of frame theory, a class of generalization of polarization formula is given, which makes the classical polarization as a special case. It provides a strong support for recovering the relative phase in polarization method. Furthermore, the same amount of intensity measurements are used as in PhaseLift method. The numerical simulations also demonstrate its good effect in (affine) phase retrieval of signal and image with Fourier measurements.

Declarations

Acknowledgements

The authors would like to thank the referees for their useful comments and remarks.

Availability of data and materials

The [cameraman.tif] data used to support the findings of this study are available from the corresponding author upon request.

Funding

This study was partially supported by National Natural Science Foundation of China (Grant No.11601152).

Competing interests

The authors declare that they have no competing interests.

Authors’ contributions

All authors contributed equally to this work. All authors read and approved the final manuscript.

References

1. Alaifari R, Daubechies I, Grohs P, Thakur, G. Reconstructing real valued functions from unsigned coefficients with respect to wavelet and other frames. J Fourier Anal Appl, 2017;23(6);1–15.
2. Alexeev B, Bandeira AS, Fickus M, Mixon DG. Phase retrieval with polarization. SIAM J Imaging Sci, 2014;7(1):35-66.
3. Bandeira AS, Chen Y, Mixon DG. Phase retrieval from power spectra of masked signals. Information and Inference: a Journal of the IMA. 2014;3(2):83-102.
4. Cahill J, Casazza P, Daubechies I. Phase retrieval in infinite-dimensional Hilbert spaces. Trans Am Math Soc, Series B. 2016;3(3):63-76.
5. Candes EJ, Eldar YC, Strohmer T, Voroninski V. Phase retrieval via matrix completion. SIAM Rev Soc Ind Appl Math. 2015;57(2):225-251.
6. Candes EJ, Strohmer T, Voroninski V. Phaselift: Exact and stable signal recovery from magnitude measurements via convex programming. Commun Pure Appl Math. 2013;66(8):1241-1274.
7. Casazza PG, Kutyniok G. Finite frames: Theory and applications. Sprin Scie & Busi Med; 2012; Sep 14.
8. Chen Y, Cheng C, Sun Q, Wang H. Phase retrieval of real-valued signals in a shift-invariant space. Appl Comput Harmon Anal. 2018.
9. Elser V. Phase retrieval by iterated projections. J Opt Soc Am A Opt Image Sci Vis. 2003; 20(1): 40-55.
10. Gao B, Sun Q, Wang Y, Xu Z. Phase retrieval from the magnitudes of affine linear measurements. Adv Appl Math Mech. 2018; 93:121-141.
11. Gerchberg RW. A practical algorithm for the determination of phase from image and diffraction plane pictures. Optik. 1972;35:237-246.
12. Millane RP. Phase retrieval in crystallography and optics. J Opt Soc Am A Opt Image Sci Vis. 1990;7(3):394-411.
13. Stefik M. Inferring DNA structures from segmentation data. Arti Intelli. 1978;11(1-2): 85-114.
14. Sun J, Qu Q, Wright J. A geometric analysis of phase retrieval. Found Comut Math. 2018;18(5):1131-1198.