Currently I am working on applications of Bourgain Embedding (or similar embeddings of finite metric spaces to $l_2$) to automatic feature engineering for machine learning/data science ( http://www.orges-leka.de/automatic_feature_engineering.html ). The method works quite well, but the only drawback is its runtime $O(N^2)$ where $N$ is the number of data points to be embedded. I have seen ( https://arxiv.org/abs/1805.07674 ) and it is a natural idea to chose $n < N$ random data points and to do the Bourgain embedding for those points. But the only proven preserved quantity is the distance distribution. My question is, if there is a way to speed up the Bourgain embedding while preserving the low distortion? This would be potentially useful for large datasets and I think it would have applications in data science / machine learning. Thanks for your help!

Currently I am working on applications of Bourgain Embedding (or similar embeddings of finite metric spaces to $l_2$) to automatic feature engineering for machine learning/data science ( http://www.orges-leka.de/automatic_feature_engineering.html, https://github.com/orgesleka/bourgain_embedding/blob/master/bourgain.py ). The method works quite well, but the only drawback is its runtime $O(N^2)$ where $N$ is the number of data points to be embedded. I have seen ( https://arxiv.org/abs/1805.07674 ) and it is a natural idea to chose $n < N$ random data points and to do the Bourgain embedding for those points. But the only proven preserved quantity is the distance distribution. My question is, if there is a way to speed up the Bourgain embedding while preserving the low distortion? This would be potentially useful for large datasets and I think it would have applications in data science / machine learning. Thanks for your help!

Currently I am working on applications of Bourgain Embedding to automatic feature engineering for machine learning/data science ( http://www.orges-leka.de/automatic_feature_engineering.html ). The method works quite well, but the only drawback is its runtime $O(N^2)$ where $N$ is the number of data points to be embedded. I have seen ( https://arxiv.org/abs/1805.07674 ) and it is a natural idea to chose $n<N$ random data points and to do the Bourgain embedding for those points. But the only proven preserved quantity is the distance distribution. My question is, if there is a way to speed up the Bourgain embedding while preserving the low distortion? This would be potentially useful for large datasets and I think it would have applications in data science / machine learning. Thanks for your help!

Currently I am working on applications of Bourgain Embedding (or similar embeddings of finite metric spaces to $l_2$) to automatic feature engineering for machine learning/data science ( http://www.orges-leka.de/automatic_feature_engineering.html ). The method works quite well, but the only drawback is its runtime $O(N^2)$ where $N$ is the number of data points to be embedded. I have seen ( https://arxiv.org/abs/1805.07674 ) and it is a natural idea to chose $n < N$ random data points and to do the Bourgain embedding for those points. But the only proven preserved quantity is the distance distribution. My question is, if there is a way to speed up the Bourgain embedding while preserving the low distortion? This would be potentially useful for large datasets and I think it would have applications in data science / machine learning. Thanks for your help!