# Questions tagged [compression]

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

58 questions
Filter by
Sorted by
Tagged with
47 views

### Why are cryptographic hash functions apparently easier to create than lossless compression schemes?

Both cryptographic hash functions and lossless compression schemes map certain long sequences of bits to shorter sequences of bits. Theoretically, lossless compressions schemes are injective, while ...
39 views

### Difference between Shannon Entropy limit and Kolmogorov Complexity?

I've read in numerous places that Shannon Entropy provides some kind of fundamental limit to the compressibility of messages (according to, for example, Shannon's source coding theorem). I have also ...
42 views

### What's this compression technique called?

Consider this string of 1's, 0's (spaces added for readability): 1010 1010 1010 1010 We can ...
56 views

### SVD for image compression

I want to make sure I understood the concept behind SVD for image compression. So, we start off with a rectangular $m \times n$ matrix that stores all the pixel values of the image. We then compute ...
11 views

### Worst-Case runtime of path compression

Consider the forest implementation of the disjoint-sets abstract data type, with an initial forest of n distinct elements (each one in a one-node tree). Let σ be any sequence of k UNIONs followed by k′...
25 views

### What is the $\Phi$ and $\Psi$ in Wavelets analysis?

I am studying wavelets and somenthing that catch my attention is the existance of a so caled scaling function $\Phi$. Let's take the Haar wavelet. I do not understand why is the scalling function ...
45 views

### What kind of transform is used in this picture?

What kind of transform used in the following picture? I think this is some kind of compression method, but I'm not sure.
27 views

### Johnson-Lindenstrauss Lemma

JL-lemma: Let $\epsilon \in (0,1)$ be given. For ervery set $Q$ of $\#Q$ points in $\mathbb{R}^N$, if $n$ is a positive integer such that $n>n_0=O(\ln(\#Q)/\epsilon^2)$, there exists a Lipschitz ...
49 views

### Entropy analysis in Laplacian pyramid

Update: The paper I mention doesn't need to be fully read in order to answer the question; I'm interested in an analysis of the change in the entropy in two specific processes, so only their technical ...
29 views

### Conditions for the Orthogonal Matching Pursuit (OMP) algorithm exact recovery when applied on complex quantities with noise?

In the scenario of sparse signal recovery, is the Orthogonal Matching Pursuit (OMP) algorithm capable to recover the exact sparse signal when applied for complex measurement vector, complex dictionary,...
28 views

### Finding the smallest set containing sums of pairs from the set

Let $n \in \mathbb{N}$ be a positive integer. Can you find one of the smallest sets $S \subset \mathbb{N}$ containing $n$ such that $1 \in S$, and for every $c \in S, c \neq 1$, there exist $a \in S$ ...
22 views

### what is the process of designing LDPC code (binary case) to correct specific number of bits?

I have two binary vectors x1 and x2 of length n=100 bits, with Hamming distance d(x1,x2)≤10. I want to compress x1 with rate H(x1|x2) and transmitting the compressed version of x1 to decoder while ...
62 views

### Image compression via SVD

Let $A$ be an image of size $m \times n$. Its SVD is $A = U\Sigma V^T$. Equivalently, $$A = \sum_{i=1}^n \sigma_i u_iv_i^T,$$ where $u_i$ and $v_i$ are the $i$-th column of $U$ and $V$, ...
21 views

### Linear noisy encoding implies linear compression

I am reading Essential Coding Theory. Exercise 6.11 reads: Show that if there is a constructive solution to Shannon’s channel coding theorem with $E$ being a linear map, then there is a constructive ...
66 views

### What is the compression impact on Sorted vs Unsorted list

Given an unsorted list of Objects with a compression ration. Can you predict the impact on the ratio, if that list would have been sorted prior to compression? Is there a reason to assume that ...
51 views

### How long can a string be before it must have considerable repeated substrings?

A considerable repeated substring $t \leqslant s \in \Sigma^*$ is a string of length $2$ that occurs at least 3 times disjointly within $s$ or a string of length $3$ or more that occurs at least $2$ ...
36 views

### Coding for data compression with large target's symbol set (where the target symbol set is larger than the source symbol set)

For data compression, every codding that I've seen is binary. It means we convert a language with $N$ symbol size to a language with $M=2$ symbol size. For example, in Huffman coding, the goal is to ...
32 views

### Maximum/minimum values for two-dimensional type-II discrete cosine transform matrix

When encoding a JPEG image, the pixels are encoded as an 8x8 matrix of values in the range [-128...127]. A two dimensional type-II DCT is applied to the matrix and the result is compressed further. ...
96 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. ...
197 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$ ...
143 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, ...
148 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 ...
50 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 ...
117 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 ...
79 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 ...
89 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 ...
78 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 ...
30 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, ...
140 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 ...
35 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 ...
44 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 ...
80 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 ...
50 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 ...
42 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 ...
116 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^...
666 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 ...
687 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 ...
80 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 ...
256 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 ...
474 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 (...
130 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 ...
143 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 ...
445 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 ...
380 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 ...
766 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 ...
6k 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)?
97 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 ...