論文の概要: Revisiting Co-Occurring Directions: Sharper Analysis and Efficient Algorithm for Sparse Matrices

• arxiv url: http://arxiv.org/abs/2009.02553v2
• Date: Thu, 17 Dec 2020 06:55:55 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-21 20:53:41.971934
• Title: Revisiting Co-Occurring Directions: Sharper Analysis and Efficient Algorithm for Sparse Matrices
• Title（参考訳）: 共起方向の再検討:スパース行列のシャーパ解析と効率的なアルゴリズム
• Authors: Luo Luo, Cheng Chen, Guangzeng Xie, Haishan Ye
• Abstract要約: 近似行列乗算(AMM)のストリーミングモデルについて検討する。 我々は、アルゴリズムが限られたメモリでデータを1回だけ渡すことができるというシナリオに興味を持っている。 AMMストリーミングのための最先端決定論的スケッチアルゴリズムは共起方向(COD)である
• 参考スコア（独自算出の注目度）: 23.22254890452548
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: We study the streaming model for approximate matrix multiplication (AMM). We are interested in the scenario that the algorithm can only take one pass over the data with limited memory. The state-of-the-art deterministic sketching algorithm for streaming AMM is the co-occurring directions (COD), which has much smaller approximation errors than randomized algorithms and outperforms other deterministic sketching methods empirically. In this paper, we provide a tighter error bound for COD whose leading term considers the potential approximate low-rank structure and the correlation of input matrices. We prove COD is space optimal with respect to our improved error bound. We also propose a variant of COD for sparse matrices with theoretical guarantees. The experiments on real-world sparse datasets show that the proposed algorithm is more efficient than baseline methods.
• Abstract（参考訳）: 近似行列乗算(AMM)のストリーミングモデルについて検討した。 我々は、アルゴリズムが限られたメモリを持つデータのみを渡すことができるというシナリオに興味を持っている。 AMMをストリーミングするための最先端の決定論的スケッチアルゴリズムは共起方向(COD)であり、ランダム化アルゴリズムよりも近似誤差がはるかに小さく、他の決定論的スケッチ手法を実証的に上回る。 本稿では,確率的近似低ランク構造と入力行列の相関を主項とするCODに対して,より厳密な誤差境界を提供する。 改良された誤差境界に対してCODが最適であることを示す。 また,理論的保証付きスパース行列に対するCODの変種も提案する。 実世界のスパースデータセットに関する実験は、提案アルゴリズムがベースライン法よりも効率的であることを示している。

関連論文リスト

• Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning [53.445068584013896]
  低ランク構造を持つ強化学習(RL)における行列推定問題について検討した。 低ランク帯では、回収される行列は期待される腕の報酬を指定し、低ランクマルコフ決定プロセス(MDP)では、例えばMDPの遷移カーネルを特徴付ける。 簡単なスペクトルベースの行列推定手法は,行列の特異部分空間を効率よく復元し,ほぼ最小の入力誤差を示すことを示す。
  論文  参考訳（メタデータ） (2023-10-10T17:06:41Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Algorithme EM r\'egularis\'e [0.0]
  本稿では,より少ないサンプルサイズに対応するために,事前知識を効率的に活用するEMアルゴリズムの正規化バージョンを提案する。 実データを用いた実験では,クラスタリングのための提案アルゴリズムの性能が向上した。
  論文  参考訳（メタデータ） (2023-07-04T23:19:25Z)
• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• Asymmetric Scalable Cross-modal Hashing [51.309905690367835]
  クロスモーダルハッシュは、大規模なマルチメディア検索問題を解決する方法として成功している。 これらの問題に対処する新しい非対称スケーラブルクロスモーダルハッシュ(ASCMH)を提案する。 我々のASCMHは、最先端のクロスモーダルハッシュ法よりも精度と効率の点で優れています。
  論文  参考訳（メタデータ） (2022-07-26T04:38:47Z)
• Fast Projected Newton-like Method for Precision Matrix Estimation under Total Positivity [15.023842222803058]
  現在のアルゴリズムはブロック座標降下法や近点アルゴリズムを用いて設計されている。 本稿では,2次元投影法に基づく新しいアルゴリズムを提案し,慎重に設計された探索方向と変数分割方式を取り入れた。 合成および実世界のデータセットに対する実験結果から,提案アルゴリズムは最先端の手法と比較して計算効率を著しく向上させることを示した。
  論文  参考訳（メタデータ） (2021-12-03T14:39:10Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。 提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
  論文  参考訳（メタデータ） (2020-12-29T04:08:38Z)
• Estimating Multiple Precision Matrices with Cluster Fusion Regularization [0.90238471756546]
  異なるクラスから複数の精度行列を推定するペナライズされた可能性を提案する。 既存の手法の多くは、精度行列間の関係に関する情報を含まないか、あるいはこの情報を先入観として要求する。
  論文  参考訳（メタデータ） (2020-03-01T01:03:22Z)

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

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