論文の概要: Non-PSD Matrix Sketching with Applications to Regression and Optimization

• arxiv url: http://arxiv.org/abs/2106.08544v1
• Date: Wed, 16 Jun 2021 04:07:48 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-17 17:39:01.843290
• Title: Non-PSD Matrix Sketching with Applications to Regression and Optimization
• Title（参考訳）: 非PSD行列スケッチと回帰と最適化への応用
• Authors: Zhili Feng, Fred Roosta, David P. Woodruff
• Abstract要約: 非PSDおよび2乗根行列の次元削減法を提案する。 複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
• 参考スコア（独自算出の注目度）: 56.730993511802865
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A variety of dimensionality reduction techniques have been applied for computations involving large matrices. The underlying matrix is randomly compressed into a smaller one, while approximately retaining many of its original properties. As a result, much of the expensive computation can be performed on the small matrix. The sketching of positive semidefinite (PSD) matrices is well understood, but there are many applications where the related matrices are not PSD, including Hessian matrices in non-convex optimization and covariance matrices in regression applications involving complex numbers. In this paper, we present novel dimensionality reduction methods for non-PSD matrices, as well as their ``square-roots", which involve matrices with complex entries. We show how these techniques can be used for multiple downstream tasks. In particular, we show how to use the proposed matrix sketching techniques for both convex and non-convex optimization, $\ell_p$-regression for every $1 \leq p \leq \infty$, and vector-matrix-vector queries.
• Abstract（参考訳）: 大きな行列を含む計算に様々な次元性低減技術が適用されている。 基礎となる行列はランダムに小さく圧縮され、元の性質の多くをほぼ保持する。 結果として、高価な計算の多くを小さな行列上で行うことができる。 正半定値行列(PSD)のスケッチはよく理解されているが、複素数を含む回帰応用における非凸最適化におけるヘッセン行列や共分散行列など、関連する行列がPSDではない多くの応用がある。 本稿では,非PSD行列に対する新しい次元性低減法と,複素成分を含む行列を包含する「二乗根」を提案する。 これらの手法を複数のダウンストリームタスクに使用できることを示す。 特に,提案した行列スケッチ手法を凸最適化と非凸最適化の両方に使用する方法,および1 に対して$\ell_p$-regression,ベクトル行列ベクトルクエリについて述べる。

関連論文リスト

• Optimal Quantization for Matrix Multiplication [35.007966885532724]
  我々は、ネスト格子に基づく普遍量化器を、任意の(非ランダムな)行列対に対する近似誤差の明示的な保証付きで、フロベニウスノルム$|A|_F, |B|_F$, $|Atop B|_F$のみの観点から、$A$, $B$とする。
  論文  参考訳（メタデータ） (2024-10-17T17:19:48Z)
• One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
  行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。 合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
  論文  参考訳（メタデータ） (2023-06-06T22:35:16Z)
• Sufficient dimension reduction for feature matrices [3.04585143845864]
  そこで本研究では,主支持行列マシン (PSMM) を用いた行列次元削減手法を提案する。 数値解析により、PSMMは既存の手法よりも優れ、実データアプリケーションでは高い解釈性を有することが示された。
  論文  参考訳（メタデータ） (2023-03-07T23:16:46Z)
• Multiresolution kernel matrix algebra [0.0]
  本研究では, あるS形式において, 最適スパース行列を生成するサンプルレットを用いて, カーネル行列の圧縮を示す。 カーネル行列の逆数(もし存在するなら)は S-形式でも圧縮可能である。 行列代数は擬微分計算によって数学的に正当化される。
  論文  参考訳（メタデータ） (2022-11-21T17:50:22Z)
• Sublinear Time Approximation of Text Similarity Matrices [50.73398637380375]
  一般的なNystr"om法を不確定な設定に一般化する。 我々のアルゴリズムは任意の類似性行列に適用でき、行列のサイズでサブ線形時間で実行される。 本手法は,CUR分解の単純な変種とともに,様々な類似性行列の近似において非常によく機能することを示す。
  論文  参考訳（メタデータ） (2021-12-17T17:04:34Z)
• Sparse Factorization of Large Square Matrices [10.94053598642913]
  本稿では,大面積の正方行列とスパースフルランク行列の積を近似する。 近似では、我々の手法は$Ntimes N$ full matrix に対して$N(log N)2$ non-zero number しか必要としない。 近似行列がスパースかつハイランクである場合,本手法により近似精度が向上することを示す。
  論文  参考訳（メタデータ） (2021-09-16T18:42:21Z)
• A Non-commutative Extension of Lee-Seung's Algorithm for Positive Semidefinite Factorizations [0.0]
  正の半定値分解(PSD)を計算するために,行列乗法更新(MMU)アルゴリズムと呼ぶLee-Seungアルゴリズムの非可換拡張について述べる。 更新方式では,2乗損失目標が非増加的であり,不動点が臨界点に対応することを示す。
  論文  参考訳（メタデータ） (2021-06-01T07:55:09Z)
• Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
  我々は、任意の正半定値(PSD)$A$に対して、$(1 pm epsilon)$を$tr(A)$に近似する新しいランダム化アルゴリズムであるHutch++を導入する。 実験ではハッチンソン法を著しく上回る結果を得た。
  論文  参考訳（メタデータ） (2020-10-19T16:45:37Z)
• 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)

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

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