# Two FFT Subspace-Based Optimization Methods for Electrical Impedance Tomography.

1. INTRODUCTIONElectrical impedance tomography has attracted intense interests recently in both mathematical and engineering fields [1,2]. It is well-know that EIT is a very challenging problem due to its nonlinear and highly ill-posed properties [3,4]. Various methods have been proposed to solve EIT problems such as factorization method [5], variationally constrained numerical method [6], and nonlinear modified gradient-like method [7]. Recently, subspace-based optimization method (SOM) is proposed to solve electrical impedance tomography problems [8]. In SOM, through a full singular value decomposition (SVD) of mapping from induced current to voltage on the boundary, the induced current is decomposed into deterministic part and ambiguous part [9]. The deterministic part can be directly computed with analytical solution, whereas the ambiguous part is obtained by optimizing the subspace spanned by singular vectors corresponding to small singular values [9]. Compared with the contrast source inversion (CSI) method [10], SOM has the properties of faster convergence rate and good robustness against noise [9]. However, a drawback of SOM is the overhead computation associated with the full SVD of mapping from induced current to voltage on the boundary [9]. In order to reduce the computational cost, an improved method is proposed in [11] to avoid the full SVD in SOM by using a thin SVD method. The thin SVD operation only generates the singular vectors corresponding to dominant singular values instead of all singular vectors. In addition, the computational speed is further increased with FFT applied in twofold subspace-based optimization method (TSOM) [12].

In this paper, we propose a new fast Fourier transform subspace-based optimization method (NFFTSOM) to solve the EIT problem in a domain with arbitrary boundary shape. Compared with the method in [8], the original contributions and advantages of the proposed method are as follows: (1) Instead of solving problems with circular boundary, where analytical Green's function is available, the proposed method extends to be applicable to a domain with arbitrary boundary shape. (2) Instead of using a noise subspace corresponding to smaller singular values in SOM, complete Fourier bases are used in NFFT-SOM. It is found that, compared with SOM, NFFT-SOM can obtain better reconstructed results in dealing with high noise EIT problem. Also, the computational complexity of the proposed method is largely reduced compared with [8] for two reasons. Firstly, it avoids the full singular-value decomposition of the mapping from the induced current to received voltage. Secondly, FFT can be directly used in algorithm to accelerate the computational speed. (3) It is also found that NFFT-SOM is robust to the change of number of significant singular values (the integer L) for both high and low noise cases, which is an important and encouraging conclusion. (4) Instead of using coupled dipole method to solve the EIT problem, we adopt a more general method, i.e., method of moment (MOM) [13,14] in NFFT-SOM.

Additionally, compared with the thin SVD method in [11], where the computational costs is reduced by constructing the ambiguous current subspace from identity matrix and deterministic current subspace, the NFFT-SOM constructs the ambiguous current subspace that is directly spanned by complete Fourier bases instead of singular vectors. Compared with the twofold subspace-based optimization method in [12], where 2D Fourier bases are used to construct the current subspace for two dimensional TM cases, 1D Fourier bases are used in NFFT-SOM for EIT problems in this paper. Since the subspace spanned by low frequency Fourier bases roughly corresponds to the subspace spanned by singular vectors with large singular values [12,15], 1D Fourier bases adopted in this paper directly exhibit such a correspondence, whereas the 2D Fourier bases adopted in [12] have to be sorted in order to exhibit such a correspondence. In addition, when the domain of interest is not a rectangle, the application of 2D Fourier bases requires an extra work of extending the domain of interest to a rectangle that is able to fully cover it. For NFFT-SOM, there is no need to extend the domain of interest to a rectangle. These are two advantages of the proposed method over [12] as far as implementing the SOM is concerned.

As mentioned above, it is well known that the behavior of Fourier functions is similar to the one of singular function in singular value decomposition (SVD) in the sense that low-frequency Fourier functions correspond to those singular functions with large singular values [12,15]. Thus, it is very natural to think that we can replace the deterministic current and noise subspace in SOM with low frequency current and space spanned by discrete Fourier bases, respectively. For convenience, we denote this method as low frequency subspace optimized method (LF-SOM). In this paper, we have discussed and assessed the performance of LF-SOM through various numerical simulations and comparisons with traditional SOM and NFFT-SOM. Additionally, it is noted that both of the proposed methods in this paper are applicable to three-dimensional cases as well.

2. THE FORWARD MODEL

In this paper, we consider a two-dimensional domain I consisting of a square and four half circles. As it is depicted in Fig. 1, the square has a width of [W.sub.1] which is surrounded by four half circles with a radius of [W.sub.1]/2. Actually, domain I can be of arbitrary shape, and we choose the one in Fig. 1 as an example to present our method. The background is homogenous material with the conductivity of [[sigma].sub.0] and some inclusions with conductivity of [sigma]([bar.r]) are embedded in a region interior to domain I. Electrical current is injected from the boundary[ .sub.I] into domain I, and voltages are measured at a number of [N.sub.r] nodes on the boundary [partial derivative] I which are labeled as dots in Fig. 1. There are a total number of [N.sub.i] excitations of current from boundary, and voltages at all nodes are measured for each excitation. Due to the presence of inclusions, the voltages measured at the boundary differ from those in homogenous case, and the differential voltage between these two cases at each node is recorded as [V.sup.q.sub.p], p = 1,2, ..., [N.sub.i], q = 1, 2, ..., [N.sub.r].

The Neumann boundary value problem in EIT can be described as the partial differential equation [nabla] x ([sigma][nabla]/x) = 0 in I, with [sigma][partial derivative]/[partial derivative]v = J on [partial derivative]I given a boundary excitation current J [member of] [H.sup.1/2]([partial derivative]I) with [[??].sub.[partial derivative]I] Jds = 0, where v is the outer normal direction on the boundary dI. This Neumann boundary value problem has a unique weak solution given that [mu] [member of] [H.sup.1] (I) with [[??].sub.[partial derivative]I] [mu]ds = 0. The partial differential equation can further be written as

[nabla] x ([[sigma].sub.0] [nabla][mu]) = -[[rho].sub.in] in I, [[sigma].sub.0] [partial derivative][mu]/[partial derivative]v = J on [partial derivative]I, (1)

with the induced source [[rho].sub.in] = [nabla] x [([sigma] - [[sigma].sub.0])[nabla][mu]]. Since the inclusions are within a region interior to I, the a at the boundary [partial derivative]I is just the known [[sigma].sub.0]. To solve Eq. (1) in method of moment [14], the Green's function G(r, r') in homogeneous background medium is defined and it satisfies the following differential equation with the normalization [[??].sub.[partial derivative]I] G(r, r')ds = 0,

[nabla] x ([[sigma].sub.0] [nabla]G (r, r')) = -[delta](r - r') with [[sigma].sub.0] [partial derivative]G/[partial derivative]v = -1/[absolute value of ([partial derivative]I)] on [partial derivative]I (2)

where [delta](r - r') is the Dirac delta function, and r and r' are the field point and source point in domain I, respectively.

The solution of every linear differential equation like Eq. (1) consists of two part: the particular solution that depends on the induced source pin together with the boundary condition [[sigma].sub.0] [partial derivative][mu]/[partial derivative]v = 0 on [partial derivative]I, and the general solution that depends on the exciting current J on the boundary that is injected into a homogeneous medium in absence of induced source pin. This conclusion is made rigorous by Eq. (2) and the fact that the total amount of [[rho].sub.in] inside I is equal to zero. Applying the Green's Theorem and considering the predefined normalization [[??].sub.[partial derivative]I]/[mu]ds = 0, it is easy to find that [[mu].sup.s] = [[integral].sup.I] G(r, r')[[rho].sub.in](r')dr' is the particular solution for differential equation in Eq. (1), and the superscript s here means "scattered" since the physical meaning of [[mu].sup.s] is actually scattered potential by the induced source. For the general solution, it satisfies that [nabla] x ([[sigma].sub.0] [nabla] [[mu].sup.0]) = 0 with [[sigma].sub.0][partial derivative][[mu].sup.0]/[partial derivative]v = J on [partial derivative]I. Thus, the compete solution for Eq. (1) is

[mathematical expression not reproducible] (3)

Utilizing the identity [nabla]' x (G(r, r')[bar.A]) = [bar.A] x [nabla]'G(r, r') + G(r, r')[nabla]' * [bar.A] with [bar.A] = ([sigma](r') - [[sigma].sub.0])[nabla]'[mu](r') and considering that [[integral].sup.I] [nabla]' x (G(r, r') [bar.A]) dr' = 0 due to divergence theorem, Eq. (3) becomes

[mu] = [[mu].sup.0] + [[integral].sub.I] - [nabla]'G(r, r') x ([sigma](r') - [[sigma].sub.0]) [nabla]' [mu](r') dr' (4)

Taking gradient on both side of Eq. (4), we have the following self-consistent equation.

[[bar.E].sup.t] = [[bar.E].sup.0] + [[integral].sub.I] - [nabla] [[nabla]'G(r, r') x ([sigma](r') - [[sigma].sub.0])[[bar.E].sup.t] (r')] dr' (5)

for electric field [[bar.E].sup.t] = -[nabla][mu] and [[bar.E].sup.0] = -[nabla][[mu].sup.0]. In method of moment (MOM) [13,14], domain I is discretized into a total number of M small squares that are centered at [[bar.r].sub.1], [[bar.r].sub.1], ..., [[bar.r].sub.M], and the mth subunit has an effective radius of [a.sub.m]. Pulse basis function and delta test function are used in MOM and the total electric field exerting on subunits [[bar.E].sup.t.sub.p] ([bar.r]m) can be expressed as,

[mathematical expression not reproducible] (6)

where p represents the pth injection of current, and [[bar.E].sup.0.sub.p]([bar.r]m) is the electric field in homogeneous background. [[??].sub.n] relates the current induced in the nth subunit [bar.J]([[bar.r].sub.n]) to the total electric field [[bar.E].sup.t.sub.p]([[bar.r].sub.n]), i.e., [bar.J]([[bar.r].sub.n]) = [[??].sub.n] x [[bar.E].sup.t.sub.p]([[bar.r].sub.n]). According to Eq. (4), [[??].sub.n] can be calculated as [mathematical expression not reproducible] is a two-dimensional identity matrix. The Green's function [[??].sub.D] ([[bar.r].sub.m], [[bar.r].sub.n]) is characterized as [[??].sub.D](r, r') x [bar.d] = -[nabla][[nabla]'G(r, r') x [bar.d]] for a arbitrary dipole [bar.d].

Since the boundary of domain I is irregular, [[??].sub.D]([[bar.r].sub.m], [[bar.r].sub.n]) has no analytical solution in our case. Instead, it can be computed using numerical software as electric field at [[bar.r].sub.m] due to a unit dipole placed at [[bar.r].sub.n] with [sigma] = [partial derivative][mu]/[partial derivative]v on [partial derivative]I. In order to deal with singularities in the integral, [[??].sub.D]([[bar.r].sub.m], [[bar.r].sub.n]) is decomposed into two parts: unbounded-domain Green's function [[??].sub.0] ([[bar.r].sub.m], [[bar.r].sub.n]) that contains singularity and is equal to -1/2[pi][[sigma].sub.0] and the general Green's function [[??].sub.I] ([[bar.r].sub.m], [[bar.r].sub.n]) that contains no singularity and is directly calculated as [mathematical expression not reproducible]. Then, the singularities in the integral can be easily calculated with the analytical solution of [[??].sub.0] ([[bar.r].sub.m], [[bar.r].sub.n]) and the other part of integral is calculated by Gaussian quadrature method [16].

The relationship between [bar.J]([[bar.r].sub.n]) and[ [bar.E].sup.t.sub.p] ([[bar.r].sub.n]), together with Eq. (6) leads to

[mathematical expression not reproducible] (7)

where [[bar.J].sub.p] is a 2M-dimensional vector [mathematical expression not reproducible], in which [J.sup.x.sub.p]([[bar.r].sub.M]) and [J.sup.y.sub.p]([[bar.r].sub.M]) are x and y component of induced current at [[bar.r].sub.M] for the pth injection of current on boundary [partial derivative]I, respectively. The superscript T denotes the transpose operator of a matrix. [[??].sub.D] is a 2M x 2M matrix [mathematical expression not reproducible], in which [[??].sub.xx] is a M x M matrix. [[??].sub.xx] (m, n) and [[??].sub.xy] (m, n) are computed as x component of electric field at [[bar.r].sub.m] due to a unit x-oriented and y-oriented dipole placed at fn, respectively. [[??].sub.yx] and [[??].sub.yy] can also be evaluated in a similar way. Thus, the induced current [[bar.J].sub.p] can be obtained from Eq. (7). According to Eq. (4), the differential voltage on the boundary V([r.sub.[partial derivative]I]) can be calculated as

[mathematical expression not reproducible] (8)

where [r.sub.[partial derivative]I] is the position at the boundary [partial derivative]I. Following the same discretized method in Eq. (6), the differential voltage [[bar.V].sub.p] at the boundary for pth injection is then calculated as

[[bar.V].sub.p] = [[??].sub.[partial derivative]] x [[bar.J].sub.p] (9)

where [[??].sub.[partial derivative]] ([r.sub.[partial derivative]I], r') is characterized as [mathematical expression not reproducible] is a [N.sub.r] x 2M matrix [mathematical expression not reproducible]. [[??].sup.x.sub.[partial derivative]](q, n) and [[??].sup.x.sub.[partial derivative]] (q, n) are calculated as potential on the boundary node [[bar.r].sub.q] due to a unit rc-oriented and y-oriented dipole at [[bar.r].sub.n], respectively. This forward model has been verified by comparing with commercial software (COMSOL), and numerical results calculated by the proposed forward model agree well with the simulation results produced by COMSOL for various examples. In addition, the mesh discretization is important in forward model for EIT problem, and an appropriate mesh is desired in order to obtain accurate internal field [17].

3. INVERSE ALGORITHM

It is well-known that EIT is a highly ill-posed problem, which means that the induced current can't be uniquely determined from Eq. (9). In the traditional SOM, a full singular value decomposition is firstly conducted on [[??].sub.[partial derivative]], in which [mathematical expression not reproducible]. The induced current [bar.J] is mathematically classified into deterministic current Js and ambiguous current [[bar.J].sup.n] with [bar.J] = [[bar.J].sup.s] + [[bar.J].sup.n]. The deterministic current [[bar.J].sup.s] is uniquely determined by the first L singular vectors [9], and ambiguous current [[bar.J].sup.n] is optimized in the subspace [[??].sup.n] spanned by the remaining 2M - L singular value vectors as [[bar.J].sup.n] = [[??].sup.n] x [[bar.[alpha]].sup.n] [9]. However, as mentioned in [11,12], the drawback of the traditional SOM is its overhead computational cost associated with a full SVD of the mapping from the induced current to received signal, especially when the domain of interest is large. Thus, alternative method to construct ambiguous part of induced current is proposed to avoid a full SVD of mapping from induced current to scattered fields [11].

3.1. New Fast Fourier Transform Subspace-Based Optimization Method (NFFT-SOM)

In this paper, we propose a new fast Fourier transform subspace-based optimization method (NFFT-SOM) which avoids a full SVD of [[??].sub.[partial derivative]], and fast Fourier transform can be used to accelerate the computational speed at the same time. In NFFT-SOM, the deterministic current is still computed by the first L singular vectors, whereas the ambiguous current is spanned by a complete Fourier bases [??], in which the 2M x 2M dimensional matrix [??] consists of units [??](m, n) = exp(-j2[pi](m - 1)(n - 1)/(2M)). Since only the first L singular vectors is needed, a thin SVD of [[bar.[??]].sub.[partial derivative]] is sufficient to supply these bases. For a full SVD of [[??].sub.[partial derivative]], the computational complexity is 0(4[N.sub.r][M.sup.2]), whereas the complexity of a thin SVD is only O(2M[N.sub.r.sup.2]) which is much smaller than that of full SVD since M is much larger than [N.sub.r] [11,18]. Thus, the induced current can be written in the form

[[bar.J].sub.p] = [[bar.J].sup.s.sub.p] + [??] x [[bar.[alpha]].sup.n.sub.p] (10)

where [[bar.[alpha]].sup.p.sub.n] is a 2M-dimensional vector to be optimized. [??] x [[bar.[alpha]].sub.p.sup.n] is calculated in fast Fourier transform way with the computational complexity of O(2M[log.sub.2]2M), whereas the complexity of direct multiplication in traditional SOM is O(2M(2M - L)). Since 2M - L is usually much larger than [log.sub.2]2M, the computation cost in NFFT-SOM is much smaller. Using Eq. (10), the residue of Eq. (9) is

[mathematical expression not reproducible] (11)

and residue of Eq. (7) becomes

[mathematical expression not reproducible] (12)

in which [mathematical expression not reproducible]. The objective function is defined as

[mathematical expression not reproducible] (13)

The optimization method used in the contrast source inversion method is adopted, i.e., alternatively updating the coefficients [[bar.[alpha]].sub.p.sup.n] and the polarization tensor [??] [9,10]. The implementation procedures are as follows:

* Step 1) Calculate [[??].sub.[partial derivative]], [[??].sub.D]. Compute the thin SVD of [[??].sub.[partial derivative]], and obtain [[bar.J].sup.s.sub.p] in Eq. (10).

* Step 2) Initial step, n = 0; Give an initial guess of [??] according to back propagation [10], and initialize [[bar.[alpha]].sup.n.sub.p,0] = 0, [[bar.[rho]].sub.p,0] = 0.

* Step 3) n=n+1.

--Step 3.1) Update calculate gradient [[bar.[alpha]].sup.n.sub.p,n]: calculate gradient [mathematical expression not reproducible] evaluate at [[bar.[alpha]].sup.n.sub.p,n-1] and [[??].sub.n-1]. Then determine the Polak-Ribiere-Polyak (PRP) directions [19]: [mathematical expression not reproducible]. Update [mathematical expression not reproducible] is the search length, and the objective function is quadratic in terms of parameter [d.sub.p,n]. [d.sub.p,n] can be easily obtained as done in [10].

--Step 3.2) Update [[??].sub.n]: For the mth subunit, m = 1,2, ..., M, calculate the induced current [([[bar.J].sub.p,n]).sub.m] and the total electric filed [([[bar.E].sup.t.sub.p,n]).sub.m]. Then objective function becomes quadratic in terms of [([[??].sub.n]).sub.m], and the solution is given by [9]:

[mathematical expression not reproducible] (14)

* Step 4) If the termination condition is satisfied, stop iteration. Otherwise, go to step 3).

3.2. Low Frequency Subspace Optimized Method (LF-SOM)

Considering the fact that low-frequency Fourier functions in FFT correspond to those singular functions with large singular values in SVD [12,15], we further replace the deterministic current [[bar.J].sup.s] in NFFT-SOM with low frequency components of current in this section, and denote the method as low frequency subspace optimized method (LF-SOM). In LF-SOM, the deterministic current [[??].sup.L.sub.p] is spanned by the first L low frequency Fourier bases, i.e., [mathematical expression not reproducible], and the coefficient [[alpha]'.sup.L.sub.p] can be calculated in a least square sense from Eq. (9) by

[mathematical expression not reproducible] (15)

The computational complexity of Eq. (15) is O(2M[N.sub.r]L), which is smaller than the computational complexity (O(2M[N.sub.r.sup.2])) of thin SVD in NFFT-SOM since L is usually smaller than [N.sub.r] according to our experience. Thus, the speed_of LF-SOM is faster compared with NFFT-SOM.

Therefore, induced current [[bar.J].sub.p] can be spanned by Fourier bases as

[mathematical expression not reproducible] (16)

where [[bar.[beta]].sup.p.sub.n] is a 2M-dimensional vector to be reconstructed. For LF-SOM, the objective function and the optimization procedures are the same as that of NFFT-SOM except that we express induced current in a different way as it is in Eq. (16).

4. NUMERICAL SIMULATION AND DISCUSSIONS

In this section, numerical examples for both high and low noise cases are considered to verify the proposed methods, and compare the performance of tradition SOM, NFFT-SOM and LF-SOM. As shown in Fig. 2(a), the "two half circles" profile is considered in numerical simulations. Although all numerical results reported in this section are for the "two half circles" profile, the proposed algorithms have been tested on various other profiles, and all drawn conclusions are the same as the one reported in this section.

In these examples, a total number of [N.sub.i] = 10 current excitations is placed at the boundary [[partial derivative].sub.I], where [J.sub.2t-1] ([phi]) = cos(t[phi]), and [J.sub.2t]([phi]) = sin(t[phi]), t = 1,2, ..., 5, and 0 [less than or equal to] [phi] [less than or equal to] 2[pi]. A total number of [N.sub.r] = 40 measurements is conducted on the boundary of [partial derivative]I. A priori information is known that inclusions are within a circle of radius [square root of 2]/2[W.sub.1] centered at the origin with [partial derivative]I = 1, which is referred to as the domain of interest. In discretization, the domain of interest is divided into 1421 subunits with dimensions 0.033 x 0.033. The measured voltage is computed by commercial software COMSOL to avoid inverse crime, and recorded as a matrix [??] with the size of [N.sub.r] x [N.sub.i]. In this examples, additive white Gaussian noise (AWGN) is added to the measured voltages, and is quantified by [mathematical expression not reproducible], where [parallel]*[parallel] denotes Frobenius norm.

The value of L is important in implementing SOM and the proposed algorithms. In previous literatures [9,12], L is usually determined from singular values of the operator [[??].sub.[partial derivative]], and a good candidate of L takes the value where singular values noticeably change the slope in the spectrum [9]. In EIT, as is depicted in Fig. 2(b), it is difficult, to find a good candidate of L directly from the spectrum of [[??].sub.[partial derivative]]. Thus, it is preferred that there is a consecutive range of integer L, instead of a single value, that can be chosen for various cases. It is also noted that there is no need to conduct a full SVD in order to plot the singular values in Fig. 2(b) since only singular values are needed. The computational cost of obtaining only singular values of [[??].sub.[partial derivative]] (0(2M[N.sub.r.sup.2])) is much cheaper than that of a full SVD (0(4[N.sub.r][M.sup.2])) [18].

If the same computer is used, for 60 iterations, it takes about 63 seconds to finish the optimization for SOM whereas it takes only about 15 and 14 seconds for NFFT-SOM and LFSOM, respectively. It suggests that compared with traditional SOM, the proposed methods has great advantage in the speed. To further compare the three methods quantitatively, exact error f is defined as [absolute value of ([A.sub.[sigma]] - [B.sub.[sigma]])]/[absolute value of ([B.sub.[sigma]])], where [A.sub.[sigma]] and [B.sub.[sigma]] are reconstructed conductivity and exact conductivity of the profile, respectively. Fig. 3(d) presents the comparison of exact error with the base of 10 logarithm in the first 300 iterations for the three inversion methods. It is found that, compared with SOM, both LF-SOM and NFFT-SOM can get a smaller exact error for high noise cases, but with more iterations.

It is worthwhile to discuss the reasons of the results in Fig. 3(d). In SOM, the deterministic current is calculated from the spectrum analysis of Eq. (9) without using any optimizations, and ambiguous current is determined by optimizing a noise subspace which is perpendicular to the deterministic current space. Since the voltages measured at the boundary [[bar.V].sub.p] contain white Gaussian noise, the calculated deterministic current differs from the exact one. When the noise level is high, the deterministic current becomes inaccurate and needs to be optimized as well. In the proposed NFFT-SOM and LF-SOM, the space to be optimized is no longer perpendicular to the deterministic current space, and instead the space spanned by complete Fourier bases is used. In the optimization, the deterministic current of NFFT-SOM and LF-SOM is further optimized based on an initial value calculated from Eq. (9). Therefore, compared with SOM, both LF-SOM and NFFT-SOM can get a smaller exact error for high noise cases, but with more iterations.

To study the effects of L on the three inversion methods, with L = 12, the reconstructed conductivity profiles at 60th iteration for SOM, NFFT-SOM, and LF-SOM are presented in Figs. 4(a), 4(b), and 4(c), respectively. It is noted that the reconstructed profile for NFFT-SOM outperforms those for the traditional SOM and LF-SOM. Fig. 4(d) shows the exact error with the base of 10 logarithm for the three inversion methods, and it suggests that SOM and LF-SOM can hardly converges to a satisfying exact error with L = 12. The exact error of SOM, NFFT-SOM, and LF-SOM varying with number of iterations for different values of L are further plotted in Figs. 5(a), 5(b), and 5(c), respectively. It suggests that NFFT-SOM is robust to L variations, and a good reconstructed results can be obtained by NFFT-SOM for 4 [less than or equal to] L [less than or equal to] 12. In comparison, the effects of L on LF-SOM and SOM are dramatic, which makes it difficult to choose an appropriate L in practice.

The effects of L on the three methods are also considered under low noise cases. With the presence of 1% white Gaussian noise, the reconstructed conductivity profiles at 60th iteration for SOM, NFFT-SOM, and LF-SOM with L = 12 are presented in Figs. 6(a), 6(b), and 6(c), respectively. It suggests that, unlike the high noise cases, the reconstruction results are quite satisfying for all the methods with L = 12. The exact error curves of SOM, NFFT-SOM, and LF-SOM for different values of L are also plotted in Figs. 7(a), 7(b), and 7(c), respectively. It is found that, compared with the high noise cases, the effects of L on all the three methods are much smaller, and a good reconstructed results can be obtained with 4 [less than or equal to] L [less than or equal to] 12 for all the inversion methods.

5. CONCLUSIONS

This paper proposes two fast Fourier transform subspace-based optimization methods (NFF-SOM and LF-SOM) to solve the EIT problem with arbitrary boundary. Through numerical simulations and analysis, it suggests that both NFF-SOM and LF-SOM have two advantages over traditional SOM. Firstly, the speed of the proposed methods is much faster than that of traditional SOM since the computational complexity is largely reduced by implementing FFT in the optimization procedures. In NFFT-SOM, the computational speed is also accelerated by avoiding the full singular-value decomposition of the mapping from the induced current to received voltage. In LF-SOM, the computational cost is further reduced by replacing the singular value decomposition with a lower computational cost least square method. Secondly, compared with SOM, both LF-SOM and NFFTSOM can get a smaller exact error for high noise cases, which means that a better reconstructed results can be obtained for the proposed methods. Most importantly, besides the above mentioned two advantages, it is found that NFFT-SOM has another advantage that it is robust to the L variations. For NFFT-SOM, there is a consecutive range of integer L, instead of a single value, that can be chosen in practice for both high and low noise cases. This is an important and encouraging advantage, especially for EIT where it is difficult, to directly find a. good candidate of L from the spectrum of [[??].sub.[partial derivative]]. Additionally, further numerical simulations and analysis also suggest that the drawback of the proposed methods is that, compared with traditional SOM, both of the proposed methods need more iterations in optimization since the noise spaces of them are spanned by complete Fourier bases.

REFERENCES

[1.] Harrach, B., J. K. Seo, and E. J. Woo, "Factorization method and its physical justification in frequency-difference electrical impedance tomography," IEEE Transactions on Medical Imaging, Vol. 29, No. 11, 1918-1926, 2010.

[2.] Goharian, M., M. Soleimani, and G. R. Moran, "A trust region subproblem for 3D electrical impedance tomography inverse problem using experimental data," Progress In Electromagnetics Research, Vol. 94, 19-32, 2009.

[3.] Polydorides, N., "Linearization error in electrical impedance tomography," Progress In Electromagnetics Research, Vol. 93, 323-337, 2009.

[4.] Borcea, L., "Electrical impedance tomography," Inverse Problems, Vol. 18, No. 6, R99-R136, 2002.

[5.] Chaulet, N., S. Arridge, T. Betcke, and D. Holder, "The factorization method for three dimensional electrical impedance tomography," Inverse Problems, Vol. 30, No. 4, 2014.

[6.] Borcea, L., G. A. Gray, and Y. Zhang, "Variationally constrained numerical solution of electrical impedance tomography," Inverse Problems, Vol. 19, No. 5, 1159-1184, 2003.

[7.] Abubakar, A. and P. M. van den Berg, "Nonlinear inversion in electrode logging in a highly deviated formation with invasion using an oblique coordinate system," IEEE Transactions on Geoscience and Remote Sensing, Vol. 38, No. 1, 25-38, 2000.

[8.] Chen, X., "Subspace-based optimization method in electric impedance tomography," Journal of Electromagnetic Waves and Applications, Vol. 23, Nos. 11-12, 1397-1406, 2009.

[9.] Chen, X., "Subspace-based optimization method for solving inverse-scattering problems," IEEE Transactions on Geoscience and Remote Sensing, Vol. 48, No. 1, 42-49, 2010.

[10.] van den Berg, P. M., A. L. van Broekhoven, and A. Abubakar, "Extended contrast source inversion," Inverse Problems, Vol. 15, No. 5, 1325-1344, 1999.

[11.] Zhong, Y., X. Chen, and K. Agarwal, "An improved subspace-based optimization method and its implementation in solving three-dimensional inverse problems," IEEE Transactions on Geoscience and Remote Sensing, Vol. 48, No. 10, 3763-3768, 2010.

[12.] Zhong, Y. and X. Chen, "An FFT twofold subspace-based optimization method for solving electromagnetic inverse scattering problems," IEEE Transactions on Antennas and Propagation, Vol. 59, No. 3, 914-927, 2011.

[13.] Gibson, W. C., The Method of Moments in Electromagnetics, CRC Press, 2014.

[14.] Lakhtakia, A. and G. W. Mulholland, "On two Numerical techniques for light scattering by dielectric agglomerated," Journal of Research of the National Institute of Standards and Technology, Vol. 98, No. 6, 699-716, 1993.

[15.] Hansen, P., M. E. Kilmer, and R. H. Kjeldsen, "Exploiting residual information in the parameter choice for discrete ill-posed problems," Bit Numerical Mathematics, Vol. 46, No. 1, 41-59, 2006.

[16.] Gil, A., J. Segura, and N. M. Temme, Numerical Methods for Special Functions, Society for Industrial and Applied Mathematics, Philadelphia, Pa, 2007.

[17.] Dehghani, H. and M. Soleimani, "Numerical modelling errors in electrical impedance tomography," Physiol. Meas., Vol. 28, No. 7, S45-S55, 2007.

[18.] Stewart, G. W., Matrix Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, 1998.

[19.] Dai, Y. H. and Y. Yuan, "A nonlinear conjugate gradient method with a strong global convergence property," SIAM Journal on Optimization, Vol. 10, No. 1, 177-182, 1999.

Zhun Wei (1), Rui Chen (1), Hongkai Zhao (2), and Xudong Chen (1), *

Received 23 August 2016, Accepted 7 November 2016, Scheduled 13 November 2016

* Corresponding author: Xudong Chen (elechenx@nus.edu.sg).

(1) Department of Electrical and Computer Engineering, National University of Singapore, Singapore 117583, Singapore. (2) Mathematic Department at University of California, Irvine, USA

Caption: Figure 1. A typical schematic of EIT problem with a two dimensional domain consisting of a square with width [W.sub.1] and four half circles with a radius of [W.sub.1]/2, in which [W.sub.1] = 1, and [[sigma].sub.0] = 1. Voltages are measured at a number of [N.sub.r] nodes on the boundary [partial derivative]I which are labeled as dots.

Caption: Figure 2. (a) The exact profile of two half circles: radii of both half circles are 0.3, and centers are located at (-0.35, -0.2) and (0.35, 0.1), respectively, (b) The singular values of the operator [[??].sub.[partial derivative]], where the base 10 logarithm of the singular value is plotted.

Caption: With the presence of 20% white Gaussian noise, the reconstructed conductivity profiles at 60th iteration for SOM, NFFT-SOM, and LF-SOM are presented in Figs. 3(a), 3(b), and 3(c), respectively. It is found that the reconstruction results are quite satisfying for all the three methods when L = 4.

Caption: Figure 3. Reconstructed conductivity profiles at the 60th iterations with L = 4 for (a) traditional SOM (b) NFFT-SOM and (c) LF-SOM, where 20% Gaussian noise is added. (d) Comparison of exact error f in the first 300 iterations for the three inversion methods with L = 4, where the base 10 logarithm of the exact error value is plotted.

Caption: Figure 4. Reconstructed conductivity profiles at the 60th iterations with L = 12 for (a) traditional SOM (b) NFFT-SOM and (c) LF-SOM, where 20% Gaussian noise is added. (d) Comparison of exact error f in the first 300 iterations for the three inversion methods with L = 12, where the base 10 logarithm of the exact error value is plotted.

Caption: Figure 5. Comparison of exact error f in the first 300 iterations for (a) traditional SOM (b) NFFTSOM and (c) LF-SOM with 20% Gaussian noise, where the base 10 logarithm of the exact error value is plotted.

Caption: Figure 6. Reconstructed conductivity profiles at the 60th iterations with L = 12 for (a) traditional SOM (b) NFFT-SOM and (c) LF-SOM, where 1% Gaussian noise is added.

Caption: Figure 7. Comparison of exact error f in the first 300 iterations for (a) traditional SOM (b) NFFT-SOM and (c) LF-SOM with 1% Gaussian noise, where the base 10 logarithm of the exact error value is plotted.

Printer friendly Cite/link Email Feedback | |

Title Annotation: | fast Fourier transform |
---|---|

Author: | Wei, Zhun; Chen, Rui; Zhao, Hongkai; Chen, Xudong |

Publication: | Progress In Electromagnetics Research |

Article Type: | Report |

Geographic Code: | 1USA |

Date: | Nov 1, 2016 |

Words: | 5731 |

Previous Article: | Optimal Illumination Schemes for Near-Field Microwave Imaging. |

Next Article: | The Factorization Method for Virtual Experiments Based Quantitative Inverse Scattering. |

Topics: |