# Questions tagged [compression]

Use this tag for questions about encoding information using fewer bits than the original representation.

44 questions
35 views

### Combine two numbers into one and extract them back

I have two numbers(A,B), I want to combine the numbers into one(C) The constraints are A's range = 0 to 3 (4 values) B's range = 0 to 900 (900 values) C must have a maximum of 3 digits only. ...
11 views

### Compactly represent nearby GPS co-ords with equal [accuracy/error/density]

For the purpose of discussion assume the GPS geoid is a sphere of 6378137 metres radius The geoid has a surface area of : 4 * pi * 6378137 metres^2 = 80150033.4 m^2 I need to send GPS coordinates ...
109 views

### How to maximize the expected number of corrected guesses?

A, B are to play heads or tails for $N$ rounds. They win a round if both guess correctly. A and B are allowed to communicate their strategy before the game starts. A knows the full sequence of $N$ ...
15 views

### The spectrum of a compression of nonsymmetric matrix

If $A\in\mathbb{R}^{n\times n}$ with a spectrum $eig(A)\subset\mathbb{C}$. Define a matrix $P\in\mathbb{R}^{n\times m}$, where $m<n$ and $P$ is a nonnegative matrix, i.e. its entries are either ...
24 views

### Encoding numbers from 0 to 255 using Huffman coding.

How can I encode numbers from 0 to 255 using Huffman coding (or any other code), so that each number (especially the largest numbers such as 255) wouldn't take 8 bits of binary space? In other words, ...
127 views

### Compressing the primes using simple addition?

Consider the sets of integers $$A = \{1, 3, 7, 13, 27\} \\ B = \{4, 10, 16, 40, 100\}$$ Elementwise addition of sets $A, B$ looks like $A + B := \{ a + b: a \in A, b \in B\}$. Now elementwise-add ...
22 views

### How much BPS(Bits per symbol) is enough to call a compression algorithm good, with respect to entropy?

Consider a general purpose lossless data compression algorithm, It compresses a randomly generated binary file of 100MB size, with random I mean I wrote a small Script to create a file with random ...
45 views

### Manual Text Compression Algorithm (done by hand)

Last year (I'm in 10th grade), during most unit/chapter tests, we were allowed to bring notes. We could prepare a 3 x 5 in. (7.62 x 12.7 cm) index card at home, and cram it with as many notes as ...
11 views

### Performance of conventional estimation approaches for sparse recovery

If we use conventional estimation methods (like Least squares or MMSE) to recover a sparse vector for which we have random measurements, is the result accurate? Why?
57 views

### Does Ramsey theory prove that all sufficiently long random sequences can be slightly compressed?

First, my apologies if this has already been asked and answered. I did search this community for five to ten minutes looking for similar questions and found none. My lay understanding of Ramsey ...
27 views

### Is compressed sensing for digital signals or could also be applied for discrete time signals?

I was wondering if is compressed sensing for digital signals? or could also be applied for discrete time signals? What I mean is lets say I have a sampled but not quantized signals, can I find the ...
49 views

### Constraint on number of codes of maximum length in a binary Huffman code.

A Random Variable '$X$' take values from a discrete alphabet $K = \{k_1, k_2, k_3,k_4 \}$, with probability mass function {$p(k_i)$} = {$0.6, 0.2, 0.15, 0.05$}. The constructed Binary Huffman codes ...
13 views

### Generating Huffman codes from unsorted code lengths.

As an exercise for myself, I am writing an Ogg Vorbis decoder. Part of the decoding process involves generating Huffman codes from a series of code lengths that is later used when decoding audio ...
60 views

### compressive sensing and biorthogonal wavelet matrix

I want to use compressive sensing to reconstruct an image from fewer samples. My problem is with Psi matrix which I want to be Biorthogonal wavelet coefficients but I don't know how to define it. I ...
27 views

### Can you help me find a Fourier transform-able approximation function basis for compression?

I have four-dimensional, piece-wise smooth, discrete (4D voxel) data that I want to approximate/ compress using as few basis functions as possible. The data are discontinuous in three dimensions, ...
48 views

### compressing random permutation of N

Is it possible to compress the given random permutation of any integer using N*(lg(N) -1) bits? For example if N= 512, then it could be represented using 512 * 9 = 4608 bits and its optimal ...
29 views

### Getting the compression ratio

Given a picture of $200x200$ pixels. Without compression, each pixel uses $10$ bits to represent a color. This image is compressed lossless by giving the colors a new coding. The coding of ...
36 views

### how to compress a 1D sampled signal

Assume you have a 1D function f(x) that you would like to sample and then reconstruct. What are some techniques of sampling that function with the fewest samples but to still get close to ...
64 views

### Is there any way to compress two or more numbers which I can get back without any errors?

I want to find out if there are any function $f$ which takes, lets say two numbers $a$, $b$ and outputs $x$, such that $f^{-1}(x)$ returns $a$ and $b$. $$f(a,b) = x$$ $$f^{-1}(x) = a,b$$ I think ...
40 views

### Can't understanding information entropy and data compression, for beginners

I watched a very well done video about information entropy, and I thought I got the concept in my mind but then I asked my self a question that denied every certainty I had. The video if you are ...
39 views

### Proving that at least half of all words with length bigger than $n$ are not compressible.

We say that a word is not compressible, if it's Kolmogorov-Complexity is bigger than the length of the word. We know that for every natural number $n$, we have at least one word which is not ...
110 views

### Typical Sets In Source Coding

I'm struggling with the following question: For typical sets in source coding, decide if it is true or false and provide a detailed proof. My ideas: a. true, since by definition we get 2^log(p) > 2^...
339 views

### Is compression possible on a uniform distribution of symbols?

I was reading about limits of data compression and I had this question that kept me thinking. Alphabet set: Set of all the unique symbols in the input data Q. If the distribution over the alphabet ...
385 views

### Change of basis for image compression (toy example)

In linear algebra course, prof. Strang uses JPEG image compression as an example of basis change (lecture 31). I would like to make sure that I understood the concept. For simplicity, let's assume ...
47 views

### How does the escape code in a Markov chain compression help?

This question is regarding the following video by google developers (after 11:20 mins) . He explains how a markov probability updated table can be used to do compression. Since it's a dynamic ...
195 views

### how to compress sound waves?

there is voice sound wave as series of numbers: we sample them into discrete numbers like: i need to compress it in half. most existing ways as simple as ignoring even samples to become half length ...
333 views

### Matrix Compression: Mapping between padded Compressed Row Storage and Compressed Column Storage?

Context There are a handful of ways to compress a matrix, $\mathbf{M}$, but Compressed Row Storage (CRS) is fairly popular due to its fast access. Similarly, there exists Compressed Column Storage (...
111 views

### For square images, do SVD and diagonalization always produce the same result in compressing images?

If not, then does SVD always work better than diagonalization? It seems to me that for square images, diagonalization is the more straightforward method when compressing images in MATLAB. However, I ...
101 views

### Shifting and compressing signal

I have a signal $$x[n] = n(u[n] - u[n-7])$$ So it is a discrete signal that goes from 0 to 6 when $n$ goes from 0 to 6, then it is 0 for all other $n$. I want to figure out what $x[4n+3]$ will look ...
317 views

### no $k$-sparse vector in null space of $A$ where $y=Ax$

Here is a part of my notes on compressed sensing. Suppose we are given an underdetermined linear system of equations $Y=AX$. For a unique solution, What we need: subtraction of no two $k$-sparse ...
214 views

### How to find Turing Machine for given arbitrary output

Are there general methods / algorithms for finding a Turing Machine that will output a given binary number? For example, I want the machine to write ...
516 views

### squashed sine wave

Sinewave I'm slightly out of my comfort zone with this one. I need to produce a function for use in an animation, but a sine wave isn't quite right. I tried adding a square wave, but that didn't work ...
4k views

### Is there any online Huffman code/decoder?

I need to see and work with Huffman code and see how does it compress data. Anyone has any link of online Huffman coder and decoder (compressor)?
63 views

### Is there any two way algorithm for compressing numbers?

I have this question that is there any way we can convert a number to another number with less character in the new number? For example, Imagine we have 811008 and if we divide this 13 times by 2, we ...
865 views

### How is this possible to convert a long string to a number with less characters?

I'm going to write a program (function) that can convert a long string to a number. For this, first I convert each character (letter) to a number; like ...
363 views

### Compressing permutations

I am looking at a compression technique that finds a permutation of the bits of a 64-bit block of data that collects all 1 bits at the beginning of the block, and sends all 0 bits to the end of the ...
86 views

### Math of Repetition

Let R = A (A | B) (A | B | C) (A | B | C | D) ... be an R-Form(A sort of repetition matching grammar). Where A,B,C,D,... are symbols that allow equality comparison. Any sequence of A,B,C,D,... can ...
26 views

### Compressing bitchains

Let there be a bit-chain consisting of $n$ characters with the following rules: The probabilities of the first character being $0$ and $1$ are $1/2$. From then on the probabilities are $p$ when the ...
24 views

### Source coding with 2 distinct distributions and entropies

I'm learning about source coding, and many of the books/resources I've read give examples of the source $X^n$ being defined as a sequence of iid random variables. How about when the sequence is ...
108 views

### What's theoretical maximum information compression rate?

Let's say I've got a random bit sequence s and a reversible function f(s), for which the following statement ...
880 views

### Is there a difference between cosine and sine transform?

Surely both should work with the same set of functions. Why is only cosine transform used in JPEG? Why not sine? It seems that using fourier transform rather than cosine transform would result in ...
127 views

### Lempel-Ziv-Welch Encoding of single character sequence

So I have this typical exam question: Consider an LZW coder for an alphabet with 32 symbols (thus represented by 5-bit symbols) using a dictionary of size 256 (thus indexed by 8-bit words). The ...
I can store any undirected simple graph N vertices using $b = (N-1)N/2$ bits, by creating a mask of the edges on the upper diagonal of the adjacency matrix. For example the adjacency matrix of $K_3$ ...