Graph clustering and the nuclear Wasserstein metric

Estudiamos el problema de aprender la estructura de clusters de un grafo aleatorio G usando una muestra independiente. Proponemos una formulación robusta basada en la métrica de Wasserstein de este problema de optimización y probamos que se puede formular como un problema tratable de optmización con...

Full description

Autores:
Roux Uribe, Daniel de
Tipo de recurso:
Fecha de publicación:
2018
Institución:
Universidad de los Andes
Repositorio:
Séneca: repositorio Uniandes
Idioma:
eng
OAI Identifier:
oai:repositorio.uniandes.edu.co:1992/35098
Acceso en línea:
http://hdl.handle.net/1992/35098
Palabra clave:
Optimización matemática - Investigaciones
Matemáticas
Rights
openAccess
License
http://creativecommons.org/licenses/by-nc-sa/4.0/
Description
Summary:Estudiamos el problema de aprender la estructura de clusters de un grafo aleatorio G usando una muestra independiente. Proponemos una formulación robusta basada en la métrica de Wasserstein de este problema de optimización y probamos que se puede formular como un problema tratable de optmización convexa. Damos garantías teóricas exactas para este problema cuando la métrica de Wasserstein es inducida por la norma nuclear y G se distribuye según el modelo estocástico por bloques. Finalmente presentamos nuestra implementación en Julia del algoritmo propuesto y mostramos su desempeño numérico en datos sintéticos.