Scalable Action Respecting Embedding

ARE is a non-linear dimensionality reduction technique for embedding observation trajectories, which captures state dynamics that traditional methods do not. The core of ARE is a semidefinite optimization with constraints requiring actions to be distance-preserving in the resulting embedding. Unfortunately, these constraints are quadratic in number and non-local (making recent scaling tricks inapplicable). Consequently, the original formulation was limited to relatively small datasets. This paper describes two techniques to mitigate these issues. We first introduce an action-guided variant of Isomap. Although it alone does not produce action-respecting manifolds, it can be used to seed conjugate gradient to implicitly solve the primal variable formulation of the ARE optimization. The optimization is not convex, but the Action-Guided Isomap provides an excellent seed often very close to the global minimum. The resulting Scalable ARE procedure gives similar results to original ARE, but can be applied to datasets an order of magnitude larger.