Sparse representation of a distribution with independent and correlated variables

Question

Here's what I'm trying to do:

Imagine a probability distribution over $\mathbf{R}^2$, $P(x,y)$. I can approximate $P(x,y)$ with set of $N$ points $\{(x,y)_i\}$ drawn from $P$. By approximate, I mean that for a test function $\phi$, I'll have $$\int\phi dP \simeq \frac{1}{N}\sum_i\phi(x_i,y_i)$$

Now imagine that the random variables x and y are strongly correlated, not necessarily in the sense of Pearson correlation, but in the sense that $y \simeq f(x)$. The support of the probability distribution will be very narrow, almost 1-dimensional. This means that I can get a good approximation with a smaller value of N... ( the variance of $\int\phi dP - \sum_i\phi(x_i,y_i)$ will be much lower than it would, if the support was wider )

This is all well and I'm happy.

Now assume instead the opposite case, $x$ and $y$ are completely independent. This implies that $P$ is separable, $P(x,y) = P_x(x)P_y(y)$

In practice, I am dealing with two 1-dimensional distribution, but the support of $P$ can be very wide. Now, if I approximate $P$ with a cloud of $N$ points, and if my test function doesn't depend on one of the variable, I will still get very good estimates with a small N, because I am oversampling the $P_x(x)$ across all $y$. However, if $\phi$ is localized in the plane, I will get a much noisier result than I would, if I sampled $P_x$ and $P_y$ independently.

We're getting to my problem!

I have a distribution $P$ over $\mathbf{R}^n$, and I know that the variables $(x,y,z,\ldots)$ are either quite correlated or quite independent from each other. I'd like to find a map $M: \mathbf{R}^n \rightarrow \mathbf{R}^n $ so that $N$ random samples from $P \circ M$ will give a good approximation.

Maybe another way to do it would be to systematically sample from every marginal distribution, and write $P(x,y) = P_x(x)P_y(y) + Q(x,y)$... or I could do a PCA first, and separate based on those components... but notice how I need to make assumptions here (a multivariate normal relationship for example), whereas in the dependent case, the random sample works beautifully and adapts to any kind of dependency? I feel like I'm missing something more generic here.

For a practical example, pick a time and date in the past year and consider the system ( earth, moon, seconds since last hour) in heliocentric coordinates. I picked second since last hour instead of say, date, so that the position of the earth and moon doesn't depend explicitly on time.

The vector is $(e_x,e_y,e_z,m_x,m_y,m_z,t)$. The marginal distribution of $t$ is uniform, and $(e_x,e_y,e_z,m_x,m_y,m_z)$ is largely independent of $t$ and lives around a 2-dimensional manifold (one parametrization being given by two angles). All in all, our random sample will sample around a 3-dimensional manifold. That's not so good. We could see that time is separable and instead sample the 2-d system (earth,moon) and the 1-d system (time). We could do even better and parametrize the system with two angles, and see that those are separable... This example could be described with three 1-dimensional distributions, but how? This parametrization is not obvious.

Answer 1

As I answer I'm rephrasing and clarifying your question a little - please correct me if something is wrong.

Firstly, shouldn't your equation have an extra term of the form $\Delta(x,y)$ on the RHS, that measures how far apart your sample points $(x_i,y_i)$ are? Because $$\int \phi dP \approx \sum_i\phi(x_i)\Delta(x)$$ where $x_i \in \R^n$ means that we want to approximate the area under the curve $\phi$ well using rectangles, where the points are sampled according to the distribution $P$. In other words, a Riemann approximation to the integral.

One sees that how well this approximation is depends on the support of $\phi$, $P$, and how `well-behaved' $\phi$ is. At least $\phi$ has to be Riemann integrable, for instance, for the RHS to converge to the LHS as the number of sample points $N$ tends to infinity.

For the moment, suppose $\phi$ is well-behaved, and the support of both $\phi$ and $P$ lives in a manifold of dimension $n$. (This would correspond to your independent, or strong correlation case, for example). A priori you need about $N^n$ sample points. But again, this depends on $\phi, P$, and how close you want to be to the integral.

I understood your question as: if one knew that the support of $P$ is on a lower-dimensional manifold, say, of dimension $d$, can one sample more efficiently (say, $N^d$ points) and still get a good approximation?

Specifically, the strategy you suggested is a change of coordinate. In this case, one wants a new set of coordinates that are uncorrelated and capture the most variance in the data (in this case, the distribution you are sampling from), and this is what PCA accomplishes. PCA doesn't assume `multivariate normal': it just assumes that the covariance exists and has finite operator norm, which is true if you assume that your distribution $P$ has finite variance. (If it doesn't then it's a pretty bad distribution)

I don't understand what you meant by `random sample works well and adapt to any kind of dependency'. If you knew before hand that $\phi$ only depends on one of the coordinates (or in general, on $d$ coordinates in $\R^n$, then by the same argument $N^d$ sample points would be enough.) It also seems to me that your sampling scheme is not clear: do you sample from $P$ by MCMC, or by some other methods?

In short, the recommendation is PCA (unless if you're assuming further specific structure).