Questions tagged [compression]
Use this tag for questions about encoding information using fewer bits than the original representation.
115 questions
0 votes
1 answer
127 views
How do RIP constants change when the constraint set is enlarged?
The linear map $\mathcal{A}(\cdot)$ is said to have RIP (restricted isometry property) with a restricted isometric constant ${\delta\in [0,1)}$ if it has the following property: \begin{equation}\label{...
- 53
3 votes
2 answers
527 views
Is there a mistake in the table on page 69 of Cover and Thomas, Elements of Information Theory, Second Edition?
The book reference is here. The problem $(3.13)$ concerns the typical set for a sequence of i.i.d. binary random variables, $X_{1}, X_{2},...,X_{25}$, where the probability that $X_i = 1$ is $0.6$ (...
- 131
0 votes
0 answers
96 views
"Is the recursive delta structure in lexicographic permutations already known?
While studying the lexicographic order of permutations of {0,1,…,n−1, I noticed that the sequence of numeric differences (deltas) between successive permutations — treated as base-10 integers — shows ...
0 votes
0 answers
57 views
Relationship between the Kruskal rank and the coherence of a matrix
I am trying to understand the relationship between the Kruskal rank and the coherence of a matrix $\mathbf{A}$. Specifically, I came across the bound: $$ \begin{equation} \kappa(\mathbf{A}) > \frac{...
- 1
3 votes
2 answers
159 views
Compression of metacomposition strings (https://oeis.org/A133494)
I am looking for a grammar or algorithm to write down what I now call 'metacompositions' (or just compositions of compositions? see https://oeis.org/A133494) of character strings with the absolute ...
0 votes
0 answers
58 views
What's the most compact storage method of a Sequence
Say I have n choices of numbers (Say 1 to n) to fill a blank and there are m Blanks, what would be the most "compact" and efficient way to store a particular sequence of them such that all ...
0 votes
0 answers
94 views
Why standardized LDPC codes, such 3GPP NR, have 4 cycles in Tanner Graph?
We know that short cycles in Tanner Graph are detrimental in error performance. So, Why standardized 5G NR LDPC codes have 4-cycles? 3rd generation Partnership Project (3GPP) had announced Base Matrix ...
- 1
1 vote
0 answers
114 views
Understanding the entropy of the normal distribution
Using the standard definition for $H[p]$, you can show that the entropy of a Normally distributed variable is $$ H(\mu, \sigma^2) = \frac{1}{2} \ln\left(2\pi\sigma^2\right) + \frac{1}{2} $$ in units ...
- 71
3 votes
1 answer
191 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 ...
0 votes
1 answer
71 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 ...
- 75
1 vote
1 answer
60 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 ...
user191074
18 votes
6 answers
5k 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
1 answer
87 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
2 votes
1 answer
75 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 ...
- 444
1 vote
0 answers
163 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 ...
