所有 $\ell_{p}$-范数中保序回归的快速、可证明算法

Jul, 2015

所有 $\ell_{p}$-范数中保序回归的快速、可证明算法

Fast, Provable Algorithms for Isotonic Regression in all $\ell_{p}$-norms

Rasmus Kyng, Anup Rao, Sushant Sachdeva

TL;DR本论文提出了一种实用的算法，可以计算出在给定有向无环图和顶点上的一组值的约束下，满足所有给定的加权Lp范数最小化的保序回归问题，同时提供严格的性能保证。

Abstract

Given a directed acyclic graph $G,$ and a set of values $y$ on the vertices, the isotonic regression of $y$ is a vector $x$ that respects the partial order described by $G,$ and minimizes $||x-y||,$ for a specifi