Fitting a Graph to One-Dimensional Data

Given n data points in R^d, an appropriate edge-weighted graph connecting the data points finds application in solving clustering, classification, and regresssion problems. The graph proposed by Daitch, Kelner and Spielman (ICML~2009) can be computed by quadratic programming and hence in polynomial...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-09
Main Authors: Siu-Wing, Cheng, Cheong, Otfried, Lee, Taegyoung, Ren, Zhengtong
Format: Article
Language:English
Subjects:
Algorithms
Clustering
Data points
Dynamic programming
Polynomials
Quadratic programming
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given n data points in R^d, an appropriate edge-weighted graph connecting the data points finds application in solving clustering, classification, and regresssion problems. The graph proposed by Daitch, Kelner and Spielman (ICML~2009) can be computed by quadratic programming and hence in polynomial time. While a more efficient algorithm would be preferable, replacing quadratic programming is challenging even for the special case of points in one dimension. We develop a dynamic programming algorithm for this case that runs in O(n^2) time.
ISSN:2331-8422