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
29 views

Can we modify the Lempel-Ziv 77 algoritm utilizing periodic functions in mathematical analysis?

The Lempel-Ziv 77 is a classical data compression scheme which was popular in early data compression algorithms. For example in deflate and GIF. One useful and curious special property of LZ77 is its ...
1
vote
1answer
23 views

Why Lempel-Ziv77 - “sliding window” algorithm uses a fixed length code for the buffer u?

I am a final year ECE student from Greece, studying about Information Theory a question came up. In the definition/description of LZ77 (Lempel-Ziv's algorithm), following is noted: "If n > 1, ...
0
votes
0answers
14 views

TOP p most informative elements in a mutually recursive multisets?

Let say we have two groups of multi-sets /repeatable elements are allowed/ i.e. ...
2
votes
1answer
77 views

Bounds for $\det(AA^T) \ge \det(ABA^T)$

Let $A$ be a $m \times n$ matrix with real entries, and let $B$ be a $n \times n$ real symmetric matrix with absolute eigenvalues $\le 1$. Are there (ideally sharp) bounds for the inequality $$\det(AA^...
1
vote
1answer
35 views

Inferring bounds from joint typicality on three variables

Consider the following exercise from Cover and Thomas: And the given solution from the solutions manual: It is reasonably clear that these bounds are valid (one simply follows the counting argument ...
0
votes
0answers
14 views

How to solve a L2 norm minimization problem with matrix orthogonal constraints

Given vectors $\mathbf{x}\in \mathbb{R}^N$ and $\mathbf{y}\in \mathbb{R}^M$ with $0\lt M\ll N$, I want to get an orthogonal $\mathbf{\Phi}\in \mathbb{R}^{M\times N}$ satisfying $\mathbf{y}=\mathbf{\...
0
votes
0answers
38 views

Show that Restricted Isometry property implies Restricted nullspace property

I need to show that if matrix A satisfies the RIP then it also satisfies the RNP. I need to prove that each of the lemmas holds and then show that RIP implies RNP using the lemmas. Lemma 1: Let the ...
0
votes
0answers
6 views

Restricted isometry property for a sparse matrix

Let $A \in \mathbb{R}^{n \times N}$. We can let $a_{ij} \sim N(0,\frac{1}{n})$ to guarantee it satisfies the RIP. Question: The above matrix is a dense matrix, is there anyway to construct $A$ such ...
1
vote
1answer
40 views

Phone numbers expressed as operations of numbers with less digits

Where I live, mobile phone numbers tend to be combinations of 9 digits, mainly starting by 6, and I've been days wonder whether is it possible to express a given number as sums/products involving less ...
1
vote
1answer
22 views

Measurements Numbers in Compressed Sensing

here is a question about Compressed sensing. Let us denote the $k$-sparse signal $x\in \mathbb{R}^n$, measurement/sensing matrix $A\in \mathbb{R}^{m\times n}$ and the measurement $y = Ax \in \mathbb{R}...
0
votes
0answers
57 views

Is compressing matrices to a single real number in a useful way possible?

I am still a newbie when it comes to stackexchange so please be indulgent with me ! TL;DR Can a bijective function $f : \mathbb{R}^n\to\mathbb{R} : \vec{x} \mapsto f(\vec{x})$ be constructed in such a ...
0
votes
0answers
24 views

General (continuous + discrete) source coding theorem

I was wondering if someone could state and prove (or knew references that state and prove) Shannon's source coding theorem in a form that works both for continuous and discrete r.v.. It is very easy ...
0
votes
0answers
24 views

N-component discrete memoryless sources

I am totally stuck in understanding the definition of N-component discrete memoryless sources. I need to use such sources in my research and the below explanation actually is this definition from a ...
1
vote
1answer
51 views

A problem of (Convex?) Optimization about compressive sensing

In fact, I'm not sure if the following question is convex. I am processing an optimization problem about compressive sensing: $$\arg\min_{A,x} \quad \lVert Ax-y \rVert _{2}^{2}+\lambda _1\lVert A^{\...
1
vote
0answers
44 views

Arithmetic entropy encoding with prime numbers.

I wonder if the following method of arithmetic entropy encoding could work for lossless compression of a binary signal: For some 24 bit signal: $Sn = \begin{pmatrix}x_{1}\\x_{2}\\ \vdots \\x_{24}\end{...
0
votes
0answers
47 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) , $$ ...
1
vote
1answer
53 views

Intuition on the Johnson-Lindenstauss lemma

Johnson-Lindenstrauss Lemma states: Let $N \gg 1$. For any $0 < \varepsilon < 1$ and $m$ points in $\mathbb{R}^N$ and $n > \frac{8 \log m}{\varepsilon^2}$ there exists a linear map $f : \...
0
votes
1answer
28 views

Proof average codeword length of a prefix code $C$ is the sum of probability of all leaf vertices that are descendant

Let $I$ represent the set of all interior vertices in a binary tree. Define the probability of vertex $v \in I$ is $P(v)$, which is the sum of the probabilities of all leaf vertices that are ...
0
votes
0answers
44 views

How to increase the compression of an RGB image from a typical smartphone camera from 2:1 to perhaps 3:1?

I have been experimenting with a simple (fixed resolution) image file compressor that I designed and wrote from "scratch", for fun, and to keep my programming skills "sharp". So ...
0
votes
0answers
17 views

Is Prediction the same as Compression?

Just came across this transcript that states: The principle is that prediction is the same thing as compression. And what that means is that whenever you have a prediction algorithm, you can also get ...
0
votes
1answer
51 views

Extending Given Digits to make Perfect Powers

I read this article titled Extending Given Digits to make Primes or Perfect Powers by Sury B, which appeared in the Resonance periodical (October 2010, Indian Statistical Institute, Bangalore). In ...
1
vote
0answers
18 views

Let $W$ be random matrix and $b$ be vector. Let $x$ be secret vector; let $(y(x))_j = \max(W_j^Tx+b,0)$. Find $x' \in B(x;r)$ s.t $y(x')=y(x)$ whp

Let $1 \le n \le p$ be large positive integers. $W$ be a random $n \times p$ matrix with entries drawn iid from $\mathcal N(0,1/p)$ and let $b$ be an $n$-dimensional random vector with coordinates ...
6
votes
2answers
167 views

Power values of polynomial

$f(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_n x^n$ is a polynomial of degree $n$ with positive integer coefficients. Primary problem statement: Is the Exponential Diophantine Equation $f(f(a) + 1) = y^...
2
votes
0answers
47 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 ...
2
votes
1answer
208 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 ...
1
vote
0answers
65 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
76 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
48 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
107 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
33 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.
1
vote
1answer
103 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 ...
1
vote
1answer
31 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
24 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
70 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$, ...
1
vote
1answer
114 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
53 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
38 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 ...
2
votes
1answer
106 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. ...
1
vote
1answer
538 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
233 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
270 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
159 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
69 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
151 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
126 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
29 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
114 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
99 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
33 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, ...