論文の概要: Alternating minimization algorithm with initialization analysis for r-local and k-sparse unlabeled sensing

• arxiv url: http://arxiv.org/abs/2211.07621v2
• Date: Thu, 12 Dec 2024 01:34:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-13 17:00:11.236205
• Title: Alternating minimization algorithm with initialization analysis for r-local and k-sparse unlabeled sensing
• Title（参考訳）: r-ローカルおよびk-スパース非ラベルセンシングの初期化解析を用いた交代最小化アルゴリズム
• Authors: Ahmed Abbasi, Shuchin Aeron, Abiy Tasissa,
• Abstract要約: 実験の結果,提案アルゴリズムは高速で,置換モデルにも適用でき,測定行列の選択にも頑健であることがわかった。 また,リンク線形回帰問題に対して,本アルゴリズムを複数の実データセット上で検証し,ベースライン法よりも優れた性能を示す。
• 参考スコア（独自算出の注目度）: 13.433637831618007
• License:
• Abstract: Unlabeled sensing is a linear inverse problem with permuted measurements. We propose an alternating minimization (AltMin) algorithm with a suitable initialization for two widely considered permutation models: partially shuffled/$k$-sparse permutations and $r$-local/block diagonal permutations. Key to the performance of the AltMin algorithm is the initialization. For the exact unlabeled sensing problem, assuming either a Gaussian measurement matrix or a sub-Gaussian signal, we bound the initialization error in terms of the number of blocks $s$ and the number of shuffles $k$. Experimental results show that our algorithm is fast, applicable to both permutation models, and robust to choice of measurement matrix. We also test our algorithm on several real datasets for the linked linear regression problem and show superior performance compared to baseline methods.
• Abstract（参考訳）: ラベルなしセンシングは、置換測定の線形逆問題である。 本稿では、部分シャッフル/$k$スパース置換と$r$-ローカル/ブロック対角置換という2つの広く検討されている置換モデルに対して、適切な初期化を施した交互最小化(AltMin)アルゴリズムを提案する。 AltMinアルゴリズムの性能の鍵は初期化である。 厳密なラベル付きセンシング問題に対して、ガウス測度行列か準ガウス信号のいずれかを仮定すると、初期化誤差はブロック数$s$とシャッフル数$k$に制限する。 実験の結果,提案アルゴリズムは高速で,置換モデルにも適用でき,測定行列の選択にも頑健であることがわかった。 また,リンク線形回帰問題に対して,本アルゴリズムを複数の実データセット上で検証し,ベースライン法よりも優れた性能を示す。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Noise misleads rotation invariant algorithms on sparse targets [0.0]
  回転不変アルゴリズムのクラスは疎線形問題を学習するのに最適であることを示す。 回転対称問題に対してベイズ最適アルゴリズムの下位境界を用いてこれを証明する。 次に、単純な非回転不変アルゴリズムに対して、同じ問題に対してより低い上限を証明した。
  論文  参考訳（メタデータ） (2024-03-05T06:25:19Z)
• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Alternating minimization for generalized rank one matrix sensing: Sharp predictions from a random initialization [5.900674344455754]
  ランクランダム行列の特性をdで推定する手法を示す。 鋭い収束は、単一のステップで正確な回復を保証する。 我々の分析は、この問題の他のいくつかの特性も明らかにしている。
  論文  参考訳（メタデータ） (2022-07-20T05:31:05Z)
• Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensing [9.264464791978362]
  Alternating Least Squares (ALS) は $O(log n + log (1/varepsilon)) $ iterations において $varepsilon$-accuracy で真の解に収束することを示す。 我々の証明の鍵となるのは、ALSの軌道が反復する観察は、ランダムな測定行列の特定のエントリのみに非常に軽度に依存することである。
  論文  参考訳（メタデータ） (2022-04-25T08:55:38Z)
• PROMPT: Parallel Iterative Algorithm for $\ell_{p}$ norm linear regression via Majorization Minimization with an application to semi-supervised graph learning [0.0]
  スパースリカバリ,データクラスタリング,半教師付き学習など,いくつかの応用がある。 我々は、MajolizaTion Minimization (PROMPT)による$ell_P$ノルム回帰のための並列反復AlgOrithMを提案する。
  論文  参考訳（メタデータ） (2021-10-23T10:19:11Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Efficient Algorithms for Multidimensional Segmented Regression [42.046881924063044]
  多次元回帰を用いた固定設計の基本問題について検討する。 我々は任意の固定次元におけるこの問題に対する最初のサンプルと計算効率のよいアルゴリズムを提供する。 提案アルゴリズムは,多次元的条件下では新規な,単純なマージ反復手法に依存している。
  論文  参考訳（メタデータ） (2020-03-24T19:39:34Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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