Curse of Dimensionality

First heard about by reading this research paper https://onlinelibrary.wiley.com/doi/full/10.1002/sam.11161

• F i can’t access this, this is so annoying because I remember they had a really nice sentence explaining how the curse of dimensionality worked.

As $n\to \infty$, $\sigma \to 0$.

It was from a stackoverflow feed: https://stackoverflow.com/questions/23391589/clustering-in-high-dimensions-some-basic-stuff

Subspace clustering for high dimensional data: https://www.kdd.org/exploration_files/parsons.pdf

CS287

For an $n$-dimensional state space, the number of states grows exponentially in $n$ (for fixed number of discretization levels per coordinate)

Therefore, in practice, discretization is considered only computationally feasible up to 5 or 6 dimensional state spaces even when using

• Variable resolution discretization
• Highly optimized implementations

Function approximation might or might not work, in practice often somewhat local.