Sign inSign up
Laplacian Matrices of Graphs: Algorithms and Applications thumbnail
slide-image
Pause
Mute
Subtitles not available
Playback speed
0.25
0.5
0.75
1
1.25
1.5
1.75
2
Full screen

Laplacian Matrices of Graphs: Algorithms and Applications

Published on Aug 20, 20154445 Views

Daniel A. Spielman

The Laplacian matrices of graphs arise in many fields including Machine Learning, Computer Vision, Optimization, Computational Science, and of course Network Analysis. We will explain what these matr

COLT 2015 - Paris

Related categories

Active LearningComputational Learning TheoryOn-line LearningReinforcement LearningSemi-supervised Learning

Chapter list

Laplacian Matrices of Graphs: Algorithms and Applications 00:00
Outline00:23
Interpolation on Graphs - 101:18
Interpolation on Graphs - 202:30
Interpolation on Graphs - 302:54
Spectra of The Laplacian matrix03:24
Measuring boundaries of sets - 106:05
Measuring boundaries of sets - 206:52
Measuring boundaries of sets - 307:05
Measuring boundaries of sets - 407:05
Spectral Clustering and Partitioning08:11
Computing Eigenvectors: the power method - 108:12
Computing Eigenvectors: the power method - 209:23
Computing Eigenvectors: the power method - 310:06
Analysis of the power method (smallest eigs)11:17
Analysis of the inverse power method12:29
Can quickly solve Laplacian and SDD equations13:26
Approximate solutions to linear equations15:07
Other solvers for Laplacian and SDD equations17:28
The Laplacian matrix of a graph - 120:05
The Laplacian matrix of a graph - 220:38
The Laplacian matrix of a graph - 321:33
Laplacian Matrices of Weighted Graphs - 223:50
Laplacian Matrices of Weighted Graphs - 125:11
Laplacians in Linear Programming25:28
Isotonic Regression (Ayer et. al. ‘55) - 127:06
Isotonic Regression (Ayer et. al. ‘55) - 227:48
Isotonic Regression (Ayer et. al. ‘55) - 328:11
Isotonic Regression (Ayer et. al. ‘55) - 428:21
Fast IPM for Isotonic Regression29:24
Linear Program for Isotonic Regression - 129:57
Linear Program for Isotonic Regression - 230:52
Linear Program for Isotonic Regression - 331:20
Linear Program for Isotonic Regression - 431:49
Linear Program for Isotonic Regression - 532:22
Linear Program for Isotonic Regression - 532:23
Linear Program for Isotonic Regression - 634:25
Linear Program for Isotonic Regression - 735:55
Approximating Graphs - 136:52
Approximating Graphs - 238:05
Approximating Graphs - 338:46
Solutions of equations are similar39:15
If can solve equations in LH can solve LG40:15
Sparsifying Graphs - 141:23
Sparsifying Graphs - 242:29
Sparsifying Graphs - 343:30
Sparsifying Graphs - 445:16
Solving Equations with Sparsifiers (Peng­‐S ‘14) - 146:26
Solving Equations with Sparsifiers (Peng‐S ‘14) - 248:15
Solving Equations with Sparsifiers (Peng­‐S ‘14) - 348:51
Solving Equations with Sparsifiers (Peng‐S ‘14) - 449:46
Solving Equations with Sparsifiers (Peng‐S ‘14) - 550:37
Symmetrizing the formula - 151:41
Symmetrizing the formula - 252:38
Solving Equations with Sparsifiers (Peng ‐S ‘14)53:55
Sparsified Cholesky Factorization (Lee-Peng-S ‘15)55:27
Cholesky Factorization on Laplacians - 156:56
Cholesky Factorization on Laplacians - 257:43
Cholesky Factorization on Laplacians - 358:03
Cholesky Factorization on Laplacians - 458:43
Cholesky Factorization on Laplacians - 559:01
Cholesky Factorization on Laplacians - 659:04
Cholesky Factorization on Laplacians - 759:07
Cholesky Factorization on Laplacians - 859:20
Sparsified Cholesky Factorization (Lee-Peng-S ‘15) - 101:00:16
Sparsified Cholesky Factorization (Lee-Peng-S ‘15) - 201:01:07
Sparsified Cholesky Factorization (Lee-Peng-S ‘15) - 301:02:33
Sparsified Cholesky Factorization (Lee-Peng-S ‘15) - 401:02:39
Sparsified Cholesky Factorization (Lee-Peng-S ‘15) - 501:02:43
Next Steps01:03:11
To learn more01:05:02