The first important observation is that state-of-the-art approaches,except CPM, fail to produce an embedding for the complete dataset (containing 100,000 cells),due to their reliance on pairwise distances for the computation of embeddings, which scalesquadratically in the number of cells
This doesn't feel quite fair, as UMAP and tSNE were designed to handle datasets of this size and have been widely used to generate embeddings for single-cell datasets of this size and larger. Also, I believe at least UMAP is sub-quadratic in the number of samples, as it uses an approximate kNN algorithm that is n log n.