Finite sign enumeration for real phase retrieval

Input a real measurement matrix $A$ with $m$ rows indexed by $[m]=\{1,\dots ,m\}$ and $d$ columns indexed by $k<d$, where $d\ge 1$ and $m\ge 0$. Use row $i-1$ of the ordinary zero-based $m\times d$ matrix for measurement label $i$. Input nonnegative intensities $b:[m]\to [0,\mathrm{\infty })$, a mode in $\{\mathrm{e}\mathrm{x}\mathrm{a}\mathrm{c}\mathrm{t},\mathrm{n}\mathrm{o}\mathrm{i}\mathrm{s}\mathrm{y}\}$, a feasibility tolerance $\epsilon \ge 0$, a maximum sign-pattern count $P\in {\mathbb{Z}}_{\ge 0}$, and a linear-solve budget $L\in {\mathbb{Z}}_{\ge 0}$. Put $r_i=\sqrt{b_i}$.

For $m=0$, let ${\mathcal{S}}_m$ contain only the empty sign vector. For $m\ge 1$, let ${\mathcal{S}}_m=\{s:[m]\to \{-1,+1\}:s_1=+1\},$ ordered lexicographically with $+1$ before $-1$ and labels in increasing order. This gives one representative from each pair $\{s,-s\}$. A signed right-hand side is $y_s=(s_i{r}_i{)}_{i\in [m]}$, interpreted in the same zero-based row order as $A$.

If $P=0$ or $L=0$, return no candidates with status budget-exhausted. Otherwise compute one SVD of $A$, form its unique Moore–Penrose inverse $A^{+}$ and kernel $\ker A$, then process at most the first $P$ patterns in ${\mathcal{S}}_m$ and perform at most $L$ signed least-squares solves. Stop when either budget is exhausted. For each processed pattern $s$, compute the minimum-Euclidean-norm least-squares solution $x_s=A^{+}{y}_s$ and signed residual $e_s=\mathrm{\parallel }A{x}_s-y_s{\mathrm{\parallel }}_2$. The budget $L$ counts right-hand-side solves after the one SVD factorization.

• In exact mode, record the affine family $x_s+\ker A$ when $e_s\le \epsilon$, together with $e_s$. Mark it exact-feasible if $e_s=0$ and tolerance-feasible if $0<e_s\le \epsilon$. If $\epsilon =0$ and all patterns are processed, return the union of the exact-feasible families modulo $x\sim -x$, or report infeasible if this union is empty. For $\epsilon >0$, report only the tolerance-qualified least-squares families; this is a tolerance screen, not a list of every vector whose residual is at most $\epsilon$.
• In noisy mode, initialize the incumbent as unset. For the first processed pattern, store $x_s$ and $J(x_s)$. For each later processed pattern, replace the incumbent by $x_s$ exactly when $J(x_s)$ is strictly smaller than the incumbent value; on a tie, keep the earlier pattern. Compute each visited candidate's squared amplitude residual $J(x_s)={\sum }_{i\in [m]}(\mathrm{\mid }(A{x}_s{)}_i\mathrm{\mid }-r_i{)}^2$ before applying that update. The feasibility tolerance is not used in this mode.
• Return the candidates and a status. Exact mode returns exact-feasible/infeasible only when $\epsilon =0$ and all patterns are processed; positive tolerance returns tolerance-feasible/no-tolerance-fit when all patterns are processed. Noisy mode returns a completed best candidate when all patterns are processed. If either budget stops enumeration before all patterns are processed, return budget-exhausted with any candidates found. A budget-exhausted result makes no claim about unvisited patterns.

No statistical optimality or intensity-noise guarantee is part of this algorithm.

Real amplitude and intensity measurement conventions

Finite-matrix Moore–Penrose equations

Existence and uniqueness of the finite-matrix pseudoinverse

Minimum-norm least-squares solve

Full affine least-squares solution family

Finite-dimensional SVD used for the solves

Finite span expansions used by the finite-dimensional orthogonal-basis argument

Euclidean norm convention

Euclidean metrics on finite real coordinate spaces

Absolute value

Nonnegative square root