Correctness and amplitude-residual objective of finite sign enumeration

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$.

If the sign vector attaining equality in step 5.1 has first entry $-1$, replace $x$ by $-x$ and $t$ by $-t$. Then the quotient class and $J(x)$ are unchanged, and $A(-x)-y_{-t}=-(Ax-y_t)$, so the squared residual is unchanged and the new vector is canonical. If $m=0$, use the unique empty pattern. Hence for every $x\in {\mathbb{R}}^d$ there are a representative $\tilde{x}\in \{x,-x\}$ and a canonical pattern $s$ with $\mathrm{\parallel }A\tilde{x}-y_s{\mathrm{\parallel }}_2^2=J(x)$, since $J(\tilde{x})=J(x)$. Least-squares minimality [F4], comparing $x_s$ to $\tilde{x}$, gives $e_s^2\le J(x)$.

For each candidate $x_s$, step 5.1 gives $J(x_s)\le \mathrm{\parallel }A{x}_s-y_s{\mathrm{\parallel }}_2^2=e_s^2$. With complete enumeration every canonical $s$ is processed. Given arbitrary $x$, step 6.1 supplies one such $s$ with $e_s^2\le J(x)$, so by step 1.2 the final incumbent has objective at most $J(x_s)\le e_s^2\le J(x)$. It is therefore a global minimizer over all $x$. If a budget leaves patterns unprocessed, this comparison gives no guarantee for a canonical pattern that was not visited.