<p>With the problem as stated, you can compress the <span class="math-container">$N$</span> real-valued vectors into <span class="math-container">$K$</span> real-valued vectors, and reconstruct the original <span class="math-container">$N$</span> vectors exactly.</p>
<p>How does this work? Suppose you want to compress two real-valued vectors into one real-valued vector. Expand all the real numbers in binary. Use the even bits to specify the first vector and the odd bits for the second vector. Similar schemes will work for any <span class="math-container">$K$</span> and <span class="math-container">$N$</span>.</p>
<p>If you want to exclude this solution, you either have to ask: how many <strong>bits</strong> can I compress the vectors into so that I can approximately reconstruct them, or you have to add some kind of continuity requirements on the encoding and decoding functions.</p>
<p>In the first case, when you ask for the minimum number of bits needed to compress the vectors so you can reconstruct them with some bound on the expected mean square error, the answer can be computed using <a href="https://en.wikipedia.org/wiki/Rate%E2%80%93distortion_theory" rel="nofollow noreferrer">rate-distortion theory</a>, a subarea of information theory.</p>

CC BY-SA 4.0
2023-12-29T13:13:33.890Z
2023-12-29T13:13:33.890Z
Peter Shor 
<p>Given a sequence of <span class="math-container">$N$</span> real-valued vectors <span class="math-container">$\mathbf{v_1}, \mathbf{v_2}, ..., \mathbf{v_N}$</span>, each of dimension <span class="math-container">$d$</span>, do any of the below bounds exist?</p>
<ol>
<li><p>The minimum number of real-valued vectors of dimension <span class="math-container">$d$</span> such that the original vectors can be reconstructed with bounded error (in other words, is there a function that maps the new set of vectors to the original set of vectors with bounded error)?</p>
</li>
<li><p>Given <span class="math-container">$K$</span> vectors, each of dimension <span class="math-container">$d$</span>, what is the minimum error that can be incurred when compressing the original <span class="math-container">$N$</span> vectors into these <span class="math-container">$K$</span> vectors and then reconstructing them?</p>
</li>
</ol>
<p>We can assume that the original vectors are I.I.D.</p>

CC BY-SA 4.0
2023-12-25T05:40:43.787Z
Please ask only one question per post.  I suggest asking the two questions separately.  I suggest being more explicit about the problem statement and the requirements.
D.W.
CC BY-SA 4.0
2023-12-25T05:40:58.430Z
For question 1, I don't understand what you are asking.  Must the additional vectors be chosen before knowing $v_1,\dots,v_N$, or can they depend on $v_1,\dots,v_N$?  What metric are you using for error?  I don't see how to guarantee bounded error without more restrictions on $v_1,\dots,v_N$, as we could choose a coefficient to $v_1$ some incredibly large number.  Can you provide any results for special cases, e.g., small values of $d$ or $N$?
D.W.
CC BY-SA 4.0
2023-12-25T14:13:39.033Z
@D.W. The number of vectors need to be chosen, but the contents depend on the input vectors. The metric is Mean Squared Error after decoding. There are no spacial cases as such, we can assume a fix size of $d$ to be 64 for example.
Susmit Agrawal
CC BY-SA 4.0
2023-12-25T21:29:53.753Z
Please don't put clarifications in the comments.  Instead, please [edit] your question to make it clear and read well for someone who encounters it for the first time.  Do you allow sending extra information in addition to the vectors sent?  Do you allow the number of additional vectors to depend on $v_1,\dots,v_N$, or is it only allowed to depend on $N$?  Do you want a bound that depends only on $N$, or on all of $v_1,\dots,v_N$, or on some quantities for $N$?  What encoding/decoding approaches have you tried so far?
D.W.
CC BY-SA 4.0
2023-12-26T19:03:42.217Z
What operations do you allow? Due to cardinality there's a bijection.
Command Master
<it.information-theory><computing-over-reals><information>
Maximum theoretical compression ratio for real-valued data
Susmit Agrawal
# Maximum theoretical compression ratio for real-valued data

(Asked by: username_0 on 2023-12-24)

Given a sequence of $N$ real-valued vectors $\mathbf{v\_1}, \mathbf{v\_2}, ..., \mathbf{v\_N}$, each of dimension $d$, do any of the below bounds exist?

1. The minimum number of real-valued vectors of dimension $d$ such that the original vectors can be reconstructed with bounded error (in other words, is there a function that maps the new set of vectors to the original set of vectors with bounded error)?
2. Given $K$ vectors, each of dimension $d$, what is the minimum error that can be incurred when compressing the original $N$ vectors into these $K$ vectors and then reconstructing them?

We can assume that the original vectors are I.I.D.

**Tags:** it.information-theory, computing-over-reals, information

> **Comments:**
> **username_1**: Please ask only one question per post.  I suggest asking the two questions separately.  I suggest being more explicit about the problem statement and the requirements.  
> **username_1**: For question 1, I don't understand what you are asking.  Must the additional vectors be chosen before knowing $v_1,\dots,v_N$, or can they depend on $v_1,\dots,v_N$?  What metric are you using for error?  I don't see how to guarantee bounded error without more restrictions on $v_1,\dots,v_N$, as we could choose a coefficient to $v_1$ some incredibly large number.  Can you provide any results for special cases, e.g., small values of $d$ or $N$?  
> **username_0**: @username_1 The number of vectors need to be chosen, but the contents depend on the input vectors. The metric is Mean Squared Error after decoding. There are no spacial cases as such, we can assume a fix size of $d$ to be 64 for example.  
> **username_1**: Please don't put clarifications in the comments.  Instead, please [edit] your question to make it clear and read well for someone who encounters it for the first time.  Do you allow sending extra information in addition to the vectors sent?  Do you allow the number of additional vectors to depend on $v_1,\dots,v_N$, or is it only allowed to depend on $N$?  Do you want a bound that depends only on $N$, or on all of $v_1,\dots,v_N$, or on some quantities for $N$?  What encoding/decoding approaches have you tried so far?  
> **username_2**: What operations do you allow? Due to cardinality there's a bijection.  

---

## 1 answers

### Answer by username_3 on 2023-12-29. Score: 3 | Accepted answer

With the problem as stated, you can compress the $N$ real-valued vectors into $K$ real-valued vectors, and reconstruct the original $N$ vectors exactly.

How does this work? Suppose you want to compress two real-valued vectors into one real-valued vector. Expand all the real numbers in binary. Use the even bits to specify the first vector and the odd bits for the second vector. Similar schemes will work for any $K$ and $N$.

If you want to exclude this solution, you either have to ask: how many **bits** can I compress the vectors into so that I can approximately reconstruct them, or you have to add some kind of continuity requirements on the encoding and decoding functions.

In the first case, when you ask for the minimum number of bits needed to compress the vectors so you can reconstruct them with some bound on the expected mean square error, the answer can be computed using [rate-distortion theory](https://en.wikipedia.org/wiki/Rate%E2%80%93distortion_theory), a subarea of information theory.


---

