A fast butterfly algorithm for generalized Radon transforms

Fast butterfly algorithm

With the previously introduced low-rank approximations and the butterfly structure, we are ready to describe the fast algorithm. Our goal is to approximate $\delta_t^{AB}$ , definition 21, so as to get $u^B(\mathbf{x})$ , definition 19, by traversing the tree structure (Figure 2) from top to bottom on the $X$ side, and from bottom to top on the $K$ side. This can be done in five major steps. To avoid too much technical detail, we deliberately defer the complete derivation of the algorithm until the appendix, and only summarize here the final updating formulas for each step.

1. Initialization. At level $l=0$ , let $A$ be the root box of $T_X$ . For each leaf box $B\in T_K$ , construct the coefficients $\{\delta_t^{AB}\}$ by

$$\delta_t^{AB}=e^{-2\pi i \Phi(\mathbf{x}_0(A),\mathbf{k}_t^B)}\su... ...B(\mathbf{k}) e^{2\pi i \Phi(\mathbf{x}_0(A),\mathbf{k})}g(\mathbf{k}) \right).$$ (23)

2. Recursion. At $l=1,2,...,L/2$ , for each pair $(A,B)$ , let $A_p$ be $A$ 's parent and $\{B_c, c=1,2,3,4\}$ be $B$ 's children from the previous level. Update $\{\delta_t^{AB}\}$ from $\{\delta_{t'}^{A_pB_c}\}$ by

$$\delta_t^{AB}=e^{-2\pi i \Phi(\mathbf{x}_0(A),\mathbf{k}_t^B)}\su... ...2\pi i \Phi(\mathbf{x}_0(A),\mathbf{k}_{t'}^{B_c})}\delta_{t'}^{A_pB_c}\right).$$ (24)

3. Switch. At middle level $l=L/2$ , for each $(A,B)$ compute the new set of coefficients $\{\delta_t^{AB}\}$ from the old set $\{\delta_s^{AB}\}$ by

$$\delta^{AB}_t= \sum_s e^{2\pi i \Phi(\mathbf{x}_t^A,\mathbf{k}_s^B)}\delta_s^{AB}.$$ (25)

4. Recursion. At $l=L/2+1,...,L$ , for each pair $(A,B)$ , update $\{\delta_t^{AB}\}$ from $\{\delta_{t'}^{A_pB_c}\}$ of the previous level by

$$\delta_t^{AB}=\sum_c e^{2\pi i \Phi(\mathbf{x}_t^A,\mathbf{k}_0(B... ...pi i \Phi(\mathbf{x}_{t'}^{A_p},\mathbf{k}_0(B_c))}\delta_{t'}^{A_pB_c}\right).$$ (26)

5. Termination. Finally at level $l=L$ , $B$ is the entire domain $K$ . For every box $A$ in $X$ and every $\mathbf{x}\in A$ , compute $u(\mathbf {x})$ by

$$u(\mathbf{x})=e^{2\pi i \Phi(\mathbf{x},\mathbf{k}_0(B))}\sum_t \... ...thbf{x}) e^{-2\pi i \Phi(\mathbf{x}_t^A,\mathbf{k}_0(B))} \delta_t^{AB}\right).$$ (27)

A fast butterfly algorithm for generalized Radon transforms