論文の概要: Sketch-and-Solve: Optimized Overdetermined Least-Squares Using Randomized Numerical Linear Algebra

• arxiv url: http://arxiv.org/abs/2409.14309v1
• Date: Sun, 22 Sep 2024 04:29:51 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-06 23:15:03.726423
• Title: Sketch-and-Solve: Optimized Overdetermined Least-Squares Using Randomized Numerical Linear Algebra
• Title（参考訳）: Sketch-and-Solve:ランダム化数値線形代数を用いた過決定最小二乗の最適化
• Authors: Alex Lavaee,
• Abstract要約: 本稿では,過度に決定された最小二乗問題を効率的に解くためにスケッチ・アンド・ソリュートアルゴリズムを適用することに焦点を当てる。 ランダム化線形代数法を用いて近似解を効率的に計算するSketch-and-Apply (SAA-SAS) アルゴリズムを提案する。 本結果は,大規模数値線形代数問題を効率的に扱う上でのスケッチ・アンド・ソルブ法の可能性を強調した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Sketch-and-solve is a powerful paradigm for tackling large-scale computational problems by reducing their dimensionality using sketching matrices. This paper focuses on applying sketch-and-solve algorithms to efficiently solve the overdetermined least squares problem, which is fundamental in various domains such as machine learning, signal processing, and numerical optimization. We provide a comprehensive overview of the sketch-and-solve paradigm and analyze different sketching operators, including dense and sparse variants. We introduce the Sketch-and-Apply (SAA-SAS) algorithm, which leverages randomized numerical linear algebra techniques to compute approximate solutions efficiently. Through extensive experiments on large-scale least squares problems, we demonstrate that our proposed approach significantly outperforms the traditional Least-Squares QR (LSQR) algorithm in terms of runtime while maintaining comparable accuracy. Our results highlight the potential of sketch-and-solve techniques in efficiently handling large-scale numerical linear algebra problems.
• Abstract（参考訳）: スケッチ・アンド・ソルブ (Sketch-and-solve) は、スケッチ行列を用いて次元を小さくすることで、大規模計算問題に取り組むための強力なパラダイムである。 本稿では, 機械学習や信号処理, 数値最適化など, 様々な領域に根ざした, 過度に決定された最小二乗問題の解法として, スケッチ・アンド・ソルジアルゴリズムを適用することに焦点を当てる。 本稿では、スケッチ・アンド・ソルブのパラダイムを概観し、濃密・スパースな変種を含む様々なスケッチ演算子を解析する。 ランダム化線形代数法を用いて近似解を効率的に計算するSketch-and-Apply (SAA-SAS) アルゴリズムを提案する。 大規模最小二乗問題に対する広範な実験により,提案手法は従来のLast-Squares QR (LSQR) アルゴリズムよりも高い性能を示し,精度は同等である。 本結果は,大規模数値線形代数問題を効率的に扱う上でのスケッチ・アンド・ソルブ法の可能性を強調した。

関連論文リスト

• Simulation-based inference with the Python Package sbijax [0.7499722271664147]
  sbijaxは、ニューラルネットワークベースの推論に様々な最先端のメソッドを実装するPythonパッケージである。 このパッケージはベイズ近似計算の機能を提供し、モデル診断を計算し、自動的に要約統計を推定する。
  論文  参考訳（メタデータ） (2024-09-28T18:47:13Z)
• Implementing Recycling Methods for Linear Systems in Python with an Application to Multiple Objective Optimization [6.131436685168423]
  我々は, 一般的なリサイクル手法を用いた線形システムの解法において, 計算の全体的なコスト削減を図る。 本研究では, リサイクリング最小残差法 (RMINRES) の有効性と, 係数行列間の写像について検討した。
  論文  参考訳（メタデータ） (2024-02-25T00:15:30Z)
• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• NumS: Scalable Array Programming for the Cloud [82.827921577004]
  タスクベース分散システム上でNumPyのような表現を最適化する配列プログラミングライブラリであるNumSを提案する。 これはLoad Simulated Hierarchical Scheduling (LSHS)と呼ばれる新しいスケジューラによって実現される。 LSHSは、ネットワーク負荷を2倍減らし、メモリを4倍減らし、ロジスティック回帰問題において実行時間を10倍減らし、Rayの性能を向上させる。
  論文  参考訳（メタデータ） (2022-06-28T20:13:40Z)
• Complex-to-Real Sketches for Tensor Products with Applications to the Polynomial Kernel [15.535749953841274]
  p$ベクトルの積のランダム化されたスケッチは、統計効率と計算加速度のトレードオフに従う。 本稿では、実乱射影を複素射影に置き換える、よく知られたスケッチの単純な複素対Real (CtR) 修正を提案する。 本手法は,文献の他のランダム化近似と比較して,精度と速度の面で最先端の性能を達成することを示す。
  論文  参考訳（メタデータ） (2022-02-04T09:15:43Z)
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update [88.73437209862891]
  2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。 本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。 ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
  論文  参考訳（メタデータ） (2021-07-15T17:33:05Z)
• Speeding Up OPFython with Numba [0.0]
  Optimum-Path Forest (OPF)は、ロジスティック回帰、サポートベクトルマシンに匹敵する最先端のアルゴリズムであることが証明されている。 最近、PythonベースのバージョンはOPFythonと呼ばれ、よりフレンドリーなフレームワークとより高速なプロトタイピング環境を提供することが提案されている。 本稿では,Numpyに基づく計算を高速化し,アルゴリズム全体の性能向上を図るため,Numbaパッケージを用いた簡易かつ高効率な高速化を提案する。
  論文  参考訳（メタデータ） (2021-06-22T14:39:32Z)
• Learning the Positions in CountSketch [51.15935547615698]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習アルゴリズムを提案する。 このアルゴリズムは, 従来よりも低階近似の精度を向上し, 初めて$k$-meansクラスタリングのような他の問題に適用できることを示す。
  論文  参考訳（メタデータ） (2020-07-20T05:06:29Z)
• Picasso: A Sparse Learning Library for High Dimensional Data Analysis in R and Python [77.33905890197269]
  本稿では,様々なスパース学習問題に対して,経路座標を統一的に最適化する新しいライブラリについて述べる。 ライブラリはR++でコード化されており、ユーザフレンドリーなスパース実験を行っている。
  論文  参考訳（メタデータ） (2020-06-27T02:39:24Z)
• Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
  カーネル法は、非パラメトリック学習に対するエレガントで原則化されたアプローチを提供するが、今のところ大規模な問題ではほとんど利用できない。 最近の進歩は、最適化、数値線形代数、ランダム射影など、多くのアルゴリズム的アイデアの利点を示している。 ここでは、これらの取り組みをさらに進めて、GPUハードウェアを最大限に活用する解決器を開発し、テストする。
  論文  参考訳（メタデータ） (2020-06-18T08:16:25Z)

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

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