論文の概要: Metric Dimension and Resolvability of Jaccard Spaces

• arxiv url: http://arxiv.org/abs/2405.11424v2
• Date: Thu, 27 Jun 2024 04:41:07 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-28 18:56:54.857701
• Title: Metric Dimension and Resolvability of Jaccard Spaces
• Title（参考訳）: ジャカード空間の計量次元と可解性
• Authors: Manuel E. Lladser, Alexander J. Paradise,
• Abstract要約: 計量空間内の点の部分集合は、空間内の各点が部分集合内の各点への距離によって一意に特徴づけられるとき、それを解くと言われる。 高い確率で、濃度のすべての異なる部分集合が、最大$sqrt|X|/ln|X|$で解けるのに十分であることを示す。
• 参考スコア（独自算出の注目度）: 49.1574468325115
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A subset of points in a metric space is said to resolve it if each point in the space is uniquely characterized by its distance to each point in the subset. In particular, resolving sets can be used to represent points in abstract metric spaces as Euclidean vectors. Importantly, due to the triangle inequality, points close by in the space are represented as vectors with similar coordinates, which may find applications in classification problems of symbolic objects under suitably chosen metrics. In this manuscript, we address the resolvability of Jaccard spaces, i.e., metric spaces of the form $(2^X,\text{Jac})$, where $2^X$ is the power set of a finite set $X$, and $\text{Jac}$ is the Jaccard distance between subsets of $X$. Specifically, for different $a,b\in 2^X$, $\text{Jac}(a,b)=|a\Delta b|/|a\cup b|$, where $|\cdot|$ denotes size (i.e., cardinality) and $\Delta$ denotes the symmetric difference of sets. We combine probabilistic and linear algebra arguments to construct highly likely but nearly optimal (i.e., of minimal size) resolving sets of $(2^X,\text{Jac})$. In particular, we show that the metric dimension of $(2^X,\text{Jac})$, i.e., the minimum size of a resolving set of this space, is $\Theta(|X|/\ln|X|)$. In addition, we show that a much smaller subset of $2^X$ suffices to resolve, with high probability, all different pairs of subsets of $X$ of cardinality at most $\sqrt{|X|}/\ln|X|$, up to a factor.
• Abstract（参考訳）: 計量空間内の点の部分集合は、空間内の各点が部分集合内の各点への距離によって一意に特徴づけられるとき、それを解くと言われる。 特に、解集合は抽象計量空間の点をユークリッドベクトルとして表すのに使うことができる。 重要なことに、三角形の不等式のため、空間の近傍の点は同様の座標を持つベクトルとして表現され、適度に選択された測度の下で記号的対象の分類問題に応用できる。 この写本では、ジャカード空間の可解性、すなわち、$(2^X,\text{Jac})$ という形の計量空間に対処し、$2^X$ は有限集合 $X$ のパワー集合であり、$\text{Jac}$ は$X$ の部分集合の間のジャカード距離である。 具体的には、異なる$a,b\in 2^X$, $\text{Jac}(a,b)=|a\Delta b|/|a\cup b|$に対して、$|\cdot|$はサイズ(すなわち濃度)を表し、$\Delta$は集合の対称差を表す。 確率的および線型代数的引数を組み合わさって、非常に確率的だがほぼ最適(最小サイズ)な$(2^X,\text{Jac})$の解集合を構成する。 特に、計量次元が$(2^X,\text{Jac})$、すなわち、この空間の解集合の最小サイズは$\Theta(|X|/\ln|X|)$であることを示す。 さらに、高い確率で 2^X$ suffices のより小さな部分集合が、最大で $\sqrt{|X|}/\ln|X|$ の濃度のすべての異なる集合の集合を、最大で 1 つの因子まで解決することを示した。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Dimension-free Remez Inequalities and norm designs [48.5897526636987]
  ドメインのクラスが$X$で、テストセットが$Y$で、Emphnormと呼ばれ、次元のないRemez型の見積もりを楽しむ。 ポリトーラスに$f$が拡張されたとき、$f$の上限は$mathcalO(log K)2d$以上増加しないことを示す。
  論文  参考訳（メタデータ） (2023-10-11T22:46:09Z)
• Tight Bounds for Volumetric Spanners and Applications [19.839528728535274]
  興味のある点の集合が与えられたとき、スパンナーはすべての点を「小さい」係数で表現できる点の行列式である。 本稿では,すべての$ell_p$ベクトルに対して,スパンナーのサイズをほぼ最適に制限し,簡単な局所探索手法を用いて構築可能であることを示す。
  論文  参考訳（メタデータ） (2023-09-29T22:43:30Z)
• Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
  次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。 また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
  論文  参考訳（メタデータ） (2023-05-12T08:43:28Z)
• Metricizing the Euclidean Space towards Desired Distance Relations in Point Clouds [1.2366208723499545]
  我々は教師なし学習アルゴリズム、具体的には$k$-Means and density-based clustering algorithm(DBSCAN)を攻撃している。 クラスタリングアルゴリズムの結果は、特定の距離関数を使用するための標準化された固定された処方令がなければ、一般的には信頼できない可能性がある。
  論文  参考訳（メタデータ） (2022-11-07T16:37:29Z)
• Matching Map Recovery with an Unknown Number of Outliers [0.0]
  我々は,2組の$d$次元雑音特徴ベクトル間のマッチング写像を求める問題を考察する。 高次元環境では、信号対雑音比が5(dlog(4nm/alpha))1/4$より大きい場合、真のマッチングマップは確率1-alpha$で復元可能であることを示す。
  論文  参考訳（メタデータ） (2022-10-24T15:59:10Z)
• Uncertainties in Quantum Measurements: A Quantum Tomography [52.77024349608834]
  量子系 $S$ に関連する可観測物は非可換代数 $mathcal A_S$ を形成する。 密度行列 $rho$ は可観測物の期待値から決定できると仮定される。 アーベル代数は内部自己同型を持たないので、測定装置は可観測物の平均値を決定することができる。
  論文  参考訳（メタデータ） (2021-12-14T16:29:53Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
  論文  参考訳（メタデータ） (2021-09-06T14:21:43Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。 2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
  論文  参考訳（メタデータ） (2021-03-10T07:33:03Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。