Questions tagged [compression]

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

Filter by
Sorted by
Tagged with
1
vote
0answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
0
votes
0answers
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′...
0
votes
0answers
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 ...
0
votes
2answers
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.
0
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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,...
1
vote
1answer
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$ ...
1
vote
0answers
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 ...
1
vote
0answers
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$, ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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$ ...
0
votes
1answer
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 ...
0
votes
0answers
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. ...
0
votes
1answer
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. ...
3
votes
3answers
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$ ...
0
votes
1answer
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, ...
8
votes
2answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
3
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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, ...
-1
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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^...
1
vote
3answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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 (...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
2answers
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 ...
3
votes
1answer
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 ...
3
votes
2answers
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 ...
1
vote
0answers
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)?
0
votes
0answers
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 ...
2
votes
3answers
2k 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 ...
2
votes
0answers
491 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 ...