Stable sparse subspace embedding for dimensionality reduction
作者：
Highlights：
• The stable sparse subspace embedded matrix is constructed for dimension reduction. In this construction, the idea of uniform sampling without replacement is adopted to obtain the position of nonzero entries in the matrix. In the constructed matrix, each row contains nd or nd+1 nonzero entries, and each column contains only one nonzero.
• We prove that our matrix is stabler than SE matrix (Dasgupta, 1999).
• It is proved that embedding the original data into dimension d=O(ϵ−2log(1∕δ)) is sufficient to preserve all the pairwise Euclidean distances up to 1±ϵ.
• Experimental results verify our theoretical analysis, and illustrate that our algorithm outperforms other compared dimension reduction methods.
摘要
•The stable sparse subspace embedded matrix is constructed for dimension reduction. In this construction, the idea of uniform sampling without replacement is adopted to obtain the position of nonzero entries in the matrix. In the constructed matrix, each row contains nd or nd+1 nonzero entries, and each column contains only one nonzero.•We prove that our matrix is stabler than SE matrix (Dasgupta, 1999).•It is proved that embedding the original data into dimension d=O(ϵ−2log(1∕δ)) is sufficient to preserve all the pairwise Euclidean distances up to 1±ϵ.•Experimental results verify our theoretical analysis, and illustrate that our algorithm outperforms other compared dimension reduction methods.
论文关键词：Dimensionality reduction,Feature projection,Random projection,Sparse,Stable
论文评审过程：Received 21 August 2019, Revised 5 February 2020, Accepted 8 February 2020, Available online 17 February 2020, Version of Record 4 April 2020.
论文官网地址：https://doi.org/10.1016/j.knosys.2020.105639
