論文の概要: Localized sketching for matrix multiplication and ridge regression

• arxiv url: http://arxiv.org/abs/2003.09097v1
• Date: Fri, 20 Mar 2020 04:25:32 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-21 22:24:55.443018
• Title: Localized sketching for matrix multiplication and ridge regression
• Title（参考訳）: 行列乗算とリッジ回帰のための局所スケッチ
• Authors: Rakshith S Srinivasa, Mark A Davenport, Justin Romberg
• Abstract要約: 局所的スケッチの新たな設定において,スケッチ化された近似行列乗法とリッジ回帰を考察する。 緩やかな条件下では、ブロック対角線スケッチ行列はO(安定ランク/エプシロン2)と$O(stat. dim. epsilon)$の値のみを必要とする。
• 参考スコア（独自算出の注目度）: 29.61816941867831
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider sketched approximate matrix multiplication and ridge regression in the novel setting of localized sketching, where at any given point, only part of the data matrix is available. This corresponds to a block diagonal structure on the sketching matrix. We show that, under mild conditions, block diagonal sketching matrices require only O(stable rank / \epsilon^2) and $O( stat. dim. \epsilon)$ total sample complexity for matrix multiplication and ridge regression, respectively. This matches the state-of-the-art bounds that are obtained using global sketching matrices. The localized nature of sketching considered allows for different parts of the data matrix to be sketched independently and hence is more amenable to computation in distributed and streaming settings and results in a smaller memory and computational footprint.
• Abstract（参考訳）: 我々は,任意の点においてデータ行列の一部しか利用できない局所的スケッチの新たな設定において,スケッチ近似行列乗法とリッジ回帰を考える。 これはスケッチ行列上のブロック対角構造に対応する。 穏やかな条件下では、ブロック対角スケッチ行列は o(stable rank / \epsilon^2) と $o( stat) のみを必要とする。 ディム epsilon)$ 行列の乗算とリッジ回帰に対する総サンプル複雑性。 これは、グローバルスケッチ行列を用いて得られる最先端の境界値と一致する。 スケッチのローカライズされた性質は、データマトリックスの異なる部分を独立してスケッチできるため、分散およびストリーミング環境での計算に適しており、結果としてメモリと計算フットプリントが小さくなる。

関連論文リスト

• Distributed Least Squares in Small Space via Sketching and Bias Reduction [0.0]
  マトリックススケッチは、大きなデータ行列のサイズを減らす強力なツールである。 誤差よりも推定器のバイアスを最小限に抑えるスケッチ手法を設計することで,これらの制限を分散環境で回避できることを示す。 特に、最適空間と現在の行列乗算時間で動作するスパーススケッチ法を提案し、2つのパスデータを用いて、ほぼ偏りのない最小二乗推定器を復元する。
  論文  参考訳（メタデータ） (2024-05-08T18:16:37Z)
• DNNLasso: Scalable Graph Learning for Matrix-Variate Data [2.7195102129095003]
  我々は,Kronecker-sum構造精度行列を推定するための,対角非負のグラフィカルラッソモデルを提案する。 DNNLassoは、最先端の手法を精度と計算時間の両方で大きなマージンで上回る。
  論文  参考訳（メタデータ） (2024-03-05T02:49:00Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。 本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。 実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
  論文  参考訳（メタデータ） (2021-09-10T07:01:15Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  非PSDおよび2乗根行列の次元削減法を提案する。 複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2021-06-16T04:07:48Z)
• Learning-Augmented Sketches for Hessians [54.97773807211337]
  第二次手法の文脈でヘッセンの学習スケッチを設計する方法を紹介します。 学習したスケッチは,「学習されていない」スケッチと比較して,重要な問題に対する近似精度が向上することを示す。
  論文  参考訳（メタデータ） (2021-02-24T14:50:59Z)
• Effective and Sparse Count-Sketch via k-means clustering [17.26941311020711]
  我々は,k平均クラスタリングアルゴリズムを用いて,カウントスケッチの再構成誤差を低減し,低次元スケッチ行列を得る。 6つの実生活分類データセットに基づく実験結果から,提案手法は従来のカウントスケッチよりも精度が高いことを示した。
  論文  参考訳（メタデータ） (2020-11-24T11:44:02Z)
• Learning the Positions in CountSketch [51.15935547615698]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習アルゴリズムを提案する。 このアルゴリズムは, 従来よりも低階近似の精度を向上し, 初めて$k$-meansクラスタリングのような他の問題に適用できることを示す。
  論文  参考訳（メタデータ） (2020-07-20T05:06:29Z)
• Sketching Transformed Matrices with Applications to Natural Language Processing [76.6222695417524]
  本稿では, 変換行列を用いて, 与えられた小さな行列の積を計算するための空間効率のよいスケッチアルゴリズムを提案する。 提案手法は誤差が小さく,空間と時間の両方で効率がよいことを示す。
  論文  参考訳（メタデータ） (2020-02-23T03:07:31Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

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

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