Combinatorial Hodge Theory and Information Processing l898 姚远 2010.3.25
Combinatorial Hodge Theory and Information Processing 姚 远 2010.3.25
Hodge decomposition a Vector calculus: Helmholtz's decomposition ie. vector fields on nice domains may be resolved into irrotational (curl-free and solenoidal(divergence-free) component vector fields F=-Vy+V×A yp scalar potential, A vector potential a Linear algebra: additive orthogonal decomposition of a skew-symmetric matrix into three skew-symmetric matrices W=W1+W2+W3 W,=ve/-ev, W2 clique-consistent, W3 inconsistent Graph theory: orthogonal decomposition of network flows into acyclic and cyclic components
Hodge Decomposition
Visual Image patches Ann Lee, Kim Pedersen, David Mumford(2003)studies statistical properties of 3x3 high contrast image patches of natural images(from Van Heteran's database) Gunnar Carlsson, Vin de Silva, Tigran Ishkhanov, Afra Zomorodian(2004-present) found those image patches concentrate around a 2-dimensional klein bottle imbedded in 7-sphere They build up simplicial complex from point cloud data 1-D Harmonic flows actually focus on densest region 3 major circles
Visual Image Patches • Ann Lee, Kim Pedersen, David Mumford (2003) studies statistical properties of 3x3 high contrast image patches of natural images (from Van Heteran’s database) • Gunnar Carlsson, Vin de Silva, Tigran Ishkhanov, Afra Zomorodian (2004-present) found those image patches concentrate around a 2-dimensional klein bottle imbedded in 7-sphere • They build up simplicial complex from point cloud data • 1-D Harmonic flows actually focus on densest region -- 3 major circles
1-D Harmonic Flows on the space of3×3 Image Patches 左上图: Klein bottle of 3x3 Image Patch Space(Courtesy of Carlsson-shkhanov circles Prescind on NOnin Lotte 2007 左下图: Harmonic flows focus on 3 major circles where most of data concentrate
1-D Harmonic Flows on the space of 3x3 Image Patches • 左上图：Klein Bottle of 3x3 Image Patch Space (Courtesy of Carlsson-Ishkhanov, 2007) • 左下图：Harmonic flows focus on 3 major circles where most of data concentrate
Ranking Psychology: LL. Thurstone(1928)(scaling) Statistics: M. Kendall(1930s, rank corellation), F Mosteller, Bradley-Terry, .. P. Diaconis(group theory), etc Economics: K Arrow, A Sen(voting and social choice theory, Nobel Laureates Computer Science: Google' s PageRank, HITS, etc We shall focus on ranking in the sequel as the construction of abstract simplicial complex is more natural and easier than point cloud data
Ranking Psychology: L. L. Thurstone (1928) (scaling) Statistics: M. Kendall (1930s, rank corellation), F. Mosteller, Bradley-Terry,…, P. Diaconis (group theory), etc. Economics: K. Arrow, A. Sen (voting and social choice theory, Nobel Laureates) Computer Science: Google’s PageRank, HITS, etc. We shall focus on ranking in the sequel as the construction of abstract simplicial complex is more natural and easier than point cloud data