Absolute Uniqueness of Phase Retrieval with Random Illumination

Introduction

Phase retrieval is a fundamental problem in many areas of physical sciences such as X-ray crystallography, astronomy, electron microscopy, coherent light microscopy, quantum state tomography and remote sensing. Because of loss of the phase information a central question of phase retrieval is the uniqueness of solution which is the focus of the present work.

Researchers in phase retrieval, however, have long settled with the notion of relative uniqueness (i.e. irreducibility) for generic (i.e. random) objects, without a practical means for deciding the reducibility of a given (i.e. deterministic) object, and searched for various ad hoc strategies to circumvent problems with stagnation and error in reconstruction. The common problem of stagnation may be due to the possibility of the iterative process to approach the object and its twin or shifted image, the support not tight enough or the boundary not sharp enough . Besides the uniqueness issue, phase retrieval is also inherently nonconvex and many researchers have believed the lack of convexity in the Fourier magnitude constraint to be a main, if not the dominant, source of numerical problems with the standard phasing algorithms . While there have been dazzling advances in applications of phase retrieval in the past decades , we still do not know just how much of the error and stagnation problems is attributable to to the lack of uniqueness or convexity.

We propose here to refocus on the issue of uniqueness as uniqueness is undoubtedly the first foundational issue of any inverse problem, including phase retrieval. Specifically we will first establish uniqueness in the absolute sense with random illumination under general, physically reasonable object constraints (Figure 1) and secondly demonstrate that random illumination practically alleviates most numerical problems and drastically improves the quality of reconstruction.

The Fourier transform can be obtained from the $z$-transform as

by some abuse of notation. The discrete phase retrieval problem is to determine $f(\mathbf{n})$ from the knowledge of the Fourier magnitude $|F({\mathbf{w}})|,\forall{\mathbf{w}}\in^{d}$.

The question of uniqueness was partially answered in which says that in dimension two or higher and with the exception of a measure zero set of finite sequences phase retrieval has a unique solution up to the equivalence class of “trivial associates” (i.e. relative uniqueness). These trivial, but omnipresent, ambiguities include constant global phase,

Conjugate inversion produces the so-called twin image.

This landmark uniqueness result, however, does not address the following issues. First, a given object array, there is no way of deciding a priori the irreducibility of the corresponding $z$-transform and the relative uniqueness of the phasing problem. Secondly, although visually no different from the true image the trivial associates (particularly spatial shift and conjugate inversion) nevertheless “confuse” the standard numerical iterative processes and cause serious stagnation .

In this paper, we study the notation of absolute uniqueness: if two finite objects $f$ and $g$ give rise to the same Fourier magnitude data, then $f=g$ unequivocally. More importantly, we present the approach of random (phase or amplitude) illumination to the absolute uniqueness of phase retrieval. The idea of random illumination is related to coded-aperture imaging whose utility in other imaging contexts than phase retrieval has been established experimentally as well as mathematically .

Our basic tool is an improved version (Theorem 2) of the irreducibility result of with, however, a completely different perspective and important practical implications. The main difference is that while the classical result works with generic (thus random) objects from a certain ensemble Theorem 2 can deal with a given, deterministic object whose support has rank $\geq 2$. This improvement is achieved by endowing the probability measure on the ensemble of illuminations, which we can manipulate, instead of the space of objects, which we can not control, as in the classical setting.

On the basis of almost sure irreducibility, the mere assumption that the phases or magnitudes of the object at two arbitrary points lie in a countable set enforces uniqueness, up to a global phase, in phase retrieval with a single random illumination (Theorem 3). The absolute uniqueness can be enforced then by imposing the positivity constraint (Corollary 1). For objects satisfying a tight sector condition, absolute uniqueness is valid with high probability depending on the object sparsity for either phase or amplitude illumination (Theorem 4). For complex-valued objects under a magnitude constraint, uniqueness up to a global phase is valid with high probability (Theorem 5). For general complex-valued objects, almost sure uniqueness, up to global phase, is proved for phasing with two independent illuminations (Theorem 6).

The paper is organized as follows. In Section 2 we discuss various sources of ambiguity. In Section 3 we prove the almost sure irreducibility (Theorem 2 and Appendix). In Section 4 we derive the uniqueness results (Theorem 3, 4, 5, 6 and Corollary 1). We demonstrate phasing with random illumination in Section 5. We conclude in Section 6.

Sources of ambiguity

As commented before the phase retrieval problem does not have a unique solution. Nevertheless, the possible solutions are constrained as stated in the following theorem .

Let the $z$-transform $F({\mathbf{z}})$ of a finite complex-valued sequence $\{f(\mathbf{n})\}$ be given by

where $F_{k},k=1,...,p$ are nontrivial irreducible polynomials. Let $G({\mathbf{z}})$ be the ${\mathbf{z}}$-transform of another finite sequence $g(\mathbf{n})$. Suppose $|F({\mathbf{w}})|=|G({\mathbf{w}})|,\forall{\mathbf{w}}\in^{d}$. Then $G({\mathbf{z}})$ must have the form

where $I$ is a subset of $\{1,2,...,p\}$.

is the autocorrelation function of $f$. Note the symmetry ${\mathcal{C}}^{*}_{f}(\mathbf{n})={\mathcal{C}}_{f}(-\mathbf{n})$.

The theorem then follows straightforwardly from the equality between the autocorrelation functions of $f$ and $g$, because $F({\mathbf{w}})F^{*}({\mathbf{w}})=G({\mathbf{w}})G^{*}({\mathbf{w}})$, and the unique factorization of polynomials (see for more details).

If the finite array $f(\mathbf{n})$ is known a priori to vanish outside the lattice ${\mathcal{N}}$, then by Shannon’s sampling theorem for band-limited functions the sampling domain for ${\mathbf{w}}$ can be limited to the finite regular grid

since $|F({\mathbf{w}})|^{2}$ is band-limited to the set $-{\mathbf{N}}\leq\mathbf{n}\leq{\mathbf{N}}$.

There are three sources of ambiguity. First, the linear phase term ${\mathbf{z}}^{-{\mathbf{m}}}$ in (1) remain undetermined because the autocorrelation operation destroys information about spatial shift. The unspecified constant phase $\theta$ is another source of ambiguity.

To understand the physical meaning of the operation

which is the $z$-transform of the conjugate space-inversed array $\{f^{*}(N),f^{*}(N-1),\cdots,f^{*}(0)\}$. The same is true in multi-dimensions.

The subtlest form of ambiguity is caused by partial conjugate inversion on some, but not all, factors of a factorable object, with a reducible $z$-transform, without which the conjugate inversion, like spatial shift and global phase, is global in nature and considered “trivial” in the literature (even though the twin image may have an opposite orientation).

In this paper, we consider both types, trivial and nontrivial, of ambiguity, as they both can degrade the performance of phasing schemes. Our main purpose is to show by rigorous analysis that with random illumination it is possible to eliminate all ambiguities at once.

Irreducibility

Random illumination amounts to replacing the original object $f(\mathbf{n})$ by

where $\lambda(\mathbf{n})$, representing the incident field, is a known array of samples of random variables (r.v.s). The idea is to first modify the object by the encoding array $\lambda(\mathbf{n})$ so that phase retrieval has unique solution and then use the prior knowledge of $\lambda$ to recover $f$.

Nearly independent random illumination can be produced by a diffuser placed near the object, cf. Figure 1. The illumination field can be randomly modulated in phase only with the use computer generated holograms , random phase plates and liquid crystal phase-only panels . One of the best known amplitude masks is uniformly redundant array and its variants . The advantage of phase mask, compared to amplitude mask, is the lossless energy transmission of an incident wavefront through the mask. By placing either phase or amplitude mask at a distance from the object, one can create an illumination field modulated in both amplitude and phase in a way dependent on the distance .

If the object support does not touch all the coordinate hyperplanes, then the the irreducibility holds true, up to some monomial of ${\mathbf{z}}$. In view of Theorem 1 this is sufficient for our purpose.

The theorem does not hold if the rank-2 condition fails. For example, let $p({\mathbf{z}})$ be any monomial and consider

which is factorable by, again, the fundamental theorem of algebra.

The proof of Theorem 2 is given in the Appendix.

Theorem 2 improves in several aspects on the classical result that the set of the reducible polynomials has zero measure in the space of multivariate polynomials with real-valued coefficients . The main improvement is that while the classical result works with generic (thus random) objects Theorem 2 deals with any deterministic object with minimum (and necessary) conditions on its support set. By definition, deterministic objects belong to the measure zero set excluded in the classical setting of . It is both theoretically and practically important that Theorem 2 places the probability measure on the ensemble of illuminations, which we can manipulate, instead of the space of objects, which we can not control.

In the next section, we go further to show that with additional, but for all practical purposes sufficiently general, constraints on the values of the object, we can essentially remove all ambiguities with the only possible exception of global phase factor. This decisive step distinguishes our method from the standard approach.

Uniqueness

Without additional a priori knowledge on the object Theorem 2, however, does not preclude the trivial ambiguities such as global phase, spatial shift and conjugate inversion. For example, we can produce another finite array $\{g(\mathbf{n})\}$ that yields the same measurement data by setting

Suppose the object support has rank $\geq 2$. Suppose either of the following cases holds:

Then $f$ is determined uniquely, up to a global phase, by the Fourier magnitude measurement on the lattice ${\mathcal{M}}$ with probability one.

For the two-point constraint in case (i) to be convex, it is necessary for the constraint set to be a singleton, namely the phases of the object at two nonzero points must take on a single known value. On the other hand, the amplitude constraint in case (ii) can never be convex unless the set is a singleton and the object phases are the same at the two points.

By Theorem 2 the $z$-transform of $\{\lambda(\mathbf{n})f(\mathbf{n})\}$ is irreducible with probability one. We prove the theorem case by case.

Case (i): Suppose the phases of $f(\mathbf{n}_{1})$ and $f(\mathbf{n}_{2})$ belong to the coutable set $\Theta\subset[0,2\pi]$. Let us show the probability that the phase of $g(\mathbf{n})$ as given by (9) with ${\mathbf{m}}\neq 0$ takes on a value in $\Theta$ at two distinct points is zero.

Since $\lambda(\mathbf{n}+{\mathbf{m}}),{\mathbf{m}}\neq 0,$ and the phases of $\lambda(\mathbf{n})$ are independent, continuous r.v.s on $[0,2\pi]$, the phase of $g(\mathbf{n}),\forall\mathbf{n},$ is continuously distributed on $[0,2\pi]$ for all $\theta$.

Now suppose the phase of $g(\mathbf{n}_{0})$ for some $\mathbf{n}_{0}$ lies in the set $\Theta$. This implies that $\theta$ must belong to the countable set $\Theta^{\prime}$ which is $\Theta$ shifted by the negative phase of $f(\mathbf{n}_{0}+{\mathbf{m}})\lambda(\mathbf{n}_{0}+{\mathbf{m}})/\lambda(\mathbf{n}_{0})$. The phase of $g(\mathbf{n})$ at a different location $\mathbf{n}\neq\mathbf{n}_{0}$, however, almost surely does not take on any value in the set $\Theta$ for any fixed $\theta\in\Theta^{\prime}$ unless ${\mathbf{m}}=0$. Since a countable union of measure-zero sets has zero measure, the probability that the phases of $g$ at two points lie in $\Theta$ is zero if ${\mathbf{m}}\neq 0$.

Likewise, $\lambda^{*}({\mathbf{N}}-\mathbf{n}+{\mathbf{m}})/\lambda(\mathbf{n}),\forall{\mathbf{m}},$ has a random phase that is continuously distributed on $[0,2\pi]$ and by the same argument the probability that the phases of $g$ as given by (10) at two points lie in $\Theta$ is zero.

The global phase $\theta$, however, can not be determined uniquely in either case.

The global phase factor can be determined uniquely by additional constraint on the values of the object. For example, the following result follows immediately from Theorem 3 (i).

With a real, positive object, the countable set for phase is the singleton $\{0\}$ and the global phase is uniquely fixed. ∎

2. Sector constraint

More generally, we consider the sector constraint that the phases of $\{f(\mathbf{n})\}$ belong to $[a,b]\subset[0,2\pi]$. For example, the class of complex-valued objects relevant to $X$-ray diffraction typically have nonnegative real and imaginary parts where the real part is the effective number of electrons coherently diffracting photons, and the imaginary part represents the attenuation . For such objects, $[a,b]=[0,\pi/2]$.

Generalizing the argument for Theorem 3 we can prove the following.

Suppose the object support has rank $\geq 2$. Let the finite object $\{f(\mathbf{n})\}$ satisfy the sector constraint that the phases of $\{f(\mathbf{n})\}$ belong to $[a,b]\subset[0,2\pi]$. Let $S$ be the sparsity (the number of nonzero elements) of the object.

In both cases, the global phase is uniquely determined if the sector $[a,b]$ is tight in the sense that no proper interval of $[a,b]$ contains all the phases of the object.

Case (i): Consider first the expression (9) with any ${\mathbf{m}}\neq 0$ and the $\textlbrackdbl S/2\textrbrackdbl$ independently distributed r.v.s of $g(\mathbf{n})$ corresponding to $[S/2]$ nonoverlapping pairs of points $\{\mathbf{n},\mathbf{n}+{\mathbf{m}}\}$. The probability for every such the phase of $g(\mathbf{n})$ to lie in the sector $[a,b]$ is $|b-a|/(2\pi)$ for any $\theta$ and hence the probability for all $g(\mathbf{n})$ with ${\mathbf{m}}\neq 0,\theta\neq 0,$ to lie in the sector is at most $|b-a|^{[S/2]}(2\pi)^{-[S/2]}$. The union over ${\mathbf{m}}\neq 0$ of these events has probability at most $|{\mathcal{N}}||b-a|^{[S/2]}(2\pi)^{-[S/2]}$.

Likewise the probability for all $g(\mathbf{n})$ given by (10) to lie in the first quadrant for any ${\mathbf{m}}$ is at most $|{\mathcal{N}}||b-a|^{[S/2]}(2\pi)^{-[S/2]}$.

Case (ii): For (9) with any ${\mathbf{m}}\neq 0$ the $[S/2]$ independently distributed random variables $g(\mathbf{n})$ corresponding to $[S/2]$ nonoverlapping pairs of points $\{\mathbf{n},\mathbf{n}+{\mathbf{m}}\}$, satisfy the sector constraint with probability at most $2^{-[S/2]}$ if $|b-a|\leq\pi$. Hence the probability that all $g(\mathbf{n})$ with ${\mathbf{m}}\neq 0$ satisfy the sector constraint is at most $|{\mathcal{N}}|2^{-[S/2]}.$

For (10) with $\theta=0$ and any ${\mathbf{m}}$, $g(\mathbf{n}_{0})=f(\mathbf{n}_{0})$ at $\mathbf{n}_{0}=({\mathbf{N}}+{\mathbf{m}})/2$ and hence $g(\mathbf{n}_{0})$ lies in the first quadrant with probability one. For $\mathbf{n}\neq\mathbf{n}_{0}$, $g(\mathbf{n})$ satisfies the sector constraint with probability $1/2$ if $|b-a|\leq\pi$. Now the $[(S-1)/2]$ independently distributed r.v.s $g(\mathbf{n})$ corresponding to nonoverlapping pairs of points $\{\mathbf{n},\mathbf{n}+{\mathbf{m}}\},\mathbf{n}\neq\mathbf{n}_{0},$ satisfy the sector constraint with probability at most $2^{-[(S-1)/2]}$ if $|b-a|\leq\pi$. Hence the probability that all $g(\mathbf{n})$ given by (10) with arbitrary ${\mathbf{m}}$ satisfy the sector constraint is at most $|{\mathcal{N}}|2^{-[(S-1)/2]}$. ∎

3. Magnitude constraint

Likewise if the object satisfies a magnitude constraint then we can use random amplitude illumination to enforce uniqueness (up to a global phase).

The proof is similar to that for Theorem 4(ii).

For (9) with any ${\mathbf{m}}\neq 0$ the $[K/2]$ independently distributed random variables $g(\mathbf{n})$ corresponding to $[K/2]$ nonoverlapping pairs of points $\{\mathbf{n},\mathbf{n}+{\mathbf{m}}\}$ satisfy $0<a\leq|g(\mathbf{n})|\leq b$ with probability less than $p^{-[K/2]}$ for any $\theta$. Hence the probability that $g(\mathbf{n})$ with ${\mathbf{m}}\neq 0$ satisfy the magnitude constraint at $K$ or more points is at most $|{\mathcal{N}}|p^{-[K/2]}$.

For (10) with any ${\mathbf{m}}$, $|g(\mathbf{n}_{0})|=|f(\mathbf{n}_{0})|$ at $\mathbf{n}_{0}=({\mathbf{N}}+{\mathbf{m}})/2$ and hence $g(\mathbf{n}_{0})$ satisfies the magnitude constraint with probability one. For $\mathbf{n}\neq\mathbf{n}_{0}$, there is at most probability $p$ for $g(\mathbf{n})$ to satisfy the magnitude constraint. By independence, the $[(K-1)/2]$ independently distributed r.v.s $g(\mathbf{n})$ corresponding to nonoverlapping pairs of points $\{\mathbf{n},\mathbf{n}+{\mathbf{m}}\},\mathbf{n}\neq\mathbf{n}_{0},$ satisfy the magnitude constraint with probability at most $p^{[(K-1)/2]}$. Hence the probability that $g(\mathbf{n})$ given by (10) with arbitrary ${\mathbf{m}}$ satisfy the magnitude constraint at $K$ or more points is at most $|{\mathcal{N}}|p^{[(K-1)/2]}$.

The global phase factor is clearly undetermined. ∎

As in Theorem 3 case (ii) the magnitude constraint here, however, is not convex.

4. Complex objects without constraint

For general complex-valued objects without any constraint, we consider two sets of Fourier magnitude data produced with two independent random illuminations and obtain almost sure uniqueness modulo global phase.

Let $\{f(\mathbf{n})\}$ be a finite complex-valued array whose support has rank $\geq 2$. Let $\{\lambda_{1}(\mathbf{n})\}$ and $\{\lambda_{2}(\mathbf{n})\}$ be two independent arrays of r.v.s satisfying the assumptions in Theorem 2.

Then with probability one $f(\mathbf{n})$ is uniquely determined, up to a global phase, by the Fourier magnitude measurements on ${\mathcal{M}}$ with two illuminations $\lambda_{1}$ and $\lambda_{2}$.

If the second illumination $\lambda_{2}$ is deterministic and results in an irreducible $z$-transform while $\lambda_{1}$ is random as above, then the same conclusion holds.

Let $g(\mathbf{n})$ be another array that vanishes outside ${\mathcal{N}}$ and produces the same data. By Theorem 1, 2 and Remark 1

Four scenarios of ambiguity exist but because of the independence of $\lambda_{1}(\mathbf{n}),\lambda_{2}(\mathbf{n})$ none can arise.

This almost surely can not occur unless ${\mathbf{m}}_{1}={\mathbf{m}}_{2}={\mathbf{0}},\theta_{1}=\theta_{2}$ in which case $g$ equals $f$ up to a global phase factor.

The other possibilities can be similarly ruled out:

for any ${\mathbf{m}}_{i},\theta_{i},i=1,2$.

The same argument above applies to the case of deterministic $\lambda_{2}$ if the resulting $z$-transform is irreducible.

Numerical examples

We test the case of random phase illumination on a real, positive $269\times 269$ image consisting of the original $256\times 256$ Cameraman in the middle, surrounded by a black margin (zero padding) of 13 pixels in width (Figure 2(a)). We synthesize and sample the Fourier magnitudes at the Nyquist rate (Remark 1) and implement the standard Error Reduction (ER) and Hybrid-Input-Output (HIO) algorithms in the framework of the oversampling method . By Corollary 1, absolute uniqueness holds with a random phase illumination.

Let ${\mathbf{\Phi}}$ and $\Lambda$ be the Fourier transform and the diagonal matrix $\hbox{\rm diag}{[\lambda(\mathbf{n})]}$ representing the illumination. For the uniform illumination $\Lambda=\mathbf{I}$. The ER and HIO algorithms are described below.

In the original version of HIO , the hard thresholding is replaced by

where the feedback parameter $\beta=0.9$ is used in the simulations. ER has the desirable property that the residual $\||\widetilde{F}|-|G_{k}|\|$ is reduced after each iteration under either uniform or random phase illumination . When absolute uniqueness holds, a vanishing residual then implies a vanishing reconstruction error.

Figure 2 shows the results of ER reconstruction with random phase illumination. The ER iteration converges to the true image after 40 iterations. For HIO reconstruciton we apply 50 ER iterations after 100 HIO iterations as suggested in . HIO has essentially the same performance as ER (Figure 3 (a), (b)). The relative residual curve, Figure 3(d), and the relative error curve, Figure 4, however, indicate a small improvement by HIO. The close proximity between the vanishing residual curve and the vanishing error curve for ER and HIO reflects the absolute uniqueness under random illumination.

With uniform illumination, ER produces a poor result (Figure 5 (a)), resulting a $72.8\%$ error (Figure 5 (b)) after more than 1000 iterations. The relative change curve, Figure 5(c), indicates stagnation or convergence to a fixed point after 100 iterations and the relative residual plot, Figure 5(d), shows non-convergence to the true image. For HIO reconstruction, we augment it with 50 ER iterations at the end of 1000 HIO iterations. While HIO improves the performance of ER but still leads to a shifted, inverted image which is also severely distorted (Figure 6 (a), (b)). The ripples and stripes in Figure 6 (a) are a well known artifact of HIO reconstruction . As expected, HIO reduces the residual and does not stagnate as much as ER (Figure 6 (c), (d)) but its error is greater than that of ER due to the interferences from shifted and twin images present under the uniform illumination (Figure 7).

To summarize, under a random phase illumination, the problems of stagnation and error disappear and phasing with ER/HIO achieves accurate, high-quality recovery. These experiments confirm our belief that a central barrier to stable and accurate phasing by the standard methods is the lack of absolute uniqueness.

Conclusions

In conclusion, we have proposed random illumination to address the uniqueness problem of phase retrieval. For general random illumination we have proved almost sure irreducibility for any complex-valued object whose support has rank $\geq 2$ (Theorem 2). We have proved the almost sure uniqueness, up to a global phase, under the two-point assumption (Theorem 3). The absolute uniqueness is then enforced by the positivity constraint (Corollary 1). Under the tight sector constraint, we have proved the absolute uniqueness with probability exponentially close to unity as the object sparsity increases (Theorem 4). Under the magnitude constraint, we have proved uniqueness up to a global phase with probability exponentially close to unity (Theorem 5). For general complex-valued objects without any constraint, we have established almost sure uniqueness modulo global phase with two independent illuminations (Theorem 6).

Numerical experiments reveal that phasing with random illumination drastically reduces the reconstruction error, the number of Fourier magnitude data and removes the stagnation problem commonly associated with the ER and HIO algorithms. Enforcement of absolute uniqueness therefore appears to have a profound effect on the performance of the standard phasing algorithms.

Systematic and detailed study of phasing in the presence of (additive or multiplicative) noise with low-resolution random illuminations and sub-Nyquist sampling rates will be presented in the forthcoming paper .

Appendix A Proof of Theorem 2

Our argument is based on and can be extended to the case of more than two independent variables. For simplicity of notation, we present the proof for the case of two independent variables.

First we state an elementary result from algebraic geometry (see, e.g., , page 65).

If a homogeneous polynomial $P(z_{0},z_{1},z_{2})$ of (total) degree $\delta\geq 2$ is irreducible, then $P^{\flat}(z_{1},z_{2})\equiv P(1,z_{1},z_{2})$ is also irreducible with degree $\delta$.

For a polynomial $Q(z_{1},z_{2})$ of degree $\delta$, the expression

defines a homogeneous polynomial of degree $\delta$ with the property $Q(z_{1},z_{2})=Q^{\sharp}(1,z_{1},z_{2})$. The process from $Q$ to $Q^{\sharp}$ is called homogenization while the reverse process is called dehomogenization. Homogenization, in conjunction with Proposition 1, is a useful tool for studying the question of irreducibility.

A subset of a projective space is closed in the Zariski topology if and only if it is an algebraic variety, i.e. the common zero set

of a finite number of homogeneous polynomials $F_{1},\cdots,F_{m}$ of the homogeneous coordinates of the projective space. The Zariski topology is much cruder than the metric topology. Indeed, a Zariski closed set is either the whole space or a measure-zero, nowhere-dense closed set in the metric topology as stated in the following (see, e.g. , page 115).

Any Zariski closed proper subset of a (real or complex) projective variety has measure zero with respect to the standard measure on the projective variety.

Now the multiplication of two polynomials of degree $j$ and $\delta-j$ determines a regular (i.e. polynomial) mapping

in the following way. Let $G({\mathbf{z}})$ and $H({\mathbf{z}})$ be homogeneous polynomials of degrees $j$ and $\delta-j$, respectively. Let $\{g(\mathbf{n})\}$ and $\{h(\mathbf{n})\}$ be the coefficients of $G$ and $H$, respectively. Then the coefficients of the image point $\Phi(G,H)$ are given by

In other words $\Phi$ is bilinear in $\{g(\mathbf{n})\}$ and $\{h(\mathbf{n})\}$ and thus is regular. Clearly we have

Let $\Sigma=\{\mathbf{n}_{1},\mathbf{n}_{2},\cdots,\mathbf{n}_{S}\}$ and let the ensemble of polynomials corresponding to $\{\lambda(\mathbf{n})f(\mathbf{n})\}$ be identified with

Following the suggestion in , we now prove

The argument is based on two observations. First the polynomial

Secondly, for any $\Sigma$ satisfying the assumptions of Theorem 2, there exists a set $T\subset\Sigma^{\sharp}$ of three points which can be transformed into $\{(r,0,0),(0,r,0),(0,0,r)\}$, the support of (16), under a rational map.

We separate the analysis of the second observation into two cases.

Case 1: $(0,0)\in\Sigma$. Then there are at least two other points, say $(m,n),(p,q)$, belonging to $\Sigma$. Without loss of generality, we assume $p+q=\delta$. Because $\Sigma$ has rank 2, $mq-np\neq 0$.

to $F(x,y,z)$. This amounts to a linear transformation from the set of independent vectors

to the set $\{(r,0,0),(0,r,0),(0,0,r)\}$. This transformation can be accomplished by the following matrix

where the divisor is nonzero. To ensure integer entries in (18) we set

Case 2: $(m,0),(0,n)\in\Sigma$ for some positive integers $m,n$. Then there is at least another point $(p,q)\in\Sigma$ such that $(m,0),(0,n),(p,q)$ are not collinear, which means $mn-np-mq\neq 0$.

Suppose $p+q=\delta$. Consider the polynomial

By the same analysis above the form (16) can be achieved by the transformation matrix

which has integer entries if $r$ is a multiple of $\delta(mn-mq-np)$. With the choice

Suppose $n=\delta$. Consider the polynomial

The form (16) can be achieved by the transformation matrix

Suppose $m=\delta$. Consider the polynomial

The form (16) can be achieved by the transformation matrix

To conclude the proof of Proposition 4, in any above case, if the polynomial $P(z_{0},z_{1},z_{2})$ is reducible (i.e. has a non-monomial factor), then we can write $P=P_{1}P_{2}$ and

where $P_{1},P_{2}$ are non-monomial factors. Let $l$ be the lowest (possibly negative) power in $x,y,z$ of $P_{i}(z_{0}(x,y,z),z_{1}(x,y,z),z_{2}(x,y,z)),i=1,2$. If $l\geq 0$, then the factorization (19) implies that $F(x,y,z)$ has a non-monomial factor. If $l<0$, then the factorization (19) implies that $(xyz)^{-l}F(x,y,z)$ has a non-monomial factor. Either case contradicts the fact that $F$ is irreducible. So $P$ is irreducible. The proof of Proposition 4 is complete.

Acknowledgements. I am grateful to my colleagues Greg Kuperberg and Brian Osserman for inspiring discussions on the proof of Theorem 2, an improvement of the earlier version which assumes convexity of the support. I thank my student Wenjing Liao for performing simulations and producing the figures.

References