Machine Learning Summer School on Theory and Practice of Computational Learning

Fitting a Graph to Vector Data

author:Daniel A. Spielman, Department of Computer Science, Yale University
published: July 30, 2009, recorded: June 2009, views: 109

Turn off the lights

You might be experiencing some problems with Your Video player.

Slides

Slides
0:00	Fitting a Graph to Vector Data
1:22	Find a natural weighted graph on V = {1, …, n} that is
2:47	Helps solve TCS problems on the vectors
3:00	Outline
4:40	Standard ways to make graphs
6:32	Our first proposal (1)
7:36	Our first proposal (2)
7:55	Motivation (1)
10:10	Motivation (2)
11:16	Motivation (3)
12:09	Motivation (4)
12:23	Motivation, tricky example (1)
12:34	Motivation, tricky example (2)
12:54	Motivation, tricky example (3)
13:09	Motivation, tricky example (4)
13:18	Motivation, tricky example (5)
14:16	Motivation, fixing bad example (1)
15:01	Motivation, fixing bad example (2)
16:57	Example (1)
18:15	Example (2)
19:03	Example (3)
20:31	Unique?
21:07	Related to
22:06	In terms of the graph Laplacian (1)
23:13	In terms of the graph Laplacian (2)
24:36	Sparse Solution
28:16	Sparsity
28:47	Degrees on real data (1)
29:21	Degrees on real data (2)
29:51	Example for which graphs are not unique
31:40	Planarity (1)
32:09	Planarity (2)
32:28	Planarity, proof (1)
33:51	Planarity, proof (2)
35:07	Classification and Regression Experiments
36:25	Classification Experiments (1)
36:52	Classification Experiments (2)
39:16	Classification Experiments (3)
39:53	Regression Error
40:25	Clustering Experiments (0.1-soft) (1)
41:14	Clustering Experiments (0.1-soft) (2)
41:49	Choosing number vectors for spectral
42:47	Quadratic Program for Edge Weights
43:39	Objective function is quadratic
44:11	Soft graph program (1)
44:36	Soft graph program (2)
45:13	Soft graph program, as NNLSQ
45:53	Computing Soft graph quickly
46:52	Computation Time (secs)
47:35	Approximate Sparse Solutions (1)
48:54	Approximate Sparse Solutions (2)
50:06	Sparsification (1)
50:55	Sparsification (2)
51:32	Lovasz’s Graphs
53:38	Open Questions

Related content

Visitors who watched this lecture also watched...