Show simple item record  

dc.contributor.authorLim, Nicken_NZ
dc.contributor.authorDurrant, Robert J.en_NZ
dc.date.accessioned2019-02-19T23:18:55Z
dc.date.available2017en_NZ
dc.date.available2019-02-19T23:18:55Z
dc.date.issued2017en_NZ
dc.identifier.citationLim, N., & Durrant, R. J. (2017). Linear dimensionality reduction in linear time: Johnson-Lindenstrauss-type guarantees for random subspace. ArXiv E-prints.en
dc.identifier.urihttps://hdl.handle.net/10289/12353
dc.description.abstractWe consider the problem of efficient randomized dimensionality reduction with norm-preservation guarantees. Specifically we prove data-dependent Johnson-Lindenstrauss-type geometry preservation guarantees for Ho's random subspace method: When data satisfy a mild regularity condition -- the extent of which can be estimated by sampling from the data -- then random subspace approximately preserves the Euclidean geometry of the data with high probability. Our guarantees are of the same order as those for random projection, namely the required dimension for projection is logarithmic in the number of data points, but have a larger constant term in the bound which depends upon this regularity. A challenging situation is when the original data have a sparse representation, since this implies a very large projection dimension is required: We show how this situation can be improved for sparse binary data by applying an efficient `densifying' preprocessing, which neither changes the Euclidean geometry of the data nor requires an explicit matrix-matrix multiplication. We corroborate our theoretical findings with experiments on both dense and sparse high-dimensional datasets from several application domains.en_NZ
dc.format.mimetypeapplication/pdf
dc.language.isoen
dc.subjectMachine learning
dc.titleLinear dimensionality reduction in linear time: Johnson-Lindenstrauss-type guarantees for random subspaceen_NZ
dc.typeJournal Article
dc.relation.isPartOfArXiv e-printsen_NZ
pubs.elements-id203666
uow.identifier.article-noarXiv:1705.06408


Files in this item

This item appears in the following Collection(s)

Show simple item record