Preface
Contents
Acronyms
Discrete Calculus: History and Future
Discrete Calculus
Origins of Vector Calculus
Origins of Discrete Calculus
Discrete vs. Discretized
Complex Networks
Content Extraction
Organization of the Book
Intended Audience
A Brief Review of Discrete Calculus
Introduction to Discrete Calculus
Topology and the Fundamental Theorem of Calculus
Differential Forms
Exterior Algebra and Antisymmetric Tensors
The Vector Spaces of p-Vectors and p-Forms
Manifolds, Tangent Spaces, and Cotangent Spaces
The Metric Tensor: Mapping p-Forms to p-Vectors
Differentiation and Integration of Forms
The Exterior Derivative
The PoincarΓ© Lemma
The Hodge Star Operator
The Codifferential Operator and the Laplace-de Rham Operator
Differential Forms and Linear Pairings
Discrete Calculus
Discrete Domains
Orientation
The Incidence Matrix
Chains
The Discrete Boundary Operator
Discrete Forms and the Coboundary Operator
Primal and Dual Complexes
The Role of a Metric: the Metric Tensor, the Discrete Hodge Star Operator, and Weighted Complexes
The Metric Tensor and the Associated Inner Product
The Discrete Hodge Star Operator
Weights
The Volume Cochain
The Dual Coboundary Operator
The Discrete Laplace-de Rham Operator
Structure of Discrete Physical Laws
Examples of Discrete Calculus
Fundamental Theorem of Calculus and the Generalized Stokes' Theorem
Generalized Stokes' Theorem on a 1-Complex
Comparison with Finite Differences Operators
Generalized Stokes' Theorem on a 2-Complex
Generalized Stokes' Theorem on a 3-Complex
The Helmholtz Decomposition
Algorithm for Computing a Helmholtz Decomposition of a Flow Field
Matrix Representation of Discrete Calculus Identities
Integration by Parts
Other Identities
Elliptic Equations
Variational Principles
Diffusion
Advection
Concluding Remarks
Circuit Theory and Other Discrete Physical Models
Circuit Laws
Steady-State Solutions
Dependent Sources
Energy Minimization
Power Minimization with Nonlinear Resistors
AC Circuits
Connections Between Circuit Theory and Other Discrete Domains
Spring Networks
Random Walks
Gaussian Markov Random Fields
Tree Counting
Linear Algebra Applied to Circuit Analysis
The Delta-Wye and Star-Mesh Transforms
Minimum-Degree Orderings
Conclusion
Applications of Discrete Calculus
Building a Weighted Complex from Data
Determining Edges and Cycles
Defining an Edge Set
Edges from an Ambient Metric
Edges by k-Nearest Neighbors
Edges from a Delaunay Triangulation
Adding Edges via the Watts-Strogatz Model
Defining a Cycle Set
Defining Cycles Geometrically: Cycles from an Embedding
Defining Cycles Algebraically
Cycle Sets and Duality
Deriving Edge Weights
Edge Weights to Reflect Geometry
Edge Weights to Penalize Data Outliers
Univariate Data
Computing Weights from Multivariate Data
Edge Weights to Cause Repulsion
Edge Weights to Represent Joint Statistics
Deducing Edge Weights from Observations
The Underdetermined Case
The Overdetermined/Inconsistent Case
Obtaining Higher-Order Weights to Penalize Outliers
Weights Beyond Flows
Metrics Defined on a Complex
Conclusion
Filtering on Graphs
Fourier and Spectral Filtering on a Graph
Graphs that Are Not Shift-Invariant
The Origins of High Frequency Noise
Energy Minimization Methods for Filtering
The Basic Energy Minimization Model
Iterative Minimization
Extended Basic Energy Model
The Total Variation Model
Filtering with Implicit Discontinuities
Filtering with Explicit, but Unknown, Discontinuities
Filtering by Gradient Manipulation
Nonlocal Filtering
Filtering Vectors and Flows
Translating Scalar Filtering to Flow Filtering
Filtering Higher-Order Cochains
Applications
Image Processing
Regular Graphs and Space-Invariant Processing
Space-Variant Imaging
Three-Dimensional Mesh Filtering
Mesh Fairing
Filtering Data on a Surface
Geospatial Data
Filtering Flow Data-Brain Connectivity
Conclusion
Clustering and Segmentation
Targeted Clustering
Primal Targeted Clustering
Probabilities Assigned to a Subset
Known Labels for a Subset of Nodes
Negative Weights
Dual Targeted Clustering
Dual Algorithms in Three Dimensions
Untargeted Clustering
Primal Untargeted Clustering
Dual Untargeted Clustering
Semi-targeted Clustering
The k-Means Model
Clustering Higher-Order Cells
Clustering Edges
Targeted Edge Clustering
Untargeted Edge Clustering
Applications
Image Segmentation
Social Networks
Machine Learning and Classification
Gene Expression
Conclusion
Manifold Learning and Ranking
Manifold Learning
Multidimensional Scaling and Isomap
Laplacian Eigenmaps and Spectral Coordinates
Locality Preserving Projections
Relationship to Clustering
Manifold Learning on Edge Data
Ranking
PageRank
PageRank as Advection
HITS
Applications
Shape Characterization
Point Correspondence
Web Search
Judicial Citation
Conclusion
Measuring Networks
Measures of Graph Connectedness
Graph Distance
Node Centrality
Distance-Based Properties of a Graph
Measures of Graph Separability
Clustering Measures
Small-World Graphs
Topological Measures
Geometric Measures
Discrete Gaussian Curvature
Discrete Mean Curvature
Applications
Social Networks
Chemical Graph Theory
Conclusion
Appendix A Representation and Storage of a Graph and Complex
General Representations for Complexes
Cells List Representation
Operator Representation
Representation of 1-Complexes
Neighbor List Representation
Appendix B Optimization
Real-Valued Optimization
Unconstrained Direct Solutions
Constrained Direct Solutions
Optimization with Boundary Conditions
Optimization with Linear Equality Constraints
Optimization with Linear Inequality Constraints
Ratio Optimization
Descent Methods
Gradient Descent
Newton's Method
Descent Methods for Constrained Optimization
Nonconvex Energy Optimization over Real Variables
Integer-Valued Optimization
Linear Objective Functions
Quadratic Objective Functions
Pure Quadratic
General Pairwise Terms
Higher-Order Terms
General Integer Programming Problems
Appendix C The Hodge Theorem: A Generalization of the Helmholtz Decomposition
The Helmholtz Theorem
The Hodge Decomposition
Summary of Notation
References
Index
Color Plates