Dimension reduction techniques in R that do not use the full distance matrix
You can try using an auto-encoder which also is a non-linear dimension reduction technique.  It uses a neural network framework to find the most efficient transformation from $p$ dimensions down to whatever you choose.  It then finds how well it can reconstruct the origianl $p$ variables, and keeps tuning until it can optimally recreate the original values as "good" (lowest MSE) as possible.

 

In this case the input has 5 variables, and it reduces it down to 2 variables using non-linear transformations.  Once you get it down to the reduced variables (the light blue nodes) it then tries using non-lienar transformations to recreate those original five inputs using a similar nn structure.  The right-five red nodes are then compared to the left-five original inputs to see how much information is encoded in those 2 middle light blue reduced variables.

I've found the h2o implementation is pretty easy to use, but finding the correct parameters (number of layers, nodes, learning rate, etc) is still tough to select depending on your data.

Heres a little blog post that goes through the h2o autoencoder with the MNIST data set.