Real phase retrieval and phaseless ambiguity

By induction on $n$, every iterated ring $\mathbb{R}[t_1,\dots ,t_n]$ is an integral domain: the base $\mathbb{R}$ is a field, hence a domain, and the successor step is exactly [F1]. In each iteration the new indeterminate has coefficient $1$ in degree $1$, whereas every preceding indeterminate is embedded as a constant polynomial; since $1\mathrm{\ne }0$ in $\mathbb{R}$, all the $t_j$ are pairwise distinct.

For $d=1$, $V_d=[1]$ and the empty product is $1$, so the formula holds. For the inductive step let $d\ge 2$ and suppose the formula holds in size $d-1$. Put $C=\mathbb{R}[t_1,\dots ,t_{d-1}]$ and $T=t_d$, so the recursive construction identifies $\mathbb{R}[t_1,\dots ,t_d]=C[T]$. Regard $D_d:=\det V_d$ as a polynomial $f(T)\in C[T]$.

The Leibniz expansion in [F2] shows that only powers $T^0,\dots ,T^{d-1}$ occur in $f$, and that the coefficient of $T^{d-1}$ is $D_{d-1}:=\det V_{d-1}$: precisely the terms with exponent $d-1$ in the last column are those permutations fixing the last row, and their remaining signed sum is the Leibniz determinant of $V_{d-1}$. For each $j<d$, substituting $T=t_j$ makes the last column equal column $j$, so alternation in [F2] gives $f(t_j)=0$.

The elements $t_1,\dots ,t_{d-1}$ are distinct in the domain $C$ by step 1.1. Starting with $f$, apply [F3] successively at $t_1,\dots ,t_{d-1}$. At stage $k$, if $f=({\prod }_{j<k}(T-t_j))g_k$, evaluation at $t_k$ gives $0=f(t_k)=({\prod }_{j<k}(t_k-t_j))g_k(t_k)\mathrm{.}$ Every factor $t_k-t_j$ is nonzero, so their product is nonzero in the domain $C$; hence $g_k(t_k)=0$, and [F3] gives $T-t_k\mid g_k$. Induction over these finitely many stages yields $f(T)=g(T){\prod }_{j<d}(T-t_j)$ for some $g(T)\in C[T]$.

By the induction hypothesis, $D_{d-1}={\prod }_{1\le p<q<d}(t_q-t_p)$, which is nonzero because each difference is nonzero in the domain $C$. Thus the coefficient of $T^{d-1}$ in $f$ is nonzero. The product ${\prod }_{j<d}(T-t_j)$ is monic of degree $d-1$. If $g$ had any nonzero coefficient at a positive power, its highest such power times this monic product would give a nonzero coefficient of $f$ above degree $d-1$, contradicting step 1.3. Therefore $g$ is constant, and comparison of the $T^{d-1}$ coefficients gives $g=D_{d-1}$. This proves $D_d=D_{d-1}{\prod }_{j<d}(t_d-t_j)={\prod }_{1\le p<q\le d}(t_q-t_p)\mathrm{.}$ By induction the determinant formula holds for every $d\ge 1$.

For distinct real nodes $s_1,\dots ,s_d$, the evaluation homomorphism in [F3] substitutes them into the formula and gives $\det V_d(s_1,\dots ,s_d)={\prod }_{p<q}(s_q-s_p)\mathrm{\ne }0$. By [F4], the square matrix with these moment-curve vectors as columns is invertible, hence has trivial coefficient kernel and linearly independent columns by [F5].

The relation $\sim$ is reflexive because $x=x$, symmetric because $z=x$ implies $x=z$ and $z=-x$ implies $x=-z$, and transitive because multiplying the two signs in $z=ϵx$ and $w=\delta z$ gives $w=(\delta ϵ)x$ with $\delta ϵ\in \{1,-1\}$. Thus $Q_d$ is the quotient set and $q(x)=[x]$ is onto by the definition of equivalence classes.

If $m\ge 1$, the relabeling $J:Y_m\to [0,\mathrm{\infty }{)}^m$ given by $J(b{)}_k=b_{k+1}$ is a bijection and ${\rho }_m(b,c)=d_2(Jb,Jc)$, so the metric axioms of [F2] restrict to $Y_m$. If $m=0$, $Y_0$ has one element and the zero function separates its only pair and is symmetric and triangular. Hence $Y_m$ is a metric space in both cases.

Replacing representatives by $x^{\mathrm{\prime }}=ϵx$ and $z^{\mathrm{\prime }}=\delta z$, with $ϵ,\delta \in \{1,-1\}$, changes the pair $(\mathrm{\parallel }x-z{\mathrm{\parallel }}_2,\mathrm{\parallel }x+z{\mathrm{\parallel }}_2)$ only by possibly interchanging its two entries, since $\mathrm{\parallel }{x}^{\mathrm{\prime }}-z^{\mathrm{\prime }}{\mathrm{\parallel }}_2=\mathrm{\parallel }x-(ϵ\delta )z{\mathrm{\parallel }}_2$ and $\mathrm{\parallel }{x}^{\mathrm{\prime }}+z^{\mathrm{\prime }}{\mathrm{\parallel }}_2=\mathrm{\parallel }x+(ϵ\delta )z{\mathrm{\parallel }}_2$. By [F7] the minimum is attained, so its value is independent of representatives.

Replacing $x$ by $-x$ changes each amplitude coordinate from $\mathrm{\mid }⟨a_i,x⟩\mathrm{\mid }$ to $\mathrm{\mid }-⟨a_i,x⟩\mathrm{\mid }=\mathrm{\mid }⟨a_i,x⟩\mathrm{\mid }$, and changes each intensity coordinate from $⟨a_i,x{⟩}^2$ to $(-⟨a_i,x⟩{)}^2=⟨a_i,x{⟩}^2$. Every intensity coordinate is nonnegative by [F6], so both maps have the stated codomain and are well defined on $Q_d$, including zero rows and the zero signal. For $m=0$ both are the unique map to the empty tuple.

Choose signs $ϵ,\delta \in \{1,-1\}$ attaining the two minima for $d_{\pm }([x],[y])$ and $d_{\pm }([y],[z])$; [F7] ensures these minima exist, and the choices are from finite two-element sets. The Euclidean triangle inequality and sign-invariance of the norm give $d_{\pm }([x],[z])\le \mathrm{\parallel }x-ϵ\delta z{\mathrm{\parallel }}_2\le \mathrm{\parallel }x-ϵy{\mathrm{\parallel }}_2+\mathrm{\parallel }y-\delta z{\mathrm{\parallel }}_2=d_{\pm }([x],[y])+d_{\pm }([y],[z])$. Thus the triangle inequality holds.

Both candidate norms are nonnegative by the nonnegative-root convention [F5], and their minimum is symmetric under interchanging $x$ and $z$. The minimum is zero exactly when $x=z$ or $x=-z$, which is exactly $[x]=[z]$ by [F1] and separation of the Euclidean metric in [F2]. Together with the triangle inequality in step 2.2, this proves that $d_{\pm }$ is a metric.

Each amplitude coordinate is nonnegative and its square is the corresponding intensity coordinate. If two nonnegative amplitudes have the same square, uniqueness of nonnegative square roots [F5] makes the amplitudes equal; conversely equal amplitudes have equal squares. Coordinatewise, the amplitude and intensity maps therefore have the same fibers and are injective simultaneously.

To prove that the complement property implies injectivity, assume the complement property [F3] and suppose ${\mathcal{I}}_{\mathrm{\Phi }}([x])={\mathcal{I}}_{\mathrm{\Phi }}([z])$. At every label $i$, equality of the intensity coordinates gives $⟨a_i,x{⟩}^2=⟨a_i,z{⟩}^2$.

Factoring the difference of squares over $\mathbb{R}$ yields $(⟨a_i,x-z⟩)(⟨a_i,x+z⟩)=0$ for every $i\in [m]$. This factorization also holds when $x=0$, $z=0$, or $a_i=0$; no nonzero-signal or nonzero-measurement hypothesis is used.

Put $S=\{i\in [m]:⟨a_i,x-z⟩=0\}$. For $i\in S$, $a_i\perp (x-z)$; for $i\mathrm{\notin }S$, the first factor in step 2.1 is nonzero, so $a_i\perp (x+z)$. By [F5], each vector in either span is a finite linear combination of its generators, and bilinearity extends each orthogonality statement to the whole span.

By the complement property [F3], either $\mathrm{span}({\mathrm{\Phi }}_S)={\mathbb{R}}^d$ or $\mathrm{span}({\mathrm{\Phi }}_{[m]\setminus S})={\mathbb{R}}^d$. In the first case step 3.1 makes $x-z$ orthogonal to every vector of ${\mathbb{R}}^d$, hence to itself; positive definiteness [F4] gives $x-z=0$. In the second case it gives $x+z=0$. Thus $[x]=[z]$ by [F2], proving injectivity.

Step 4.1 proves that the complement property implies injectivity. For injectivity implying the complement property, argue contrapositively and suppose the complement property fails; then some $S\subseteq [m]$ has the proper subspaces $U=\mathrm{span}({\mathrm{\Phi }}_S)$ and $V=\mathrm{span}({\mathrm{\Phi }}_{[m]\setminus S})$. We prove that every proper subspace $W\le {\mathbb{R}}^d$ has a nonzero orthogonal vector. Let $r=\dim W<d$ by [F6], choose a basis $w_0,\dots ,w_{r-1}$ of $W$, and define $L_W:{\mathbb{R}}^d\to {\mathbb{R}}^r$ by $L_W(x)=(⟨x,w_j⟩{)}_{j<r}$. Bilinearity makes $L_W$ linear. Its kernel is $W^{\perp }$: vanishing against the basis implies vanishing against every vector of $W$ because the basis spans $W$ and [F5] expresses each span vector as a finite linear combination; the converse is immediate. By [F7], the image is a subspace of ${\mathbb{R}}^r$, so [F6] gives $\mathrm{rank}{L}_W=\dim (\mathrm{im}{L}_W)\le r$. Rank-nullity [F7] and $\dim {\mathbb{R}}^d=d$ then give $\dim W^{\perp }=\dim \ker L_W=d-\mathrm{rank}{L}_W\ge d-r>0$. By [F6] a zero subspace has dimension zero, so $W^{\perp }$ contains a nonzero vector. Apply this argument to $U$ and $V$ and choose nonzero $u\in U^{\perp }$ and $v\in V^{\perp }$.

Set $x=u+v$ and $z=u-v$. Since $v\mathrm{\ne }0$, $x=z$ would imply $2v=0$, impossible by [F8]; since $u\mathrm{\ne }0$, $x=-z$ would imply $2u=0$, also impossible. Hence $[x]\mathrm{\ne }[z]$ by [F2].

If $i\in S$, then $a_i\in U$ and $u\perp a_i$, so $⟨a_i,x⟩=⟨a_i,v⟩$ and $⟨a_i,z⟩=-⟨a_i,v⟩$. If $i\mathrm{\notin }S$, then $a_i\in V$ and $v\perp a_i$, so both measurements equal $⟨a_i,u⟩$. If $a_i=0$, it lies in $U$ and both measurements are zero. Squaring shows equality of the intensity coordinates at every label, including when either component of the partition is empty.

When $m=0$, the only partition has both sides empty, and both spans equal $\{0\}\mathrm{\ne }{\mathbb{R}}^d$ by [F5] and $d\ge 1$. The complement property fails, while steps 5.1–6.2 give distinct global-sign classes with the same unique empty data. Thus the zero-measurement case is included.

Steps 6.1 and 6.2 give distinct quotient classes with the same intensity data, so ${\mathcal{I}}_{\mathrm{\Phi }}$ is not injective. Together with step 4.1 and the definition of phase retrieval [F1], this proves the stated equivalence.

Fix a processed pattern $s$. The finite SVD in [F9] exists for $A$; by [F4], $x_s=A^{+}{y}_s$ minimizes the signed residual norm. The pseudoinverse identity [F3] gives $A(I-A^{+}A)=A-A{A}^{+}A=0$, so $(I-A^{+}A)z\in \ker A$ for every $z$; conversely, if $k\in \ker A$, then $(I-A^{+}A)k=k$. Thus the affine family in [F5] is exactly $x_s+\ker A$.

Put $N_m=1$ when $m=0$. For $m\ge 1$, deleting the fixed coordinate $s_1=+1$ bijects the canonical patterns with sign tuples on labels $2,\dots ,m$. Starting with one empty tuple, each added label doubles the number of possible prefixes, so there are $2^{m-1}$ canonical patterns. Each iteration processes one pattern and uses one signed solve; the algorithm stops after its pattern limit $P$, solve limit $L$, or all $N_m$ patterns are reached. Thus it terminates after no more than each of $P$, $L$, and $N_m$ signed solves; full pattern processing uses exactly $N_m$ solves, and the pattern count is exponential in $m\ge 1$. If $P,L>0$, the procedure computes one SVD before processing patterns. In noisy mode, after the first pattern the incumbent minimizes $J$ among processed candidates; each later candidate replaces it exactly when its objective is smaller, while a tie preserves the earlier incumbent. Induction over the processed sequence proves the same minimum property after every update.

The least-squares family has an exact solution precisely when its residual minimum is zero: by [F6], $e_s=0$ exactly when $A{x}_s-y_s=0$. If this holds, every member of $x_s+\ker A$ solves the same equation; if it does not, none does, because $x_s$ already minimizes the residual.

Having established the zero-residual criterion in step 2.1, suppose exact mode with $\epsilon =0$ processes every pattern. If $Ax=y_s$ for some processed $s$, then $(Ax{)}_i^2=r_i^2=b_i$ at each label, so ${\mathcal{I}}_{\mathrm{\Phi }}([x])=b$. Conversely, suppose ${\mathcal{I}}_{\mathrm{\Phi }}([x])=b$. For every label, $(Ax{)}_i^2=r_i^2$, so $(Ax{)}_i=r_i$ or $(Ax{)}_i=-r_i$ by factoring $((Ax{)}_i-r_i)((Ax{)}_i+r_i)=0$ in the real field; when $r_i=0$ both choices give zero. Choose the corresponding $t_i\in \{-1,+1\}$. If $m\ge 1$ and $t_1=-1$, replace $x$ by $-x$ and $t$ by $-t$; the quotient class is unchanged and the new sign pattern has first coordinate $+1$. If $m=0$, use the unique empty pattern. Therefore a canonical pattern $s$ has a signed exact solution in the class $[x]$.

By step 2.1 the exact solution from step 3.1 belongs to $x_s+\ker A$, and that pattern is recorded by the algorithm. Conversely, every recorded family in exact mode with $\epsilon =0$ has $e_s=0$ by [F1], so step 2.1 makes each of its members solve $Ax=y_s$ and hence have intensity data $b$. This proves that the returned union modulo sign is exactly the stated inverse image, and it is empty exactly when no such class exists.

The complete exact-mode correspondence is established in step 4.1. For noisy mode, for any sign vector $t:[m]\to \{-1,+1\}$ write $y_t=(t_i{r}_i{)}_{i\in [m]}$. Fix a real $u$ and $r\ge 0$. If $u\ge 0$, then $(u-r{)}^2=(\mathrm{\mid }u\mathrm{\mid }-r{)}^2$ and $(u+r{)}^2-(u-r{)}^2=4ur\ge 0$. If $u<0$, put $v=-u>0$; then $(u+r{)}^2=(v-r{)}^2=(\mathrm{\mid }u\mathrm{\mid }-r{)}^2$ and $(u-r{)}^2-(u+r{)}^2=4vr\ge 0$. Thus the sign matching the sign of $u$ attains the smaller of $(u-r{)}^2$ and $(u+r{)}^2$, and every sign choice has squared residual at least $(\mathrm{\mid }u\mathrm{\mid }-r{)}^2$. Apply this coordinatewise to $u_i=(Ax{)}_i$ and $r_i$, and sum: every sign vector $t$ satisfies $J(x)\le \mathrm{\parallel }Ax-y_t{\mathrm{\parallel }}_2^2$, and a sign vector chosen coordinatewise attains equality. For $m=0$, both sides are the empty sum $0$.