位相回復

同義語:位相回復問題phase retrieval

概要

位相回復(phase retrieval)とは、Fourier 変換の絶対値など位相を失った測定値から信号を復元する問題である。台が有限な信号の振幅は自己相関と同じ情報で、1 次元では解は多項式の根の裏返しで尽くされ、一般の信号に自明でない解がある。2 次元以上ではほとんどすべての信号の多項式が既約で、自明な曖昧さを除いて一意に決まり、実の一般の測定では補集合の性質が単射と同値で $2N-1$ 個が必要である。計算には PhaseLift や交互射影を使い、回折の測定や光学の像の再構成に現れる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: Fourier変換, 離散Fourier変換, 一意分解整域, 半正定値計画

X 線回折やレーザーの測定では、波の強さ、すなわち Fourier 変換の絶対値は測れるが、位相は測れない。位相回復 は、この絶対値だけから信号を復元する問題である。位相には像の情報の大部分があるので、一見すると復元は絶望的に見える。ところが、信号の台が有限であることを使うと、次元によって答えがはっきり分かれる。1 次元ではほとんどすべての信号に本質的に別の解があり、2 次元以上ではほとんどすべての信号が自明な変換を除いて一意に決まる。
この記事では、この対比を多項式の因数分解の言葉で証明する。1 次元の解は根の裏返しで尽くされる。2 次元以上で一意なのは、多変数の多項式がほとんど既約だからである。さらに、一般の測定ベクトルでの必要十分条件(補集合の性質)、凸緩和 PhaseLift の正しさの判定、交互射影の誤差の単調性とその限界を示す。

定義と使える条件

$n=(n_1,\dots,n_d)$ を非負整数の組、$B_n:=\prod_i\{0,\dots,n_i\}$ を箱とする。$x\colon\mathbb{Z}^d\to\mathbb{C}$ は有限個の点を除いて $0$ の関数とし、$\mathcal Fx(\omega):=\sum_kx_ke^{-ik\cdot\omega}$($\omega\in\mathbb{T}^d$)とおく。

位相回復問題と自明な曖昧さ

Fourier 位相回復 とは、$\lvert\mathcal Fx\rvert$ から $x$ を求める問題である。次の変換は $\lvert\mathcal Fx\rvert$ を変えない。これらを 自明な曖昧さ という($\lvert c\rvert=1$、$m\in\mathbb{Z}^d$)。

  1. 大域的な位相:$x_k\mapsto cx_k$。
  2. 平行移動:$x_k\mapsto x_{k-m}$。
  3. 共役反転:$x_k\mapsto\overline{x_{m-k}}$。

一般の位相回復 とは、$a_1,\dots,a_m\in\mathbb{C}^N$(または $\mathbb{R}^N$)を与えて、$b_j:=\lvert\langle a_j,x\rangle\rvert$ から $x\in\mathbb{C}^N$($\mathbb{R}^N$)を大域的な位相を除いて求める問題である。

信号の 自己相関 を $\alpha_m:=\sum_kx_{k+m}\overline{x_k}$ とする。使える条件は次のとおりである。

  • (i) 台の条件:$x$ の台が有限で、箱 $B_n$ に入ることが分かっている。
  • (ii) 過剰標本:$\lvert\mathcal Fx\rvert$ を $\mathbb{T}^d$ 全体か、各方向 $N_i\ge2n_i+1$ 点の格子の上で知っている。
  • (iii) 既約性:$x$ の多項式 $X(z):=\sum_kx_kz^k$ が既約である(2 次元以上で、ほとんどすべての $x$ で成り立つ)。

公式の表

量式・結論使える条件根拠
振幅と自己相関$\lvert\mathcal Fx(\omega)\rvert^2=\sum_m\alpha_me^{-im\cdot\omega}$台が有限prop-pr-autocorr
1 次元の解の全体$Y=c\prod_j(z-s_j)$、$s_j\in\{r_j,1/\overline{r_j}\}$$d=1$、$x_0x_n\ne0$thm-pr-flip
1 次元の解の個数自明な曖昧さを除いて $2^{n-1}$ 個根が一般の位置thm-pr-flip
多次元の一意性自明な曖昧さだけ(iii)thm-pr-irreducible
既約でない $x$測度零$n_i\ge1$ が 2 方向以上thm-pr-generic
実の測定の必要十分条件補集合の性質$\mathbb{R}^N$thm-pr-complement
実の測定の個数$m\ge2N-1$ が必要、一般の位置なら十分$\mathbb{R}^N$cor-pr-2n
複素の測定の個数$m\ge4N-4$ なら一般の測定で単射$\mathbb{C}^N$(証明しない)CEHV15 Theorem 1.1
PhaseLift の成功の判定双対証明があれば $xx^*$ が唯一の解prop-pr-certificate の条件prop-pr-certificate
交互射影の誤差$E_{k+1}\le E_k$$A$ は列フルランクprop-pr-er

主定理

振幅から自己相関へ

振幅は自己相関と同じ情報である

$\lvert\mathcal Fx(\omega)\rvert^2=\sum_m\alpha_me^{-im\cdot\omega}$ である。$x$ の台が $B_n$ に入るなら $\alpha_m$ の台は $\lvert m_i\rvert\le n_i$ に入り、$N_i\ge2n_i+1$ の格子の上の $\lvert\mathcal Fx\rvert$ から $\alpha_m$ が決まる。Laurent 多項式としては
$$ \sum_m\alpha_mz^m=X(z)\widetilde X(z),\qquad\widetilde X(z):=\sum_k\overline{x_k}z^{-k} $$
である。

積を展開し離散 Fourier 変換を逆に解く

$\lvert\mathcal Fx\rvert^2=\sum_{k,l}x_k\overline{x_l}e^{-i(k-l)\cdot\omega}$ で、$m=k-l$ でまとめる。$\lvert m_i\rvert\le n_i$ の点は $\prod\mathbb{Z}/N_i\mathbb{Z}$ の中で互いに異なるので、離散Fourier変換 の反転公式で $\alpha_m$ が求まる。積の式は $z_j=e^{-i\omega_j}$ のとき $\overline{z^k}=z^{-k}$ であることから、展開して同じ和になる。$\square$

$\widetilde{\phantom{X}}$ は Laurent 多項式環 $R:=\mathbb{C}[z_1^{\pm1},\dots,z_d^{\pm1}]$ の共役線形な環自己同型である。$\widetilde{\widetilde X}=X$ である。$R$ は一意分解整域で、単元は $cz^m$($c\ne0$)である。問題は、$X\widetilde X$ から $X$ を求めるという因数分解の問題になった。

1 次元:根の裏返しが解のすべて

$d=1$ とし、$x_0x_n\ne0$、$X(z)=x_n\prod_{j=1}^n(z-r_j)$ とする。$\rho(z):=1/\overline z$ を単位円についての反転とする。$\lvert e^{i\omega}-r\rvert=\lvert r\rvert\,\lvert e^{i\omega}-\rho(r)\rvert$ なので、根 $r$ を $\rho(r)$ に置き換えて定数を調整しても振幅は変わらない。

根の裏返し

$y$ の台が $\{0,\dots,n\}$ に入り $\lvert\mathcal Fy\rvert=\lvert\mathcal Fx\rvert$ であることは、ある $S\subset\{1,\dots,n\}$ と $\lvert c\rvert=1$ で
$$ Y(z)=c\,x_n\prod_{j\in S}\lvert r_j\rvert\prod_{j\in S}\bigl(z-\rho(r_j)\bigr)\prod_{j\notin S}(z-r_j) $$
となることと同値である。$r_j,\rho(r_j)$($j=1,\dots,n$)の $2n$ 個が相異なるとき、位相を除いて解はちょうど $2^n$ 個あり、$S$ と補集合が共役反転で対応する。したがって自明な曖昧さを除くと $2^{n-1}$ 個である。

$\rho$ の軌道ごとに根の選び方を数える

十分性。 上の絶対値の等式から $\lvert Y(e^{-i\omega})\rvert=\lvert X(e^{-i\omega})\rvert$ である。
必要性。 ずれ $n$ の自己相関から $y_n\overline{y_0}=x_n\overline{x_0}\ne0$ なので $Y$ の次数は $n$ で $y_0\ne0$ である。prop-pr-autocorr から $Y\widetilde Y=X\widetilde X$ である。$z^n\widetilde X(z)$ の根は $\rho(r_j)$ なので、$\mathbb{C}\setminus\{0\}$ の多重集合として $\{s_j\}\uplus\rho\{s_j\}=\{r_j\}\uplus\rho\{r_j\}$ である($s_j$ は $Y$ の根)。$\rho$ の軌道 $\{r,\rho(r)\}$ ごとに見る。$\lvert r\rvert\ne1$ のとき、$r$ の $\{r_j\}$ での重複度を $p$、$\rho(r)$ の重複度を $q$、$\{s_j\}$ での同様の数を $p',q'$ とすると $p'+q'=p+q$ である。これは $\{r_j\}$ の軌道の中の $p+q$ 個のうちいくつかを裏返して得られる。$\lvert r\rvert=1$ のとき $2p'=2p$ で変わらない。よって $\{s_j\}$ は裏返しで得られる。定数の絶対値は振幅の等式から決まる。
個数。 仮定から異なる $S$ は異なる根の集合を与える。$\{s_j\}$ を共役反転すると $\rho\{s_j\}$、すなわち補集合の $S$ になる。$\{0,\dots,n\}$ に台が入るという条件で平行移動は働かない。$\square$

$n\ge2$ では $2^{n-1}\ge2$ なので、一般の位置の 1 次元信号には自明でない解が必ずある。台の条件だけでは足りない(BS79、BBE17 Theorem 3.1)。

多次元:ほとんどすべてが一意

既約なら一意

$X$ が多項式環 $\mathbb{C}[z_1,\dots,z_d]$ で既約で、単項式の定数倍でないとする。$y$ が有限台で $\lvert\mathcal Fy\rvert=\lvert\mathcal Fx\rvert$ なら、$y$ は $x$ の自明な曖昧さである。

一意分解整域で素元が割る方を見る

$Y(z):=\sum_ky_kz^k\in R$ とする。prop-pr-autocorr と Laurent 多項式が $\mathbb{T}^d$ の上の値で決まることから、$R$ で $Y\widetilde Y=X\widetilde X$ である。$X$ は $R$ の素元である(既約で $z_i$ で割れないので局所化で素元のまま)。よって $X\mid Y$ または $X\mid\widetilde Y$ である。
$Y=Xh$ のとき、$X\widetilde X=Xh\widetilde X\widetilde h$ から $h\widetilde h=1$ である。$h$ は単元なので $h=cz^m$ で、$h\widetilde h=\lvert c\rvert^2$ から $\lvert c\rvert=1$ である。よって $y_k=cx_{k-m}$ である。
$\widetilde Y=Xh$ のとき、$Y=\widetilde X\widetilde h$ で、同様に $h=cz^m$、$\lvert c\rvert=1$ である。よって $y_k=\overline c\,\overline{x_{-m-k}}$ である。$\square$

次の補題の 1 行が、1 次元と 2 次元の違いのすべてである。

箱の格子点の数

$a,b$ を非負整数の組、$n=a+b$、$a\ne0\ne b$ とし、$n_i\ge1$ となる $i$ が 2 個以上あるとする。$P:=\prod(a_i+1)$、$Q:=\prod(b_i+1)$、$M:=\prod(n_i+1)$ とすると $P+Q-1< M$ である。

2 つの箱では埋まらない点をとる

$[0,n]$ の中の箱 $[0,a]$ と箱 $[a,n]$ は格子点をそれぞれ $P$ 個、$Q$ 個もち、共有点は $a$ だけである。$a_j\ge1$、$b_l\ge1$ となる $j\ne l$ がとれれば、第 $j$ 座標が $a_j-1$、第 $l$ 座標が $a_l+1$ の点はどちらの箱にも入らない。そのような $j\ne l$ がとれないのは、$a,b$ の台が同じ 1 点のときだけで、これは仮定に反する。$\square$

$d=1$ なら 2 つの箱で $[0,n]$ が埋まり、$P+Q-1=M$ である。これは「1 変数の多項式はいつも因数分解できる」ことの次元の数え方による表現である。

既約な多項式はほとんどすべて

$n_i\ge1$ となる $i$ が 2 個以上あるとする。$\mathbb{C}^{B_n}$ の点 $x$ で、$X$ が既約でないか、$z_i$ の次数が $n_i$ より小さい $i$ があるものの全体は、Lebesgue 測度零である。$\mathbb{R}^{B_n}$ の点で $X$ が $\mathbb{C}$ 上既約でないものも測度零である。したがって、ほとんどすべての $x$ について、thm-pr-irreducible の結論が成り立つ。

積写像の像は次元が足りない

次数が落ちる $x$ は座標部分空間の有限和に入るので測度零である。各 $z_i$ の次数がちょうど $n_i$ の $X$ が可約なら、$X=fg$ で、$f,g$ の次数の組 $a,b$ は $a+b=n$、$a\ne0\ne b$ をみたす。この $(a,b)$ は有限通りである。$f$ の係数の 1 つを $1$ に正規化できるので、$X$ は多項式写像 $\mathbb{C}^{P-1}\times\mathbb{C}^Q\to\mathbb{C}^M$(有限個)の像に入る。lem-pr-box から実次元は $2(P+Q-1)< 2M$ なので、Sardの定理 の補題「次元の低い空間からの写像の像」により像は測度零である。
実係数の場合。$\mathbb{R}$ 上で可約なものは同じ議論で $P+Q-1< M$ から測度零である。$\mathbb{R}$ 上既約で $\mathbb{C}$ 上可約な $X$ の既約因子を $f$ とする。$\overline f$ が $f$ の定数倍なら $f$ を実係数にでき、矛盾する。そうでなければ $f\overline f\mid X$ なので $X=cf\overline f$($c$ は実数)である。$f$ の 1 つの係数を $1$ に正規化すると実次元 $2(P-1)+1=2P-1$ のパラメータで書け、$a=b$ の場合の補題から $2P-1< M$ なので、やはり測度零である。
$X$ が既約で 2 変数以上を含むので単項式でなく、thm-pr-irreducible が使える。$\square$

この 2 つの定理の主張は M. H. Hayes と J. H. McClellan による(Hay82、HM82、BBE17 Theorem 3.21・3.22)。ここの証明は格子点の数え方で書いた。

一般の測定ベクトル

補集合の性質

$a_1,\dots,a_m\in\mathbb{R}^N$ とする。写像 $x\mapsto(\lvert\langle a_j,x\rangle\rvert)_j$ が $\mathbb{R}^N/\{\pm1\}$ の上で単射であるのは、どの $S\subset\{1,\dots,m\}$ についても $\{a_j\}_{j\in S}$ か $\{a_j\}_{j\notin S}$ が $\mathbb{R}^N$ を張るとき(補集合の性質)に限る。

和と差に分ける

補集合の性質が成り立たないとする。ある $S$ と $u,v\ne0$ で、$u\perp a_j$($j\in S$)、$v\perp a_j$($j\notin S$)である。$x:=u+v$、$y:=u-v$ とすると、どの $j$ でも $\lvert\langle a_j,x\rangle\rvert=\lvert\langle a_j,y\rangle\rvert$ であり、$u,v\ne0$ から $x\ne\pm y$ である。
逆に $\lvert\langle a_j,x\rangle\rvert=\lvert\langle a_j,y\rangle\rvert$(全 $j$)、$x\ne\pm y$ とする。$S:=\{j:\langle a_j,x\rangle=\langle a_j,y\rangle\}$ とすると、$j\in S$ で $a_j\perp x-y$、$j\notin S$ で $a_j\perp x+y$ で、$x\mp y\ne0$ なのでどちらも張らない。$\square$

必要な測定の数

$\mathbb{R}^N$ で単射なら $m\ge2N-1$ である。$m\ge2N-1$ で、どの $N$ 個の $a_j$ も 1 次独立なら単射である。

半分に分ける

$m\le2N-2$ なら $N-1$ 個以下の 2 組に分けられ、どちらも張らない。$m\ge2N-1$ なら $S$ と補集合の一方は $N$ 個以上で、張る。$\square$

これらは R. Balan・P. Casazza・D. Edidin による(BCE06、証明は BCMN14 Theorem 3 にもある)。複素の場合は事情が違い、$m\ge4N-4$ なら一般の位置の測定で単射である(CEHV15 Theorem 1.1。この記事では証明しない)。

PhaseLift

$\lvert\langle a_j,x\rangle\rvert^2=\operatorname{tr}(a_ja_j^*xx^*)$ なので、$x$ について 2 次の条件は $X=xx^*$ について線形である。階数 $1$ の条件を跡の最小化に置き換えた 半正定値計画
$$ \min\ \operatorname{tr}X\quad\text{s.t.}\quad X\succeq0,\ \operatorname{tr}(a_ja_j^*X)=b_j^2\ (j=1,\dots,m) $$
を PhaseLift という(CSV13)。

双対証明による判定

$x\ne0$、$b_j=\lvert\langle a_j,x\rangle\rvert$ とする。実数 $\lambda_j$ で、$Y:=I-\sum_j\lambda_ja_ja_j^*$ が $Y\succeq0$、$Yx=0$、$\operatorname{rank}Y=N-1$ をみたすものがあれば、$xx^*$ は PhaseLift のただ 1 つの解である。

差を $\operatorname{tr}(YX)$ で表す

実行可能な $X$ について $\operatorname{tr}(YX)=\operatorname{tr}X-\sum_j\lambda_jb_j^2$ である。$X=xx^*$ を代入すると $0=\lvert x\rvert^2-\sum_j\lambda_jb_j^2$ なので、$\operatorname{tr}X-\lvert x\rvert^2=\operatorname{tr}(YX)\ge0$ である(半正定値計画 の補題「半正定値行列の内積は非負」)。等号なら $YX=0$ で、$X$ の像は $\ker Y=\mathbb{C}x$ に入るので $X=cxx^*$、跡を比べて $c=1$ である。$\square$

このような $\lambda$ の存在を確率的に示したのが次の定理である。この記事では証明しない。$a_j$ が単位球面上で独立に一様なとき、定数 $c_0,\gamma>0$ があり、$m\ge c_0N\log N$ なら、固定した $x$ について確率 $1-3e^{-\gamma m/N}$ 以上で PhaseLift は $xx^*$ を返す(CSV13 Theorem 1.1)。さらに $m\ge c_0N$ に改良され、高い確率ですべての $x$ に同時に成り立つ(CL14 Theorem 1.2)。

交互射影

$A$ を列フルランクの行列、$b\ge0$ とし、$\lvert Ax\rvert=b$ を解きたい(Fourier の場合、$A$ は過剰標本の離散 Fourier 変換を台 $T$ に制限したもの)。$\phi(w)$ を各成分 $w_j/\lvert w_j\rvert$($w_j=0$ なら任意の単位複素数)のベクトルとする。誤差減少法 は次の反復である(GS72、Fie82):
$$ y_k:=b\odot\phi(Ax_k),\qquad x_{k+1}:=A^+y_k,\qquad E_k:=\bigl\|\lvert Ax_k\rvert-b\bigr\|_2. $$

誤差の単調性

$E_{k+1}\le E_k$ である。

2 つの最短距離の性質

各成分で $\min_{\lvert u\rvert=1}\lvert w-b_ju\rvert=\lvert\lvert w\rvert-b_j\rvert$ で、最小は $u=\phi(w)$ でとられるので、$y_k$ は $\{y:\lvert y\rvert=b\}$ の中で $Ax_k$ に最も近く、$E_k=\|Ax_k-y_k\|$ である。また $Ax_{k+1}=AA^+y_k$ は $A$ の値域の中で $y_k$ に最も近い。よって
$$ E_{k+1}=\|Ax_{k+1}-y_{k+1}\|\le\|Ax_{k+1}-y_k\|\le\|Ax_k-y_k\|=E_k $$
である。$\square$

$\{y:\lvert y\rvert=b\}$ は凸でないので、単調性は解への収束を意味しない。$E_k$ は正の値で止まりうる(ex-pr-stagnation)。
図: 左は複素平面で、単位円と x=(6,-5,1) の多項式の根 2, 3 およびその裏返し 1/2, 1/3。右は 2 次元の誤差減少法の相対誤差の両対数グラフで、誤差は単調に減り 0.05 付近で止まる。 図: 左は複素平面で、単位円と x=(6,-5,1) の多項式の根 2, 3 およびその裏返し 1/2, 1/3。右は 2 次元の誤差減少法の相対誤差の両対数グラフで、誤差は単調に減り 0.05 付近で止まる。

計算の手順

  1. 問題の型を決める。Fourier 型なら次元 $d$ と台の箱を、一般の測定なら $m$ と $N$ を確かめる。
  2. 振幅の標本が各方向 $2n_i+1$ 点以上あることを確かめ、自己相関 $\alpha_m$ を計算する(prop-pr-autocorr)。
  3. $d=1$ なら、$\sum_m\alpha_mz^{m+n}$ の根を求めて $\rho$ の組に分け、裏返しを列挙する(thm-pr-flip)。解を 1 つに決めるには、追加の情報(非負性、既知の成分、別の測定)を使う。
  4. $d\ge2$ なら既約性を期待してよい。解を求めるには、誤差減少法やその改良(Fienup の入出力法など、Fie82、BCL02)を初期値を変えて何度も走らせる。
  5. 止める判定:$E_k/\|b\|$ が雑音の水準以下になるか、減少が止まったら終える。$E_k$ が大きいまま止まったら初期値を変える。
  6. 測定を設計できるなら、ランダムな $a_j$ と PhaseLift を使う($N$ が小さいとき。$N^2$ 個の未知数の半正定値計画を解く)。

例題

長さ 3 の信号の裏返し

$x=(6,-5,1)$、$X=(z-2)(z-3)$。
使う公式:thm-pr-flip($n=2$、$\rho(2)=\frac12$、$\rho(3)=\frac13$)。
答え:解は位相を除いて $(6,-5,1)$、$(1,-5,6)$、$(3,-7,2)$、$(2,-7,3)$ の 4 個で、自己相関は共通の $(6,-35,62,-35,6)$ である。自明な曖昧さを除くと $(6,-5,1)$ と $(3,-7,2)$ の 2 個である。$\omega=\pi/2$ で $\lvert\mathcal Fx\rvert^2=50$ で、$(3,-7,2)$ も $\lvert3+7i-2\rvert^2=50$ である。

2 次元:可約と既約

可約:$X=(1+2z_1)(1+3z_2)$、行列で $x=\begin{pmatrix}1&3\\2&6\end{pmatrix}$。第 1 の因子を裏返すと $(2+z_1)(1+3z_2)$、$y=\begin{pmatrix}2&6\\1&3\end{pmatrix}$ で、自己相関は同じだが、$y$ は $x$ の自明な曖昧さでない。
既約:$X=1+z_1+z_2+2z_1z_2$ は既約である(因子は $(p+qz_1)(u+vz_2)$ の形しかなく、$pu=qu=pv=1$ から $qv=1$ となって $2$ と合わない)。よって自明な曖昧さを除いて一意である。

既約でも不安定

$x_\varepsilon:=\begin{pmatrix}1&3\\2&6+\varepsilon\end{pmatrix}$ は $\varepsilon\ne0$ で既約なので、$\lvert\mathcal Fx_\varepsilon\rvert$ から一意に決まる。一方、ex-pr-2d の $y$ と比べると、$3\times3$ の格子の上の振幅(正規化なしの和)の差の $\ell^2$ ノルムは $\varepsilon=10^{-3}$ で $0.00266$ だが、信号の差は($y$ と、その反転の符号違いまで見ても)$4.47$ である。一意性は安定性を意味しない。

実の測定

$\mathbb{R}^2$ で $a=e_1,e_2,e_1+e_2$、$b=(2,3,1)$。
使う公式:cor-pr-2n(どの 2 本も 1 次独立)。
答え:$x=(\pm2,\pm3)$ のうち $\lvert x_1+x_2\rvert=1$ をみたすのは $\pm(2,-3)$ だけである。$a_3$ を除くと $(2,3)$ と $(2,-3)$ を区別できない。

誤差減少法の停滞と 2 次元の数値例

$A$ の行を $e_1,e_2,(e_1+e_2)/\sqrt2$ とし、$x^\star=(1,1)$ の $b=(1,1,\sqrt2)$ をとる。初期値 $x_0=(1,-1.2)$ から $x_1=(0.5,-1.5)$ となり、以後動かない。$E_0\approx1.2884$、$E_k=1$($k\ge1$)である。初期値 $(1.2,0.8)$ なら $x^\star$ に達する。

途中の計算を開く

$Ax_1$ の符号は $(+,-,-)$ で、$y=(1,-1,-\sqrt2)$。$A^{\top}A=\begin{pmatrix}3/2&1/2\\1/2&3/2\end{pmatrix}$、$A^{\top}y=(0,-2)$ から $A^+y=(0.5,-1.5)$。$\lvert Ax_1\rvert=(0.5,1.5,1/\sqrt2)$ で $E^2=\frac14+\frac14+\frac12=1$。


Fourier の例:$8\times8$ の $[0,1)$ の一様乱数の信号(種 $20261107$)、$16\times16$ の格子、非負性と台の射影、一様乱数の初期値で、$E_k/\|b\|$ は次のとおりである。

$k$$0$$1$$10$$100$$1000$$2000$
相対誤差$0.3241$$0.2299$$0.1497$$0.0923$$0.0523$$0.0523$

誤差は単調に減るが $0$ にならず、$k=2000$ の解は真の信号から相対距離 $0.626$、その共役反転から $0.284$ 離れている。一様乱数の信号は確率 $1$ で既約で解は一意だが(thm-pr-generic)、この反復は解に届いていない。

使える条件と反例

外す条件反例成り立たなくなること
$d\ge2$$d=1$、$x=(6,-5,1)$自明でない解がある(ex-pr-flip)
(iii) 既約性$(1+2z_1)(1+3z_2)$2 次元でも自明でない解がある(ex-pr-2d)
(ii) 過剰標本$N=n+1$ の格子:$x=(6,-5,1)$ の 3 点の振幅に任意の位相を付けて逆変換した $(4.10277,-5.68585,3.58308)$自己相関が違うのに格子の上の振幅が同じ(prop-pr-autocorr の結論が成り立たない)
(i) 台が有限$\hat y=e^{i\theta(\omega)}\hat x$($\theta$ は一般の滑らかな周期関数)thm-pr-irreducible の結論が成り立たない。$y$ は無限に広がる
測定の数 $m\ge2N-1$$\mathbb{R}^2$ で $e_1,e_2$$(1,1)$ と $(1,-1)$ が同じ測定値(cor-pr-2n)
どの $N$ 個も独立$\mathbb{R}^2$ で $e_1,e_1,e_2$($m=3=2N-1$)同じ 2 点が同じ測定値で、単射でない
PhaseLift の証明の存在$a=(1,1)/\sqrt2$、$x=e_1$($b^2=\frac12$)解は $\frac12aa^{\top}$(跡 $\frac12$)で $xx^{\top}$(跡 $1$)でない
確かめを開く

最後の行:$\operatorname{tr}X\ge a^{\top}Xa=\frac12$($\lvert a\rvert=1$)で、等号は $\frac12aa^{\top}$。一方 $x=a$ なら $b^2=1$ で $\lambda=1$、$Y=I-aa^{\top}$ は prop-pr-certificate の条件をみたす。3 行目:逆変換の値は位相 $(0,1,-1)$ のものである。自己相関の端の値は $14.70$ で、$x$ の $6$ と違う。

よくある誤り

誤り正しくはなぜ
信号の長さと同じ個数の標本で足りるとする各方向 $2n_i+1$ 点が要る自己相関の台が約 2 倍(prop-pr-autocorr)
1 次元も 2 次元も同じだと考える1 次元はほとんど非一意、2 次元以上はほとんど一意thm-pr-flip、thm-pr-generic
反転や平行移動の違いを誤りと数える自明な曖昧さは測定から区別できないdef-pr-main
誤差が減り続ければ解に近づくと考える正の値で止まるex-pr-stagnation
一意なら雑音に強いと考える可約な点の近くでは不安定ex-pr-unstable
実の場合の $2N-1$ を複素にも使う複素では別の数え方になるCEHV15

補足

総説と関連する話題

Fourier 型の問題の一意性とアルゴリズムの総説に BBE17 がある。誤差減少法と凸射影の関係は BCL02 が論じている。線形の測定の疎な復元は 圧縮センシング で扱う。PhaseLift の跡の最小化は、圧縮センシングの $\ell^1$ 最小化の行列版にあたる。

関連項目

参考文献

[1]
Tamir Bendory; Robert Beinert; Yonina C. Eldar, Fourier Phase Retrieval: Uniqueness and Algorithms, Compressed Sensing and its Applications, Applied and Numerical Harmonic Analysis, Birkhäuser (2017); arXiv:1705.09590v3, 2017, 55–91
[2]
Afonso S. Bandeira; Jameson Cahill; Dustin G. Mixon; Aaron A. Nelson, Saving phase: Injectivity and stability for phase retrieval, Applied and Computational Harmonic Analysis 37 (2014), no. 1; arXiv:1302.4618v3, 2014, 106–125
[3]
Aldo Conca; Dan Edidin; Milena Hering; Cynthia Vinzant, An algebraic characterization of injectivity in phase retrieval, Applied and Computational Harmonic Analysis 38 (2015), no. 2; arXiv:1312.0158v1, 2015, 346–356
[4]
Emmanuel J. Candès; Thomas Strohmer; Vladislav Voroninski, PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming, Communications on Pure and Applied Mathematics 66 (2013), no. 8; arXiv:1109.4499v1, 2013, 1241–1274
[5]
Emmanuel J. Candès; Xiaodong Li, Solving Quadratic Equations via PhaseLift When There Are About as Many Equations as Unknowns, Foundations of Computational Mathematics 14 (2014), no. 5; arXiv:1208.6247v2, 2014, 1017–1026
[6]
R. W. Gerchberg; W. O. Saxton, A practical algorithm for the determination of phase from image and diffraction plane pictures, Optik 35 (1972), 1972, 237–246
[7]
Yu. M. Bruck; L. G. Sodin, On the ambiguity of the image reconstruction problem, Optics Communications 30 (1979), no. 3, 1979, 304–308
[8]
Monson H. Hayes, The reconstruction of a multidimensional sequence from the phase or magnitude of its Fourier transform, IEEE Transactions on Acoustics, Speech, and Signal Processing 30 (1982), no. 2, 1982, 140–154
[9]
Monson H. Hayes; James H. McClellan, Reducible polynomials in more than one variable, Proceedings of the IEEE 70 (1982), no. 2, 1982, 197–198
[10]
Radu Balan; Pete Casazza; Dan Edidin, On signal reconstruction without phase, Applied and Computational Harmonic Analysis 20 (2006), no. 3, 2006, 345–356
[11]
J. R. Fienup, Phase retrieval algorithms: a comparison, Applied Optics 21 (1982), no. 15, 1982, 2758–2769
[12]
Heinz H. Bauschke; Patrick L. Combettes; D. Russell Luke, Phase retrieval, error reduction algorithm, and Fienup variants: a view from convex optimization, Journal of the Optical Society of America A 19 (2002), no. 7, 2002, 1334–1345

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する