• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >Algorithms for Lipschitz Extensions on Graphs.
【24h】

Algorithms for Lipschitz Extensions on Graphs.

机译：图上Lipschitz扩展的算法。

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We develop fast algorithms for solving regression problems on graphs where one is given the value of a function at some vertices, and must find its smoothest possible extension to all vertices. The extension we compute is the absolutely minimal Lipschitz extension, and is the limit for large p of p-Laplacian regularization. We present an algorithm that computes a minimal Lipschitz extension in expected linear time, and an algorithm that computes an absolutely minimal Lipschitz extension in expected time O(mn). The latter algorithm has variants that seem to run much faster in practice. These extensions are particularly amenable to regularization: we can perform l0-regularization on the given values in polynomial time and 1i-regularization on the initial function values and on graph edge weights in time O(m 3/2).;Our definitions and algorithms naturally extend to directed graphs.
机译：我们开发了快速算法来解决图上的回归问题，在该图上给定一个函数在某些顶点处的值，并且必须找到对所有顶点的最平滑扩展。我们计算的扩展是绝对最小的Lipschitz扩展，并且是p-Laplacian正则化的大p的限制。我们提出了一种算法，该算法在期望的线性时间内计算最小的Lipschitz扩展，以及一种算法，在期望的时间O（mn）中计算绝对最小的Lipschitz扩展。后一种算法的变体在实践中似乎运行得快得多。这些扩展特别适合于正则化：我们可以对多项式时间中的给定值执行l0正则化，并对初始函数值和时间O（m 3/2）中的图边缘权重执行1i正则化。;我们的定义和算法自然地扩展到有向图。

著录项

  • 作者

    Rao, Anup.;

  • 作者单位

    Yale University.;

  • 授予单位 Yale University.;
  • 学科 Mathematics.;Computer science.;Applied mathematics.
  • 学位 Ph.D.
  • 年度 2015
  • 页码 91 p.
  • 总页数 91
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号