The method of types presented by Csiszar and Korner is a central tool used to develop and analyze the basic properties and constraints on sequences of data over finite alphabets. A central problem considered using these tools is that of data compression, and specifically lossy data compression. In this work we consider this very problem, however, instead of sequences of data we consider directed graphs. We show that given a more natural distortion measure, fitting the data structure of a directed graph, the method of types cannot be applied. The suggested distortion measure aims to preserves the local structure of a directed graph. We build on the recent work of Barvinok and extend the method of types to the two dimensional setting of directed graphs. We see that the extension is quite natural in many ways. Given this extension we provide a lower and upper bound on the rate-distortion problem of lossy compression given the suggested distortion measure.
翻译：Csiszar 和 Korner 提出的类型方法,是用来开发和分析关于定数字母数据序列的基本特性和限制因素的一个核心工具。考虑使用这些工具时的一个中心问题是数据压缩,特别是数据压缩。但是,在这项工作中,我们考虑的正是这个问题,而不是我们所考虑的定向图表数据序列。我们表明,如果采取更自然的扭曲措施,与定向图表的数据结构相匹配,则无法应用类型方法。建议的扭曲措施旨在保护定向图表的本地结构。我们以Barvinok 的近期工作为基础,将类型方法扩大到定向图形的两维设置。我们看到,扩展在许多方面都是非常自然的。鉴于这一扩展,我们为建议的扭曲计量提出的损失率和扭曲问题提供了一个更低的上限。
相关内容
- Today (iOS and OS X): widgets for the Today view of Notification Center
- Share (iOS and OS X): post content to web services or share content with others
- Actions (iOS and OS X): app extensions to view or manipulate inside another app
- Photo Editing (iOS): edit a photo or video in Apple's Photos app with extensions from a third-party apps
- Finder Sync (OS X): remote file storage in the Finder with support for Finder content annotation
- Storage Provider (iOS): an interface between files inside an app and other apps on a user's device
- Custom Keyboard (iOS): system-wide alternative keyboards
Source: iOS 8 Extensions: Apple’s Plan for a Powerful App Ecosystem
微信扫码咨询专知VIP会员