論文の概要: Matching Map Recovery with an Unknown Number of Outliers
- arxiv url: http://arxiv.org/abs/2210.13354v1
- Date: Mon, 24 Oct 2022 15:59:10 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-25 22:18:49.427561
- Title: Matching Map Recovery with an Unknown Number of Outliers
- Title（参考訳）: 未知数の異常値によるマップリカバリのマッチング
- Authors: Arshak Minasyan, Tigran Galstyan, Sona Hunanyan, Arnak Dalalyan
- Abstract要約: 我々は,2組の$d$次元雑音特徴ベクトル間のマッチング写像を求める問題を考察する。
高次元環境では、信号対雑音比が5(dlog(4nm/alpha))1/4$より大きい場合、真のマッチングマップは確率1-alpha$で復元可能であることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of finding the matching map between two sets of
$d$-dimensional noisy feature-vectors. The distinctive feature of our setting
is that we do not assume that all the vectors of the first set have their
corresponding vector in the second set. If $n$ and $m$ are the sizes of these
two sets, we assume that the matching map that should be recovered is defined
on a subset of unknown cardinality $k^*\le \min(n,m)$. We show that, in the
high-dimensional setting, if the signal-to-noise ratio is larger than
$5(d\log(4nm/\alpha))^{1/4}$, then the true matching map can be recovered with
probability $1-\alpha$. Interestingly, this threshold does not depend on $k^*$
and is the same as the one obtained in prior work in the case of $k =
\min(n,m)$. The procedure for which the aforementioned property is proved is
obtained by a data-driven selection among candidate mappings
$\{\hat\pi_k:k\in[\min(n,m)]\}$. Each $\hat\pi_k$ minimizes the sum of squares
of distances between two sets of size $k$. The resulting optimization problem
can be formulated as a minimum-cost flow problem, and thus solved efficiently.
Finally, we report the results of numerical experiments on both synthetic and
real-world data that illustrate our theoretical results and provide further
insight into the properties of the algorithms studied in this work.
- Abstract（参考訳）: 我々は,2組の$d$次元雑音特徴ベクトル間のマッチング写像を求める問題を考察する。
私たちの設定の特徴的な特徴は、第1集合のすべてのベクトルが対応するベクトルを第2集合に持つと仮定しないことである。
もし$n$ と $m$ がこれらの2つの集合のサイズであれば、回復すべきマッチング写像は未知の濃度 $k^*\le \min(n,m)$ の部分集合上で定義されると仮定する。
高次元設定では、信号-雑音比が5(d\log(4nm/\alpha))^{1/4}$より大きい場合、真のマッチングマップは確率1-\alpha$で復元可能であることを示す。
興味深いことに、このしきい値は$k^*$に依存しず、$k = \min(n,m)$の場合の前の作業で得られたものと同じである。
上記の性質が証明された手順は、候補マッピング $\{\hat\pi_k:k\in[\min(n,m)]\}$ 間のデータ駆動選択によって得られる。
各$\hat\pi_k$ は、2つのサイズ $k$ の間の距離の平方和を最小化する。
結果の最適化問題は最小コストのフロー問題として定式化することができ、効率よく解ける。
最後に, 合成データと実世界データの両方における数値実験の結果について報告し, 本研究で研究したアルゴリズムの性質について考察する。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Combinatorial optimization of the coefficient of determination [0.0]
決定係数が最も高い平面上の$n$点の$k$-部分集合を選択するための効率的なアルゴリズムを開発する。
誤差のない$n=30$までの試行で,提案手法の最適性を実験的に実証した。
論文 参考訳（メタデータ） (2024-10-12T00:53:25Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering [42.526664955704746]
そこで我々は,リストデコダブルなスパース平均推定のための,新しい,概念的にシンプルな手法を開発した。
特に、$k$-sparse方向の「確実に有界な」$t-thモーメントを持つ分布の場合、このアルゴリズムは、サンプル複雑性$m = (klog(n))O(t)/alpha(mnt)$の誤差を1/alpha(O (1/t)$で達成する。
Gaussian inliers の特別な場合、我々のアルゴリズムは $Theta (sqrtlog) の最適誤差を保証する。
論文 参考訳（メタデータ） (2022-06-10T17:38:18Z) - Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。
我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文 参考訳（メタデータ） (2022-03-18T18:50:52Z) - Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
本稿では, エッジ重み付き2つの完全グラフが潜在測地によって相関する問題について検討する。
近似最大極大推定器を導出し、高い確率で$pi*$の完全回復を確実に達成する。
副次的な発見として、[Ume88] の有望なスペクトルアルゴリズムが幾何モデルにおける最大可能性のさらなる近似として現れることを示す。
論文 参考訳（メタデータ） (2022-02-22T04:14:45Z) - Computational Complexity of Normalizing Constants for the Product of
Determinantal Point Processes [12.640283469603357]
正規化定数の計算における計算複雑性について検討する。
例えば、$sum_Sdet(bf A_S,S)p$は、すべての(固定された)正の偶数に対して、$p$ が UP-hard で Mod$_3$P-hard であることを示す。
論文 参考訳（メタデータ） (2021-11-28T14:08:25Z) - On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。
本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。
我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
論文 参考訳（メタデータ） (2020-08-15T11:06:45Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。