Multiresolution Graph Models
summary
Argues that multiresolution matrix factorization (MMF) reframes graph wavelets as a multilevel matrix factorization using local k‑point rotations (e.g. Givens rotations), producing a sparse, localized hierarchical basis that compresses diffusion or adjacency operators. Provides greedy and randomized algorithms, claims near O(n log n) scaling for randomized versions, and shows small-scale experiments where MMF outperforms treelets on hierarchical or Kronecker‑like graphs but performs poorly on purely random matrices; implementation is working but not yet demonstrated at million‑node scale.
AI-written summary · about
chapters (22)
- 0:00Multiresolution Graph Models
- 1:17Spectral Graph Theory
- 5:32Multiresolution analysis
- 10:06The multiresolution mantra
- 14:40Recent approaches
- 16:06Multiresolution on R
- 19:12Multiresolution on discrete spaces
- 22:27General principles
- 24:06Key observation
- 25:48Multiresolution factorization
- 28:37Form of the Q&local rotations
- 30:09The optimization problem
- 31:51Optimization details — Jacobi MMF
- 35:07Hierarchical structure
- 35:43Applications
- 37:03Relationship to Diffusion Wavelets
- 38:33Relationship to Treelets
- 39:46Relationship to multigrid, fast multipole, and hierarchical matrices
- 42:15Hölder condition
- 43:41A-rank homogeneous matrices
- 44:36Experimental Results
- 47:42CONCLUSIONS
related talks
46mSolvable Model of Unsupervised Feature Learning
01h 11mTensor Decompositions: Uniqueness and Smoothed Analysis
01h 03mRecent Progress in High-Dimensional Learning
37mA Bluffer's Guide to Dimension Reduction
36mLow-rank matrix approximations in Python
01h 00mTensor Graphical Models For Complex And High Dimensional Data
36mThe Rank of Sparse Random Matrices
54mGraph Machine Learning & Random Graph Models