Conditional Kolmogorov complexity of an array of continuous variables

92 Views Asked by At

I know that conditional complexity is a measure that can only be applied to strings of discrete characters, but I'm curious if there's an analogue for continuous variables. For example, it's easy to convert an array of real numbers $X'$ into a string of integers $X$ by ranking them. I could then compare two such strings $X$ and $Y$ of equal length and compute, for example, an edit distance. Certainly the distance between these two discrete strings is one measure of the conditional complexity $K(X|Y)$, and surely that distance tells me something about the original pair of continuous vectors $(X'|Y')$. Does that mean I have some amount of conditional algorithmic information about the continuous data? Or is it a different kind of information when it's about continuous data?

What's more, suppose I have a function $f(Y') = Y'-X'$. I then compute the distance between ranked $X'$ and ranked $f(Y')$. Now I have a pair of distances, both derived from $X'$ and $Y'$. Even though I'm using different functions of $Y$, both of these distances are still giving information about $X'$ and $Y'$. That's clear since, if I gave you $X'$ and its respective distances from both $Y'$ and $f(Y')$, but not $Y'$ or $f(Y')$ themselves, you could always evaluate whether any continuous vector $Z'$ is a viable candidate for $Y'$ by computing the same pair of distances for $X'$ and $Z'$ and comparing them to the set of distances I gave you for $X'$ and $Y'$. You are thus reducing the size of the universe of possible candidates for $Y'$, and therefore also reducing the uncertainty in $Y'$, which is the definition of information (or entropy). The two distances are also each giving me non-redundant information about the two continuous vectors. This is clear because, if I'd also computed the distance between ranked $X'$ and ranked $g(Y') = Y' * X'$, and then given you all three distances, you could use the third distance to reduce the uncertainty in $Y'$ even further.

So, yeah, my question is, what do we call the information I get from $K(X|Y)$ and $K(X|f[Y]))$ and $K(X|g[Y])$ about $(X'|Y')$? Is it continuous conditional complexity? Regular entropy? Something else?