Dimensionality Reduction with Point-distributions Similarity Invariant

Existing dimensionality reduction methods all perform dimensionality reduction by preserving some invariant in the space before and after dimensionality reduction. This paper proposes a new dimensionality reduction invariant: preserving the invariant of the point-distributions similarity. We also design a linear and efficient method to achieve dimensionality reduction while preserving this invariant. We theoretically prove the feasibility of our method for dimensionality reduction. Furthermore, our results on benchmark datasets and single-cell expression data demonstrate the effectiveness and efficiency of the proposed method.

Data mining frequently relies on dimensionality reduction to compress massive, complex datasets into simple visual maps. However, traditional tools are computationally heavy because they compare every single pair of data points, creating a severe bottleneck for large-scale information. To overcome this, we introduce $\Psi$-DR (or PSIDR), an exceptionally fast, linear-time algorithm that shifts the focus from individual point-to-point comparisons to the broader layout of the dataset. Recognizing that real-world data naturally forms a mixture of distinct groups, like different image categories or cell types, $\Psi$-DR keeps the similarity of each point and the groups unchanged. It maps out the broad landmarks of these main group distributions first, then positions individual points based solely on their similarity to those landmarks. Consequently, $\Psi$-DR slashes processing times from hours to seconds on massive datasets while producing an incredibly clean separation of categories. This ensures highly accurate results for downstream classification and clustering tasks without the expensive computational cost.