論文の概要: Low Complexity Sequential Search with Size-Dependent Measurement Noise
- arxiv url: http://arxiv.org/abs/2005.07814v2
- Date: Tue, 1 Sep 2020 17:55:40 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-02 23:36:29.240569
- Title: Low Complexity Sequential Search with Size-Dependent Measurement Noise
- Title（参考訳）: サイズ依存計測ノイズを用いた低複雑性シーケンシャル探索
- Authors: Sung-En Chiu, Tara Javidi
- Abstract要約: 本稿では、エージェントが任意の時間にその領域にターゲットが存在するかどうかを問い合わせる領域を選択することができるターゲットローカライゼーション問題について考察する。
アレイ処理における初期ビームアライメント、ネットワークにおける重ヒッタ検出、ロボット工学におけるビジュアルサーチといった実用的応用により、我々は事実上重要な複雑さの制約/指標を考察する。
新規検索戦略として$dyaPM$と$hiePM$が提案されている。
- 参考スコア（独自算出の注目度）: 19.201555109949677
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper considers a target localization problem where at any given time an
agent can choose a region to query for the presence of the target in that
region. The measurement noise is assumed to be increasing with the size of the
query region the agent chooses. Motivated by practical applications such as
initial beam alignment in array processing, heavy hitter detection in
networking, and visual search in robotics, we consider practically important
complexity constraints/metrics: \textit{time complexity}, \textit{computational
and memory complexity}, and the complexity of possible query sets in terms of
geometry and cardinality.
Two novel search strategy, $dyaPM$ and $hiePM$, are proposed. Pertinent to
the practicality of out solutions, $dyaPM$ and $hiePM$ are of a connected query
geometry (i.e. query set is always a connected set) implemented with low
computational and memory complexity. Additionally, $hiePM$ has a hierarchical
structure and, hence, a further reduction in the cardinality of possible query
sets, making $hiePM$ practically suitable for applications such as beamforming
in array processing where memory limitations favors a smaller codebook size.
Through a unified analysis with Extrinsic Jensen Shannon (EJS) Divergence,
$dyaPM$ is shown to be asymptotically optimal in search time complexity
(asymptotic in both resolution (rate) and error (reliability)). On the other
hand, $hiePM$ is shown to be near-optimal in rate. In addition, both $hiePM$
and $dyaPM$ are shown to outperform prior work in the non-asymptotic regime.
- Abstract（参考訳）: 本稿では、エージェントが任意の時間にその領域にターゲットが存在するかどうかを問い合わせる領域を選択することができるターゲットローカライゼーション問題について考察する。
測定ノイズは、エージェントが選択するクエリ領域のサイズに応じて増加すると仮定される。
配列処理における初期ビームアライメント,ネットワークのヘビーヒッター検出,ロボティクスにおけるビジュアルサーチといった実用的な応用に動機づけられ,実際的に重要な複雑性制約/メトリクスである \textit{time complexity}, \textit{computational and memory complexity},幾何や濃度の観点から可能なクエリ集合の複雑さを考える。
新規検索戦略として$dyaPM$と$hiePM$が提案されている。
アウトソリューションの実用性に応じて、$dyaPM$ と $hiePM$ は、計算とメモリの複雑さの低い(すなわち、クエリ集合は常に連結集合である)連結クエリ幾何学である。
さらに$hiePM$は階層構造を持ち、従ってクエリセットの濃度がさらに低下するので、メモリ制限がより小さいコードブックサイズを好む配列処理のビームフォーミングのようなアプリケーションに$hiePM$は実用的に適している。
Extrinsic Jensen Shannon (EJS) Divergence を用いた統一解析により、$dyaPM$ は検索時間の複雑さ(解像度(レート)とエラー(信頼性)の両方において漸近的に最適であることが示されている。
一方、$hiepm$は最適に近い値であることが示されている。
さらに、$hiePM$ と $dyaPM$ は、非漸近的体制における事前の作業より優れていることを示す。
関連論文リスト
- Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity [0.0]
我々は最も高速な決定論的アルゴリズムの近似係数を6+epsilon$から5+epsilon$に改善する。
本手法は, しきい値のグリーディ・サブルーチンと, 候補解としての2つの解集合の構築という, 2つの成分の性能を最適化することに基づいている。
論文 参考訳（メタデータ） (2024-05-20T02:24:58Z) - Robust Approximation Algorithms for Non-monotone $k$-Submodular
Maximization under a Knapsack Constraint [0.0]
2つの決定論的近似アルゴリズムは、knapsack制約の下での非単調な$k$-部分モジュラー複雑性の問題に対して提案される。
提案アルゴリズムは,非単調な目的に対して,O(nk)$クエリの計算量内で一定の近似比を提供する。
論文 参考訳（メタデータ） (2023-09-21T12:42:52Z) - Linear Query Approximation Algorithms for Non-monotone Submodular
Maximization under Knapsack Constraint [16.02833173359407]
この研究は、2つの定数係数近似アルゴリズムを導入し、クナップサック制約の基底集合に対して非単調な部分モジュラーに対して線形なクエリ複雑性を持つ。
$mathsfDLA$は6+epsilon$の近似係数を提供する決定論的アルゴリズムであり、$mathsfRLA$は4+epsilon$の近似係数を持つランダム化アルゴリズムである。
論文 参考訳（メタデータ） (2023-05-17T15:27:33Z) - Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
線形マルコフ決定過程(MDP)を学習するための新たな報酬なしアルゴリズムを提案する。
我々のアルゴリズムの核心は、探索駆動の擬似回帰を用いた不確実性重み付き値目標回帰である。
我々のアルゴリズムは$tilde O(d2varepsilon-2)$ episodesを探索するだけで、$varepsilon$-optimal policyを見つけることができる。
論文 参考訳（メタデータ） (2023-03-17T17:53:28Z) - PRECISION: Decentralized Constrained Min-Max Learning with Low
Communication and Sample Complexities [25.153506493249854]
min-max最適化問題に対する適応型マルチエージェント学習手法を提案する。
また,反復回数を削減できるPrecisionというアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-03-05T00:26:10Z) - The Hypervolume Indicator Hessian Matrix: Analytical Expression,
Computational Time Complexity, and Sparsity [4.523133864190258]
本稿では,$d$次元決定空間における$n$点の(固定サイズ)集合からスカラー超体積指標値への写像のヘッセン行列の解析式を確立する。
ヘッセン行列はニュートン・ラフソン最適化法のような二階法において重要な役割を担い、局所最適集合の検証に使用できる。
論文 参考訳（メタデータ） (2022-11-08T11:24:18Z) - Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-01T14:10:38Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。
提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
論文 参考訳（メタデータ） (2021-03-03T22:42:15Z) - Average-case Complexity of Teaching Convex Polytopes via Halfspace
Queries [55.28642461328172]
平均的なケースの教えの複雑さは$Theta(d)$であり、最悪のケースの教えの複雑さは$Theta(n)$とは対照的である。
我々の洞察は、$phi$-separable dichotomiesの平均ケースの複雑さに厳密な拘束力を確立することを可能にする。
論文 参考訳（メタデータ） (2020-06-25T19:59:24Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。