Dimensionality Reduction has Quantifiable Imperfections: Two Geometric Bounds
In this paper, we investigate Dimensionality reduction (DR) maps in an information retrieval setting from a quantitative topology point of view. In particular, we show that no DR maps can achieve perfect precision and perfect recall simultaneously. Thus a continuous DR map must have imperfect precision. We further prove an upper bound on the precision of Lipschitz continuous DR maps. While precision is a natural measure in an information retrieval setting, it does not measure `how' wrong the retrieved data is. We therefore propose a new measure based on Wasserstein distance that comes with similar theoretical guarantee. A key technical step in our proofs is a particular optimization problem of the $L_2$-Wasserstein distance over a constrained set of distributions. We provide a complete solution to this optimization problem, which can be of independent interest on the technical side.
Code (0)
등록된 구현이 없습니다.
Tasks
Dimensionality ReductionInformation RetrievalRetrievalVocal Bursts Valence PredictionSimilar Papers 제목 키워드 기반
Dimensionality Reduction for Wasserstein Barycenter
The Wasserstein barycenter is a geometric construct which captures the notion of centrality among probability distributions, and which has found many applications in machine learning. However, most algorithms for finding…
Dimensionality ReductionPreserving Vector Space Properties in Dimensionality Reduction: A Relationship Preserving Loss Framework
Dimensionality reduction can distort vector space properties such as orthogonality and linear independence, which are critical for tasks including cross-modal retrieval, clustering, and classification. We propose a Relat…
Dimensionality ReductionKnowledge DistillationCross-Modal RetrievalFederated LearningFeature Space Sketching for Logistic Regression
We present novel bounds for coreset construction, feature selection, and dimensionality reduction for logistic regression. All three approaches can be thought of as sketching the logistic regression inputs. On the corese…
Dimensionality Reductionfeature selectionregressionRandom projections of random manifolds
Interesting data often concentrate on low dimensional smooth manifolds inside a high dimensional ambient space. Random projections are a simple, powerful tool for dimensionality reduction of such data. Previous works hav…
Dimensionality ReductionEstimates on the domain of validity for Lyapunov-Schmidt reduction
Lyapunov-Schmidt reduction is a dimensionality reduction technique in nonlinear systems analysis that is commonly utilised in the study of bifurcation problems in high-dimensional systems. The method is a systematic proc…
Dimensionality Reduction