简介
The field of discrete calculus, also known as discrete exterior calculus, focuses on finding a proper set of definitions and differential operators that make it possible to operate the machinery of multivariate calculus on a finite, discrete space. In contrast to traditional goals of finding an accurate discretization of conventional multivariate calculus, discrete calculus establishes a separate, equivalent calculus that operates purely in the discrete space without any reference to an underlying continuous process.This unique text brings together into a single framework current research in the three areas of discrete calculus, complex networks, and algorithmic content extraction. Although there have been a few intersections in the literature between these disciplines, they have developed largely independently of one another, yet researchers working in any one of these three areas can strongly benefit from the tools and techniques being used in the others. Many example applications from several fields of computational science are provided to demonstrate the usefulness of this framework to a broad range of problems. Readers are assumed to be familiar with the basics of vector calculus, graph theory, and linear algebra.Topics and features: presents a thorough review of discrete calculus, with a focus on key concepts required for successful application; unifies many standard image processing algorithms into a common framework for viewing a wide variety of standard algorithms in filtering, clustering, and manifold learning that may be applied to processing data associated with a graph or network; explains how discrete calculus provides a natural definition of low-frequency on a graph, which then yields filtering and denoising algorithms; discusses how filtering algorithms can give rise to clustering algorithms, which can be used to develop manifold learning and data discovery methods; examines ranking algorithms, as well as algorithms for analyzing the structure of a network.Graduate students and researchers interested in discrete calculus, complex networks, image processing and computer graphics will find this text/reference a clear introduction to the foundations of discrete calculus as well as a useful guide to have readily available for their work.Dr. Leo J. Grady is a Senior Research Scientist with Siemens Corporate Research in Princeton, New Jersey, USA. Dr. Jonathan R. Polimeni is a Research Fellow at the Massachusetts General Hospital in Boston, Massachusetts, USA, and Instructor in Radiology at Harvard Medical School, Boston, Massachusetts, USA.
目录
Preface 5
Contents 6
Acronyms 11
Discrete Calculus: History and Future 13
Discrete Calculus 13
Origins of Vector Calculus 14
Origins of Discrete Calculus 15
Discrete vs. Discretized 16
Complex Networks 18
Content Extraction 19
Organization of the Book 20
Intended Audience 20
A Brief Review of Discrete Calculus 22
Introduction to Discrete Calculus 23
Topology and the Fundamental Theorem of Calculus 24
Differential Forms 26
Exterior Algebra and Antisymmetric Tensors 27
The Vector Spaces of p-Vectors and p-Forms 27
Manifolds, Tangent Spaces, and Cotangent Spaces 30
The Metric Tensor: Mapping p-Forms to p-Vectors 33
Differentiation and Integration of Forms 36
The Exterior Derivative 36
The Poincar茅 Lemma 40
The Hodge Star Operator 42
The Codifferential Operator and the Laplace-de Rham Operator 46
Differential Forms and Linear Pairings 47
Discrete Calculus 48
Discrete Domains 49
Orientation 52
The Incidence Matrix 54
Chains 55
The Discrete Boundary Operator 56
Discrete Forms and the Coboundary Operator 58
Primal and Dual Complexes 60
The Role of a Metric: the Metric Tensor, the Discrete Hodge Star Operator, and Weighted Complexes 64
The Metric Tensor and the Associated Inner Product 64
The Discrete Hodge Star Operator 65
Weights 67
The Volume Cochain 67
The Dual Coboundary Operator 69
The Discrete Laplace-de Rham Operator 70
Structure of Discrete Physical Laws 73
Examples of Discrete Calculus 73
Fundamental Theorem of Calculus and the Generalized Stokes' Theorem 75
Generalized Stokes' Theorem on a 1-Complex 75
Comparison with Finite Differences Operators 79
Generalized Stokes' Theorem on a 2-Complex 81
Generalized Stokes' Theorem on a 3-Complex 82
The Helmholtz Decomposition 83
Algorithm for Computing a Helmholtz Decomposition of a Flow Field 86
Matrix Representation of Discrete Calculus Identities 87
Integration by Parts 87
Other Identities 88
Elliptic Equations 89
Variational Principles 92
Diffusion 92
Advection 96
Concluding Remarks 98
Circuit Theory and Other Discrete Physical Models 100
Circuit Laws 102
Steady-State Solutions 103
Dependent Sources 106
Energy Minimization 108
Power Minimization with Nonlinear Resistors 110
AC Circuits 110
Connections Between Circuit Theory and Other Discrete Domains 113
Spring Networks 113
Random Walks 115
Gaussian Markov Random Fields 119
Tree Counting 121
Linear Algebra Applied to Circuit Analysis 126
The Delta-Wye and Star-Mesh Transforms 126
Minimum-Degree Orderings 128
Conclusion 130
Applications of Discrete Calculus 132
Building a Weighted Complex from Data 133
Determining Edges and Cycles 134
Defining an Edge Set 134
Edges from an Ambient Metric 135
Edges by k-Nearest Neighbors 136
Edges from a Delaunay Triangulation 136
Adding Edges via the Watts-Strogatz Model 136
Defining a Cycle Set 137
Defining Cycles Geometrically: Cycles from an Embedding 138
Defining Cycles Algebraically 139
Cycle Sets and Duality 142
Deriving Edge Weights 143
Edge Weights to Reflect Geometry 143
Edge Weights to Penalize Data Outliers 144
Univariate Data 144
Computing Weights from Multivariate Data 149
Edge Weights to Cause Repulsion 151
Edge Weights to Represent Joint Statistics 152
Deducing Edge Weights from Observations 152
The Underdetermined Case 153
The Overdetermined/Inconsistent Case 154
Obtaining Higher-Order Weights to Penalize Outliers 155
Weights Beyond Flows 157
Metrics Defined on a Complex 158
Conclusion 161
Filtering on Graphs 163
Fourier and Spectral Filtering on a Graph 164
Graphs that Are Not Shift-Invariant 167
The Origins of High Frequency Noise 170
Energy Minimization Methods for Filtering 171
The Basic Energy Minimization Model 171
Iterative Minimization 172
Extended Basic Energy Model 175
The Total Variation Model 176
Filtering with Implicit Discontinuities 178
Filtering with Explicit, but Unknown, Discontinuities 180
Filtering by Gradient Manipulation 182
Nonlocal Filtering 182
Filtering Vectors and Flows 183
Translating Scalar Filtering to Flow Filtering 184
Filtering Higher-Order Cochains 187
Applications 188
Image Processing 188
Regular Graphs and Space-Invariant Processing 188
Space-Variant Imaging 190
Three-Dimensional Mesh Filtering 193
Mesh Fairing 193
Filtering Data on a Surface 195
Geospatial Data 200
Filtering Flow Data-Brain Connectivity 201
Conclusion 205
Clustering and Segmentation 206
Targeted Clustering 207
Primal Targeted Clustering 208
Probabilities Assigned to a Subset 209
Known Labels for a Subset of Nodes 212
Negative Weights 216
Dual Targeted Clustering 217
Dual Algorithms in Three Dimensions 220
Untargeted Clustering 222
Primal Untargeted Clustering 223
Dual Untargeted Clustering 227
Semi-targeted Clustering 228
The k-Means Model 228
Clustering Higher-Order Cells 234
Clustering Edges 234
Targeted Edge Clustering 234
Untargeted Edge Clustering 235
Applications 236
Image Segmentation 236
Social Networks 242
Machine Learning and Classification 243
Gene Expression 247
Conclusion 249
Manifold Learning and Ranking 250
Manifold Learning 251
Multidimensional Scaling and Isomap 252
Laplacian Eigenmaps and Spectral Coordinates 254
Locality Preserving Projections 256
Relationship to Clustering 258
Manifold Learning on Edge Data 258
Ranking 260
PageRank 260
PageRank as Advection 262
HITS 263
Applications 264
Shape Characterization 264
Point Correspondence 267
Web Search 269
Judicial Citation 271
Conclusion 273
Measuring Networks 274
Measures of Graph Connectedness 275
Graph Distance 275
Node Centrality 276
Distance-Based Properties of a Graph 277
Measures of Graph Separability 281
Clustering Measures 281
Small-World Graphs 284
Topological Measures 286
Geometric Measures 288
Discrete Gaussian Curvature 289
Discrete Mean Curvature 290
Applications 292
Social Networks 292
Chemical Graph Theory 293
Conclusion 295
Appendix A Representation and Storage of a Graph and Complex 297
General Representations for Complexes 297
Cells List Representation 297
Operator Representation 298
Representation of 1-Complexes 299
Neighbor List Representation 299
Appendix B Optimization 301
Real-Valued Optimization 302
Unconstrained Direct Solutions 303
Constrained Direct Solutions 304
Optimization with Boundary Conditions 304
Optimization with Linear Equality Constraints 307
Optimization with Linear Inequality Constraints 309
Ratio Optimization 311
Descent Methods 314
Gradient Descent 314
Newton's Method 314
Descent Methods for Constrained Optimization 317
Nonconvex Energy Optimization over Real Variables 318
Integer-Valued Optimization 318
Linear Objective Functions 318
Quadratic Objective Functions 320
Pure Quadratic 320
General Pairwise Terms 322
Higher-Order Terms 324
General Integer Programming Problems 324
Appendix C The Hodge Theorem: A Generalization of the Helmholtz Decomposition 325
The Helmholtz Theorem 325
The Hodge Decomposition 332
Summary of Notation 337
References 340
Index 358
Color Plates 365
Contents 6
Acronyms 11
Discrete Calculus: History and Future 13
Discrete Calculus 13
Origins of Vector Calculus 14
Origins of Discrete Calculus 15
Discrete vs. Discretized 16
Complex Networks 18
Content Extraction 19
Organization of the Book 20
Intended Audience 20
A Brief Review of Discrete Calculus 22
Introduction to Discrete Calculus 23
Topology and the Fundamental Theorem of Calculus 24
Differential Forms 26
Exterior Algebra and Antisymmetric Tensors 27
The Vector Spaces of p-Vectors and p-Forms 27
Manifolds, Tangent Spaces, and Cotangent Spaces 30
The Metric Tensor: Mapping p-Forms to p-Vectors 33
Differentiation and Integration of Forms 36
The Exterior Derivative 36
The Poincar茅 Lemma 40
The Hodge Star Operator 42
The Codifferential Operator and the Laplace-de Rham Operator 46
Differential Forms and Linear Pairings 47
Discrete Calculus 48
Discrete Domains 49
Orientation 52
The Incidence Matrix 54
Chains 55
The Discrete Boundary Operator 56
Discrete Forms and the Coboundary Operator 58
Primal and Dual Complexes 60
The Role of a Metric: the Metric Tensor, the Discrete Hodge Star Operator, and Weighted Complexes 64
The Metric Tensor and the Associated Inner Product 64
The Discrete Hodge Star Operator 65
Weights 67
The Volume Cochain 67
The Dual Coboundary Operator 69
The Discrete Laplace-de Rham Operator 70
Structure of Discrete Physical Laws 73
Examples of Discrete Calculus 73
Fundamental Theorem of Calculus and the Generalized Stokes' Theorem 75
Generalized Stokes' Theorem on a 1-Complex 75
Comparison with Finite Differences Operators 79
Generalized Stokes' Theorem on a 2-Complex 81
Generalized Stokes' Theorem on a 3-Complex 82
The Helmholtz Decomposition 83
Algorithm for Computing a Helmholtz Decomposition of a Flow Field 86
Matrix Representation of Discrete Calculus Identities 87
Integration by Parts 87
Other Identities 88
Elliptic Equations 89
Variational Principles 92
Diffusion 92
Advection 96
Concluding Remarks 98
Circuit Theory and Other Discrete Physical Models 100
Circuit Laws 102
Steady-State Solutions 103
Dependent Sources 106
Energy Minimization 108
Power Minimization with Nonlinear Resistors 110
AC Circuits 110
Connections Between Circuit Theory and Other Discrete Domains 113
Spring Networks 113
Random Walks 115
Gaussian Markov Random Fields 119
Tree Counting 121
Linear Algebra Applied to Circuit Analysis 126
The Delta-Wye and Star-Mesh Transforms 126
Minimum-Degree Orderings 128
Conclusion 130
Applications of Discrete Calculus 132
Building a Weighted Complex from Data 133
Determining Edges and Cycles 134
Defining an Edge Set 134
Edges from an Ambient Metric 135
Edges by k-Nearest Neighbors 136
Edges from a Delaunay Triangulation 136
Adding Edges via the Watts-Strogatz Model 136
Defining a Cycle Set 137
Defining Cycles Geometrically: Cycles from an Embedding 138
Defining Cycles Algebraically 139
Cycle Sets and Duality 142
Deriving Edge Weights 143
Edge Weights to Reflect Geometry 143
Edge Weights to Penalize Data Outliers 144
Univariate Data 144
Computing Weights from Multivariate Data 149
Edge Weights to Cause Repulsion 151
Edge Weights to Represent Joint Statistics 152
Deducing Edge Weights from Observations 152
The Underdetermined Case 153
The Overdetermined/Inconsistent Case 154
Obtaining Higher-Order Weights to Penalize Outliers 155
Weights Beyond Flows 157
Metrics Defined on a Complex 158
Conclusion 161
Filtering on Graphs 163
Fourier and Spectral Filtering on a Graph 164
Graphs that Are Not Shift-Invariant 167
The Origins of High Frequency Noise 170
Energy Minimization Methods for Filtering 171
The Basic Energy Minimization Model 171
Iterative Minimization 172
Extended Basic Energy Model 175
The Total Variation Model 176
Filtering with Implicit Discontinuities 178
Filtering with Explicit, but Unknown, Discontinuities 180
Filtering by Gradient Manipulation 182
Nonlocal Filtering 182
Filtering Vectors and Flows 183
Translating Scalar Filtering to Flow Filtering 184
Filtering Higher-Order Cochains 187
Applications 188
Image Processing 188
Regular Graphs and Space-Invariant Processing 188
Space-Variant Imaging 190
Three-Dimensional Mesh Filtering 193
Mesh Fairing 193
Filtering Data on a Surface 195
Geospatial Data 200
Filtering Flow Data-Brain Connectivity 201
Conclusion 205
Clustering and Segmentation 206
Targeted Clustering 207
Primal Targeted Clustering 208
Probabilities Assigned to a Subset 209
Known Labels for a Subset of Nodes 212
Negative Weights 216
Dual Targeted Clustering 217
Dual Algorithms in Three Dimensions 220
Untargeted Clustering 222
Primal Untargeted Clustering 223
Dual Untargeted Clustering 227
Semi-targeted Clustering 228
The k-Means Model 228
Clustering Higher-Order Cells 234
Clustering Edges 234
Targeted Edge Clustering 234
Untargeted Edge Clustering 235
Applications 236
Image Segmentation 236
Social Networks 242
Machine Learning and Classification 243
Gene Expression 247
Conclusion 249
Manifold Learning and Ranking 250
Manifold Learning 251
Multidimensional Scaling and Isomap 252
Laplacian Eigenmaps and Spectral Coordinates 254
Locality Preserving Projections 256
Relationship to Clustering 258
Manifold Learning on Edge Data 258
Ranking 260
PageRank 260
PageRank as Advection 262
HITS 263
Applications 264
Shape Characterization 264
Point Correspondence 267
Web Search 269
Judicial Citation 271
Conclusion 273
Measuring Networks 274
Measures of Graph Connectedness 275
Graph Distance 275
Node Centrality 276
Distance-Based Properties of a Graph 277
Measures of Graph Separability 281
Clustering Measures 281
Small-World Graphs 284
Topological Measures 286
Geometric Measures 288
Discrete Gaussian Curvature 289
Discrete Mean Curvature 290
Applications 292
Social Networks 292
Chemical Graph Theory 293
Conclusion 295
Appendix A Representation and Storage of a Graph and Complex 297
General Representations for Complexes 297
Cells List Representation 297
Operator Representation 298
Representation of 1-Complexes 299
Neighbor List Representation 299
Appendix B Optimization 301
Real-Valued Optimization 302
Unconstrained Direct Solutions 303
Constrained Direct Solutions 304
Optimization with Boundary Conditions 304
Optimization with Linear Equality Constraints 307
Optimization with Linear Inequality Constraints 309
Ratio Optimization 311
Descent Methods 314
Gradient Descent 314
Newton's Method 314
Descent Methods for Constrained Optimization 317
Nonconvex Energy Optimization over Real Variables 318
Integer-Valued Optimization 318
Linear Objective Functions 318
Quadratic Objective Functions 320
Pure Quadratic 320
General Pairwise Terms 322
Higher-Order Terms 324
General Integer Programming Problems 324
Appendix C The Hodge Theorem: A Generalization of the Helmholtz Decomposition 325
The Helmholtz Theorem 325
The Hodge Decomposition 332
Summary of Notation 337
References 340
Index 358
Color Plates 365
- 名称
- 类型
- 大小
光盘服务联系方式: 020-38250260 客服QQ：4006604884
云图客服：
用户发送的提问，这种方式就需要有位在线客服来回答用户的问题，这种 就属于对话式的,问题是这种提问是否需要用户登录才能提问
Video Player
×
Audio Player
×
pdf Player
×
