0
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Dec 25, 2023 at 5:40
  • 1
    $\begingroup$ 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$? $\endgroup$
    – D.W.
    Commented Dec 25, 2023 at 5:40
  • $\begingroup$ @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. $\endgroup$ Commented Dec 25, 2023 at 14:13
  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Commented Dec 25, 2023 at 21:29
  • $\begingroup$ What operations do you allow? Due to cardinality there's a bijection. $\endgroup$ Commented Dec 26, 2023 at 19:03

1 Answer 1

3
$\begingroup$

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, a subarea of information theory.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.