論文の概要: Faster Maximum Feasible Subsystem Solutions for Dense Constraint Matrices

• arxiv url: http://arxiv.org/abs/2102.05744v1
• Date: Wed, 10 Feb 2021 21:26:27 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-12 14:05:00.601196
• Title: Faster Maximum Feasible Subsystem Solutions for Dense Constraint Matrices
• Title（参考訳）: 密制約行列に対する高速最大実現可能サブシステム解
• Authors: Fereshteh Fakhar Firouzeh, John W. Chinneck, Sreeraman Rajan
• Abstract要約: Max Feasible Subsystem 問題は、機械学習や圧縮センシングといった幅広い応用において重要である。 厳密な制約行列の場合,既存のFSを拡張して,解の品質を維持したり改善したりしながら,その速度を大幅に向上させる。 圧縮センシングにおける二項分類とスパースリカバリ(sparse recovery)という,密度制約行列を持つ2つのアプリケーション上で,拡張アルゴリズムを検証した。
• 参考スコア（独自算出の注目度）: 0.2578242050187029
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Finding the largest cardinality feasible subset of an infeasible set of linear constraints is the Maximum Feasible Subsystem problem (MAX FS). Solving this problem is crucial in a wide range of applications such as machine learning and compressive sensing. Although MAX FS is NP-hard, useful heuristic algorithms exist, but these can be slow for large problems. We extend the existing heuristics for the case of dense constraint matrices to greatly increase their speed while preserving or improving solution quality. We test the extended algorithms on two applications that have dense constraint matrices: binary classification, and sparse recovery in compressive sensing. In both cases, speed is greatly increased with no loss of accuracy.
• Abstract（参考訳）: 線形制約の不可能集合の最大のカーディナリティ実現可能なサブセットを見つけることは、最大実現可能なサブシステム問題(MAX FS)である。 この問題を解決することは、機械学習や圧縮センシングなど、幅広いアプリケーションにおいて不可欠である。 MAX FSはNPハードであるが、有用なヒューリスティックアルゴリズムが存在するが、大きな問題では遅い。 我々は,厳密な制約行列の場合の既存のヒューリスティックスを拡張し,解の品質を維持したり改善したりしながら,その速度を大幅に向上させる。 重み付き制約行列を持つ2つのアプリケーションで拡張アルゴリズムをテストする:バイナリ分類と圧縮センシングにおけるスパース回復。 どちらの場合も、精度を損なわずに速度が大幅に向上します。

関連論文リスト

• 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)
• HyperAttention: Long-context Attention in Near-Linear Time [78.33061530066185]
  本稿では,長期的文脈の複雑さの増大に伴う計算課題に対処するため,HyperAttentionという近似的な注意機構を提案する。 実証的には、大規模なエントリを特定するためにLocality Sensitive Hashing(LSH)を使用して、HyperAttentionは既存のメソッドよりも優れています。 各種長文長データセットにおけるHyperAttentionの実証的性能を検証した。
  論文  参考訳（メタデータ） (2023-10-09T17:05:25Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• An Inexact Feasible Quantum Interior Point Method for Linearly Constrained Quadratic Optimization [0.0]
  量子線形システムアルゴリズム(QLSA)は、線形システムの解法に依存するアルゴリズムを高速化する可能性がある。 本研究では, 線形制約付き2次最適化問題の解法において, 実効性のないQIPM(Inexact-Feasible QIPM)を提案する。
  論文  参考訳（メタデータ） (2023-01-13T01:36:13Z)
• Block-coordinate Frank-Wolfe algorithm and convergence analysis for semi-relaxed optimal transport problem [20.661025590877774]
  凸半緩和最適輸送(OT)問題に対する高速ブロックコーディネートFrank-Wolfe (BCFW) アルゴリズムを提案する。 数値実験により,提案アルゴリズムはカラー転送に有効であり,最先端のアルゴリズムを超越することを示した。
  論文  参考訳（メタデータ） (2022-05-27T05:54:45Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。 量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。 提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
  論文  参考訳（メタデータ） (2022-05-24T03:49:10Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。 MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
  論文  参考訳（メタデータ） (2021-02-15T07:10:33Z)
• Multi-Objective Matrix Normalization for Fine-grained Visual Recognition [153.49014114484424]
  双線形プールは細粒度視覚認識(FGVC)において大きな成功を収める 近年,行列パワー正規化は双線形特徴量において2次情報を安定化させることができることが示されている。 両線形表現を同時に正規化できる効率的な多目的行列正規化法(MOMN)を提案する。
  論文  参考訳（メタデータ） (2020-03-30T08:40:35Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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