Grady / Polimeni Discrete Calculus

Applied Analysis on Graphs for Computational Science
1. Auflage 2010
ISBN: 978-1-84996-290-2
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 366 Seiten

This unique text brings together into a single framework current research in the three areas of discrete calculus, complex networks, and algorithmic content extraction. Many example applications from several fields of computational science are provided.

Autoren/Hrsg.

Grady, Leo J.

Polimeni, Jonathan R.

Inhaltsverzeichnis

1;Preface;6
2;Contents;7
3;Acronyms;12
4;Discrete Calculus: History and Future;14
4.1;Discrete Calculus;14
4.1.1;Origins of Vector Calculus;15
4.1.2;Origins of Discrete Calculus;16
4.1.3;Discrete vs. Discretized;17
4.2;Complex Networks;19
4.3;Content Extraction;20
4.4;Organization of the Book;21
4.5;Intended Audience;21
5;A Brief Review of Discrete Calculus;23
5.1;Introduction to Discrete Calculus;24
5.1.1;Topology and the Fundamental Theorem of Calculus;25
5.1.2;Differential Forms;27
5.1.2.1;Exterior Algebra and Antisymmetric Tensors;28
5.1.2.1.1;The Vector Spaces of p-Vectors and p-Forms;28
5.1.2.1.2;Manifolds, Tangent Spaces, and Cotangent Spaces;31
5.1.2.1.3;The Metric Tensor: Mapping p-Forms to p-Vectors;34
5.1.2.2;Differentiation and Integration of Forms;37
5.1.2.2.1;The Exterior Derivative;37
5.1.2.2.2;The Poincaré Lemma;41
5.1.2.3;The Hodge Star Operator;43
5.1.2.3.1;The Codifferential Operator and the Laplace-de Rham Operator;47
5.1.2.4;Differential Forms and Linear Pairings;48
5.1.3;Discrete Calculus;49
5.1.3.1;Discrete Domains;50
5.1.3.1.1;Orientation;53
5.1.3.1.2;The Incidence Matrix;55
5.1.3.1.3;Chains;56
5.1.3.1.4;The Discrete Boundary Operator;57
5.1.3.2;Discrete Forms and the Coboundary Operator;59
5.1.3.3;Primal and Dual Complexes;61
5.1.3.4;The Role of a Metric: the Metric Tensor, the Discrete Hodge Star Operator, and Weighted Complexes;65
5.1.3.4.1;The Metric Tensor and the Associated Inner Product;65
5.1.3.4.2;The Discrete Hodge Star Operator;66
5.1.3.4.3;Weights;68
5.1.3.4.4;The Volume Cochain;68
5.1.3.5;The Dual Coboundary Operator;70
5.1.3.6;The Discrete Laplace-de Rham Operator;71
5.1.4;Structure of Discrete Physical Laws;74
5.1.5;Examples of Discrete Calculus;74
5.1.5.1;Fundamental Theorem of Calculus and the Generalized Stokes' Theorem;76
5.1.5.1.1;Generalized Stokes' Theorem on a 1-Complex;76
5.1.5.1.2;Comparison with Finite Differences Operators;80
5.1.5.1.3;Generalized Stokes' Theorem on a 2-Complex;82
5.1.5.1.4;Generalized Stokes' Theorem on a 3-Complex;83
5.1.5.2;The Helmholtz Decomposition;84
5.1.5.2.1;Algorithm for Computing a Helmholtz Decomposition of a Flow Field;87
5.1.5.3;Matrix Representation of Discrete Calculus Identities;88
5.1.5.3.1;Integration by Parts;88
5.1.5.3.2;Other Identities;89
5.1.5.4;Elliptic Equations;90
5.1.5.4.1;Variational Principles;93
5.1.5.5;Diffusion;93
5.1.5.6;Advection;97
5.1.6;Concluding Remarks;99
5.2;Circuit Theory and Other Discrete Physical Models;101
5.2.1;Circuit Laws;103
5.2.2;Steady-State Solutions;104
5.2.2.1;Dependent Sources;107
5.2.2.2;Energy Minimization;109
5.2.2.2.1;Power Minimization with Nonlinear Resistors;111
5.2.3;AC Circuits;111
5.2.4;Connections Between Circuit Theory and Other Discrete Domains;114
5.2.4.1;Spring Networks;114
5.2.4.2;Random Walks;116
5.2.4.3;Gaussian Markov Random Fields;120
5.2.4.4;Tree Counting;122
5.2.4.5;Linear Algebra Applied to Circuit Analysis;127
5.2.4.5.1;The Delta-Wye and Star-Mesh Transforms;127
5.2.4.5.2;Minimum-Degree Orderings;129
5.2.5;Conclusion;131
6;Applications of Discrete Calculus;133
6.1;Building a Weighted Complex from Data;134
6.1.1;Determining Edges and Cycles;135
6.1.1.1;Defining an Edge Set;135
6.1.1.1.1;Edges from an Ambient Metric;136
6.1.1.1.2;Edges by k-Nearest Neighbors;137
6.1.1.1.3;Edges from a Delaunay Triangulation;137
6.1.1.1.4;Adding Edges via the Watts-Strogatz Model;137
6.1.1.2;Defining a Cycle Set;138
6.1.1.2.1;Defining Cycles Geometrically: Cycles from an Embedding;139
6.1.1.2.2;Defining Cycles Algebraically;140
6.1.1.2.3;Cycle Sets and Duality;143
6.1.2;Deriving Edge Weights;144
6.1.2.1;Edge Weights to Reflect Geometry;144
6.1.2.2;Edge Weights to Penalize Data Outliers;145
6.1.2.2.1;Univariate Data;145
6.1.2.2.2;Computing Weights from Multivariate Data;150
6.1.2.3;Edge Weights to Cause Repulsion;152
6.1.2.4;Edge Weights to Represent Joint Statistics;153
6.1.2.5;Deducing Edge Weights from Observations;153
6.1.2.5.1;The Underdetermined Case;154
6.1.2.5.2;The Overdetermined/Inconsistent Case;155
6.1.3;Obtaining Higher-Order Weights to Penalize Outliers;156
6.1.3.1;Weights Beyond Flows;158
6.1.4;Metrics Defined on a Complex;159
6.1.5;Conclusion;162
6.2;Filtering on Graphs;164
6.2.1;Fourier and Spectral Filtering on a Graph;165
6.2.1.1;Graphs that Are Not Shift-Invariant;168
6.2.1.2;The Origins of High Frequency Noise;171
6.2.2;Energy Minimization Methods for Filtering;172
6.2.2.1;The Basic Energy Minimization Model;172
6.2.2.1.1;Iterative Minimization;173
6.2.2.2;Extended Basic Energy Model;176
6.2.2.3;The Total Variation Model;177
6.2.3;Filtering with Implicit Discontinuities;179
6.2.4;Filtering with Explicit, but Unknown, Discontinuities;181
6.2.5;Filtering by Gradient Manipulation;183
6.2.6;Nonlocal Filtering;183
6.2.7;Filtering Vectors and Flows;184
6.2.7.1;Translating Scalar Filtering to Flow Filtering;185
6.2.8;Filtering Higher-Order Cochains;188
6.2.9;Applications;189
6.2.9.1;Image Processing;189
6.2.9.1.1;Regular Graphs and Space-Invariant Processing;189
6.2.9.1.2;Space-Variant Imaging;191
6.2.9.2;Three-Dimensional Mesh Filtering;194
6.2.9.2.1;Mesh Fairing;194
6.2.9.3;Filtering Data on a Surface;196
6.2.9.4;Geospatial Data;201
6.2.9.5;Filtering Flow Data-Brain Connectivity;202
6.2.10;Conclusion;206
6.3;Clustering and Segmentation;207
6.3.1;Targeted Clustering;208
6.3.1.1;Primal Targeted Clustering;209
6.3.1.1.1;Probabilities Assigned to a Subset;210
6.3.1.1.2;Known Labels for a Subset of Nodes;213
6.3.1.1.3;Negative Weights;217
6.3.1.2;Dual Targeted Clustering;218
6.3.1.2.1;Dual Algorithms in Three Dimensions;221
6.3.2;Untargeted Clustering;223
6.3.2.1;Primal Untargeted Clustering;224
6.3.2.2;Dual Untargeted Clustering;228
6.3.3;Semi-targeted Clustering;229
6.3.3.1;The k-Means Model;229
6.3.4;Clustering Higher-Order Cells;235
6.3.4.1;Clustering Edges;235
6.3.4.1.1;Targeted Edge Clustering;235
6.3.4.1.2;Untargeted Edge Clustering;236
6.3.5;Applications;237
6.3.5.1;Image Segmentation;237
6.3.5.2;Social Networks;243
6.3.5.3;Machine Learning and Classification;244
6.3.5.4;Gene Expression;248
6.3.6;Conclusion;250
6.4;Manifold Learning and Ranking;251
6.4.1;Manifold Learning;252
6.4.1.1;Multidimensional Scaling and Isomap;253
6.4.1.2;Laplacian Eigenmaps and Spectral Coordinates;255
6.4.1.3;Locality Preserving Projections;257
6.4.1.4;Relationship to Clustering;259
6.4.1.5;Manifold Learning on Edge Data;259
6.4.2;Ranking;261
6.4.2.1;PageRank;261
6.4.2.1.1;PageRank as Advection;263
6.4.2.2;HITS;264
6.4.3;Applications;265
6.4.3.1;Shape Characterization;265
6.4.3.2;Point Correspondence;268
6.4.3.3;Web Search;270
6.4.3.4;Judicial Citation;272
6.4.4;Conclusion;274
6.5;Measuring Networks;275
6.5.1;Measures of Graph Connectedness;276
6.5.1.1;Graph Distance;276
6.5.1.2;Node Centrality;277
6.5.1.3;Distance-Based Properties of a Graph;278
6.5.2;Measures of Graph Separability;282
6.5.2.1;Clustering Measures;282
6.5.2.2;Small-World Graphs;285
6.5.3;Topological Measures;287
6.5.4;Geometric Measures;289
6.5.4.1;Discrete Gaussian Curvature;290
6.5.4.2;Discrete Mean Curvature;291
6.5.5;Applications;293
6.5.5.1;Social Networks;293
6.5.5.2;Chemical Graph Theory;294
6.5.6;Conclusion;296
7;Appendix A Representation and Storage of a Graph and Complex;298
7.1;General Representations for Complexes;298
7.1.1;Cells List Representation;298
7.1.2;Operator Representation;299
7.2;Representation of 1-Complexes;300
7.2.1;Neighbor List Representation;300
8;Appendix B Optimization;302
8.1;Real-Valued Optimization;303
8.1.1;Unconstrained Direct Solutions;304
8.1.2;Constrained Direct Solutions;305
8.1.2.1;Optimization with Boundary Conditions;305
8.1.2.2;Optimization with Linear Equality Constraints;308
8.1.2.3;Optimization with Linear Inequality Constraints;310
8.1.2.4;Ratio Optimization;312
8.1.3;Descent Methods;315
8.1.3.1;Gradient Descent;315
8.1.3.2;Newton's Method;315
8.1.3.3;Descent Methods for Constrained Optimization;318
8.1.4;Nonconvex Energy Optimization over Real Variables;319
8.2;Integer-Valued Optimization;319
8.2.1;Linear Objective Functions;319
8.2.2;Quadratic Objective Functions;321
8.2.2.1;Pure Quadratic;321
8.2.2.2;General Pairwise Terms;323
8.2.2.3;Higher-Order Terms;325
8.2.3;General Integer Programming Problems;325
9;Appendix C The Hodge Theorem: A Generalization of the Helmholtz Decomposition;326
9.1;The Helmholtz Theorem;326
9.2;The Hodge Decomposition;333
10;Summary of Notation;338
11;References;341
12;Index;359
13;Color Plates;366