DiffRed: Dimensionality Reduction guided by stable rank
<|reference_start|>DiffRed: Dimensionality Reduction guided by stable rank: In this work, we propose a novel dimensionality reduction technique, DiffRed, which first projects the data matrix, A, along first $k_1$ principal components and the residual matrix $A^{*}$ (left after subtracting its $k_1$-rank approximation) along $k_2$ Gaussian random vectors. We evaluate M1, the distortion of mean-squared pair-wise distance, and Stress, the normalized value of RMS of distortion of the pairwise distances. We rigorously prove that DiffRed achieves a general upper bound of $O\left(\sqrt{\frac{1-p}{k_2}}\right)$ on Stress and $O\left(\frac{(1-p)}{\sqrt{k_2*\rho(A^{*})}}\right)$ on M1 where $p$ is the fraction of variance explained by the first $k_1$ principal components and $\rho(A^{*})$ is the stable rank of $A^{*}$. These bounds are tighter than the currently known results for Random maps. Our extensive experiments on a variety of real-world datasets demonstrate that DiffRed achieves near zero M1 and much lower values of Stress as compared to the well-known dimensionality reduction techniques. In particular, DiffRed can map a 6 million dimensional dataset to 10 dimensions with 54% lower Stress than PCA.<|reference_end|>
@article{shukla2024diffred:,
    title={DiffRed: Dimensionality Reduction guided by stable rank},
    author={Prarabdh Shukla, Gagan Raj Gupta, Kunal Dutta},
    journal={arXiv preprint arXiv:2403.05882},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.05882},
    primaryClass={cs.LG}
}