$\mathbb{R}^{2k}$ is Theoretically Large Enough for Embedding-based Top-$k$ Retrieval

• URL: http://arxiv.org/abs/2601.20844v2
• Date: Thu, 29 Jan 2026 03:54:29 GMT
• Title: $\mathbb{R}^{2k}$ is Theoretically Large Enough for Embedding-based Top-$k$ Retrieval
• Authors: Zihao Wang, Hang Yin, Lihui Liu, Hanghang Tong, Yangqiu Song, Ginny Wong, Simon See,
• Abstract summary: This paper studies the minimal dimension required to embed subset memberships ($m$ elements and $mchoose k$ subsets of at most $k$ elements) into vector spaces, denoted as Minimal Embeddable Dimension (MED)<n>The tight bounds of MED are derived theoretically and supported empirically for various notions of "distances" or "similarities," including the $ell$ metric, inner product and cosine similarity.
• Score: 99.8640829555514
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: This paper studies the minimal dimension required to embed subset memberships ($m$ elements and ${m\choose k}$ subsets of at most $k$ elements) into vector spaces, denoted as Minimal Embeddable Dimension (MED). The tight bounds of MED are derived theoretically and supported empirically for various notions of "distances" or "similarities," including the $\ell_2$ metric, inner product, and cosine similarity. In addition, we conduct numerical simulation in a more achievable setting, where the ${m\choose k}$ subset embeddings are chosen as the centroid of the embeddings of the contained elements. Our simulation easily realizes a logarithmic dependency between the MED and the number of elements to embed. These findings imply that embedding-based retrieval limitations stem primarily from learnability challenges, not geometric constraints, guiding future algorithm design.

Related papers

• Low-degree Lower bounds for clustering in moderate dimension [53.03724383992195]
  We study the fundamental problem of clustering $n$ points into $K$ groups drawn from a mixture of isotropic Gaussians in $mathbbRd$.<n>We show that while the difficulty of clustering for $n leq dK$ is driven by dimension reduction and spectral methods, the moderate-dimensional regime involves more delicate phenomena leading to a "non-optimal rate"<n>We provide a novel non-spectral algorithm matching this rate, shedding new light on the computational limits of the clustering problem in moderate dimension.
  arXiv  Detail & Related papers  (2026-02-26T14:03:55Z)
• Bounds on Lorentz-violating parameters in magnetically confined 2D systems: A phenomenological approach [0.0]
  We present a framework to constrain minimal SME coefficients $a_mu$ and $b_mu$ using magnetically confined two-dimensional electron systems.<n>Working in the nonrelativistic (Schr"odinger--Pauli) limit with effective mass, we derive the radial problem for cylindrical geometries.
  arXiv  Detail & Related papers  (2025-10-28T11:11:59Z)
• Fourier Sliced-Wasserstein Embedding for Multisets and Measures [3.396731589928944]
  We present a novel method to embed multisets and measures over Rd into Euclidean space.<n>We prove that it is impossible to embed distributions over Rd into Euclidean space in a bi-Lipschitz manner.
  arXiv  Detail & Related papers  (2024-05-26T11:04:41Z)
• Continuous Multidimensional Scaling [14.537835814280221]
  Multidimensional scaling (MDS) is the act of embedding proximity information about a set of $n$ objects in $d$-dimensional Euclidean space.<n>Here we are concerned with embedding dissimilarities by minimizing Kruskal's (1964) raw stress criterion.<n>Standard results from the theory of point-to-set maps can be used to establish that, if $n$ is fixed and a sequence of dissimilarity converges, then the limit of their embedded structures is the embedded structure of the limiting dissimilarity matrix.<n>We present such a reformulation, em continuous MDS.
  arXiv  Detail & Related papers  (2024-02-06T22:13:51Z)
• Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams [34.7582575446942]
  We give the first approximation algorithm for MDS with quasi-polynomial dependency on $Delta.<n>Our algorithms are based on a novel geometry-aware analysis of a conditional rounding of the Sherali-Adams LP.
  arXiv  Detail & Related papers  (2023-11-29T17:42:05Z)
• Tight Bounds for Volumetric Spanners and Applications [19.839528728535274]
  Given a set of points of interest, a spanner is a determinant of points using which all the points can be expressed using "small" coefficients. In this paper, we give almost optimal bounds on the size of spanners for all $ell_p$ vectors, and show that they can be constructed using a simple local search procedure.
  arXiv  Detail & Related papers  (2023-09-29T22:43:30Z)
• Polynomial Width is Sufficient for Set Representation with High-dimensional Features [69.65698500919869]
  DeepSets is the most widely used neural network architecture for set representation. We present two set-element embedding layers: (a) linear + power activation (LP) and (b) linear + exponential activations (LE)
  arXiv  Detail & Related papers  (2023-07-08T16:00:59Z)
• Parameterized Approximation Schemes for Clustering with General Norm Objectives [0.6956677722498498]
  This paper considers the well-studied regime of designing a $(k,epsilon)$-approximation algorithm for a $k$-clustering problem. Our main contribution is a clean and simple EPAS that settles more than ten clustering problems.
  arXiv  Detail & Related papers  (2023-04-06T15:31:37Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  We convert high-dimensional $ell_infty$-approachability problems to low-dimensional pseudonorm approachability problems. We develop an algorithmic theory of pseudonorm approachability, analogous to previous work on approachability for $ell$ and other norms.
  arXiv  Detail & Related papers  (2023-02-03T03:19:14Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  A basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = Omega(, d2/mathrmpolylog(d),)$. Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix.
  arXiv  Detail & Related papers  (2022-08-19T18:00:34Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  We consider the problem of quantizing a linear model learned from measurements. We derive an information-theoretic lower bound for the minimax risk under this setting. We show that our method and upper-bounds can be extended for two-layer ReLU neural networks.
  arXiv  Detail & Related papers  (2022-02-23T02:39:04Z)
• De Rham compatible Deep Neural Network FEM [0.0]
  We generalize previous results in that no restrictions on the regular simplicial partitions $mathcalT$ of $Omega$ are required for DNN. We indicate generalizations of our constructions to higher-order compatible spaces and other, non-compatible classes of discretizations.
  arXiv  Detail & Related papers  (2022-01-14T11:22:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.