論文の概要: An Improved Greedy Algorithm for Subset Selection in Linear Estimation

• arxiv url: http://arxiv.org/abs/2203.16070v1
• Date: Wed, 30 Mar 2022 05:52:16 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-17 07:06:14.713918
• Title: An Improved Greedy Algorithm for Subset Selection in Linear Estimation
• Title（参考訳）: 線形推定におけるサブセット選択のための改良されたグレディアルゴリズム
• Authors: Shamak Dutta, Nils Wilde, Stephen L. Smith
• Abstract要約: 有限個の予測位置において、観測値の最もよい推定値を与えるような k 個の位置の集合を求める空間場における部分選択問題を考える。 観測選択の1つのアプローチは、空間の格子離散化を行い、グリードアルゴリズムを用いて近似解を得ることである。 本稿では,予測位置と予測位置によって形成される傾斜角の遠心点のみからなる探索空間を考慮し,計算複雑性を低減する手法を提案する。
• 参考スコア（独自算出の注目度）: 5.994412766684842
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we consider a subset selection problem in a spatial field where we seek to find a set of k locations whose observations provide the best estimate of the field value at a finite set of prediction locations. The measurements can be taken at any location in the continuous field, and the covariance between the field values at different points is given by the widely used squared exponential covariance function. One approach for observation selection is to perform a grid discretization of the space and obtain an approximate solution using the greedy algorithm. The solution quality improves with a finer grid resolution but at the cost of increased computation. We propose a method to reduce the computational complexity, or conversely to increase solution quality, of the greedy algorithm by considering a search space consisting only of prediction locations and centroids of cliques formed by the prediction locations. We demonstrate the effectiveness of our proposed approach in simulation, both in terms of solution quality and runtime.
• Abstract（参考訳）: 本稿では, 有限個の予測位置において, 観測値の最適な推定値を与えるk個の位置の集合を求める空間場における部分選択問題について考察する。 測定は連続体内の任意の位置で行うことができ、異なる点における場の値間の共分散は広く用いられる2乗指数共分散関数によって与えられる。 観測選択の1つのアプローチは、空間の格子離散化を行い、グリードアルゴリズムを用いて近似解を得ることである。 解のクオリティは、より細かいグリッド解像度で向上するが、計算量を増やすコストがかかる。 本研究では,予測位置と予測位置によって形成されたクランクのセンタロイドのみからなる探索空間を考えることにより,計算複雑性を低減し,逆に解質を向上させる手法を提案する。 シミュレーションにおける提案手法の有効性を,ソリューションの品質と実行性の両方の観点から示す。

関連論文リスト

• Adaptive $k$-nearest neighbor classifier based on the local estimation of the shape operator [49.87315310656657]
  我々は, 局所曲率をサンプルで探索し, 周辺面積を適応的に定義する適応型$k$-nearest(kK$-NN)アルゴリズムを提案する。 多くの実世界のデータセットから、新しい$kK$-NNアルゴリズムは、確立された$k$-NN法と比較してバランスの取れた精度が優れていることが示されている。
  論文  参考訳（メタデータ） (2024-09-08T13:08:45Z)
• A Stochastic-Gradient-based Interior-Point Algorithm for Solving Smooth Bound-Constrained Optimization Problems [12.29270365918848]
  提案アルゴリズムは、他のインテリアポイント法からの主観的特異な制約に基づいている。 提案アルゴリズムは,プロジェクション,ステップサイズ,シーケンスシーケンスのバランスを慎重に保ち,数値的および決定論的両方の設定において収束を保証する。
  論文  参考訳（メタデータ） (2023-04-28T15:30:43Z)
• Stochastic Approximation with Decision-Dependent Distributions: Asymptotic Normality and Optimality [8.771678221101368]
  我々は、アルゴリズムが使用するデータ分布が反復列に沿って進化する決定依存問題に対する近似を解析する。 軽微な仮定の下では、アルゴリズムの反復と解の偏差は正規であることを示す。 また,平均化アルゴリズムの性能は局所的に最小限であることを示す。
  論文  参考訳（メタデータ） (2022-07-09T01:44:17Z)
• Distributed stochastic proximal algorithm with random reshuffling for non-smooth finite-sum optimization [28.862321453597918]
  非滑らかな有限サム最小化は機械学習の基本的な問題である。 本稿では,確率的リシャフリングを用いた分散近位勾配アルゴリズムを開発し,その問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-11-06T07:29:55Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
  任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。 提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
  論文  参考訳（メタデータ） (2021-05-23T19:21:55Z)
• Distributed Adaptive Nearest Neighbor Classifier: Algorithm and Theory [6.696267547013535]
  そこで本研究では,データ駆動基準によりパラメータ選択された,近接する隣人の数がパラメータとなる分散適応型NN分類器を提案する。 有限標本性能を向上する最適チューニングパラメータを探索する際,早期停止規則を提案する。 特に、サブサンプルサイズが十分に大きい場合、提案した分類器がほぼ最適な収束率を達成することを示す。
  論文  参考訳（メタデータ） (2021-05-20T14:38:41Z)
• Towards Feature-Based Performance Regression Using Trajectory Data [0.9281671380673306]
  ブラックボックス最適化は非常に活発な研究領域であり、毎年多くの新しいアルゴリズムが開発されている。 アルゴリズムの多様性はメタプロブレム(メタプロブレム):どのアルゴリズムが与えられた問題を選択するか? 過去の研究では、探索ランドスケープ分析に基づくインスタンスごとのアルゴリズム選択が、このメタプロブレムに取り組むための効率的な手段であることが示されている。
  論文  参考訳（メタデータ） (2021-02-10T10:19:13Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。 本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。 ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
  論文  参考訳（メタデータ） (2020-06-11T19:40:38Z)
• Optimization of Graph Total Variation via Active-Set-based Combinatorial Reconditioning [48.42916680063503]
  本稿では,この問題クラスにおける近位アルゴリズムの適応型事前条件付け手法を提案する。 不活性エッジのネスト・フォレスト分解により局所収束速度が保証されることを示す。 この結果から,局所収束解析は近似アルゴリズムにおける可変指標選択の指針となることが示唆された。
  論文  参考訳（メタデータ） (2020-02-27T16:33:09Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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