91,99 €
Mehr erfahren.
- Herausgeber: John Wiley & Sons
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Englisch
This book provides researchers and engineers in the imaging field with the skills they need to effectively deal with nonlinear inverse problems associated with different imaging modalities, including impedance imaging, optical tomography, elastography, and electrical source imaging. Focusing on numerically implementable methods, the book bridges the gap between theory and applications, helping readers tackle problems in applied mathematics and engineering. Complete, self-contained coverage includes basic concepts, models, computational methods, numerical simulations, examples, and case studies.
- Provides a step-by-step progressive treatment of topics for ease of understanding.
- Discusses the underlying physical phenomena as well as implementation details of image reconstruction algorithms as prerequisites for finding solutions to non linear inverse problems with practical significance and value.
- Includes end of chapter problems, case studies and examples with solutions throughout the book.
- Companion website will provide further examples and solutions, experimental data sets, open problems, teaching material such as PowerPoint slides and software including MATLAB m files.
Essential reading for Graduate students and researchers in imaging science working across the areas of applied mathematics, biomedical engineering, and electrical engineering and specifically those involved in nonlinear imaging techniques, impedance imaging, optical tomography, elastography, and electrical source imaging
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 517
Veröffentlichungsjahr: 2012
Ähnliche
Table of Contents
Title Page
Copyright
Preface
List of Abbreviations
Chapter 1: Introduction
1.1 Forward Problem
1.2 Inverse Problem
1.3 Issues in Inverse Problem Solving
1.4 Linear, Nonlinear and Linearized Problems
Reference
Chapter 2: Signal and System as Vectors
2.1 Vector Spaces
2.2 Vector Calculus
2.3 Taylor's Expansion
2.4 Linear System of Equations
2.5 Fourier Transform
References
Chapter 3: Basics of Forward Problem
3.1 Understanding a PDE using Images as Examples
3.2 Heat Equation
3.3 Wave Equation
3.4 Laplace and Poisson Equations
References
Further Reading
Chapter 4: Analysis for Inverse Problem
4.1 Examples of Inverse Problems in Medical Imaging
4.2 Basic Analysis
4.3 Variational Problems
4.4 Tikhonov Regularization and Spectral Analysis
4.5 Basics of Real Analysis
References
Further Reading
Chapter 5: Numerical Methods
5.1 Iterative Method for Nonlinear Problem
5.2 Numerical Computation of One-Dimensional Heat Equation
5.3 Numerical Solution of Linear System of Equations
5.4 Finite Difference Method (FDM)
5.5 Finite Element Method (FEM)
References
Further Reading
Chapter 6: CT, MRI and Image Processing Problems
6.1 X-ray Computed Tomography
6.2 Magnetic Resonance Imaging
6.3 Image Restoration
6.4 Segmentation
References
Further Reading
Chapter 7: Electrical Impedance Tomography
7.1 Introduction
7.2 Measurement Method and Data
7.3 Representation of Physical Phenomena
7.4 Forward Problem and Model
7.5 Uniqueness Theory and Direct Reconstruction Method
7.6 Back-Projection Algorithm
7.7 Sensitivity and Sensitivity Matrix
7.8 Inverse Problem of EIT
7.9 Static Imaging
7.10 Time-Difference Imaging
7.11 Frequency-Difference Imaging
References
Chapter 8: Anomaly Estimation and Layer Potential Techniques
8.1 Harmonic Analysis and Potential Theory
8.2 Anomaly Estimation using EIT
8.3 Anomaly Estimation using Planar Probe
References
Further Reading
Chapter 9: Magnetic Resonance Electrical Impedance Tomography
9.1 Data Collection using MRI
9.2 Forward Problem and Model Construction
9.3 Inverse Problem Formulation using B or J
9.4 Inverse Problem Formulation using Bz
9.5 Image Reconstruction Algorithm
9.6 Validation and Interpretation
9.7 Applications
References
Chapter 10: Magnetic Resonance Elastography
10.1 Representation of Physical Phenomena
10.2 Forward Problem and Model
10.3 Inverse Problem in MRE
10.4 Reconstruction Algorithms
10.5 Technical Issues in MRE
References
Further Reading
Index
This edition first published 2013
© 2013, John Wiley & Sons, Ltd
Registered office
John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ, United Kingdom
For details of our global editorial offices, for customer services and for information about how to apply for permission to reuse the copyright material in this book please see our website at www.wiley.com.
The right of the author to be identified as the author of this work has been asserted in accordance with the Copyright, Designs and Patents Act 1988.
All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, except as permitted by the UK Copyright, Designs and Patents Act 1988, without the prior permission of the publisher.
Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic books.
Designations used by companies to distinguish their products are often claimed as trademarks. All brand names and product names used in this book are trade names, service marks, trademarks or registered trademarks of their respective owners. The publisher is not associated with any product or vendor mentioned in this book. This publication is designed to provide accurate and authoritative information in regard to the subject matter covered. It is sold on the understanding that the publisher is not engaged in rendering professional services. If professional advice or other expert assistance is required, the services of a competent professional should be sought.
MATLAB® is a trademark of The MathWorks, Inc. and is used with permission. The MathWorks does not warrant the accuracy of the text or exercises in this book. This book's use or discussion of MATLAB® software or related products does not constitute endorsement or sponsorship by The MathWorks of a particular pedagogical approach or particular use of the MATLAB® software.
Library of Congress Cataloging-in-Publication Data
Seo, Jin Keun.
Nonlinear inverse problems in imaging / Jin Keun Seo and Eung Je Woo.
pages cm
Includes bibliographical references and index.
ISBN 978-0-470-66942-6 (hardback)
1. Image processing–Mathematics. 2. Cross-sectional
imaging–Mathematics. 3. Inverse problems (Differential equations) 4.
Nonlinear theories. I. Woo, E. J. (Eung Je) II. Title.
TA1637.S375 2013
621.36′70151–dc23
2012031509
A catalogue record for this book is available from the British Library.
Print ISBN: 978-0-470-66942-6
Preface
Imaging techniques in science, engineering and medicine have evolved to expand our ability to visualize the internal information in an object such as the human body. Examples may include X-ray computed tomography (CT), magnetic resonance imaging (MRI), ultrasound imaging and positron emission tomography (PET). They provide cross-sectional images of the human body, which are solutions of corresponding inverse problems. Information embedded in such an image depends on the underlying physical principle, which is described in its forward problem. Since each imaging modality has limited viewing capability, there have been numerous research efforts to develop new techniques producing additional contrast information not available from existing methods.
There are such imaging techniques of practical significance, which can be formulated as nonlinear inverse problems. Electrical impedance tomography (EIT), magnetic induction tomography (MIT), diffuse optical tomography (DOT), magnetic resonance electrical impedance tomography (MREIT), magnetic resonance electrical property tomography (MREPT), magnetic resonance elastography (MRE), electrical source imaging and others have been developed and adopted in application areas where new contrast information is in demand. Unlike X-ray CT, MRI and PET, they manifest some nonlinearity, which result in their image reconstruction processes being represented by nonlinear inverse problems.
Visualizing new contrast information on the electrical, optical and mechanical properties of materials inside an object will widen the applications of imaging methods in medicine, biotechnology, non-destructive testing, geophysical exploration, monitoring of industrial processes and other areas. Some are advantageous in terms of non-invasiveness, portability, convenience of use, high temporal resolution, choice of dimensional scale and total cost. Others may offer a higher spatial resolution, sacrificing some of these merits.
Owing primarily to nonlinearity and low sensitivity, in addition to the lack of sufficient information to solve an inverse problem in general, these nonlinear inverse problems share the technical difficulties of ill-posedness, which may result in images with a low spatial resolution. Deep understanding of the underlying physical phenomena as well as the implementation details of image reconstruction algorithms are prerequisites for finding solutions with practical significance and value.
Research outcomes during the past three decades have accumulated enough knowledge and experience that we can deal with these topics in graduate programs of applied mathematics and engineering. This book covers nonlinear inverse problems associated with some of these imaging modalities. It focuses on methods rather than applications. The methods mainly comprise mathematical and numerical tools to solve the problems. Instrumentation will be treated only in enough detail to describe practical limitations imposed by measurement methods.
Readers will acquire the diverse knowledge and skills needed to deal effectively with nonlinear inverse problems in imaging by following the steps below.
This book is for advanced graduate courses in applied mathematics and engineering. Prerequisites for students with a mathematical background are vector calculus, linear algebra, partial differential equations and numerical analysis. For students with an engineering background, we recommend taking linear algebra, numerical analysis, electromagnetism, signal and system and also preferably instrumentation.
Lecture notes, sample codes, experimental data and other teaching material are available at http://mimaging.yonsei.ac.kr/NIPI.
List of Abbreviations
Notations for Domains and Vector Spaces
Chapter 1
Introduction
We consider a physical system where variables and parameters interact in a domain of interest. Variables are physical quantities that are observable or measurable, and their values change with position and time to form signals. We may express system structures and properties as parameters, which may also change with position and time. For a given system, we understand its dynamics based on underlying physical principles describing the interactions among the variables and parameters. We adopt mathematical tools to express the interactions in a manageable way.
A physical excitation to the system is an input and its response is an output. The response is always accompanied by some form of energy transfer. The input can be applied to the system externally or internally. For the internal input, we may also use the term “source”. Observations or measurements can be done at the outside, on the boundary and also on the inside of the system. For the simplicity of descriptions, we will consider boundary measurements as external measurements. Using the concept of the generalized system, we will introduce the forward and inverse problems of a physical system.
1.1 Forward Problem
The generalized system H in Figure 1.1 has a system parameter p, input x and output y. We first need to understand how they are entangled in the system by understanding underlying physical principles. A mathematical representation of the system dynamics is the forward problem formulation. We formulate a forward problem of the system in Figure 1.1 as
1.1
where H is a nonlinear or linear function of p and x. We should note that the expression in (1.1) may not be feasible in some cases where the relation between the input and output can only be described implicitly.
Figure 1.1 Forward problem for a system with parameter p, input x and output y
To treat the problem in a computationally manageable way, we should choose core variables and parameters of most useful and meaningful information to quantify their interrelations. The expression in (1.1), therefore, could be an approximation of complicated interactions among variables and parameters. In practice, we may not be able to control the input precisely because of technical limitations, and the measured output will always be contaminated by noise. Solving a forward problem is to find the output from a given input and system parameter. Evaluation of (1.1) suffices for its solution.
A simple example is a sound recording and reproduction system including a microphone, amplifier and speaker. An input sound wave enters the system through the microphone, goes through the amplifier and exits the system as an output sound wave through the speaker. The system characteristics are determined by the electrical and mechanical properties of the system components, including the gain or amplitude amplification factor, phase change, frequency bandwidth, power and so on.
In most physical systems, inputs are mixed within the system to produce outputs. The mixing process is accompanied by smearing of information embedded in the inputs. Distinct features of the inputs may disappear in the outputs, and the effects of the system parameters may spread out in the observed outputs.
1.2 Inverse Problem
For a given forward problem, we may consider two types of related inverse problems as in Figure 1.2. The first type is to find the input from a measured output and identified system parameter. The second is to find the system parameter from a designed input and measured output. We symbolically express these two cases as follows:
1.5
and
1.6
where and are nonlinear or linear functions. We may need to design multiple inputs carefully to get multiple input–output pairs with enough information to solve the inverse problems.
Figure 1.2 Two different inverse problems for a system with parameter p, input x and output y
In general, most inverse problems are complicated, since the dynamics among inputs, outputs and system parameters are attributed to complex, possibly nonlinear, physical phenomena. Within a given measurement condition, multiple inputs may result in the same output for given system parameters. Similarly, different system parameters may produce the same input–output relation. The inversion process, therefore, suffers from the uncertainty that originates from the mixing process of the corresponding forward problem.
To seek a solution of an inverse problem, we first need to understand how those factors are entangled in the system by understanding the underlying physical principles. Extracting core variables of most useful information, we should properly formulate a forward problem to quantify their interrelations. This is the reason why we should investigate the associated forward problem before trying to solve the inverse problem.
1.3 Issues in Inverse Problem Solving
In solving an inverse problem, we should consider several factors. First, we have to make sure that there exists at least one solution. This is the issue of the existence of a solution, which must be checked in the formulation of the inverse problem. In practice, it may not be a serious question, since the existence is obvious as long as the system deals with physically existing or observable quantities. Second is the uniqueness of a solution. This is a more serious issue in both theoretical and practical aspects, and finding a unique solution of an inverse problem requires careful analyses of the corresponding forward and inverse problems. If a solution is not unique, we must check its optimality in terms of its physical meaning and practical usefulness.
To formulate a manageable problem dealing with key information, we often go through a simplification process and sacrifice some physical details. Mathematical formulations of the forward and inverse problems, therefore, suffer from modeling errors. In practice, measured data always include noise and artifacts. To acquire a quantitative numerical solution of the inverse problem, we deal with discretized versions of the forward and inverse problems. The discretization process may add noise and artifacts. We must carefully investigate the effects of these practical restrictions in the context of the existence and uniqueness of a solution.
We introduce the concept of well-posedness as proposed by Hadamard (1902). When we construct a mathematical model of a system to transform the associated physical phenomena into a collection of mathematical expressions and data, we should consider the following three properties.
In the sense of Hadamard, a problem is well-posed when it meets the above requirements of existence, uniqueness and continuity. If these requirements are not met, the problem is ill-posed.
If we can properly formulate the forward problem of a physical system and also its inverse problem, we can safely assume that a solution exists. Non-uniqueness often becomes a practically important issue, since it is closely related with the inherent mixing process of the forward problem. Once the inputs are mixed, uniquely sorting out some inputs and system parameters may not be feasible. The mixing process may also cause sensitivity problems. When the sensitivity of a certain output to the inputs and/or system parameters is low, small changes in the inputs or system parameters may result in small and possibly discontinuous changes in the output, with measurement errors. The inversion process in general includes a step where the measured output values are divided by sensitivity factors. If we divide small measured values, including errors, by a small sensitivity factor, we may amplify the errors in the results. The effects of the amplified errors may easily dominate the inversion process and result in useless solutions, which do not comply with the continuity requirement.
Considering that mixing processes are embedded in most forward problems and that the related inverse problems are ill-posed in many cases, we need to devise effective methods to deal with such difficulties. One may incorporate as much a priori information as possible in the inversion process. Preprocessing methods such as denoising and feature extraction can be employed. One may also need to implement some regularization techniques to find a compromise between the robustness of an inversion method and the accuracy or sharpness of its solution.
1.4 Linear, Nonlinear and Linearized Problems
Linearity is one of the most desirable features in solving an inverse problem. We should carefully check whether the forward and inverse problems are linear or not. If not, we may try to approximately linearize the problems in some cases. We first define the linearity of the forward problem in Figure 1.1 as follows.
1.10
for any constants K1 and K2.
For the inverse problems in Figure 1.2, we may similarly define the linearity for two functions and . Note that we should separately check the linearity of the three functions H, and . Any problem, either forward or inverse, is nonlinear if it does not satisfy both of the homogeneity and additivity requirements.
1.11
Figure 1.3 Illustration of a linearization process
Problems either forward or inverse can be linear or nonlinear depending on the underlying physical principles. Proper formulations of forward and inverse problems using mathematical tools are essential steps before any attempt to seek solution methods. In the early chapters of the book, we study mathematical backgrounds to deal with linear and nonlinear problems. In the later chapters, we will introduce several imaging modalities.
Reference
Hadamard J 1902 Sur les problèmes aux dérivées partielles et leur signification physique. Bull. Univ. Princeton, 13, 49–52.
Chapter 2
Signal and System as Vectors
To solve forward and inverse problems, we need mathematical tools to formulate them. Since it is convenient to use vectors to represent multiple system parameters, variables, inputs (or excitations) and outputs (or measurements), we first study vector spaces. Then, we introduce vector calculus to express interrelations among them based on the underlying physical principles. To solve a nonlinear inverse problem, we often linearize an associated forward problem to utilize the numerous mathematical tools of the linear system. After introducing such an approximation method, we review mathematical techniques to deal with a linear system of equations and linear transformations.
2.1 Vector Spaces
2.1.1 Vector Space and Subspace
A subset W of a vector space V over F is a subspace of V if and only if au + v ∈ W for all and for all u, v ∈ W. The subspace W itself is a vector space.
The span G is the smallest subspace of V containing G. For example, if , then span{(1, 2, 3), (1, − 2, 0)} is the plane .
Otherwise, u1, …, unare linearly dependent.
Figure 2.1 Linearly independent and dependent vectors
2.1.2 Basis, Norm and Inner Product
If is a basis for W, then any vector v ∈ W can be expressed uniquely as . If G′ is another basis of W, then G′ contains exactly the same number n of elements.
To quantify a measure of similarity or dissimilarity among vectors, we need to define the magnitude of a vector and the distance between vectors. We use the norm ||u|| of a vector u to define such a magnitude. In the area of topology, the metric is also used for defining a distance. To distinguish different vectors in a vector space, we define a measure of distance or metric between two vectors u and v as the norm ||u − v||. The norm must satisfy the following three rules.
Here, the notation stands for “for all” and iff stands for “if and only if”.
2.1
In addition to the distance between vectors, it is desirable to establish the concept of an angle between them. This requires the definition of an inner product.
For a real inner product space V, the inner product provides angle information between two vectors u and v. We denote the angle θ between u and v as
We interpret the angle as follows.
2.1.3 Hilbert Space
When we analyze a vector f in a vector space V having a basis , we wish to represent f as
Computation of the coefficients aj could be very laborious when the vector space V is not equipped with an inner product and is not an orthonomal set. A Hilbert space is a closed vector space equipped with an inner product.
For u, v, w ∈ H, a Hilbert space, we have the following properties.
For the proof of the above theorem, see Rudin (1970). Let S be a closed subspace of a Hilbert space H. We define the orthogonal complement S⊥ of S as
According to the projection theorem, we can define a projection map PS:H → S such that the value PS(u) satisfies
or
From the Pythagorean theorem,
Figure 2.3 illustrate the projection of a vector u onto a subspace S.
Figure 2.3 Illustration of a projection of a vector u onto a subspace S
2.2 Vector Calculus
Based on the underlying physical principles, we need to express interrelations among system parameters, variables, excitations and measurements. A scalar-valued function f(x) defined in represents a numerical quantity at a point . Examples may include temperature, voltage, pressure, altitude and so on. A vector-valued function F(x) is a vector quantity at . It represents a vector field such as displacement, velocity, force, electric field intensity, magnetic flux density and so on. We now review the vector calculus of gradient, divergence and curl to handle basic dynamics among variables and parameters.
2.2.1 Gradient
Let . For a given unit vector , the directional derivative of f at x in the direction b is denoted by ∂bf(x). It represents the rate of increase in f at x in the direction of b:
2.2.2 Divergence
The divergence of F(r) at a point r, written as div F, is the net outward flux of F per unit volume of a ball centered at r as the ball shrinks to zero:
where dS is the surface element, Br(r) is the ball with radius r and center r, and ∂B is the boundary of B, which is a sphere.
2.2.3 Curl
If F represents an electric field intensity, the circulation will be an electromotive force around the path C.
The curl of a vector field F, denoted by curl F, is a vector whose magnitude is the maximum net circulation of F per unit area as the area shrinks to zero and whose direction is the normal direction of the area when the area is oriented to make the net circulation maximum. We can define the b-directional net circulation of F at r precisely by
where is the disk centered at r with radius r and normal to d. Then, curl F is its maximum net circulation:
2.2.4 Curve
A curve in and is represented, respectively, by
and
The curve is said to be regular if r′(t) ≠ 0 for all t. The arc lengths(t) of between r(t0) to r(t1) is given by
The unit tangent vector T of the curve is given by
The unit normal vector n of the curve is determined by
where κ is the curvature given by
2.2.5 Curvature
Now, consider a curve given implicitly by the level set of :
Then, the normal and tangent vectors to the level curve are
The curvature κ is
imply
Hence,
The curvature κ at a given point is the inverse of the radius of a disk that best fits the curve at that point.
Next, we consider a space curve in represented by
Then
The curvature κ and torsion τ are computed by
where [ ] stands for the triple scalar product. If the relation between the moving coordinate system {T, N, B} and the fixed coordinates {x, y, z} is
then
We consider a regular surface :
Note that . The condition corresponding to the regularity of a space curve is that
or
If |ru × rv| ≠ 0, the tangent vectors ru and rv generate a tangent plane that is spanned by ru and rv. The surface normal vector is expressed as
and the unit normal vector n is
2.3 Taylor's Expansion
The dynamics among system parameters, variables, excitations and measurements are often expressed as complicated nonlinear functions. In a nonlinear inverse problem, we may adopt a linearization approach in its solution-seeking process. Depending on the given problem, one may need to adopt a specific linearization process. In this section, we review Taylor's expansion as a tool to perform such an approximation.
Taylor polynomials are often used to approximate a complicated function. Taylor's expansion for about x is
2.2
where O(|h|m+1) is the remainder term containing the (m + 1)th order of h. Precisely, the remainder term is
This expansion leads to numerical differential formulas of f in various ways, for example:
It starts with an initial guess x0 and generates a sequence {xn} by the formula
It may not converge to a solution in general. The convergence issue will be discussed later.
We turn our attention to the second derivative f′′(x). By Taylor's expansion, we approximate f′′(x) by
The sign of f′′(x) gives local information about f for a sufficiently small positive h:
We consider a multi-dimensional case . The following fourth-order Taylor's theorem in n variables will be used later.
This leads to
If D2f(x) is a positive definite matrix, then, for a sufficiently small r,
which leads to the sub-MVP
Similarly, the super-MVP can be derived for a negative definite matrix D2f(x).
2.4 Linear System of Equations
We consider a linear system of equations including system parameters, variables, excitations and measurements. We may derive it directly from a linear physical system or through a linearization of a nonlinear system. Once we express a forward problem as a linear transform of inputs or system parameters to measured outputs, we can adopt numerous linear methods to seek solutions of the associated inverse problem. For the details of linear system of equations, please refer to Strang (2005, 2007).
2.4.1 Linear System and Transform
2.3
Using two vectors , and a matrix , we can express the linear system as
2.4
or
Figure 2.4 Linear system with multiple inputs and multiple outputs
In most problems, the output vector y consists of measured data. If the input vector x includes external excitations or internal sources, the matrix is derived from the system transfer function or gain determined by the system structure and parameters. When the vector x contains system parameters, the linear system of equations in (2.4) is formulated subject to certain external excitations or internal sources, information about which is embedded in the matrix .
Figure 2.5 Three cases of linear systems of equations
2.4.2 Vector Space of Matrix
We denote by a set of linear transforms from to , that is, is the vector space consisting of m × n matrices
We call an m × 1 matrix a column vector and an 1 × n matrix a row vector. For the matrix A, we denote its ith row vector as
and its jth column vector as
For two vectors , we define their inner product by
and define the outer product as
For and , we consider a linear transform or a linear system of equations:
We can understand it as either
2.5
or
2.6
Figure 2.6 Two different representations of a linear system of equations y = Ax
We now summarize the null space, range and rank of a matrix before we describe how to solve for x.
From (2.5) and (2.6), we have
2.7
and
2.8
If , the following hold:
We also note that
2.4.3 Least-Squares Solution
If ATA is invertible, then
and the projection matrix on R(A) can be expressed as
2.9
that is, x† is orthogonal to N(A).
Figure 2.7 Least-squares and minimum-norm solutions of y = Ax
2.4.4 Singular Value Decomposition (SVD)
Let A be an m × n matrix. Then ATA can be decomposed into
2.10
and
2.11
2.12
where
2.13
This has the very useful property of splitting any matrix A into rank-one pieces ordered by their sizes:
2.14
Figure 2.8 shows two graphical representations of the SVD. If σt+1, …, σr are negligibly small, we may approximate by the truncated SVD as
2.15
with t < r.
Figure 2.8 Graphical representations of the SVD,
Figure 2.9 Interpretation of
2.4.5 Pseudo-inverse
The pseudo-inverse of A is
2.16
Here, in the pseudo-inverse Σ† of the diagonal matrix Σ, each σ ≠ 0 is replaced by 1/σ.
Since
2.17
the products AA† and A†A can be viewed as projection matrices:
2.18
2.19
Hence, x† satisfies the normal equation
2.20
2.5 Fourier Transform
Joseph Fourier (1768–1830) introduced the Fourier series to solve the heat equation. Since then, Fourier analysis has been widely used in many branches of science and engineering. It decomposes a general function f(x) into a linear combination of basic harmonics, sines or cosines, that is easier to analyze. For details of the theory, refer to Bracewell (1999) and Gasquet and Witomski (1998). We introduce the Fourier transform as a linear transform since it is also widely used in the inverse problem area.
2.5.1 Series Expansion
Assume that a set {ϕ0, ϕ1, …} is an orthonormal basis of a Hilbert space H, that is:
If we denote by Pn the projection map from H to Vn, then
If we denote , then . By the Pythagorean theorem, we have
and we obtain the Bessel inequality
2.21
By the Bessel inequality, the series
Moreover,
or
Hence,
This gives us the following series expansion:
2.5.2 Fourier Transform
For each p with 1 ≤ p < ∞, we denote the class of measurable functions f on such that by :
where the Lp-norm of f is
Let us summarize the Fourier transform pairs of some important functions.
Scaling property:
Shifting property:
Dirac delta function:
Dirac comb:
Indicator function of the interval [a, b], denoted by χ
[a, b]
(
x
), is
We have
The Fourier transform of Gaussian function is given by
Derivative: if , then integrating by parts leads to
The following Fourier inversion provides that f can be recovered from its Fourier transform .
2.22
Indeed, the Fourier inversion formula holds for general because is dense in and . We omit the proof because it requires some time-consuming arguments of Lebesgue measure theory and some limiting process in L2. For a rigorous proof, please refer to Gasquet and Witomski (1998).
The following Poisson summation formula indicates that the T-periodic summation of f is expressed as discrete samples of its Fourier transform with the sampling distance 1/T.
2.24
2.25
2.5.3 Discrete Fourier Transform (DFT)
Assume that f is a continuous signal such that
Choose a number N so that
Its Fourier transform for xi ∈ [ − Ξ/2, Ξ/2] is expressed approximately by
In particular, we have
Since
we have the following approximations:
From the above approximations, we can define the discrete Fourier transform.
The DFT matrix has the following interesting properties.
Let
a
j−1
be the
j
th row (or column) of the Fourier transform matrix . Then,
The column vectors
a
0
, …,
a
N−1
are eigenvectors of the following matrix corresponding to the Laplace operator:
Hence, {
a
0
, …,
a
N−1
} forms an orthogonal basis over the
N
-dimensional vector space and
If and are the DFTs of
f
and
g
, then we have Parseval's identity:
2.5.4 Fast Fourier Transform (FFT)
From the definition of the DFT, we have
Since and , the (M + j, 2k)-component of the matrix is
and the (M + j, 2k − 1)-component of the matrix is
The FFT is based on the following key identity:
2.26
where is the N × N DFT matrix defined in the previous section and
2.5.5 Two-Dimensional Fourier Transform
The one-dimensional definition of the Fourier transform can be extended to higher dimensions. The Fourier transform of a two-dimensional function ρ(x, y), denoted by S(kx, ky), is defined by
We can generalize all the results in the one-dimensional Fourier transform to the two-dimensional case because the two-dimensional Fourier transform can be expressed as two one-dimensional Fourier transforms along x and y variables:
If ρ(x, y) and S(kx, ky) are a Fourier transform pair, we have the following properties.
Scaling property:
Shifting property:
Modulation:
Fourier inversion formula:
Sampling theorem: if supp(S) ⊂ [ − B, B] × [ − B, B], then the original data ρ(x, y) can be reconstructed by the interpolation formula
References
Bracewell R 1999 The Fourier Transform and Its Applications, 3rd edn. McGraw-Hill, New York.
Gasquet C and Witomski P 1998 Fourier Analysis and Applications: Filtering, Numerical Computation, Wavelets. Springer, New York.
Rudin W 1970 Real and Complex Analysis. McGraw-Hill, New York.
Strang G 2005 Linear Algebra and Its Applications, 4th edn. Thomson Learning, London.
Strang G 2007 Computational Science and Engineering. Wellesley-Cambridge, Wellesley, MA.
