Questions tagged [compression]

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

107 questions
Filter by
Sorted by
Tagged with
111 views

Efficient algorithm to solve a sparse recovery problem

I come across with a problem of the form $y=Hx + z \in \mathbb{R}^m$, where $z\in \mathbb{R}^m$ is the noise vector, and $x \in \mathbb{R}^N$ is partially known. $H\in \mathbb{R}^{m \times N}$ can be ...
• 657
41 views

Does Entropy really change depending on the encoding? [closed]

So I'm self studying information theory, and I have a few doubts on entropy and encoding as a whole. I'm trying to compress a simple 16bit signed int sequence of values the best I can. I learned about ...
• 65
1 vote
31 views

What's the maximum possible compression ratio for different languages?

Given two alphabets $A=\{a_1, a_2, ..., a_n\}$ and $B=\{b_1, b_2, b_3, ..., b_m\}$, what is the maximum average compression ratio possible to achieve by bijectively encoding strings of B using strings ...
• 1,303
4k views

Why can't I compress an encrypted file?

Let's say I have a txt file, called harry_potter.txt. I can easily compress it with any compression algorithm. So the entropy of the file is "smaller" ...
• 293
1 vote
47 views

Signal Processing, Data Compression, and Complex Numbers

A detached exercise in my course asks us to be able to simplify the following summation, where j is an imaginary number. The current material involves lossless and lossy compression, however I am ...
• 13
45 views

Compress uniform distribution on the unit circle with one bit with minimum MSE

Consider a uniform distribution over a unit circle. If written in polar coordinates, the pdf of the angle would be $$p(\theta)=\frac{1}{2\pi}.$$ I want to find an encoder $\Theta\to Z$ and a decoder ...
• 368
1 vote
151 views

Tribonacci Code $K(C)=1$

Motivation: The following is a problem I encountered some time ago and it bothers me since I did not solve it as expected. My original way to solve it was using calculus, however, I was expected to ...
88 views

Existence of optimal code (Proof)

I'm reading about Huffman coding, more precisely, the proof that it is an optimal code. Most proofs I found assume an existence of an optimal code (without justifying the existence). This is pointed ...
• 373
1 vote
66 views

• 125
105 views

How do I quantify the amount of information in the following expression?

Suppose that $N = \mbox{factorial}(9999999999)$. The number $N$ is mindbogglingly huge and, yet, can be represented very neatly and compactly as $\mbox{factorial}(9999999999)$. I have two questions: ...
43 views

Given all permutations of N-digits, what is the ratio of random-seeming vs non-random-seeming sequences?

My question is inspired by the comment in this article that the 20 digit sequence 03729563829603547134 seems "more random" than 99999999999999999999. One could use some measure of ...
• 139
94 views

Entropy of "finite length" Bernoulli process

I need to compress the outputs of a Bernoulli process and already decided to use Golomb coding. However, there is something that still feels confusing to me and that I hope to understand better. Maybe ...
1 vote
77 views

finding an optimal set of relative frequencies that generate an optimal prefix-free code (Huffman)

A (memoryless) source generates symbols $a_1, a_2, \dots, a_n$ with relative frequencies $f_1, f_2, \dots, f_n$. Assume that the frequencies are all positive. An optimal prefix-free code for this ...
• 346
1 vote
61 views

How is Kolmogorov complexity calculated?

In lectures, my professor discussed Kolmogorov complexity for 10 minutes but I have too many questions opened. My professor claimed (and I was able to prove it myself) that $|K(X)| \leq |x|+1$. But ...
• 21
192 views

Is the Kolmogorov complexity of any string equally low?

I'm learning just now about this topic so this might be the most naive of the questions. So, if I understand it correctly, the string: ...
• 271
55 views

What is the gradient operator in this context?

I've been trying to learn math recently by implementing papers that I find related to projects I'm working on. Usually when I encounter a problem, I just google it, find the answer and continue on but ...
1 vote
37 views

Compression by indexing sequences

I am curious if there are applications for something along the following lines, and how does it compare to existing methods? (Keep in mind that I know almost nothing about compression.) Is there a ...
• 515
74 views

• 238
56 views

Derivative of $\lVert Ax-y \rVert _{2}^{2l}$

$A$ is an $m \times n$ matrix, $x$ is a $n \times 1$ vector, $y$ is an $m \times 1$ vector. Is this solution true? Solution: Let $$f\left( x \right) = \left( Ax-y \right) ^T\left( Ax-y \right) ,$$ ...
• 628
1 vote
155 views

• 3,356
50 views

Sending a pair of coordinates in $[0,1]^2$ using a small number of bits

Consider a random variable $X$ that is uniform on $[0,1]^2$. I want to send this variable to a receiver, using $2k$ bits, with an encoding $Y$. The receiver knows the prior distribution and when ...
• 431
671 views

Is compressibility a good test for randomness of a pseudorandom sequence?

I am interested in tests and definitions of randomness of a sequence generated by a pseudo-random number generator. A similar question was asked a few years ago, and the response was to use a ...
• 160
1 vote