Graph Wedgelets: Adaptive Data Compression on Graphs based on Binary Wedge Partitioning Trees and Geometric Wavelets
We introduce graph wedgelets - a tool for data compression on graphs based on the representation of signals by piecewise constant functions on adaptively generated binary graph partitionings. The adaptivity of the partitionings, a key ingredient to obtain sparse representations of a graph signal, is realized in terms of recursive wedge splits adapted to the signal. For this, we transfer adaptive partitioning and compression techniques known for 2D images to general graph structures and develop discrete variants of continuous wedgelets and binary space partitionings. We prove that continuous results on best m-term approximation with geometric wavelets can be transferred to the discrete graph setting and show that our wedgelet representation of graph signals can be encoded and implemented in a simple way. Finally, we illustrate that this graph-based method can be applied for the compression of images as well.
Code (0)
등록된 구현이 없습니다.
Tasks
Data CompressionSimilar Papers 제목 키워드 기반
Parallel Stroked Multi Line: a model-based method for compressing large fingerprint databases
With increasing usage of fingerprints as an important biometric data, the need to compress the large fingerprint databases has become essential. The most recommended compression algorithm, even by standards, is JPEG2K. B…
Adaptive Learned Image Compression with Graph Neural Networks
Efficient image compression relies on modeling both local and global redundancy. Most state-of-the-art (SOTA) learned image compression (LIC) methods are based on CNNs or Transformers, which are inherently rigid. Standar…
Image CompressionIngesting High-Velocity Streaming Graphs from Social Media Sources
Many data science applications like social network analysis use graphs as their primary form of data. However, acquiring graph-structured data from social media presents some interesting challenges. The first challenge i…
CPUVocal Bursts Intensity PredictionAn Information-theoretic Framework for the Lossy Compression of Link Streams
Graph compression is a data analysis technique that consists in the replacement of parts of a graph by more general structural patterns in order to reduce its description length. It notably provides interesting explorati…
Sample compression schemes for balls in graphs
One of the open problems in machine learning is whether any set-family of VC-dimension $d$ admits a sample compression scheme of size $O(d)$. In this paper, we study this problem for balls in graphs. For a ball $B=B_r(x)…