[Lecture Note] Positional Source Coding for Sparse Data

Motivation

The data regime has changed:

• High-dimensinal
• Structured
• Large-volume
• Unknown distribution

Sparse and Structured Data are everywhere:

• images and video
• event-triggered sensing and cyber-physical systems
• Large learning models and distributed learning

From data to bits : why source coding ?

Source-Coding Fundations

Theorem :

Claude Shannon

Fixed-Length Binary Representation – Simple but wasteful

Every outocome costs $b$ bits. Total Length $=Nb$

Two design Lessons from Shannon:

1. vector source coding is necessary
2. Optimal coding depends on the source distribution

Can we approach entropy utilizing data structures ?

Target : a vector code that learns what it needs from the current data vector itself

Unary Coding – The simplest variable-length code

Run-Length Coding – Encode Repetition, Not every symbol

When a sequences are very regular

Powerful when the original have long runs

Elias Gamma Coding - Universal Interger Coding

1. For $n$, let $k=\lfloor\log _2 n\rfloor$
2. Write $k$ leading zeros followed by the biany representation of $n$

Golomb Coding – Match GEometric Run lengths

Arithmetic Coding - Encode a Squence as an interval

Huffman Coding - Optimal Symbol - Wise Prefix Coding

1. Merge the two least-probable nodes
2. Repeat until one hinary tree remains
3. Read root-to-leaf paths as prefix free codewords

But changing models require rebuilding or adaptation

The Trade-off of the calssical Schemes

Run-length representation is a transform; its efficiency depends on the run code

Continuous sources - Quantization and Rate-Distortion

Choose quantization levels thar are accurate

Lloyd’s Algorithm - A practical distortion-minmizing quantize

1. Initialize
2. assign
3. update centroids
4. convergence

Proposed Positional Source-Coding Scheme

Discrete System Model and Design Goal

Discrete inputs first -> continuous-valued sources next

Frequency Information - The Type Vector

Type definition:

$$t(x)=\sum \delta(x_n-l)$$

The type reveals:

• level ordering

Position Information - One support per value

Shrink the supports, then encode their runs

Continuous-Valued Inputs – Quantize for compressibility

Performance Analysis and Numerical Evidence

Theorem 1 - Rate of each indexed support

Empirical types converge to the unknown probablities, so $M_t$ is selected directly from the data

Near Entropy Without a New Codebook

simpler data-derived setup and lower codebook burden - not uncoditional asymptotic dominance

When does the Gap become Small ?

c- Dominant sources

discrete sources - approaching the entropy benchmark

Model Compression for Federated Learning

Real-World Text compression

• Beats Huffman on all six copora

Conclusion and Code-Domain Computation outlook

Takeaway

1. What + where : values that occur – and their positions

2. shrinking supports : exposes run-length structure at every level

3. Lossless + data0adaptive : near entropy under the stated saymptotic model

4. favorable regimes

   dominant and sparse outcome distributions

5. Extensions

   Quantized continuouss data, models and text

• Outlook I - Addition directyly on types and supports

• Outlook II - Multiplication and a research agenda