I don't think that's a serious restriction. Firstly - in general it's trivially true that you have probability 0 to cleanly embed a high dimensional space into

I don't think that's a serious restriction. Firstly - in general it's trivially true that you have probability 0 to cleanly embed a high dimensional space into a 2/3 dimensional representation over the set of all possible high dimensional data - yet interesting data often does have lower-dimensional structure. Secondly - so what? Can you think of plausible scenario where this assumption does not hold and it's possible to generate a low-dimensional embedding? If it's impossible to embed, then it's not an algorithmic problem if you fail to find an embedding.