論文の概要: Algorithmic Solution for Systems of Linear Equations, in
$\mathcal{O}(mn)$ time
- arxiv url: http://arxiv.org/abs/2104.12570v2
- Date: Fri, 22 Sep 2023 18:07:00 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-27 05:31:43.873516
- Title: Algorithmic Solution for Systems of Linear Equations, in
$\mathcal{O}(mn)$ time
- Title（参考訳）: 線形方程式系のアルゴリズム解、$\mathcal{O}(mn)$ time
- Authors: Nikolaos P. Bakas
- Abstract要約: 方程式の線形系の探索解を超高速に求める新しいアルゴリズムを提案する。
実行時間は最先端のメソッドと比較して非常に短い。
この論文はアルゴリズム収束の理論的証明も含んでいる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present a novel algorithm attaining excessively fast, the sought solution
of linear systems of equations. The algorithm is short in its basic formulation
and, by definition, vectorized, while the memory allocation demands are
trivial, because, for each iteration, only one dimension of the given input
matrix $\mathbf X$ is utilized. The execution time is very short compared with
state-of-the-art methods, exhibiting $> \times 10^2$ speed-up and low memory
allocation demands, especially for non-square Systems of Linear Equations, with
ratio of equations versus features high (tall systems), or low (wide systems)
accordingly. The accuracy is high and straightforwardly controlled, and the
numerical results highlight the efficiency of the proposed algorithm, in terms
of computation time, solution accuracy and memory demands. The paper also
comprises a theoretical proof for the algorithmic convergence, and we extend
the implementation of the proposed algorithmic rationale to feature selection
tasks.
- Abstract（参考訳）: 本稿では,線形方程式系の解法として,超高速に解く新しいアルゴリズムを提案する。
このアルゴリズムは基本的な定式化では短く、定義上はベクトル化されるが、各反復では与えられた入力行列 $\mathbf x$ の1次元のみが使用されるため、メモリ割り当て要求は自明である。
実行時間は最先端の手法と比較して非常に短く、特に線形方程式の非二乗系において、計算式と高次(全系)あるいは低(全体系)の比で、計算時間10^2$のスピードアップと低メモリ割り当ての要求を示す。
精度は高く、直接的に制御されており、計算時間、解の精度、メモリ要求量の観点から、提案アルゴリズムの効率を数値的に強調する。
本論文は,アルゴリズム収束の理論的証明も含み,提案手法の実装を特徴選択タスクに拡張する。
関連論文リスト
- Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Efficient distributed representations with linear-time attention scores normalization [3.8673630752805437]
本研究では,有界ノルムを持つ埋め込みベクトルに対するアテンションスコア正規化定数の線形時間近似を提案する。
推定公式の精度は、競合するカーネルメソッドを桁違いに上回る。
提案アルゴリズムは高度に解釈可能であり,任意の埋め込み問題に容易に適応できる。
論文 参考訳（メタデータ） (2023-03-30T15:48:26Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Fast Projected Newton-like Method for Precision Matrix Estimation under
Total Positivity [15.023842222803058]
現在のアルゴリズムはブロック座標降下法や近点アルゴリズムを用いて設計されている。
本稿では,2次元投影法に基づく新しいアルゴリズムを提案し,慎重に設計された探索方向と変数分割方式を取り入れた。
合成および実世界のデータセットに対する実験結果から,提案アルゴリズムは最先端の手法と比較して計算効率を著しく向上させることを示した。
論文 参考訳（メタデータ） (2021-12-03T14:39:10Z) - Quantum Algorithm for Solving a Quadratic Nonlinear System of Equations [0.22940141855172036]
アルゴリズムの複雑さは$O(rm polylog(n/epsilon))$であり、これは次元$n$の最適古典アルゴリズムよりも指数関数的に改善される。
我々のアルゴリズムは指数関数的にQNSEの解を加速し、あらゆる非線形問題に適用できる。
論文 参考訳（メタデータ） (2021-12-03T00:27:16Z) - Hybrid algorithms to solve linear systems of equations with limited
qubit resources [7.111403318486868]
古典的手法を用いた複雑性は方程式のサイズとともに線形に増加する。
Harrowらによって提案されたHHLアルゴリズムは、最も優れた古典的アルゴリズムと比較して指数加速度を達成する。
本稿では,反復位相推定アルゴリズムに基づいて3つのハイブリッド反復位相推定アルゴリズム(HIPEA)を設計する。
論文 参考訳（メタデータ） (2021-06-29T15:10:55Z) - 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) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。
この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。
古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文 参考訳（メタデータ） (2020-07-01T18:43:32Z) - Symbolic Regression using Mixed-Integer Nonlinear Optimization [9.638685454900047]
シンボリック回帰(SR)問題は、機械学習において難しい問題である。
混合整数非線形最適化と明示列挙法を組み合わせたハイブリッドアルゴリズムを提案する。
我々のアルゴリズムは、いくつかの合成データセットに対して、最先端のSRソフトウェアと最近の物理学に触発されたAI Feynmanという手法で競合していることを示す。
論文 参考訳（メタデータ） (2020-06-11T20:53:17Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。