Phase retrieval

Introduction

In the setting of frame theory, the concept of phaseless reconstruction was introduced in 2006 by Balan, Casazza, and Edidin . At that time, they classified phaseless reconstruction in the real case by proving that a generic family of (2N-1)-vectors in $\mathcal{R}^{N}$ does phaseless reconstruction and no set of (2N-2)-vectors can do this. In the complex case, they showed that a generic set of (4N-2)-vectors does phaseless reconstruction. Since then there has been a multitude of mathematical research devoted to this area. One area in particular is the study of phaseless reconstruction by projections onto subspaces. An in depth study of phase retrieval by projections was done by Cahill, Casazza, Peterson, and Woodland in where they showed that phase retrieval by projections can be done in the real case with $(2N-1)$-projections of arbitrary non-trivial rank and in the complex case with $(4N-2)$-projections. We continue the study of phase retrieval by providing a variety of new results in both the one-dimensional and higher dimensional cases as well as giving a large number of examples showing the limitations of the theory.

The complex case has proven to be a very difficult problem and as such has yet to be fully classified. There has been incremental progress towards this end and in particular Heinossaari, Mazzarella and Wolf showed that M-vectors doing phaseless reconstruction in $\mathcal{C}^{N}$ requires $M\geq 4N-4-2\alpha$, where $\alpha$ is the number of $1^{\prime}s$ in the binary expansion of $(N-1)$. Bodmann later showed that phaseless reconstruction in $\mathcal{C}^{N}$ can be done with $(4N-4)$-vectors. Following this, Conca, Edidin, Hering, and Vinzant proved that a generic frame with $(4N-4)$-vectors does phaseless reconstruction in $\mathcal{C}^{N}$. They also showed that if $N=2^{k}+1$ then no set of $M$-vectors with $M<4N-4$ can do phaseless reconstruction. Bandeira, Cahill, Mixon, and Nelson conjectured that for all $N$, no fewer than $(4N-4)$-vectors can do phaseless reconstruction. Recently, Vinzant showed that this conjecture does not hold by giving 11 vectors in $\mathcal{C}^{4}$ which do phase retrieval. And recently, Xu showed that phase retrieval can be done in $\mathcal{R}^{4}$ with six 2-dimensional subspaces.

Frame Theory

This section first provides a basic review of necessary terms and theorems from finite frame theory and then goes on to develop numerous new results regarding frames, Riesz bases and complements. For a more in depth study of finite frame theory the interested reader is referred to Finite Frames: Theory and Applications . To set notation, given $N\in\mathcal{N}$, $\mathcal{H}_{N}$ represents a $($real or complex$)$ Hilbert space of $($finite$)$ dimension $N$.

A family of vectors $\{\varphi_{i}\}_{i=1}^{M}$ in an $N$-dimensional Hilbert space $\mathcal{H}_{N}$ is a frame if there are constants $0<A\leq B<\infty$ so that for all $x\in\mathcal{H}_{M}$,

where $A$ and $B$ are lower and upper frame bounds, respectively. The largest $A$ and smallest $B$ satisfying these inequalities are called the optimal frame bounds.

If $A=B$ is possible, then $\{\varphi_{i}\}_{i=1}^{M}$ is an A-tight frame. If $A=B=1$ is possible, then $\{\varphi_{i}\}_{i=1}^{M}$ is a Parseval frame.

If $\|\varphi_{i}\|=1$ for all $i\in[M]$ then $\{\varphi_{i}\}_{i=1}^{M}$ is an unit norm frame.

$\{\langle x,\varphi_{i}\rangle\}_{i=1}^{M}$ are called the frame coefficients of the vector $x\in\mathcal{H}_{N}$ with respect to frame $\{\varphi_{i}\}_{i=1}^{M}$.

The frame operator S of the frame, for any $x\in\mathcal{H}_{N}$, is given by

The frame operator is a particularly important object in the study of frame theory.

Let $\{\varphi_{i}\}_{i=1}^{M}$ be a frame for $\mathcal{H}_{N}$ with frame bounds $A$ and $B$ and frame operator $S$. $S$ is positive, invertible, and self adjoint. Moreover, the optimal frame bounds of $\{\varphi_{i}\}_{i=1}^{M}$ are given by $A=\lambda_{min}(S)$ and $B=\lambda_{max}(S)$, the minimum and maximum eigenvalues of $S$, respectively.

In particular, the frame operator of a Parseval frame is the identity operator. This fact makes Parseval frames very helpful in applications because they possess the property of perfect reconstruction. That is, $\{\varphi_{i}\}_{i=1}^{M}$ is a Parseval frame for $\mathcal{H}_{N}$ if and only if for any $x\in\mathcal{H}_{N}$ we have

There is a direct method for constructing Parseval frames. For $M\geq N$, given an $M\times M$ unitary matrix, select any $N$ rows from this matrix, then the column vectors from these rows form a Parseval frame for $\mathcal{H}_{N}$. Moreover, the leftover set of $M-N$ rows also have the property that its $M$ columns form a Parseval frame for $\mathcal{H}_{M-N}$. The following well known theorem, known as Naimark’s Theorem, utilizes this type of construction and shows that this is the only way to obtain Parseval frames.

$\{\varphi_{i}\}_{i=1}^{M}$ is a Parseval frame for $\mathcal{H}_{N}$.

For all $i=1,\dots,M$, we have $Pe_{i}=T\varphi_{i}$.

There exist $\psi_{1},\dots,\psi_{M}\in\mathcal{H}_{M-N}$ such that $\{\varphi_{i}\oplus\psi_{i}\}_{i=1}^{M}$ is an orthonormal basis of $\mathcal{H}_{M}$.

Moreover, if (3) holds, then $\{\psi_{i}\}_{i=1}^{M}$ is a Parseval frame for $\mathcal{H}_{M-N}$. If $\{\psi^{\prime}_{i}\}_{i=1}^{M}$ is another Parseval frame as in (3), then there exists a unique unitary operator $L$ on $\mathcal{H}_{M-N}$ such that $L\psi_{i}=\psi_{i}^{\prime},$ for all $i=1,\dots,M$.

Explicitly, we call $\{\psi_{i}\}_{i=1}^{M}$ the Naimark Complement of $\Phi$. If $\Phi=\{\varphi_{i}\}_{i=1}^{M}$ is a Parseval frame, then the analysis operator $T$ of the frame is an isometry. So we can associate $\varphi_{i}$ with $T\varphi_{i}=Pe_{i}$, and with a slight abuse of notation we have:

$\Phi=\{\varphi_{i}\}_{i=1}^{M}$ is a Parseval frame for $\mathcal{H}_{N}$ if and only if there is an $M$-dimensional Hilbert space $\mathcal{K}_{M}$ with an orthonormal basis $\{e_{i}\}_{i=1}^{M}$ such that the orthogonal projection $P:\mathcal{K}_{M}\rightarrow\mathcal{H}_{N}$ satisfies $Pe_{i}=\varphi_{i}$ for all $i=1,\dots,M$. Moreover, the Naimark complement of $\Phi$ is $\{(I-P)e_{i}\}_{i=1}^{M}.$

Note that Naimark complements are only defined for Parseval frames. Furthermore, Naimark complements are only defined up to unitary equivalence. That is, if $\{\varphi_{i}\}_{i=1}^{M}\subseteq\mathcal{H}_{N}$ and $\{\psi_{i}\}_{i=1}^{M}\subseteq\mathcal{H}_{M-N}$ are Naimark complements, and $U$ and $V$ are unitary operators, then $\{U\varphi_{i}\}_{i=1}^{M}$ and $\{V\psi_{i}\}_{i=1}^{M}$ are also Naimark complements.

To clarify terminology, as mentioned in Naimark’s Theorem and as will be throughout this paper, an orthogonal projection or simply a projection is a self-adjoint projection.

Frames in the finite dimensional setting are just spanning sets. At times, it is useful to look at subsets of a frame which are also spanning sets.

A frame $\{\varphi_{i}\}_{i=1}^{M}$ in $\mathcal{H}_{N}$ satisfies the complement property if for all subsets $S\subset\{1,\dots,M\}$, either $\operatorname{span}\{\varphi_{i}\}_{i\in S}=\mathcal{H}_{N}$ or $\operatorname{span}\{\varphi_{i}\}_{i\in S^{c}}=\mathcal{H}_{N}$.

Given a family of vectors $\Phi=\{\varphi_{i}\}_{i=1}^{M}$ in $\mathcal{H}_{N}$, the spark of $\Phi$ is defined as the cardinality of the smallest linearly dependent subset of $\Phi$. When $\operatorname{spark}(\Phi)=N+1$, every subset of size $N$ is linearly independent and $\Phi$ is said to be full spark.

Let $\Phi:=\{\varphi_{i}\}_{i=1}^{M}$ be a frame in $\mathcal{H}_{N}$ such that $M\geq 2N-1$.

If $\Phi$ is full spark then $\Phi$ has the complement property.

If $\Phi$ has the complement property and $M=2N-1$ then $\Phi$ is full spark.

The notion of spark is the measure of how resilient a frame is against erasures, so full spark is a desired property of a frame. In general, it is very difficult to check the spark of a frame. In attempts to further characterize full spark frames, in the authors classified full spark Parseval frames through the use of the frame’s Naimark complement.

A Parseval frame is full spark if and only if its Naimark complement is full spark.

Often times in applications, a frame is linearly dependent and hence the decomposition of a signal with respect to a frame is not unique. However, it may be necessary to have a unique decomposition without restricting the frame to such properties as orthogonality. A Riesz basis provides this uniqueness and does not have as strong of a condition as orthogonality.

A spanning family of vectors $\{\varphi_{i}\}_{i=1}^{N}$ in a Hilbert space $\mathcal{H}_{N}$ is called a Riesz basis with lower (respectively, upper) Riesz bounds A (respectively, B), if, for all scalars $\{a_{i}\}_{i=1}^{N}$, we have

Let $P$ be a projection on $\mathcal{H}_{M}$ with orthonormal basis $\{e_{i}\}_{i=1}^{M}$ and let $I\subset\{1,2,\ldots,M\}$. The following are equivalent:

$\{Pe_{i}\}_{i\in I}$ is linearly independent.

$\{\left(I-P\right)e_{i}\}_{i\in I^{c}}$ spans $\left(I-P\right)\mathcal{H}$.

Let $P$ be a projection of rank $N$ on $\mathcal{H}_{M}$ with orthonormal basis $\{e_{i}\}_{i=1}^{M}$. The following are equivalent:

(1) $\{Pe_{i}\}_{i=1}^{M}$ has the complement property.

(2) Whenever we partition $\{(I-P)e_{i}\}_{i=1}^{M}$ into two sets, one of them is linearly independent.

The previous results analyze when a collection of projections and their orthogonal complements are linearly independent and when they possess the complement property. A natural next step is to see when a projection of an orthonormal basis is full spark.

Let $P$ be a projection of rank $N$ on $\mathcal{H}_{M}$ with orthonormal basis $\{e_{i}\}_{i=1}^{M}$. The following are equivalent:

(1) $\{Pe_{i}\}_{i=1}^{M}$ is full spark.

(2) For every $I\subset\{1,2,\ldots M\}$ with $|I|=M-N$ the vectors $\{(I-P)e_{i}\}_{i\in I}$ spans $(I-P)(\mathcal{H})$.

This follows immediately from Proposition 2.8.∎

Instead of only considering an orthonormal basis for our projections, the next proposition slightly generalizes this idea by using Riesz bases.

Let $\{\varphi_{i}\}_{i=1}^{N}$ be a Riesz basis with dual basis $\{\varphi_{i}^{*}\}_{i=1}^{N}$ for $\mathcal{H}_{N}$ and let $P$ be an orthogonal projection on $\mathcal{H}_{N}$ of rank $M$. Let $I\subset\{1,\dots,N\}$. The following are equivalent:

$\{P\varphi_{i}\}_{i\in I}$ spans $P\mathcal{H}_{N}$

$\{(I-P)\varphi_{i}^{*}\}_{i\in I^{c}}$ is independent.

(1) $\Rightarrow$ (2) (Proof by contrapositive.) Assume $\{(I-P)\varphi_{i}^{*}\}_{i\in I^{c}}$ is NOT independent. Choose $\{b_{i}\}_{i\in I^{c}}$ not all zero so that $\sum_{i\in I^{c}}b_{i}(I-P)\varphi_{i}^{*}=0$. Then $x:=\sum_{i\in I^{c}}b_{i}\varphi_{i}^{*}=\sum_{i\in I^{c}}b_{i}P\varphi_{i}^{*}\in P\mathcal{H}_{N}$. If $j\in I$, then

since $i\in I^{c}$ and $j\in I$. Thus $x\perp\operatorname{span}\{P\varphi_{j}\}_{j\in I}$ showing that $\{P\varphi_{j}\}_{j\in I}$ does not span $P\mathcal{H}_{N}$.

(2) $\Rightarrow$ (1) (Proof by contrapositive.) Assume $\operatorname{span}\{P\varphi_{i}\}_{i\in I}\neq P\mathcal{H}_{N}$. Then there exists a non-zero $x\in P\mathcal{H}_{N}$ with $x\perp\operatorname{span}\{P\varphi_{i}\}_{i\in I}$. Also $x=\sum_{i=1}^{N}\langle x,\varphi_{i}\rangle\varphi_{i}^{*}$. Now for $i\in I,\langle x,P\varphi_{i}\rangle=\langle Px,\varphi_{i}\rangle=\langle x,\varphi_{i}\rangle=0$. Hence

Thus, $\sum_{i\in I^{c}}\langle x,\varphi_{i}\rangle(I-P)\varphi_{i}^{*}=0$ where $\langle x,\varphi_{i}\rangle\neq 0$ for at least one $i\in I^{c}$. Therefore $\{(I-P)\varphi_{i}^{*}\}_{i\in I^{c}}$ is NOT independent.∎

Similarly, the following result classifies full spark projections of Riesz bases as follows.

Let $\{\varphi_{i}\}_{i=1}^{N}$ be a Riesz basis on $\mathcal{H}_{N}$ and $P$ an orthogonal projection on $\mathcal{H}_{N}$ of rank $M$. The following are equivalent:

$\{P\varphi_{i}\}_{i=1}^{N}$ is full spark.

For all $I\subset\{1,2,\ldots,N\}$ with $|I|=M$ we have:

$\{P\varphi_{i}\}_{i=1}^{N}$ is not full spark if and only if there exists an $I\subset\{1,2,\ldots,N\}$ with $|I|=M$ and $\{a_{i}\}_{i\in I}$ not all zero such that $\sum_{i\in I}a_{i}P\varphi_{i}=0$ if and only if $\sum_{i\in I}a_{i}(I-P)\varphi_{i}=\sum_{i\in I}a_{i}\varphi_{i}$ if and only if

A natural question to ask, in light of Proposition 2.14, is if $\{\varphi_{i}\}_{i=1}^{N}$ is a Riesz basis for $\mathcal{H}_{N}$ and $\{P\varphi_{i}\}_{i=1}^{N}$ is full spark on its range for some rank-$M$ projection $P$, then is $\{(I-P)\varphi_{i}\}_{i=1}^{N}$ full spark on its range? The following example shows that the answer is no.

Let $\{e_{1},e_{1}+e_{2}\}$ be a Riesz basis for $\mathcal{R}^{2}$, where $\{e_{i}\}_{i=1}^{2}$ is the standard orthonormal basis for $\mathcal{R}^{2}$. Let $P$ be the rank-1 projection onto $e_{1}$. Then $\{Pe_{1},P(e_{1}+e_{2})\}=\{e_{1}\}$ is full spark on its range. However, $\{(I-P)e_{1},(I-P)(e_{1}+e_{2})\}=\{0,e_{2}\}$ is not full spark on its range.

Phase Retrieval

Phase retrieval has been a long standing problem in mathematics and engineering alike. Recently, the mathematical study of phase retrieval by subspace components (or projections) has been more deeply developed and we further study this area here. In particular, this section expands and generalizes a few results from and as well as develops many new results with its main theorem focused on classifying phase retrieval by projections via norm retrieval by vectors.

A family of vectors $\{\varphi_{i}\}_{i=1}^{M}$ does phase retrieval in $\mathcal{H}$ if whenever $x,y\in\mathcal{H}$ satisfy

A family of projections $\{P_{i}\}_{i=1}^{M}$ does phase retrieval in $\mathcal{H}$ if whenever $x,y\in\mathcal{H}$ satisfy

If $\{W_{i}\}_{i=1}^{M}$ is a family of subspaces of $\mathcal{H}$, we say they do phase retrieval if the orthogonal projections onto the $W_{i}$ do phase retrieval.

One of the main results in is the following.

A family of vectors $\Phi$ in $R^{N}$ does phase retrieval if and only if $\Phi$ has the complement property. In the complex case, phase retrieval implies complement property but the converse fails.

In , the authors analyzed phase retrieval by projections and provided the following results.

Phase retrieval in $\mathcal{R}^{N}$ is possible using $2N-1$ subspaces, each of any dimension less than $N$.

Phase retrieval in $\mathcal{C}^{N}$ is possible using $4N-3$ subspaces, each of any dimension less than $N$.

If $\{\varphi_{i}\}_{i=1}^{M}$ is a frame in $\mathcal{H}_{N}$ which allows phase retrieval then $\{P\varphi_{i}\}_{i=1}^{M}$ allows phase retrieval for all orthogonal projections $P$ on $\mathcal{H}_{N}$.

Generalizing Proposition 3.4 to subspaces leads to the following result.

If $\{e_{i}\}_{i=1}^{2N}$ is an orthonormal basis for $\mathcal{H}_{2N}$, then for all $k\leq N$ there exists a projection of $\mathcal{H}_{2N}$ onto a $k$-dimensional subspace $W$ such that $\{Pe_{i}\}_{i=1}^{2N}$ does phase retrieval on its range.

We can further generalize Proposition 3.5 to Riesz bases as follows.

If $\Phi=\{\varphi_{i}\}_{i=1}^{M}$ is a Riesz basis for $\mathcal{H}_{M}$ and $N\leq M$ then there exists a projection $P$ on $\mathcal{H}_{M}$ of rank $N$ so that $\{P\varphi_{i}\}_{i=1}^{M}$ is full spark on its range. Hence, if $2N-1\leq M$ then $\{P\varphi_{i}\}_{i=1}^{M}$ yields phase retrieval on its range.

Let $S$ be the frame operator for $\Phi$. Then $\{S^{-\frac{1}{2}}\varphi_{i}\}_{i=1}^{M}$ is an orthonormal basis for $\mathcal{H}_{M}$. Hence, there exists a projection $P$ of rank $N$ such that $\{PS^{-\frac{1}{2}}\varphi_{i}\}_{i=1}^{M}$ is full spark. Thus by Proposition 2.14, $(I-P)\mathcal{H}_{M}\cap\operatorname{span}\{S^{-\frac{1}{2}}\varphi_{i}\}_{i\in I}=\{0\}$ for all $I\subset\{1,\dots,M\}$ with $|I|=N$.

Let $W=S^{\frac{1}{2}}(I-P)\mathcal{H}_{M}$ and suppose $x\in W\cap\operatorname{span}\{\varphi_{i}\}_{i\in I}$. Then $x=S^{\frac{1}{2}}(I-P)y=\sum_{i\in I}b_{i}\varphi_{i}$ for some $y\in\mathcal{H}_{M}$, and $b_{i}\in H$. So

Now let $Q$ be the projection onto $W$. Then $\{(I-Q)\varphi_{i}\}_{i=1}^{M}=\{P\varphi_{i}\}_{i=1}^{M}$ is full spark, by Proposition 2.14. When $2N-1\leq M$ then $\{(I-Q)\varphi_{i}\}_{i=1}^{M}=\{P\varphi_{i}\}_{i=1}^{M}$ is full spark and thus has the complement property. Therefore $\{P\varphi_{i}\}_{i=1}^{M}$ yields phase retrieval. ∎

The set of vectors $\{e_{1},e_{2},e_{3},e_{1}+e_{2},e_{1}+e_{3},e_{2}+e_{3}\}$ have the property that it does phase retrieval but no full spark subset does phase retrieval.

If $\{\varphi_{i}\}_{i=1}^{M}$ is a Riesz basis for $\mathcal{H}_{M}$ with dual Riesz basis $\{\varphi_{i}^{*}\}_{i=1}^{M}$ and $2N-1\leq M\leq 2N+1$, then there exists a projection $P$ of rank $N$ so that both of the following hold:

$\{P\varphi_{i}\}_{i=1}^{M}$ does phase retrieval on its range, and

$\{(I-P)\varphi_{i}^{*}\}_{i=1}^{M}$ does phase retrieval on its range.

The proof follows from Proposition 3.6. ∎

In , the authors provided necessary and sufficient conditions for when subspaces do phase retrieval by relating them to the one dimensional case. Their results were proven for the real case. The complex case is more technical so we will prove this here. To accomplish this, we give a few preliminary results. Note that the following results hold in both the real and complex case.

Let $\{W_{i}\}_{i=1}^{M}$ be subspaces of $\mathcal{H}_{N}$ allowing phase retrieval. For every orthonormal basis $\{\varphi_{i,j}\}_{j=1}^{J_{i}}$ of $W_{i}$, the set $\Phi=\{\varphi_{i,j}\}_{i=1,j=1}^{M,J_{i}}$ allows phase retrieval in $\mathcal{H}_{N}$.

Let $P_{i}$ be the orthogonal projection onto $W_{i}$ for each $i=\{1,\dots,M\}$. For every $i=1,2,\ldots,M$ and for any $x,y\in\mathcal{H}_{N}$ such that $|\langle x,\varphi_{i,j}\rangle|=|\langle y,\varphi_{i,j}\rangle|$ for all $j=\{1,\dots,J_{i}\}$, we have

Since $\{W_{i}\}_{i=1}^{M}$ allows phase retrieval it follows that $x=cy$ for some $c\in\mathcal{C}$ with $|c|=1$. Hence, $\Phi$ allows phase retrieval. ∎

Let $P$ be a projection onto an $M$-dimensional subspace, $W$, of $\mathcal{H}_{N}$. Given $x,y\in\mathcal{H}_{N}$, the following are equivalent:

There exists an orthonormal basis $\{\varphi_{i}\}_{i=1}^{M}$ for $W$ such that $|\langle x,\varphi_{i}\rangle|=|\langle y,\varphi_{i}\rangle|$, for all $i=1,2,\ldots,M$.

$(1)\Rightarrow(2)$: Consider the vectors $Px,Py\in W$ with $\|Px\|=\|Py\|$. We examine the following three cases.

Case 1: Assume $Px=cPy$ for some $|c|=1$.

In this case, for any orthonormal basis $\{\varphi_{i}\}_{i=1}^{M}$ for $W$ we have

Hence, for the next two cases, we can assume $Px\not=cPy$ for any $|c|=1$.

Case 2: Assume $\langle Px,Py\rangle=0$. Hence $\langle Py,Px\rangle=0$.

Note $\varphi_{1}$ and $\varphi_{2}$ are both unit norm. Letting $c=1/(\|Px+Py\|\|Px-Py\|)$ we have

So $\{\varphi_{1},\varphi_{2}\}$ is an orthonormal set. Also,

Similarly, $|\langle x,Px-Py\rangle|=|\langle y,Px-Py\rangle|.$ Hence, $|\langle x,\varphi_{i}\rangle|=|\langle y,\varphi_{i}\rangle|$ for $i=1,2$. Note that $Px,Py\in\operatorname{span}{\{\varphi_{1},\varphi_{2}\}}$. Now, take $\{\varphi_{i}\}_{i=1}^{M}$ to be any orthonormal completion of $\{\varphi_{1},\varphi_{2}\}$ to an orthonormal basis for $W$. Then, for all $i=3,4,\ldots,M$ we have

Therefore, $|\langle x,\varphi_{i}\rangle|=|\langle y,\varphi_{i}\rangle|$ for all $i=\{1,\dots,M\}$ where $\{\varphi_{i}\}_{i=1}^{M}$ is an orthonormal basis for $W$, as desired.

In this case, let $d=\langle Px,Py\rangle/|\langle Px,Py\rangle|$ so that $|d|=1$, and let

Note that $\varphi_{1}$ and $\varphi_{2}$ are both unit norm. Letting $c=1/\|Px+dPy\|\|Px-dPy\|$ we have

Hence, $\{\varphi_{1},\varphi_{2}\}$ is an orthonormal set. Now the proof follows as in Case 2.

$(2)\Rightarrow(1)$: This is immediate by:

Combining Lemma 3.9 and Lemma 3.10, we arrive at a characterization for when $\{W_{i}\}_{i=1}^{M}$ does phaseless reconstruction in $\mathcal{H}_{N}$ in terms of orthonormal bases. Note, in the authors proved the following result for the real case. We will now give the proof for the complex case.

Let $\{W_{i}\}_{i=1}^{M}$ be subspaces of $\mathcal{H}_{N}$. The following are equivalent:

$\{W_{i}\}_{i=1}^{M}$ allows phase retrieval in $\mathcal{H}_{N}$.

For every orthonormal basis $\{\varphi_{i,j}\}_{j=1}^{J_{i}}$ of $W_{i}$, the set $\{\varphi_{i,j}\}_{i=1,j=1}^{M,J_{i}}$ allows phase retrieval in $\mathcal{H}_{N}$.

$(2)\Rightarrow(1)$: Suppose we have $x,y\in\mathcal{H}_{N}$ with $\|P_{i}x\|=\|P_{i}y\|$, for all $i=1,2,\ldots,M$. By Lemma 3.10 we can choose orthonormal bases $\Phi=\{\varphi_{i,j}\}_{i=1,j=1}^{M,J_{i}}$ so that

By (2), $\Phi$ does phase retrieval and so $x=cy$ for some $|c|=1$. I.e. $\{W_{i}\}_{i=1}^{M}$ does phase retrieval. ∎

Since orthonormal bases are very restrictive, we would like to relax the conditions in Theorem 3.11 to see what properties the vectors within the subspaces have when the $\{W_{i}\}_{i=1}^{M}$ are assumed to allow phase retrieval. A natural next step would be to look at a Riesz basis as opposed to orthogonal vectors. In particular, since unitary operators are the only linear operators which preserve orthogonality, by moving to a Riesz basis we can instead look at invertible operators. However, the following example shows that if $\{W_{i}\}_{i=1}^{M}$ allows phase retrieval in $\mathcal{R}^{N}$ and $\{\varphi_{ij}\}_{j=1}^{J_{i}}$ is a Riesz basis for $W_{i}$ for each $i\in\{1,\dots,M\}$ then it is not necessarily true that $\{\varphi_{ij}\}_{j=1,i=1}^{M,J_{i}}$ allows phase retrieval in $\mathcal{R}^{N}$.

Let $\{e_{i}\}_{i=1}^{3}$ be an orthonormal basis for $\mathcal{R}^{3}$. Define the subspaces

Let $x\in R^{3}$. Then $x=\sum_{i=1}^{3}\alpha_{i}e_{i}$ where $\alpha_{i}=\langle x,e_{i}\rangle$ for $i=1,2,3$. We have

First, we will show that we can recover $\pm x$ from $\{||P_{W_{i}}x||^{2}\}_{i=1}^{6}$.

We can recover the absolute values of the coefficients:

Thus, if two of the coefficients are zero then we have $x=\pm|\alpha_{i}|e_{i}$ for some $i$. From now on we will assume at least two of the coefficients are nonzero.

Case 1: Assume $\alpha_{1}=0$. We may assume without loss of generality that $\alpha_{2}>0$, and thus $\alpha_{2}=||P_{W_{2}}x||$. Finally,

Case 2: Assume $\alpha_{1}\neq 0$. We may assume without loss of generality that $\alpha_{1}>0$, and thus

This shows that $\{W_{i}\}_{i=1}^{6}$ does phase retrieval.

However, if we choose the linearly independent (and not orthonormal) basis $\{e_{1}+e_{2},e_{2}\}$ for $W_{1}$ and the spanning element from the other subspaces, we get the set of vectors $\{e_{1}+e_{2},e_{2},e_{2},e_{3},e_{1}+e_{2},e_{2}+e_{3},e_{1}+e_{3}\}=\{e_{1}+e_{2},e_{2},e_{3},e_{2}+e_{3},e_{1}+e_{3}\}$. Notice that if we partition this set as follows $\{e_{2}+e_{3},e_{2},e_{3}\},\{e_{1}+e_{2},e_{1}+e_{3}\}$ then neither set spans $R^{3}$. Hence this set does not have the complement property and therefore does not allow phase retrieval.

In Example 3.12, $\{W_{i}^{\perp}\}_{i=1}^{6}$ does phase retrieval. To see this, we just need to see that this family can retrieve the norm of any vector $x\in\mathcal{R}^{3}$. Let $\{Q_{i}\}_{i=1}^{6}$ be the orthogonal projections onto each of $\{W_{i}^{\perp}\}_{i=1}^{6}$. Then,

Given a vector $x\in\mathcal{R}^{3}$, we have

Hence we know $\{|\langle x,e_{i}\rangle|^{2}\}_{i=1}^{3}$ and so we know $\|x\|^{2}$.

In light of Example 3.12 we cannot replace “orthonormal bases” with “Riesz bases” in Theorem 3.11 (2). The next theorem shows that the key property of orthonormal bases in Theorem 3.11 is not just that they span, but that they give norm retrieval.

A family of vectors $\{\varphi_{i}\}_{i=1}^{M}$ does norm retrieval in $\mathcal{H}_{N}$ if whenever $x,y\in\mathcal{H}_{N}$ satisfy

A family of projections $\{P_{i}\}_{i=1}^{M}$ does norm retrieval in $\mathcal{H}_{N}$ if whenever $x,y\in\mathcal{H}_{N}$ satisfy

Let $\{W_{i}\}_{i=1}^{M}$ be subspaces of $\mathcal{H}_{N}$. The following are equivalent:

$\{W_{i}\}_{i=1}^{M}$ allows phase retrieval in $\mathcal{H}_{N}$.

For every sequence $\{\varphi_{i,j}\}_{j=1}^{J_{i}}\subset W_{i}$ which gives norm retrieval in $W_{i}$, the sequence $\{\varphi_{i,j}\}_{j=1,i=1}^{J_{i},M}$ allows phase retrieval.

(1) $\Rightarrow$ (2) For each $i=1,\ldots,M$ let $\{\varphi_{i,j}\}_{j=1}^{J_{i}}$ be a sequence in $W_{i}$ which gives norm retrieval in $W_{i}$. Let $x,y\in\mathcal{H}_{N}$ such that $|\langle x,\varphi_{i,j}\rangle|=|\langle y,\varphi_{i,j}\rangle|$ for all $j=1,\ldots,J_{i}$, $i=1,\ldots,M$. For each $i=1,\ldots,M$ let $P_{i}$ be the projection onto $W_{i}$. We have

and since $\{\varphi_{i,j}\}_{j=1}^{J_{i}}$ gives norm retrieval in $W_{i}$, we have $\|P_{i}x\|=\|P_{i}y\|$ for all $i=1,\ldots,M$. Since $\{W_{i}\}_{i=1}^{M}$ gives phase retrieval, we have $x=cy$ for some $c$ with $|c|=1$.

(2) $\Rightarrow$ (1) Since orthonormal bases give norm retrieval, (2) implies that each sequence $\{\varphi_{i,j}\}_{j=1,i=1}^{J_{i},M}$ gives phase retrieval, where $\{\varphi_{i,j}\}_{j=1}^{J_{i}}$ is an orthonormal basis for $W_{i}$. Theorem 3.11 implies that the subspaces $\{W_{i}\}_{i=1}^{M}$ allow phase retrieval.∎

Theorem 3.15 provides a clear connection between phase retrieval by projections and sequences of vectors giving norm retrieval. In conjunction with this theorem, recall the following theorems from and .

Given $\{\varphi_{i}\}_{i=1}^{M}$ spanning $\mathcal{H}_{N}$, there exists an invertible operator $T$ on $\mathcal{H}_{N}$ so that the collection of orthogonal projections onto the vectors $\{T\varphi_{i}\}_{i=1}^{M}$ allows norm retrieval.

If a family of vectors $\{\varphi_{i}\}_{i=1}^{M}$ does phase retrieval on $\mathcal{H}_{N}$ and $T$ is an invertible operator on $\mathcal{H}_{N}$, then $\{T\varphi_{i}\}_{i=1}^{M}$ does phase retrieval.

In light of these results, it seems natural to question if invertible operators preserve phase retrieval by projections. However, the following example illustrates that Theorem 3.17 fails in the higher dimensional case.

Let $\{e_{i}\}_{i=1}^{3}$ be the standard orthonormal basis in $\mathcal{R}^{3}$. Define the subspaces $\{W_{i}\}_{i=1}^{6}$ as in Example 3.12. Define the linear operator $T$ on the basis elements by:

We can choose the following orthonormal bases from each subspace:

Indeed, if we partition this set into the following two sets:

then we see that neither of the two sets spans $\mathcal{R}^{3}$. Thus the subspaces $\{TW_{i}\}_{i=1}^{6}$ do not yield phase retrieval. Therefore, we have shown that there exists a bounded operator $T$ such that $\{TW_{i}\}_{i=1}^{6}$ does not yield phase retrieval, even though the original subspaces, $\{W_{i}\}_{i=1}^{6}$, did yield phase retrieval.

Subspaces which allow phase retrieval

In this section we develop properties of vectors and subspaces which allow phase retrieval. In particular, we start with a frame which fails phase retrieval and compute the minimum number of vectors necessary to add to the frame so that it will yield phase retrieval. After this computation, we then actually construct such sets. The following results show that for a given frame which fails the complement property, then for all partitions $I_{1},I_{2}$ of the frame for which neither set spans $\mathcal{R}^{M}$, there is a minimal number of vectors we can add to make this set possess the complement property. Moreover, there is an open dense set of vectors which suffice.

Let $\{\varphi_{i}\}_{i=1}^{M}$ be a frame for $\mathcal{R}^{N}$. Fix $k\in N\cup\{0\}$ such that

Then there exists $\{\varphi_{M+1},\dots,\varphi_{M+k}\}\subset\mathcal{R}^{N}$ such that $\{\varphi_{i}\}_{i=1}^{M+k}$ has the complement property. Moreover, if $\{\varphi_{i}\}_{i=1}^{M}\cup\{\psi_{j}\}_{j=1}^{s}$ has the complement property, then $s\geq k$.

Let $\{\varphi_{i}\}_{i=1}^{M}$ be a frame for $\mathcal{R}^{N}$. Fix $k\in M\cup\{0\}$ such that

Since $\{\varphi_{i}\}_{i=1}^{M}$ is a finite collection of vectors then there is a finite number of sets $I\subset A_{0}$. For each $I\subset A_{0}$ we see that $\operatorname{dim}(\operatorname{span}\{\varphi_{i}\}_{i\in I})\leq N-1$ and $\operatorname{dim}(\operatorname{span}\{\varphi_{i}\}_{i\in I^{c}})\leq N-1$, and hence $\operatorname{span}\{\varphi_{i}\}_{i\in I}$ and $\operatorname{span}\{\varphi_{i}\}_{i\in I^{c}}$ both have measure zero. This implies that there is a vector (in fact, an open dense set of vectors) $\varphi_{M+1}$ such that $\varphi_{M+1}\notin\operatorname{span}\{\varphi_{i}\}_{i\in I}$, $\varphi_{M+1}\notin\operatorname{span}\{\varphi_{i}\}_{i\in I^{c}}$, $\operatorname{dim}(\operatorname{span}(\{\varphi_{i}\}_{i\in I}\cup\varphi_{M+1}))\geq N-k+1$ and $\operatorname{dim}(\operatorname{span}(\{\varphi_{i}\}_{i\in I^{c}}\cup\varphi_{M+1}))\geq N-k+1$, for any $I\subset A_{0}$.

For each $I\subset A_{1}$, $\operatorname{dim}(\operatorname{span}(\{\varphi_{i}\}_{i\in I}\cup\varphi_{M+1}))\leq N-1$ and $\operatorname{dim}(\operatorname{span}(\{\varphi_{i}\}_{i\in I^{c}}\cup\varphi_{M+1}))\leq N-1$ and hence have measure zero. Thus the union of all subspaces defined by $I\subset A_{1}$ have measure zero. Hence there exists a vector $\varphi_{M+2}$ such that $\varphi_{M+2}\notin\operatorname{span}(\{\varphi_{i}\}_{i\in I}\cup\varphi_{M+1})$, $\varphi_{M+2}\notin\operatorname{span}(\{\varphi_{i}\}_{i\in I^{c}}\cup\varphi_{M+1})$, $\operatorname{dim}(\operatorname{span}(\{\varphi_{i}\}_{i\in I}\cup\{\varphi_{M+j}\}_{j=1}^{2}))\geq N-k+2$ and $\operatorname{dim}(\operatorname{span}(\{\varphi_{i}\}_{i\in I^{c}}\cup\{\varphi_{M+j}\}_{j=1}^{2}))\geq N-k+2$, for any $I\subset A_{1}$.

Continue in this manner by defining $A_{k}$ and adding $\varphi_{M+k}$ until $|A_{k}|=0$. Therefore $\{\varphi_{i}\}_{i=1}^{M+k}$ has the complement property.

For the moreover part let $I\subset\{1,\ldots,M\}$ be such that $\operatorname{span}\{\varphi_{i}\}_{i\in I}\neq\mathcal{R}^{N}$ and

If $\{\psi_{j}\}_{j=1}^{s}$ is a sequence such that $\{\varphi_{i}\}_{i=1}^{M}\cup\{\psi_{i}\}_{j=1}^{s}$ has the complement property, then $\{\varphi_{i}\}_{i\in I^{c}}\cup\{\psi_{i}\}_{j=1}^{s}$ must span $\mathcal{R}^{N}$, that is

Let $\{\varphi_{i}\}_{i=1}^{M}$ be a frame for $\mathcal{R}^{N}$. Fix $k\in N\cup\{0\}$ such that

Then there exists an open dense set $O_{M+1}\subset\mathcal{R}^{N}$ such that for all $\varphi_{M+1}\in O_{M+1}$,

This follows from Theorem 4.1 since the union of all subsets $I\subset A_{0}$ has measure zero. Hence its complement, call it $O_{M+1}$, is full measure and thus open and dense. For any vector $\varphi_{M+1}\in O_{M+1}$, we have $\varphi_{M+1}\notin\operatorname{span}\{\varphi_{i}\}_{i\in I}$, $\varphi_{M+1}\notin\operatorname{span}\{\varphi_{i}\}_{i\in I^{c}}$, $\operatorname{dim}(\operatorname{span}(\{\varphi_{i}\}_{i\in I}\cup\varphi_{M+1}))\geq N-k+1$ and $\operatorname{dim}(\operatorname{span}(\{\varphi_{i}\}_{i\in I^{c}}\cup\varphi_{M+1}))\geq N-k+1$, for any $I\subset A_{0}$. ∎

In light of Theorem 4.1 and Theorem 4.2, the next result is surprising. It says that if we have families of vectors $\Phi_{1},\Phi_{2}$ which do phase retrieval in two different Hilbert spaces, and we want to do phase retrieval in the orthogonal sum of these Hilbert spaces, we will have to add a very large number of vectors to $\Phi_{1}$ and $\Phi_{2}$.

Let $\Phi_{j}=\{\varphi_{i}^{j}\}_{i=1}^{M_{j}}$ yield phase retrieval on $\mathcal{H}_{N_{j}}$ for $j=1,2$. Let $H=\mathcal{H}_{N_{1}}\oplus\mathcal{H}_{N_{2}}$. If $\Phi=\{\varphi_{i}\}_{i=1}^{M}$ is a set of vectors in $H$ and $\Phi\cup\Phi_{1}\cup\Phi_{2}$ does phase retrieval, then $M\geq N_{1}+N_{2}-1$.

Moreover, there exists a $\Phi=\{\varphi_{i}\}_{i=1}^{N_{1}+N_{2}-1}$ so that $\Phi\cup\Phi_{1}\cup\Phi_{2}$ does phase retrieval.

Proof of claim: If $M\leq N_{1}+N_{2}-2$, then there exists a partition of $\{1,\dots,M\}$ into $\{I_{1},I_{2}\}$ with $|I_{1}|\leq N_{2}-1$ and $|I_{2}|\leq N_{1}-1$. Hence $\Phi_{j}\cup\{\varphi_{i}\}_{i\in I_{j}}$ doesn’t span for $j=1,2$.

Proof of the moreover part: Consider the span of all subsets of $\Phi_{1}\cup\Phi_{2}$ which do NOT span $H$ but do span at least either $\mathcal{H}_{N_{1}}$ or $\mathcal{H}_{N_{2}}$. There exists a vector $\varphi_{1}$ which is not in the span of any of these subsets. Do the same thing with $\Phi_{1}\cup\Phi_{2}\cup\{\varphi_{1}\}$ and pick $\varphi_{2}$ not in the span of any of these subsets. Continue in this way to pick $\Phi=\{\varphi_{i}\}_{i=1}^{N_{1}+N_{2}-1}$.