Paper Info
Title
Too many secants: a hierarchical approach to secant-based dimensionality reduction on large data sets
Abstract
A fundamental question in many data analysis settings is the problem of discerning the “natural” dimension of a data set. That is, when a data set is drawn from a manifold (possibly with noise), a meaningful aspect of the data is the dimension of that manifold. Various approaches exist for estimating this dimension, such as the method of Secant-Avoidance Projection (SAP). Intuitively, the SAP algorithm seeks to determine a projection which best preserves the lengths of all secants between points in a data set; by applying the algorithm to find the best projections to vector spaces of various dimensions, one may infer the dimension of the manifold of origination. That is, one may learn the dimension at which it is possible to construct a diffeomorphic copy of the data in a lower-dimensional Euclidean space. Using Whitney's embedding theorem, we can relate this information to the natural dimension of the data. A drawback of the SAP algorithm is that a data set with T points has O(T <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) secants, making the computation and storage of all secants infeasible for very large data sets. In this paper, we propose a novel algorithm that generalizes the SAP algorithm with an emphasis on addressing this issue. That is, we propose a hierarchical secant-based dimensionality-reduction method, which can be employed for data sets where explicitly calculating all secants is not feasible.
Year
DOI
Venue
2018
10.1109/HPEC.2018.8547515
2018 IEEE High Performance extreme Computing Conference (HPEC)
Keywords
DocType
Volume
Secant sets,dimensionality reduction,big data
Conference
abs/1808.01686
ISSN
ISBN
Citations 
2377-6943
978-1-5386-5990-8
0
PageRank 
References 
Authors
0.34
11
4
Name
Order
Citations
PageRank
Henry Kvinge101.35
Elin Farnell201.69
Michael Kirby313714.40
Chris Peterson46810.93