Spectral Algorithms: From Theory to Practice 2014
2014-10-27..2014-10-31
Berkeley, United States
[Fast Algorithms via Spectral Methods 2014, Information Theory, Learning and Big Data (Simons Institute, 2015), Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013), Learning, Algorithm Design and Beyond Worst-Case Analysis, Randomized Numerical Linear Algebra and Applications 2018, Semidefinite Optimization, Approximation and Applications 2014]
| title | author | length |
|---|---|---|
| Topic Modeling: A Provable Spectral Method | Ravi Kannan | 49m |
Provides a provable pipeline that recovers K topic vectors by combining threshold then SVD with k‑means and a catchword extraction step, under four explicit… | ||
| Exact Recovery via Convex Relaxations | Moses Charikar | 51m |
Convex relaxations often recover exact clusterings under random models: experiments show a pairwise LP is integral 88% of the time, strengthened to 100% for… | ||
| The Impact of Regularization in Spectral Clustering | Bin Yu | 38m |
Regularizing the graph by adding a constant to the adjacency (or to degrees) reduces eigenvector variability and uncovers large communities that unregularized… | ||
| Multiscale Analysis on and of Graphs | Mauro Maggioni | 47m |
Claim: a large sparse weighted graph is compressible into a sequence of much smaller graphs that preserve diffusion up to a user epsilon. Method uses the… | ||
| Multiresolution Graph Models | Risi Kondor | 53m |
Argues that multiresolution matrix factorization (MMF) reframes graph wavelets as a multilevel matrix factorization using local k‑point rotations (e.g. Givens… | ||
| Some Probabilistic Uses of Dirichlet Eigenvectors | Persi Diaconis | 56m |
Proves quantitative rates of convergence to the quasi-stationary distribution for absorbing chains, gives the closed-form cosine law on a path and shows… | ||
| Independent Component Analysis: From Theory to Practice and Back | Santosh Vempala | 52m |
Problem: recover unknown linear mixing A from samples X = A S where S has independent coordinates and at most one Gaussian. Algorithm: make samples isotropic… | ||
| Tensor Methods for Learning Latent Variable Models: Theory and Practice | Animashree Anandkumar | 52m |
Shows that method-of-moments using third-order tensor moments plus whitening via rank-k SVD gives consistent, polynomial-time recovery of latent-variable… | ||
| Random Walks on Directed Graphs | Fan Chung | 45m |
Defines a symmetric normalized Laplacian via Perron vector for a directed transition matrix and proves Cheeger-type bounds: the spectral gap controls cut… | ||
| Random Embeddings, Matrix-valued Kernels and Deep Learning | Vikas Sindhwani | 56m |
Claim: large-scale randomized kernel models match deep nets on a speech benchmark when scaled and optimized. Implementation uses random Fourier features (up to… | ||
| A Statistical Model for Tensor Principal Component Analysis | Andrea Montanari | 47m |
Model: symmetric spiked tensor X = beta v0^{\otimes K} + Z with Gaussian rotation‑invariant noise; the statistical threshold is constant: MLE succeeds once… | ||
| Graph Matching: Relax or Not? | Alex Bronstein | 56m |
Convex quadratic relaxation over pseudo-stochastic matrices recovers the exact permutation whenever adjacency matrices have simple spectrum and no eigenvector… | ||
| Random Walks on Simplicial Complexes and Isoperimetric Inequalities | Sayan Mukherjee | 46m |
Extends spectral graph ideas to simplicial complexes by working with the Hodge Laplacian and defining concrete up/down random walks on oriented k‑cells… | ||
| Connection Laplacian, Hodge Laplacian, and Tensor Laplacian of a Graph | Lek-Heng Lim | 53m |
Argues that the Cheeger constant equals the second eigenvalue of the 1‑Laplacian and defines that 1‑Laplacian as B^T sign(Bf) so the Rayleigh/Lagrange… | ||
| Spectral Algorithms for Learning Latent Variable Models | Sham Kakade | 49m |
Spectral methods use explicit moment equations and tensor algebra to recover latent mixtures: three-word documents suffice for identifiable topic vectors… | ||
| Comparing the Theory and Practice of Spectral Algorithms to Combinatorial Flow Algorithms for ... | Dorit Hochbaum | 59m |
Dorit Hochbaum, UC Berkeley
Spectral Algorithms: From Theory to Practice
http://simons.berkeley.edu/talks/dorit-hochbaum-2014-10-30 | ||
| On the Estimation of the Cheeger Constant | Ery Arias-Castro | 45m |
Proves that for fixed measurable sets with positive reach the Rn-neighborhood graph cut converges to the continuous perimeter when Rn → 0 slowly, using… | ||
| Applied Hodge Theory | Yuan Yao | 43m |
Linear-algebra Hodge theory on clique complexes decomposes pairwise edge data exactly into orthogonal components: a solvable gradient (global) component found… | ||
| The Hidden Convexity of Spectral Clustering | Luis Rademacher | 40m |
Shows that K-way spectral clustering is recovered exactly by maximizing a contrast F(u)=sum_i G(u·x_i) on the sphere when G(√t) is strictly convex (plus a mild… | ||
| Robust Spectral Diffusions for Data Applications | David Gleich | 49m |
Shows that PageRank is a spectral relaxation of an s–t min‑cut construction and that the push algorithm exactly solves a one-norm regularized two-norm problem… | ||
| Learning Functions and Sets with Spectral Regularization | Lorenzo Rosasco | 46m |
Presents a concrete alternative to penalized learning: replace ridge/Tikhonov by spectral filter functions and implement them by early-stopped iterations… | ||
| Some Applications in Human Behavior Modeling | Jerry Zhu | 42m |
Models verbal fluency as a random walk observed only at first visits, uses an absorbing random walk construction to compute hit probabilities and builds a… | ||
| Spectral Approaches to Nearest Neighbor Search | Alexandr Andoni | 49m |
Proposes reducing approximate nearest neighbor to a spectral graph problem, building a sparsified neighborhood graph and embedding via Laplacian eigenmaps so… | ||
| An Efficient Parallel Solver for SDD Linear Systems | Richard Peng | 53m |
Presents an algorithm that solves SDD (graph Laplacian) systems with nearly-linear work and polylog depth by building an “approximate inverse chain”… | ||
| Graph Based Processing of Big Images | Hui Han Chin | 49m |
Rewrites common image tasks (TV denoising, Poisson blending, spectral segmentation) as a single graph Laplacian linear system so one solver can be reused… | ||
| nothing matches | ||