Discrete Calculus (eBook)

Preface 6
Contents 7
Acronyms 12
Discrete Calculus: History and Future 14
Discrete Calculus 14
Origins of Vector Calculus 15
Origins of Discrete Calculus 16
Discrete vs. Discretized 17
Complex Networks 19
Content Extraction 20
Organization of the Book 21
Intended Audience 21
A Brief Review of Discrete Calculus 23
Introduction to Discrete Calculus 24
Topology and the Fundamental Theorem of Calculus 25
Differential Forms 27
Exterior Algebra and Antisymmetric Tensors 28
The Vector Spaces of p-Vectors and p-Forms 28
Manifolds, Tangent Spaces, and Cotangent Spaces 31
The Metric Tensor: Mapping p-Forms to p-Vectors 34
Differentiation and Integration of Forms 37
The Exterior Derivative 37
The Poincaré Lemma 41
The Hodge Star Operator 43
The Codifferential Operator and the Laplace-de Rham Operator 47
Differential Forms and Linear Pairings 48
Discrete Calculus 49
Discrete Domains 50
Orientation 53
The Incidence Matrix 55
Chains 56
The Discrete Boundary Operator 57
Discrete Forms and the Coboundary Operator 59
Primal and Dual Complexes 61
The Role of a Metric: the Metric Tensor, the Discrete Hodge Star Operator, and Weighted Complexes 65
The Metric Tensor and the Associated Inner Product 65
The Discrete Hodge Star Operator 66
Weights 68
The Volume Cochain 68
The Dual Coboundary Operator 70
The Discrete Laplace-de Rham Operator 71
Structure of Discrete Physical Laws 74
Examples of Discrete Calculus 74
Fundamental Theorem of Calculus and the Generalized Stokes' Theorem 76
Generalized Stokes' Theorem on a 1-Complex 76
Comparison with Finite Differences Operators 80
Generalized Stokes' Theorem on a 2-Complex 82
Generalized Stokes' Theorem on a 3-Complex 83
The Helmholtz Decomposition 84
Algorithm for Computing a Helmholtz Decomposition of a Flow Field 87
Matrix Representation of Discrete Calculus Identities 88
Integration by Parts 88
Other Identities 89
Elliptic Equations 90
Variational Principles 93
Diffusion 93
Advection 97
Concluding Remarks 99
Circuit Theory and Other Discrete Physical Models 101
Circuit Laws 103
Steady-State Solutions 104
Dependent Sources 107
Energy Minimization 109
Power Minimization with Nonlinear Resistors 111
AC Circuits 111
Connections Between Circuit Theory and Other Discrete Domains 114
Spring Networks 114
Random Walks 116
Gaussian Markov Random Fields 120
Tree Counting 122
Linear Algebra Applied to Circuit Analysis 127
The Delta-Wye and Star-Mesh Transforms 127
Minimum-Degree Orderings 129
Conclusion 131
Applications of Discrete Calculus 133
Building a Weighted Complex from Data 134
Determining Edges and Cycles 135
Defining an Edge Set 135
Edges from an Ambient Metric 136
Edges by k-Nearest Neighbors 137
Edges from a Delaunay Triangulation 137
Adding Edges via the Watts-Strogatz Model 137
Defining a Cycle Set 138
Defining Cycles Geometrically: Cycles from an Embedding 139
Defining Cycles Algebraically 140
Cycle Sets and Duality 143
Deriving Edge Weights 144
Edge Weights to Reflect Geometry 144
Edge Weights to Penalize Data Outliers 145
Univariate Data 145
Computing Weights from Multivariate Data 150
Edge Weights to Cause Repulsion 152
Edge Weights to Represent Joint Statistics 153
Deducing Edge Weights from Observations 153
The Underdetermined Case 154
The Overdetermined/Inconsistent Case 155
Obtaining Higher-Order Weights to Penalize Outliers 156
Weights Beyond Flows 158
Metrics Defined on a Complex 159
Conclusion 162
Filtering on Graphs 164
Fourier and Spectral Filtering on a Graph 165
Graphs that Are Not Shift-Invariant 168
The Origins of High Frequency Noise 171
Energy Minimization Methods for Filtering 172
The Basic Energy Minimization Model 172
Iterative Minimization 173
Extended Basic Energy Model 176
The Total Variation Model 177
Filtering with Implicit Discontinuities 179
Filtering with Explicit, but Unknown, Discontinuities 181
Filtering by Gradient Manipulation 183
Nonlocal Filtering 183
Filtering Vectors and Flows 184
Translating Scalar Filtering to Flow Filtering 185
Filtering Higher-Order Cochains 188
Applications 189
Image Processing 189
Regular Graphs and Space-Invariant Processing 189
Space-Variant Imaging 191
Three-Dimensional Mesh Filtering 194
Mesh Fairing 194
Filtering Data on a Surface 196
Geospatial Data 201
Filtering Flow Data-Brain Connectivity 202
Conclusion 206
Clustering and Segmentation 207
Targeted Clustering 208
Primal Targeted Clustering 209
Probabilities Assigned to a Subset 210
Known Labels for a Subset of Nodes 213
Negative Weights 217
Dual Targeted Clustering 218
Dual Algorithms in Three Dimensions 221
Untargeted Clustering 223
Primal Untargeted Clustering 224
Dual Untargeted Clustering 228
Semi-targeted Clustering 229
The k-Means Model 229
Clustering Higher-Order Cells 235
Clustering Edges 235
Targeted Edge Clustering 235
Untargeted Edge Clustering 236
Applications 237
Image Segmentation 237
Social Networks 243
Machine Learning and Classification 244
Gene Expression 248
Conclusion 250
Manifold Learning and Ranking 251
Manifold Learning 252
Multidimensional Scaling and Isomap 253
Laplacian Eigenmaps and Spectral Coordinates 255
Locality Preserving Projections 257
Relationship to Clustering 259
Manifold Learning on Edge Data 259
Ranking 261
PageRank 261
PageRank as Advection 263
HITS 264
Applications 265
Shape Characterization 265
Point Correspondence 268
Web Search 270
Judicial Citation 272
Conclusion 274
Measuring Networks 275
Measures of Graph Connectedness 276
Graph Distance 276
Node Centrality 277
Distance-Based Properties of a Graph 278
Measures of Graph Separability 282
Clustering Measures 282
Small-World Graphs 285
Topological Measures 287
Geometric Measures 289
Discrete Gaussian Curvature 290
Discrete Mean Curvature 291
Applications 293
Social Networks 293
Chemical Graph Theory 294
Conclusion 296
Appendix A Representation and Storage of a Graph and Complex 298
General Representations for Complexes 298
Cells List Representation 298
Operator Representation 299
Representation of 1-Complexes 300
Neighbor List Representation 300
Appendix B Optimization 302
Real-Valued Optimization 303
Unconstrained Direct Solutions 304
Constrained Direct Solutions 305
Optimization with Boundary Conditions 305
Optimization with Linear Equality Constraints 308
Optimization with Linear Inequality Constraints 310
Ratio Optimization 312
Descent Methods 315
Gradient Descent 315
Newton's Method 315
Descent Methods for Constrained Optimization 318
Nonconvex Energy Optimization over Real Variables 319
Integer-Valued Optimization 319
Linear Objective Functions 319
Quadratic Objective Functions 321
Pure Quadratic 321
General Pairwise Terms 323
Higher-Order Terms 325
General Integer Programming Problems 325
Appendix C The Hodge Theorem: A Generalization of the Helmholtz Decomposition 326
The Helmholtz Theorem 326
The Hodge Decomposition 333
Summary of Notation 338
References 341
Index 359
Color Plates 366