論文の概要: A Sketching Method for Finding the Closest Point on a Convex Hull

• arxiv url: http://arxiv.org/abs/2102.10502v1
• Date: Sun, 21 Feb 2021 03:55:18 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-23 14:34:21.278220
• Title: A Sketching Method for Finding the Closest Point on a Convex Hull
• Title（参考訳）: 凸面上の最も近い点を見つけるためのスケッチ法
• Authors: Roozbeh Yousefzadeh
• Abstract要約: 我々は,データセットの凸殻上の点を,その外側の問合せ点に最も近いようにスケッチするアルゴリズムを開発した。 本手法は, 既成のアルゴリズムよりも高速な凸問題の最適解を導出する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We develop a sketching algorithm to find the point on the convex hull of a dataset, closest to a query point outside it. Studying the convex hull of datasets can provide useful information about their geometric structure and their distribution. Many machine learning datasets have large number of samples with large number of features, but exact algorithms in computational geometry are usually not designed for such setting. Alternatively, the problem can be formulated as a linear least-squares problem with linear constraints. However, solving the problem using standard optimization algorithms can be very expensive for large datasets. Our algorithm uses a sketching procedure to exploit the structure of the data and unburden the optimization process from irrelevant points. This involves breaking the data into pieces and gradually putting the pieces back together, while improving the optimal solution using a gradient project method that can rapidly change its active set of constraints. Our method eventually leads to the optimal solution of our convex problem faster than off-the-shelf algorithms.
• Abstract（参考訳）: 我々は,データセットの凸殻上の点を,その外側の問合せ点に最も近いようにスケッチするアルゴリズムを開発した。 データセットの凸包の研究は、その幾何学的構造とその分布に関する有用な情報を提供することができる。 多くの機械学習データセットは多数の特徴を持つサンプルを持っているが、計算幾何学における正確なアルゴリズムは通常そのような設定のために設計されていない。 あるいは、線形制約を持つ線型最小二乗問題として定式化することもできる。 しかし、標準最適化アルゴリズムを使って問題を解決することは、大規模なデータセットにとって非常に高価である。 提案アルゴリズムでは,データ構造を利用したスケッチ処理を行い,無関係な点から最適化プロセスを解き放つ。 これには、データを断片に分割し、徐々にピースをつなぎ合わせながら、アクティブな制約セットを迅速に変更できる勾配のプロジェクトメソッドを使用して最適なソリューションを改善します。 本手法は, 既成のアルゴリズムよりも高速な凸問題の最適解を導出する。

関連論文リスト

• Mathematical Programming Algorithms for Convex Hull Approximation with a Hyperplane Budget [0.0]
  我々は、すべての正の点と負の点を含む、ほとんどのK面を持つ凸多面体を探索する。 この問題は純粋凸多面体近似の文献で知られている。 私たちの関心は、制約学習の応用の可能性に起因しています。
  論文  参考訳（メタデータ） (2024-07-24T15:08:52Z)
• CLIPPER: Robust Data Association without an Initial Guess [38.56736000339334]
  初期推定を必要としないデータアソシエーションのためのグラフ理論の定式化について検討する。 既存のグラフ理論アプローチは、未重み付きグラフを最適化し、重み付きエッジに符号化された重要な一貫性情報を破棄し、NPハード問題を正確に解こうとする。 この問題に対して2つの緩和法を導入する: 凸半有限緩和法は経験的に厳密であることが判明し、CLIPPERと呼ばれる高速な1次アルゴリズムはミリ秒でほぼ最適解に到達する。
  論文  参考訳（メタデータ） (2024-02-11T19:16:01Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
  次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。 我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-16T13:57:19Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• Fast and Robust Non-Rigid Registration Using Accelerated Majorization-Minimization [35.66014845211251]
  非剛性登録は、ターゲット形状と整合する非剛性な方法でソース形状を変形させるが、コンピュータビジョンにおける古典的な問題である。 既存のメソッドは通常$ell_p$型ロバストノルムを使用してアライメントエラーを測定し、変形の滑らかさを規則化する。 本稿では、アライメントと正規化のためのグローバルなスムーズなロバストノルムに基づく、ロバストな非剛体登録のための定式化を提案する。
  論文  参考訳（メタデータ） (2022-06-07T16:00:33Z)
• Efficient Projection-Free Online Convex Optimization with Membership Oracle [11.745866777357566]
  ユークリッド球上で定義された任意のアルゴリズムAを、球に含まれる制約付き集合 C 上のアルゴリズムに変換する新しい還元法を提案する。 我々の削減には、O(T log T) を T ラウンド後に C 上で Oracle に呼び出しる必要があり、C 上の線形最適化は不要である。
  論文  参考訳（メタデータ） (2021-11-10T17:22:29Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)
• Aligning Partially Overlapping Point Sets: an Inner Approximation Algorithm [80.15123031136564]
  変換の値に関する事前情報がない点集合を整列するロバストな手法を提案する。 我々のアルゴリズムは変換の正規化を必要とせず、変換の値に関する事前情報がない状況に対処できる。 実験により,提案手法が最先端のアルゴリズムよりも高いロバスト性を示した。
  論文  参考訳（メタデータ） (2020-07-05T15:23:33Z)

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

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