# Almost Phase Retrieval with Few Intensity Measurements

Authors: Wei Zhong
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

In signal processing, the phases of the measurements are often unknown. To recover a signal of lengthN, Balan, Casazza, and Edidin showed that it suffices to know at least 2N-1 intensity measurements. We give another characterization of frames which give phase retrieval for almost all signals with only N+1 intensity measurements. We provide a method to test if a frame has this property or not. With our method, we can construct tight frames or modify any frames such that they give almost phase retrieval. Numerical results show that frames with this property can recover signals with high probability.


---

## Body

## 1. Introduction

Given a set of vectors{φk}1≤k≤M⊂KN (K=R or C), the phase retrieval problem is to recover a signal from {|〈x,φk〉|}1≤k≤M which is called intensity measurements. Phase retrieval is a key step in speech processing [1], X-ray crystallography [2], and so forth. Since frames are redundant systems of vectors in a Hilbert space, it is possible to reconstruct signals with suitable frames.First, we introduce the definition of phase retrieval.Definition 1 (see [3, Definition 2.4]).
One calls that a set of vectors{φk}1≤k≤M in KN gives phase retrieval if for all x,y∈KN satisfying |〈x,φk〉|=|〈y,φk〉|, for all k=1,2,…,M, there exists a constant c∈K with |c|=1 such that x=cy.In fact, this definition is equivalent to the following.Definition 2.
One calls that a set of vectors{φk}1≤k≤M in KN gives phase retrieval if for all x,y∈KN satisfying
(1)〈x,φk〉=ck〈y,φk〉,1≤k≤M,
where ck∈K and |ck|=1, one has c1=c2=⋯=cM.LetW be an N×M matrix of rank N. If the set of columns of  W gives phase retrieval, we also say that the matrix W gives phase retrieval.Balan et al. [4] studied the properties of such frames with minimal measurements. For the real frames, they gave the following result.Proposition 3 (see [4, Theorem 2.2]).
LetΦ={φk}1≤k≤M be a frame for RN. If M≥2N-1, then a generic frame Φ gives phase retrieval.Here a generic frameΦ means a member of some nonempty Zariski open subset of the set of all M-element frames in RN. We refer to [5, Section 2.2] for details.For the complex frame, a similar result also holds.Proposition 4 (see [4, Theorem 2.2]).
LetΦ={φk}1≤k≤M be a frame for CN. If M≥4N-2, then a generic frame Φ gives phase retrieval.ForRN, M≥2N-1 is necessary. But for CN, Bandeira et al. conjectured the following.Conjecture 5 (see [6]).
LetΦ={φk}1≤k≤M be a frame for CN, N≥2. Then the following holds.(i)
IfM<4N-4, then Φ does not give phase retrieval.(ii)
IfM≥4N-4 and Φ is a generic frame, then Φ gives phase retrieval.Then, Conca et al. [5] confirmed Conjecture 5(ii). But (i) is still an open problem.Recently, people have studied more properties of such frames. Ohlsson and Eldar [7] studied the minimal measurements of sparse signals. If sparse signals contain noise, Eldar and Mendelson [8] also studied the minimal measurements and gave a recovery algorithm. By convex programming, Candès, Strohmer, and Vladislav gave a method which is called phaselift to recover a signal from its magnitude measurements. Then Gross et al. [9] and Alexeev et al. [10] developed other methods with phaselift. Chen et al. [11] estimated the error of phaselift. Schniter and Rangan [12] used compressed sensing to recover sparse signals via generalized approximate message passing.If we do not require thatΦ gives phase retrieval, for all x∈KN, we may need fewer measurements. Fickus et al. [13] studied when Φ gives phase retrieval for almost all vectors of KN. In this paper, we first introduce some preliminary results of frames which give phase retrieval. Then, we show our characterization and some properties of such frames. We give a method to test if a frame gives almost phase retrieval. Finally, we provide some examples to illustrate our results.


## 2. Main Results

First, we introduce some preliminary results.A set of finitely many vectorsΦ={φk}1≤k≤M in KN is called a frame if there are two positive constants α≤β such that, for every x∈KN,
(2)α∥x∥2≤∑k=1M‍|〈x,φ〉|2≤β∥x∥2.
A frame is said to be tight if α=β and Parseval if α=β=1. If the right-hand side of (2) holds, it is said to be a Bessel sequence. Define the analysis and synthesis operators of a frame by
(3)T:KN⟶l2,T(x)={〈x,φk〉}1≤k≤M,T*:l2⟶KN,T*{ck}1≤k≤M=∑k=1M‍ckφk,
respectively.We call{〈x,φk〉}1≤k≤M the frame coefficients of x. It can be shown that T*T is invertible on KN and, for each x∈KN,
(4)x=∑k=1M‍〈x,φk〉(T*T)-1φk.
We call that S=T*T is the frame operator and {φ~k=(T*T)-1φk}1≤k≤M the canonical dual frame for Φ. It is easy to see that S-1 is the frame operator of {φ~k}. Generally, if {ψk}1≤k≤M satisfies
(5)x=∑k=1M‍〈x,φk〉ψk,
for every x∈KN, we call that {ψk}1≤k≤M is a dual frame for Φ. For more details on frame theory and applications, we refer the reader to [14, 15] and so forth.Fickus et al. gave the following definition.Definition 6 (see [13, Definition 7]).
A set of vectors{φk}1≤k≤M in KN gives almost phase retrieval if it gives phase retrieval for almost every x∈KN.Next, we study real frames which give almost phase retrieval. Characterizing the complex frames which give almost phase retrieval remains an open problem.Denote thekth row and the lth column of a matrix A by rowkA and collA, respectively. They gave a characterization of such frames.Proposition 7 (see [13, Theorem 12]).
LetA be an N×M matrix on R. Suppose each column of A is nonzero. Then A gives almost phase retrieval if and only if A is of rankN and, for each nonempty proper subset Γ⊂{1,2,…,M},
(6)rank⁡(E)+rank⁡(F)>N,
where E and F are the matrices consisting of {colkA}k∈Γ and {colkA}k∈ΓC, respectively.Here we give another characterization which shows more properties of the almost phase retrieval. LetΓ be a subset of {1,2,…,M}. Denote
(7)αkΓ={1,k∈Γ-1,k∉Γ,ik=1,2,…,M.
For a matrix A, denote
(8)AΓ=A·diag⁡(α1Γ,α2Γ,…,αMΓ).
Denote the range and null space of an operator or matrix A by R(A) and N(A), respectively. Our first main result is the following.Theorem 8.
LetΦ={φk}1≤k≤M be a frame for RN with analysis operator T. Suppose that the (M-N)×M matrix A satisfies
(9)N(A)=R(T).
Then Φ gives almost phase retrieval if and only if
(10)rank⁡(A)<rank⁡(AAΓ)
holds for every nonempty proper subset Γ⊂{1,2,…,M}.Proof.
First we prove the necessity. We assume that there exists a nonempty proper subsetΓ⊂{1,2,…,M} which does not satisfy (10). That is,
(11)rank⁡(A)=rank⁡(AAΓ).
Since rank⁡(A)=rank⁡(AΓ), we have
(12)N(A)=N(AΓ).
Hence for every
(13)c={c1,c2,…,cM}∈R(T),
we have
(14)c′={α1Γc1,α2Γc2,…,αMΓcM}∈R(T).
But αkΓ≠αlΓ for k∈Γ and l∈ΓC. Hence Φ does not give almost phase retrieval.
Sufficiency. Let Γ be a nonempty proper subset of {1,2,…,M}. Then N(A)∩N(AΓ) is a proper subspace of N(A)=R(T). Let C0 be the union of all such subspaces and S0=T-1C0. Since S0 is the union of finitely many proper subspaces of RN, its Lebesgue measure in RN is 0. And for every x∈RN∖S0, Tx∉C0. That means Φ gives phase retrieval on RN∖S0. Hence Φ gives almost phase retrieval.Remark 9.
In Theorem8, we only need M>N.Proposition7 can be considered as a consequence of Theorem 8. In fact, let E and F be defined as in Proposition 7. We have
(15)rank⁡(EFE-F)=rank⁡(2E0E-F)=rank⁡(2E00-F)=rank⁡(E)+rank⁡(F).
By Theorem 8, we get Proposition 7.Now we have characterizations of frames which give almost phase retrieval. But it is tedious to test if a frame satisfies (6) or (10).Next we give a method to test if a general frame gives almost phase retrieval. By Theorem8, (11) holds if Φ does not give almost phase retrieval. First we give a condition for A satisfying (11).Lemma 10.
LetA be an N×M matrix on R. Suppose that its columns are nonzero. Denote by S the space spanned by rows of A. If the rows of A are orthogonal basis of S, then, for every nonempty proper subset Γ⊂{1,2,…,M},
(16)rank⁡(A)=rank⁡(AAΓ)
holds if and only if, for every k∈Γ, l∈ΓC,
(17)〈colkA,collA〉=0.Proof.
First we prove the necessity. We assume that (16) holds. Then each row of AΓ is a linear combination of rows of A. Therefore there exists cij∈R such that
(18)rowkAΓ=c1krow1A+⋯+cNkrowNA,k=1,2,…,N.
That is,
(19)AΓ=CA,
where C is an N×N matrix on R. Since the rows of A form an orthonormal basis of S, the rows of AΓ form also an orthonormal basis of S. Hence C is an orthogonal matrix. Hence, for every k∈Γ,  l∈Γc,
(20)〈colkA,collA〉=〈C·colkA,C·collA〉=〈colkAΓ,collAΓ〉=-〈colkA,collA〉.
Therefore,
(21)〈colkA,collA〉=0.
Sufficiency. Denote by E and F the matrices consisting of {colkA}k∈Γ and {colkA}k∈ΓC, respectively. Let SE and SF be the spaces spanned by columns of E and F, respectively. By (17), we have
(22)SE⊥SF.
Since each column of A is nonzero, SE and SF are proper subspaces of RN. Therefore, there exists an N×N matrix C on R such that, for every x1∈SE and x2∈SF,
(23)Cx1=x1,Cx2=-x2.
Then we have
(24)CA=AΓ.
Hence we get (16).Lemma10 shows that if the matrix A can not be split into two orthogonal parts, then the corresponding frame Φ (see Theorem 8) gives almost phase retrieval. Here we need the fact that the rows of A are orthogonal. If the columns of A contain a natural basis, the result still holds.Lemma 11.
LetA be an N×M matrix on R. Suppose that the columns of A contain a natural basis {ei}1≤i≤N of  RN. For every nonempty proper subset Γ⊂{1,2,…,M},
(25)rank⁡(A)=rank⁡(AAΓ)
holds if and only if, for every k∈Γ, l∈Γc,
(26)〈colkA,collA〉=0.Proof.
For every nonempty proper subsetΓ⊂{1,2,…,M}, denote by E and F the matrices consisting of {colkA}k∈Γ and {colkA}k∈ΓC, respectively. Suppose that E contains {ei}i∈Θ and F contains {ei}i∈ΘC. Then,
(27)〈colkA,collA〉=0,∀k∈Γ,l∈ΓC,
holds if and only if each column of E is a linear combination of {ei}i∈Θ and each column of F is a linear combination of {ei}i∈ΘC, which is equivalent to rank⁡(E)=|Θ| and rank⁡(F)=|ΘC|=N-rank⁡(E). Therefore,
(28)rank⁡(AAΓ)=rank⁡(E)+rank⁡(F)=N=rank⁡(A).Next we show that we can choose a suitable matrixA to test if Φ gives almost phase retrieval.Theorem 12.
LetA be an N×M matrix on R. Each column of A is nonzero. Denote by S the space spanned by rows of A. Let the (M-N)×M matrix B consist of some  M-N linearly independent vectors in Sc⊂RM. If A gives almost phase retrieval on RN, then B gives almost phase retrieval on RM-N. Moreover, if rows of the N×M matrix A~ on R span S, then A~ also gives almost phase retrieval on RN.Before proving Theorem12, we introduce a result on the Naimark complement of Parseval frames.Proposition 13 (Naimark’s Theorem [14, Theorem 1.9]).
LetΦ={φk}1≤k≤M be a frame for KN with analysis operator T. Let {ek}1≤k≤M be the standard basis of  l2M, and let P:l2M→l2M be the orthogonal projection onto R(T). Then the following conditions are equivalent.(i)
Φ is a Parseval frame for KN.(ii)
For allk=1,2,…,M, we have Pek=Tϕk.(iii)
There exist{ψk}1≤k≤M⊂KM-N such that {φk⊕ψk}1≤k≤M is an orthonormal basis of KM.Moreover, if (iii) holds, then {ψk}1≤k≤M is a Parseval frame for KM-N.We call that{ψk}1≤k≤M is a Naimark complement of {φk}1≤k≤M.Proof of Theorem12.
Take an(M-N)×M matrix D whose rows are orthogonal basis of Sc. Then the columns of D form a Parseval frame of RM-N. Since N(D)=R(A) and A gives almost phase retrieval, by Theorem 8, for any nonempty proper subset Γ⊂{1,2,…,M}, we have
(29)rank⁡(D)<rank⁡(DDΓ).
By Lemma 10, there exist some k∈Γ and l∈Γc such that
(30)〈colkD,collD〉≠0.
Let E be a Naimark complement of D. Then the rows of E belong to S. Since
(31)〈colkE,collE〉+〈colkD,collD〉=0,
we have
(32)〈colkE,collE〉≠0.
By Lemma 10,
(33)rank⁡(E)<rank⁡(EEΓ).
Since N(E)=R(B), B gives almost phase retrieval on RM-N, thanks to Theorem 8.From the above results, we give a method to test if anN×M matrix A gives almost phase retrieval on RN or not.Denote byA1 and A2 the matrices consisting of the first N columns and the last M-N columns of A, respectively. Without loss of generality, we assume that A1 is of rank N. And A1-1A has the following form:
(34)A~=(10⋯0a1,N+1⋯a1,M01⋯0a2,N+1⋯a2,M⋯⋯00⋯1aN,N+1⋯aN,M).
Then A~ gives almost phase retrieval if and only if A does. Without loss of generality, we assume that each column of A~ is nonzero; otherwise we can drop the columns which are zero. Denote
(35)supp⁡(colkA~)={λ:colkλA~≠0},
where colkλA~ is the λth element of colkA~. Next we do the following steps.(1)
Setk1=N+1. If supp⁡(col1A~)={1,2,…,N}, end. Otherwise, set
(36)Γ={k:supp⁡(colk)⊂supp⁡(colk1),N+1≤k≤M}.IfΓ={N+1,N+2,…,M}, end. Otherwise, go to step (2).(2)
Find akl∈{N+1,N+2,…,M}∖Γ such that colkl has two nonzero elements colklλ1A~ and colklλ2A~ satisfying λ1∈⋃1l-1supp⁡(colkiA~) and λ2∈(⋃1l-1supp⁡(colkiA~))C. If there exists no such column of A~, end. Otherwise, go to step (3).(3)
If⋃1lsupp⁡(colkiA~)={1,2,…,N}, end. Otherwise, set
(37)Γ={k:supp⁡(colk)⊂⋃1lsupp⁡(colkiA~),N+1≤k≤M}.IfΓ={N+1,N+2,…,M}, end. Otherwise, go to step (2).After finitely many steps, sayL steps, we get Γ and ⋃1Lsupp⁡(colkiA~)≜Λ finally. There are two cases.(i)
ConsiderΛ≠{1,2,…,N}. For every k1∈Γ∪Λ and k2∈({N+1,N+2,…,M}∖Γ)∪ΛC={1,2,…,M}∖(Γ∪Λ), we have
(38)〈colk1A~,colk2A~〉=0.By Lemma11 and Theorem 8, A~ does not give almost phase retrieval and neither does A.(ii)
ConsiderΛ={1,2,…,N}. For any k1,k2∈{1,2,…,N}, there exist j1,j2,…,js∈{1,2,…,M} such that
(39)〈colk1A,colj1A〉≠0,〈colj1A,colj2A〉≠0,kkkkkkkkkikkkk⋮〈coljs-1A,coljsA〉≠0,〈coljsA,colk2A〉≠0.Therefore, there exists some nonempty proper subsetΓ~⊂{1,2,…,M} satisfying (26). Hence A~ gives almost phase retrieval, and so does A.Remark 14.
Balan et al. [4, Theorem 2.9] proved that A~ gives almost phase retrieval while A~ has a column colkA such that supp⁡colkA={1,2,…,M}. By the above method, it is easy to see that A~ gives almost phase retrieval. And we find more general matrices which give almost phase retrieval in some sense.Remark 15.
In our method, we need to compute the inverse ofA1. But rank⁡(A)=N is necessary; the processes of transforming A to A~ and computing rank⁡(A) are conducted at the same time. Next it is very easy to compute Γ. Therefore, the computation complexity O(M-N) is acceptable.Here we give a method to test if a frame gives almost phase retrieval or not. With this method, we can construct frames which have this property. For the unit norm tight frames, Fickus et al. [13] gave a sufficient condition.Proposition 16 (see [13, Theorem 13]).
IfM and N are relatively prime, then every unit norm tight frame Φ={φk}1≤k≤M∈RN gives almost phase retrieval.Different from Proposition16, for any M>N, we can construct a tight frame Φ={ϕk}1≤k≤M which gives almost phase retrieval from the above methods.First, we can construct anN×M matrix A~ of the form (34) such that it gives almost phase retrieval. For example, we can choose A~ such that one of the last M-N columns does not contain zero element. Second, by the Gram-Schmidt process or other methods, we get a matrix A^ from A~ such that the rows of A^ are orthogonal. Third, let
(40)A~=C·(row1(A^)∥row1(A^)∥2row2(A^)∥row2(A^)∥2⋮rowN(A^)∥rowN(A^)∥2),
where C∈R is a constant. Then the columns of A form a tight frame with frame bound C by the following proposition.Proposition 17 (see [16, Lemma 1.1]).
The columns of anN×M matrix A are a tight frame with frame bound C if and only if
(41)A·AT=C·Id.If anN×M matrix A does not give almost phase retrieval, we know that Λ≠{1,2,…,N} from the above method. Then we can choose a column of A~, say colk0A~, such that k0∈{N+1,N+2,…,M} and supp⁡(colk0)⊂Λ. Let B~ be a matrix satisfying
(42)colkB~={colkA~,k≠k0,colkA~+v,k=k0,
where
(43)vj={ϵj≠0,j∈ΛC,0,others.
Then we can check that set Λ with respect to B~ is {1,2,…,N}. Let B=A1B~. Then B gives almost phase retrieval. On the other hand, the canonical dual frame is always used to reconstruct the original vector. Sun [17] gave the following stability result of canonical dual frame.Proposition 18 (see [17, Theorem 4.1]).
LetΦ and Φ~ and Ψ and Ψ~ be two pairs of canonical dual frames for RN. Denote the frame operator of Φ and Ψ by S and W, respectively. Denote the frame bounds of Φ and Ψ by (α1,β1) and (α2,β2), respectively. Then(i)
ifΦ-Ψ is a Bessel sequence with an upper bound δ, then so is Φ~-Ψ~ with an upper bound δ((α1+β1+β11/2β21/2)/(α1α2))2.(ii)
If(44)|〈Sf,f〉-〈Wf,f〉|≤δ∥f∥22,then(45)|〈S-1f,f〉-〈W-1f,f〉|≤δα1α2∥f∥22.Since(46)∥(B-A)x∥22≤∥A1∥22∥(B~-A~)x∥22=∥A1∥22|〈x,v〉|2≤∥v∥22∥A1∥22∥x∥22,
for every x∈RN, for ∥v∥22 small enough, the matrix B is a good approach of A. Denote the frames consisting of the columns of A and B by Φ and Ψ, respectively. From Proposition 18, we see that the canonical dual frame of Ψ is also a good approach of the canonical dual frame of Φ. Hence, if A does not give almost phase retrieval, we can get a new matrix B which gives almost phase retrieval with a little change. And the process system is stable.


## 3. Numerical Results

In this section, we provide some examples to show the frames in Theorem8 give almost phase retrieval.LetΦ={φk}1≤k≤M be a frame for RN with analysis operator T. For x∈RN, we want to recover x from {|〈x,φk〉|}1≤k≤M. Based on Theorem 8, we use the following algorithm.(i)
Take some(M-N)×M matrix A such that N(A)=R(T). For every α=(α1,α2,…,αM), αk=±1, 1≤k≤M, denote
(47)bα=(α1|〈x,φ1〉|,α2|〈x,φ2〉|,…,|〈x,αMφM〉|).(ii)
Computeϵα=A·bα. Set
(48)α0=argminα⁡∥A·bα∥2.(iii)
Sety=∑1≤k≤M‍αk0|〈x,φk〉|ψk, where {ψk}1≤k≤M is a dual frame of Φ. Then y=±x.A practical method to construct the desired frameΦ is using random vectors. Given M and N, let Φ be a set of vectors in RN with entries generated with the Gaussian random variable. In our tests, any frame generated in this way satisfies (10). For simplicity, we take (N,M)=(8,9) and (N,M)=(8,10).We test our algorithm to recover signals from their intensity measurements with different noise levels. That is, the measurement is{|〈x,φk〉|+nk}1≤k≤M where n=(n1,n2,…,nM) is a noise with the norm σ. We perform 5 trials. In each trial, we generate a set of new random vectors and solve the phase retrieval problem with 1000 random vectors with norm 1. Figures 1 and 2 show the results of the 5 trials. We see that the result is perfect and noise free. Whenever σ<1/2M-1, the performance is good. Observe that the aliasing occurs for signals in S0 consisting of 2M-1 proper subspaces. The results are also acceptable with larger noises. This shows that the frames in Theorem 8 can give phase retrieval with high probability.Recovery of signals from their intensity measurements with different noise levels, whereN=8 and M=9.
(a)
Trial 1
(b)
Trial 2
(c)
Trial 3
(d)
Trial 4
(e)
Trial 5Recovery of signals from their intensity measurements with different noise levels, whereN=8 and M=10.
(a)
Trial 1
(b)
Trial 2
(c)
Trial 3
(d)
Trial 4
(e)
Trial 5


## 4. Conclusion

In this paper, we show thatN+1 intensity measurements are enough to reconstruct almost all signals of  length N. With our characterization, we provide a method to test if a frame has this property. Numerical results show that we can use these frames to recover signals with high probability.



---

*Source: 384613-2014-09-25.xml*