Mathematical Methods and Algorithms for Signal Processing

Paperback | August 4, 1999

byTodd K. Moon, Wynn C. Stirling

not yet rated|write a review

Mathematical Methods and Algorithms for Signal Processing tackles the challenge of providing readers and practitioners with the broad tools of mathematics employed in modern signal processing. Building from an assumed background in signals and stochastic processes, the book provides a solid foundation in analysis, linear algebra, optimization, and statistical signal processing. Interesting modern topics not available in many other signal processing books; such as the EM algorithm, blind source operation, projection on convex sets, etc., in addition to many more conventional topics such as spectrum estimation, adaptive filtering, etc. For those interested in signal processing.

Pricing and Purchase Info

$234.73

In stock online
Ships free on orders over $25
HURRY, ONLY 1 LEFT!

From Our Editors

It requires a lot of mathematical knowledge for modern signal processing to work. Todd Moon and Wynn Sterling provide readers with this knowledge in Mathematical Methods and Algorithms for Signal Processing. The authors focus on such topics as EM algorithm, blind source operation, and projection on convex sets, spectrum estimation ...

From the Publisher

Mathematical Methods and Algorithms for Signal Processing tackles the challenge of providing readers and practitioners with the broad tools of mathematics employed in modern signal processing. Building from an assumed background in signals and stochastic processes, the book provides a solid foundation in analysis, linear algebra, op...

From the Jacket

Mathematical Methods and Algorithms for Signal Processing tackles the challenge of providing readers and practitioners with the broad tools of mathematics employed in modern signal processing. Building from an assumed background in signals and stochastic processes, the book provides a solid foundation in analysis, linear algebra, opti...

TODD K. MOON is currently with the Electrical and Computer Engineering department at Utah State University, where he has taught widely in the area of signals and systems, including signal processing, communications, controls, and information theory. His research interests have included signal separation, spread-spectrum communicat...

other books by Todd K. Moon

Dragonwriter: A Tribute to Anne McCaffrey and Pern
Dragonwriter: A Tribute to Anne McCaffrey and Pern

Kobo ebook|Aug 6 2013

$13.89 online$17.99list price(save 22%)
Error Correction Coding: Mathematical Methods and Algorithms
Error Correction Coding: Mathematical Methods and Algor...

Hardcover|Jun 6 2005

$246.18 online$251.99list price
Format:PaperbackDimensions:937 pages, 9.9 × 8 × 2 inPublished:August 4, 1999Publisher:Pearson EducationLanguage:English

The following ISBNs are associated with this title:

ISBN - 10:0201361868

ISBN - 13:9780201361865

Customer Reviews of Mathematical Methods and Algorithms for Signal Processing

Reviews

Extra Content

From the Author

Preface Rationale The purpose of this book is to bridge the gap between introductory signal processing classes and the mathematics prevalent in contemporary signal processing research and practice, by providing a unified applied treatment of fundamental mathematics, seasoned with demonstrations using MATLAB®. This book is intended not only for current students of signal processing, but also for practicing engineers who must be able to access the signal processing research literature, and for researchers looking for a particular result to apply. It is thus intended both as a textbook and as a reference. Both the theory and the practice of signal processing contribute to and draw from a variety of disciplines: controls, communications, system identification, information theory, artificial intelligence, spectroscopy, pattern recognition, tomography, image analysis, and data acquisition, among others. To fulfill its role in these diverse areas, signal processing employs a variety of mathematical tools, including transform theory, probability, optimization, detection theory, estimation theory, numerical analysis, linear algebra, functional analysis, and many others. The practitioner of signal processing— the "signal processor"— may use several of these tools in the solution of a problem; for example, setting up a signal reconstruction algorithm, and then optimizing the parameters of the algorithm for optimum performance. Practicing signal processors must have knowledge of both the theory and the implementation of the mathematics: how and why it works, and how to make the computer do it. The breadth of mathematics employed in signal processing, coupled with the opportunity to apply that math to problems of engineering interest, makes the field both interesting and rewarding. The mathematical aspects of signal processing also introduce some of its major challenges: how is a student or engineering practitioner to become versed in such a variety of mathematical techniques while still keeping an eye toward applications? Introductory texts on signal processing tend to focus heavily on transform techniques and filterbased applications. While this is an essential part of the training of a signal processor, it is only the tip of the iceberg of material required by a practicing engineer. On the other hand, more advanced texts typically develop mathematical tools that are specific to a narrow aspect of signal processing, while perhaps missing connections between these ideas and related areas of research. Neither of these approaches provides sufficient background to read and understand broadly in the signal processing research literature, nor do they equip the student with many signal processing tools. The signal processing literature has moved steadily toward increasing sophistication: applications of the singular value decomposition (SVD) and wavelet transforms abound; everyone knows something about these by now, or should! Part of this move toward sophistication is fueled by computer capabilities, since computations that formerly required considerable effort and understanding are now embodied in convenient mathematical packages. A naive view might held that this automation threatens the expertise of the engineer: Why hire a specialist to do what anyone can do in ten minutes with a MATLAB toolbox? Viewed more positively, the power of the computer provides a variety of new opportunities, as engineers are freed from computational drudgery to pursue new applications. Computer software provides platforms upon which innovative ideas may be developed with ever greater ease. Taking advantage of this new freedom to develop useful concepts will require a solid understanding of mathematics, both to appreciate what is in the toolboxes and to extend beyond their limits. This book is intended to provide a foundation in the requisite mathematics. We assume that students using this text have had a course in traditional transformbased digital signal processing at the senior or firstyear graduate level, and a traditional course in stochastic processes. Though basic concepts in these areas are reviewed, this book does not supplant the more focused coverage that these courses provide. Features Vectorspace geometry, which puts leastsquares and minimum meansquares in the same framework, and the concept of signals as vectors in an appropriate vector space, are both emphasized. This vectorspace approach provides a natural framework for topics such as wavelet transforms and digital communications, as well as the traditional topics of optimum prediction, filtering, and estimation. In this context, the more general notion of metric spaces is introduced, with a discussion of signal norms. The linear algebra used in signal processing is thoroughly described, both in concept and in numerical implementation. While software libraries are commonly available to perform linear algebra computations, we feel that the numerical techniques presented in this book exercise student intuition regarding the geometry of vector spaces, and build understanding of the issues that must be addressed in practical problems. The presentation includes a thorough discussion of eigenbased methods of computation, including eigenfilters, MUSIC, and ESPRIT; there is also a chapter devoted to the properties and applications of the SVD. Toeplitz matrices, which appear throughout the signal processing literature, are treated both from a numerical point of view— as an example of recursive algorithms— and in conjunction with the latticefiltering interpretation. The matrices in linear algebra are viewed as operators; thus, the important concept of an operator is introduced. Associated notions, such as the range, nullspace, and norm of an operator are also presented. While a full coverage of operator theory is not provided, there is a strong foundation that can serve to build insight into other operators. In addition to linear algebraic concepts, there is a discussion of computation . Algorithms are presented for computing the common factorizations, eigenvalues, eigenvectors, SVDs, and many other problems, with some numerical consideration for implementation. Not all of this material is necessarily intended for classroom use in a conventional signal processing course— there will not be sufficient time in most cases. Nonetheless, it provides an important perspective to prospective practitioners, and a starting point for implementations on other platforms. Instructors may choose to emphasize certain numeric concepts because they highlight particular topics, such as the geometry of vector spaces. The CauchySchwartz inequality is used in a variety of places as an optimizing principle. Recursive least square and least mean square adaptive filters are presented as natural outgrowths of more fundamental concepts: matrix inverse updates and steepest descent. Neural networks and blind source separation are also presented as applications of steepest descent. Several chapters are devoted to iterative and recursive methods. Though iterative methods are of great theoretical and practical significance, no other signal processing textbook provides a similar breadth of coverage. Methods presented include projection on convex sets, composite mapping, the EM algorithm, conjugate gradient, and methods of matrix inverse computation using iterative methods. Detection and estimation are presented with several applications, including spectrum estimation, phase estimation, and multidimensional digital communications. Optimization is a key concept in signal processing, and examples of optimization, both unconstrained and constrained, appear throughout the text. Both a theoretical justification for Lagrange multiplier methods and a physical interpretation are explicitly spelled out in a chapter on optimization. A separate chapter discusses linear programming and its applications. Optimizations on graphs (shortestpath problems) are also examined, with a variety of applications in communications and signal processing. The EM algorithm as presented here is the only treatment in a signal processing textbook that we are aware of. This powerful algorithm is used for many otherwise intractable estimation and learning problems. In general, the presentation is at a more formal level than in many recent digital signal processing texts, following a "theorem/proof" format throughout. At the same time, it is less formal than many math texts covering the same material. In this, we have attempted to help the student become comfortable with rigorous thinking, without overwhelming them with technicalities. (A brief review of methods of proofs is also provided to help students develop a sense of how to approach the proofs.) Ultimately, the aim of this book is to teach its reader how to think about problems. To this end, some material is covered more than once, from different perspectives (e.g., with more than one proof for certain results), to demonstrate that there is usually more than one way to approach a problem. Throughout the text, the intent has been to explain the "what" and the "why" of the mathematics, but not become overwrought with some of the more technical mathematical preoccupations. In this regard, the book does not always thoroughly treat questions of "how well:" (For example, in our coverage of linear numerical analysis, the perturbation analysis that characterizes much of the research literature has been largely ignored. Nor do issues of computational complexity form a major consideration.) To visualize this approach, consider an automotive analogy: Our intent is to "get under the hood" to a sufficient degree that it is clear why the engine runs and what it can do, but not to provide a molecularlevel description of the metallurgical structure of the piston rings. Such finegrained investigations might be a necessary part of research into finetuning the performance of the engine— or the algorithm— but are not appropriate for a student learning the basic mechanics. Throughout the chapters and in the appendices, there is a great deal of material that will be of reference value to practicing engineers. For example, there are facts regarding matrix rank, the invertibility of matrices, properties of Hermitian matrices, properties of structured matrices preserved under multiplication, and an extensive table of gradients. Not all of this material is necessarily intended for classroom use, but is provided to enhance the value of the book as a reference. Nevertheless, where such reference material is provided, it is usually accompanied by an explanation of its derivation, so that related facts may often be derived by the reader. Though this book does not provide the final word in any research area, for many research paths it will at least provide a good first step. The contents of the book have been selected according to a variety of criteria. The primary criterion was whether material has been of use or interest to us in our research; questions from students and the need to find clear explanations, exceptional writings found in other textbooks and papers, have also been determining factors. Some of the material has been included for its practicality, and some for its outstanding beauty. In the ongoing debate regarding the teaching of mathematics to engineers, recent proposals suggest using "just in time" mathematics: provide the mathematical concept only when the need for it arises in the solution of an engineering problem. This approach has arisen as a response to the charge that mathematical pedagogy has been motivated by a "just in case" approach: we’ll teach you all this stuff just in case you ever happen to need it. In reality, these approaches are neither fully desirable nor achievable, potentially lacking rigor and depth on the one hand, and motivation and insight on the other. As an alternative, we hope that the presentation in this book is "justified," so that the level of mathematics is suited to its application, and the applications are seen in conjunction with the concepts. Programs The algorithms found throughout the text, written in MATLAB, allow the reader to see how the concepts developed in the text might be implemented, allow easy exploration of the concepts (and, sometimes, of the limitations of the theory), and provide a useful library of core functionality for a variety of signal processing research applications. With thorough theoretical and applied discussion surrounding each algorithm, this is not simply a book of recipes; raw ingredients are provided to stir up some interesting stews! In most cases, the algorithms themselves have not been presented in the text. Instead, an icon is used to indicate that the text an algorithm is to be found on the included CDROM (in some instances the algorithm consists of several related files). In the interest of brevity, typechecking of arguments has not been incorporated into the functions. Otherwise, we believe that all of the code provided works, at least to produce the examples described in the book. Of course, information regarding program bugs, fixes, and improvements is always welcome. Nevertheless, we are required to make the standard disclaimer of warranty which can be found in its entirety on pg. 946. Readers are free to use the programs or any derivatives of them for any scientific purpose, with appropriate citation of this book. Updated versions of the programs, and other information, can be found at the following website: www.prenhafl.com/moon Exercises The exercises found at the end of each chapter are loosely divided into sections, but it may be necessary to draw from material in other sections (or even other chapters) in order to solve some of the problems. There are relatively few merely numerical exercises. With the computer performing automated computations in many cases, simply running numbers doesn’t provide an informative exercise. Readers are encouraged, of course, to play around with the algorithms to get a sense of how they work. Insight frequently can be gained on some difficult problems by trying several related numerical approaches. The intent of the exercises is to engage the reader in the development of the theory in the book. Many of the exercises require derivations of results presented in the chapters, or proofs of some of the lemmas and theorems; other exercises require programming an extension or modification of a MATLAB algorithm presented in the chapter; and still others lead the student through a stepbystep process leading to some significant result (for example, a derivation of Gaussian quadrature or linear prediction theory, extension of inverses of Toeplitz matrices, or another derivation of the Kalman filter). As students work through these exercises, they should develop skill in organizing their thinking (which can help them to approach other problems) as well as acquire background in a variety of important topics. Most of the exercises require a fair degree of insight and effort to solve— students should plan on being challenged. Wherever possible, students are encouraged to interact with the computer for computational assistance, insight, and feedback. A solutions manual is available to instructors who have adopted the book for classroom use. Not only are solutions provided but, in many cases, MATLAB and MATHEMATICA&3153; code is also provided, indicating how a problem might be approached using the computer. Solutions to selected exercises can also be found on the CDROM. Courses of study There is clearly more information in this book than can be covered in a single semester, or even a full year. Several different courses of study could be devised based on this material, giving instructors the opportunity to choose the material suitable for the needs and development of their students. For example, depending on the focus of the class, instructors might choose to skip completely the numerical aspects of algorithms or, conversely, make them a focus of the course. Several possible course options are described in the following list. In a straightforward overview, the material in the first two parts is regarded as the foundation upon which the major concepts of signal processing are built. The first part provides a review of signal models and representations (e.g., difference equations, transfer functions, statespace form), and introduces several important signal processing problems, such as spectrum estimation and system identification. The second part provides a thorough foundation in linear algebra, working from an undergraduate level up through several applications. Selections from these first two parts, with possible additions from the first appendix on mathematical fundamentals, would make a solid singlesemester course in "mathematical methods for signals and systems." A possible course sequence might be as follows: Move fairly quickly through Chapter 1 (with sections 1.8 and 1.10 optional, depending on interest (12 weeks)). In Chapter 2, move quickly to the vectorspace concepts, then focus on the concept of orthogonality. It may be useful to skip the more technical sections associated with infinitedimensional vector spaces (for example, sections 2.1.2, 2.1.3, and 2.16). (2 weeks) Spend time in Chapter 3 on leastsquares and minimum meansquare filtering and estimation concepts, and the dual approximation problem (sections 3.13.14). (23 weeks) Depending on interest, examine either wavelet transforms or digital communications from this geometric viewpoint. (1 week) In Chapter 4, focus on sections 4.14.5 to get the geometry of the operators, 4.9 for a return to the leastsquares idea, and 4.10 for practical computation issues. Introduce the recursive least square filter in section 4.11, and visit partitioned matrix inverses in section 4.12. (23 weeks) In Chapter 5, focus on sections 5.2 and 5.3. The QR factorization, in particular, is a foundation for many signal processing algorithms. If a numeric implementation viewpoint is not of interest, then material after section 5.3.5 may be omitted. (23 weeks) Sections 6.16.5 constitute the principal theory of chapter 6. After these sections have been covered, applications may be drawn from sections 6.76.12, with those in 6.8 and 6.9 probably of the most interest. If a numeric focus is desired, section 6.14 may be covered. (23 weeks) The theory of the SVD in sections 7.17.5 should be covered, followed by a subset of applications from sections 7.67.9. (23 weeks) Topics related to special matrices (with special emphasis on Toeplitz matrices) can fill any remaining time. Chapters 1014 would fit well into a first course on detection and estimation, especially when supplemented by some of the material on linear algebra (such as eigendecompositions and the SVD). This book can be the basis for a onesemester tools course that selects topics from parts I, II, and III. Assuming prior familiarity with continuoustime and discretetime systems, topics in such a course could include the following. (a) The multivariate Gaussian density (section 1.7). ( (b) Essential vectorspace notions (sections 2.12.6, 2.10, 2.13, 2.142.15). (2 weeks) (c) Applications of vectorspace concepts; for example, leastsquares and minimum meansquares filtering (sections 3.1, 3.2, 3.4, 3.83.12). (3 weeks) (d) Matrix factorizations (sections 5.2 and 5.3, no numeric discussion). ( (e) Singular value decompositions (sections 7.17.3, 7.5), with some applications (such as section 7.6). (2 weeks) (f) Introduction to detection and estimation (sections 10.110.3, 10.510.6). (1 week) (g) Detection theory (sections 11.111.6). (3 weeks) (h) Estimation theory (sections 12.112.2, 12.412.6). (2 weeks) (i) Kalman filtering (sections 13.1, 13.2, or 13.3). (1 week) A course in "iterative methods for signal processing" could focus on chapters in part IV The course material could well be accompanied by a student research project. A course in "methods of optimization for signal processing" could focus on chapters in part V Yet another alternative is a wrapup course for students in the signals and systems area, who are familiar with their topic areas but wish to sharpen their analytical skills. This course could be similar to the first one outlined, with less time spent in Chapter 1 and more time spent examining numerical implementations. Topics from the last parts of the book could also be selected.

Read from the Book

Preface Rationale The purpose of this book is to bridge the gap between introductory signal processing classes and the mathematics prevalent in contemporary signal processing research and practice, by providing a unified applied treatment of fundamental mathematics, seasoned with demonstrations using MATLAB®. This book is intended not only for current students of signal processing, but also for practicing engineers who must be able to access the signal processing research literature, and for researchers looking for a particular result to apply. It is thus intended both as a textbook and as a reference. Both the theory and the practice of signal processing contribute to and draw from a variety of disciplines: controls, communications, system identification, information theory, artificial intelligence, spectroscopy, pattern recognition, tomography, image analysis, and data acquisition, among others. To fulfill its role in these diverse areas, signal processing employs a variety of mathematical tools, including transform theory, probability, optimization, detection theory, estimation theory, numerical analysis, linear algebra, functional analysis, and many others. The practitioner of signal processing— the "signal processor"— may use several of these tools in the solution of a problem; for example, setting up a signal reconstruction algorithm, and then optimizing the parameters of the algorithm for optimum performance. Practicing signal processors must have knowledge of both the theory and the implementation of the mathematics: how and why it works, and how to make the computer do it. The breadth of mathematics employed in signal processing, coupled with the opportunity to apply that math to problems of engineering interest, makes the field both interesting and rewarding. The mathematical aspects of signal processing also introduce some of its major challenges: how is a student or engineering practitioner to become versed in such a variety of mathematical techniques while still keeping an eye toward applications? Introductory texts on signal processing tend to focus heavily on transform techniques and filter-based applications. While this is an essential part of the training of a signal processor, it is only the tip of the iceberg of material required by a practicing engineer. On the other hand, more advanced texts typically develop mathematical tools that are specific to a narrow aspect of signal processing, while perhaps missing connections between these ideas and related areas of research. Neither of these approaches provides sufficient background to read and understand broadly in the signal processing research literature, nor do they equip the student with many signal processing tools. The signal processing literature has moved steadily toward increasing sophistication: applications of the singular value decomposition (SVD) and wavelet transforms abound; everyone knows something about these by now, or should! Part of this move toward sophistication is fueled by computer capabilities, since computations that formerly required considerable effort and understanding are now embodied in convenient mathematical packages. A naive view might held that this automation threatens the expertise of the engineer: Why hire a specialist to do what anyone can do in ten minutes with a MATLAB toolbox? Viewed more positively, the power of the computer provides a variety of new opportunities, as engineers are freed from computational drudgery to pursue new applications. Computer software provides platforms upon which innovative ideas may be developed with ever greater ease. Taking advantage of this new freedom to develop useful concepts will require a solid understanding of mathematics, both to appreciate what is in the toolboxes and to extend beyond their limits. This book is intended to provide a foundation in the requisite mathematics. We assume that students using this text have had a course in traditional transform-based digital signal processing at the senior or first-year graduate level, and a traditional course in stochastic processes. Though basic concepts in these areas are reviewed, this book does not supplant the more focused coverage that these courses provide. Features Vector-space geometry, which puts least-squares and minimum mean-squares in the same framework, and the concept of signals as vectors in an appropriate vector space, are both emphasized. This vector-space approach provides a natural framework for topics such as wavelet transforms and digital communications, as well as the traditional topics of optimum prediction, filtering, and estimation. In this context, the more general notion of metric spaces is introduced, with a discussion of signal norms. The linear algebra used in signal processing is thoroughly described, both in concept and in numerical implementation. While software libraries are commonly available to perform linear algebra computations, we feel that the numerical techniques presented in this book exercise student intuition regarding the geometry of vector spaces, and build understanding of the issues that must be addressed in practical problems. The presentation includes a thorough discussion of eigen-based methods of computation, including eigenfilters, MUSIC, and ESPRIT; there is also a chapter devoted to the properties and applications of the SVD. Toeplitz matrices, which appear throughout the signal processing literature, are treated both from a numerical point of view— as an example of recursive algorithms— and in conjunction with the lattice-filtering interpretation. The matrices in linear algebra are viewed as operators; thus, the important concept of an operator is introduced. Associated notions, such as the range, nullspace, and norm of an operator are also presented. While a full coverage of operator theory is not provided, there is a strong foundation that can serve to build insight into other operators. In addition to linear algebraic concepts, there is a discussion of computation . Algorithms are presented for computing the common factorizations, eigenvalues, eigenvectors, SVDs, and many other problems, with some numerical consideration for implementation. Not all of this material is necessarily intended for classroom use in a conventional signal processing course— there will not be sufficient time in most cases. Nonetheless, it provides an important perspective to prospective practitioners, and a starting point for implementations on other platforms. Instructors may choose to emphasize certain numeric concepts because they highlight particular topics, such as the geometry of vector spaces. The Cauchy-Schwartz inequality is used in a variety of places as an optimizing principle. Recursive least square and least mean square adaptive filters are presented as natural outgrowths of more fundamental concepts: matrix inverse updates and steepest descent. Neural networks and blind source separation are also presented as applications of steepest descent. Several chapters are devoted to iterative and recursive methods. Though iterative methods are of great theoretical and practical significance, no other signal processing textbook provides a similar breadth of coverage. Methods presented include projection on convex sets, composite mapping, the EM algorithm, conjugate gradient, and methods of matrix inverse computation using iterative methods. Detection and estimation are presented with several applications, including spectrum estimation, phase estimation, and multidimensional digital communications. Optimization is a key concept in signal processing, and examples of optimization, both unconstrained and constrained, appear throughout the text. Both a theoretical justification for Lagrange multiplier methods and a physical interpretation are explicitly spelled out in a chapter on optimization. A separate chapter discusses linear programming and its applications. Optimizations on graphs (shortest-path problems) are also examined, with a variety of applications in communications and signal processing. The EM algorithm as presented here is the only treatment in a signal processing textbook that we are aware of. This powerful algorithm is used for many otherwise intractable estimation and learning problems. In general, the presentation is at a more formal level than in many recent digital signal processing texts, following a "theorem/proof" format throughout. At the same time, it is less formal than many math texts covering the same material. In this, we have attempted to help the student become comfortable with rigorous thinking, without overwhelming them with technicalities. (A brief review of methods of proofs is also provided to help students develop a sense of how to approach the proofs.) Ultimately, the aim of this book is to teach its reader how to think about problems. To this end, some material is covered more than once, from different perspectives (e.g., with more than one proof for certain results), to demonstrate that there is usually more than one way to approach a problem. Throughout the text, the intent has been to explain the "what" and the "why" of the mathematics, but not become overwrought with some of the more technical mathematical preoccupations. In this regard, the book does not always thoroughly treat questions of "how well:" (For example, in our coverage of linear numerical analysis, the perturbation analysis that characterizes much of the research literature has been largely ignored. Nor do issues of computational complexity form a major consideration.) To visualize this approach, consider an automotive analogy: Our intent is to "get under the hood" to a sufficient degree that it is clear why the engine runs and what it can do, but not to provide a molecular-level description of the metallurgical structure of the piston rings. Such fine-grained investigations might be a necessary part of research into fine-tuning the performance of the engine— or the algorithm— but are not appropriate for a student learning the basic mechanics. Throughout the chapters and in the appendices, there is a great deal of material that will be of reference value to practicing engineers. For example, there are facts regarding matrix rank, the invertibility of matrices, properties of Hermitian matrices, properties of structured matrices preserved under multiplication, and an extensive table of gradients. Not all of this material is necessarily intended for classroom use, but is provided to enhance the value of the book as a reference. Nevertheless, where such reference material is provided, it is usually accompanied by an explanation of its derivation, so that related facts may often be derived by the reader. Though this book does not provide the final word in any research area, for many research paths it will at least provide a good first step. The contents of the book have been selected according to a variety of criteria. The primary criterion was whether material has been of use or interest to us in our research; questions from students and the need to find clear explanations, exceptional writings found in other textbooks and papers, have also been determining factors. Some of the material has been included for its practicality, and some for its outstanding beauty. In the ongoing debate regarding the teaching of mathematics to engineers, recent proposals suggest using "just in time" mathematics: provide the mathematical concept only when the need for it arises in the solution of an engineering problem. This approach has arisen as a response to the charge that mathematical pedagogy has been motivated by a "just in case" approach: we''ll teach you all this stuff just in case you ever happen to need it. In reality, these approaches are neither fully desirable nor achievable, potentially lacking rigor and depth on the one hand, and motivation and insight on the other. As an alternative, we hope that the presentation in this book is "justified," so that the level of mathematics is suited to its application, and the applications are seen in conjunction with the concepts. Programs The algorithms found throughout the text, written in MATLAB, allow the reader to see how the concepts developed in the text might be implemented, allow easy exploration of the concepts (and, sometimes, of the limitations of the theory), and provide a useful library of core functionality for a variety of signal processing research applications. With thorough theoretical and applied discussion surrounding each algorithm, this is not simply a book of recipes; raw ingredients are provided to stir up some interesting stews! In most cases, the algorithms themselves have not been presented in the text. Instead, an icon is used to indicate that the text an algorithm is to be found on the included CD-ROM (in some instances the algorithm consists of several related files). In the interest of brevity, type-checking of arguments has not been incorporated into the functions. Otherwise, we believe that all of the code provided works, at least to produce the examples described in the book. Of course, information regarding program bugs, fixes, and improvements is always welcome. Nevertheless, we are required to make the standard disclaimer of warranty which can be found in its entirety on pg. 946. Readers are free to use the programs or any derivatives of them for any scientific purpose, with appropriate citation of this book. Updated versions of the programs, and other information, can be found at the following website: www.prenhafl.com/moon Exercises The exercises found at the end of each chapter are loosely divided into sections, but it may be necessary to draw from material in other sections (or even other chapters) in order to solve some of the problems. There are relatively few merely numerical exercises. With the computer performing automated computations in many cases, simply running numbers doesn''t provide an informative exercise. Readers are encouraged, of course, to play around with the algorithms to get a sense of how they work. Insight frequently can be gained on some difficult problems by trying several related numerical approaches. The intent of the exercises is to engage the reader in the development of the theory in the book. Many of the exercises require derivations of results presented in the chapters, or proofs of some of the lemmas and theorems; other exercises require programming an extension or modification of a MATLAB algorithm presented in the chapter; and still others lead the student through a step-by-step process leading to some significant result (for example, a derivation of Gaussian quadrature or linear prediction theory, extension of inverses of Toeplitz matrices, or another derivation of the Kalman filter). As students work through these exercises, they should develop skill in organizing their thinking (which can help them to approach other problems) as well as acquire background in a variety of important topics. Most of the exercises require a fair degree of insight and effort to solve— students should plan on being challenged. Wherever possible, students are encouraged to interact with the computer for computational assistance, insight, and feedback. A solutions manual is available to instructors who have adopted the book for classroom use. Not only are solutions provided but, in many cases, MATLAB and MATHEMATICA&3153; code is also provided, indicating how a problem might be approached using the computer. Solutions to selected exercises can also be found on the CD-ROM. Courses of study There is clearly more information in this book than can be covered in a single semester, or even a full year. Several different courses of study could be devised based on this material, giving instructors the opportunity to choose the material suitable for the needs and development of their students. For example, depending on the focus of the class, instructors might choose to skip completely the numerical aspects of algorithms or, conversely, make them a focus of the course. Several possible course options are described in the following list. In a straightforward overview, the material in the first two parts is regarded as the foundation upon which the major concepts of signal processing are built. The first part provides a review of signal models and representations (e.g., difference equations, transfer functions, state-space form), and introduces several important signal processing problems, such as spectrum estimation and system identification. The second part provides a thorough foundation in linear algebra, working from an undergraduate level up through several applications. Selections from these first two parts, with possible additions from the first appendix on mathematical fundamentals, would make a solid single-semester course in "mathematical methods for signals and systems." A possible course sequence might be as follows: Move fairly quickly through Chapter 1 (with sections 1.8 and 1.10 optional, depending on interest (1-2 weeks)). In Chapter 2, move quickly to the vector-space concepts, then focus on the concept of orthogonality. It may be useful to skip the more technical sections associated with infinite-dimensional vector spaces (for example, sections 2.1.2, 2.1.3, and 2.16). (2 weeks) Spend time in Chapter 3 on least-squares and minimum mean-square filtering and estimation concepts, and the dual approximation problem (sections 3.1-3.14). (2-3 weeks) Depending on interest, examine either wavelet transforms or digital communications from this geometric viewpoint. (1 week) In Chapter 4, focus on sections 4.1-4.5 to get the geometry of the operators, 4.9 for a return to the least-squares idea, and 4.10 for practical computation issues. Introduce the recursive least square filter in section 4.11, and visit partitioned matrix inverses in section 4.12. (2-3 weeks) In Chapter 5, focus on sections 5.2 and 5.3. The QR factorization, in particular, is a foundation for many signal processing algorithms. If a numeric implementation viewpoint is not of interest, then material after section 5.3.5 may be omitted. (2-3 weeks) Sections 6.1-6.5 constitute the principal theory of chapter 6. After these sections have been covered, applications may be drawn from sections 6.76.12, with those in 6.8 and 6.9 probably of the most interest. If a numeric focus is desired, section 6.14 may be covered. (2-3 weeks) The theory of the SVD in sections 7.1-7.5 should be covered, followed by a subset of applications from sections 7.6-7.9. (2-3 weeks) Topics related to special matrices (with special emphasis on Toeplitz matrices) can fill any remaining time. Chapters 10-14 would fit well into a first course on detection and estimation, especially when supplemented by some of the material on linear algebra (such as eigendecompositions and the SVD). This book can be the basis for a one-semester tools course that selects topics from parts I, II, and III. Assuming prior familiarity with continuous-time and discrete-time systems, topics in such a course could include the following. (a) The multivariate Gaussian density (section 1.7). ( (b) Essential vector-space notions (sections 2.1-2.6, 2.10, 2.13, 2.14-2.15). (2 weeks) (c) Applications of vector-space concepts; for example, least-squares and minimum mean-squares filtering (sections 3.1, 3.2, 3.4, 3.8-3.12). (3 weeks) (d) Matrix factorizations (sections 5.2 and 5.3, no numeric discussion). ( (e) Singular value decompositions (sections 7.1-7.3, 7.5), with some applications (such as section 7.6). (2 weeks) (f) Introduction to detection and estimation (sections 10.1-10.3, 10.510.6). (1 week) (g) Detection theory (sections 11.1-11.6). (3 weeks) (h) Estimation theory (sections 12.1-12.2, 12.4-12.6). (2 weeks) (i) Kalman filtering (sections 13.1, 13.2, or 13.3). (1 week) A course in "iterative methods for signal processing" could focus on chapters in part IV The course material could well be accompanied by a student research project. A course in "methods of optimization for signal processing" could focus on chapters in part V Yet another alternative is a wrap-up course for students in the signals and systems area, who are familiar with their topic areas but wish to sharpen their analytical skills. This course could be similar to the first one outlined, with less time spent in Chapter 1 and more time spent examining numerical implementations. Topics from the last parts of the book could also be selected.

Table of Contents

I. INTRODUCTION AND FOUNDATIONS.

 1. Introduction and Foundations.

II. VECTOR SPACES AND LINEAR ALGEBRA.

 2. Signal Spaces.

 3. Representation and Approximation in Vector Spaces.

 4. Linear Operators and Matrix Inverses.

 5. Some Important Matrix Factorizations.

 6. Eigenvalues and Eigenvectors.

 7. The Singular Value Decomposition.

 8. Some Special Matrices and Their Applications.

 9. Kronecker Products and the Vec Operator.

III. DETECTION, ESTIMATION, AND OPTIMAL FILTERING.

10. Introduction to Detection and Estimation, and Mathematical Notation.

11. Detection Theory.

12. Estimation Theory.

13. The Kalman Filter.

IV. ITERATIVE AND RECURSIVE METHODS IN SIGNAL PROCESSING.

14. Basic Concepts and Methods of Iterative Algorithms.

15. Iteration by Composition of Mappings.

16. Other Iterative Algorithms.

17. The EM Algorithm in Signal Processing.

V. METHODS OF OPTIMIZATION.

18. Theory of Constrained Optimization.

19. Shortest-Path Algorithms and Dynamic Programming.

20. Linear Programming.

APPENDIXES.

A. Basic Concepts and Definitions.

B. Completing the Square.

C. Basic Matrix Concepts.

D. Random Processes.

E. Derivatives and Gradients.

F. Conditional Expectations of Multinomial and Poisson r.v.s.

From Our Editors

It requires a lot of mathematical knowledge for modern signal processing to work. Todd Moon and Wynn Sterling provide readers with this knowledge in Mathematical Methods and Algorithms for Signal Processing. The authors focus on such topics as EM algorithm, blind source operation, and projection on convex sets, spectrum estimation and adaptive filtering. The authors assume that the readers have a background in signals and stochastic processes. This book also includes an accompanying CD-ROM that will provide readers with the hands-on experience they need to master these mathematical methods.