論文の概要: Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and
Graph Problems
- arxiv url: http://arxiv.org/abs/2006.14015v1
- Date: Wed, 24 Jun 2020 19:33:49 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-17 13:33:45.184340
- Title: Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and
Graph Problems
- Title（参考訳）: 線形代数・統計・グラフ問題の解法のためのベクトル行列ベクトルクエリ
- Authors: Cyrus Rashtchian, David P. Woodruff and Hanlin Zhu
- Abstract要約: ベクトル行列ベクトルクエリを用いて行列について学習する一般的な問題を考える。
これらのクエリは、固定フィールド上の$boldsymbolumathrmTboldsymbolMboldsymbolv$の値を提供する。
我々は、線形代数、統計、グラフにまたがる様々な問題に対して、新しい上界と下界を提供する。
- 参考スコア（独自算出の注目度）: 58.83118651518438
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the general problem of learning about a matrix through
vector-matrix-vector queries. These queries provide the value of
$\boldsymbol{u}^{\mathrm{T}}\boldsymbol{M}\boldsymbol{v}$ over a fixed field
$\mathbb{F}$ for a specified pair of vectors $\boldsymbol{u},\boldsymbol{v} \in
\mathbb{F}^n$. To motivate these queries, we observe that they generalize many
previously studied models, such as independent set queries, cut queries, and
standard graph queries. They also specialize the recently studied matrix-vector
query model. Our work is exploratory and broad, and we provide new upper and
lower bounds for a wide variety of problems, spanning linear algebra,
statistics, and graphs. Many of our results are nearly tight, and we use
diverse techniques from linear algebra, randomized algorithms, and
communication complexity.
- Abstract（参考訳）: ベクトル行列-ベクトルクエリによる行列学習の一般的な問題を考える。
これらのクエリは、固定フィールド上の $\boldsymbol{u}^{\mathrm{t}}\boldsymbol{m}\boldsymbol{v}$ の値を与え、特定のベクトルの組 $\boldsymbol{u},\boldsymbol{v} \in \mathbb{f}^n$ に対して$\mathbb{f}$ を与える。
これらのクエリを動機づけるため、独立セットクエリ、カットクエリ、標準グラフクエリなど、これまで研究されてきた多くのモデルを一般化する。
また、最近研究された行列ベクトルクエリモデルも特化している。
我々の研究は探索的で広範であり、線形代数、統計、グラフにまたがる様々な問題に対して、新しい上と下の境界を提供する。
結果の多くはほぼ厳密であり、線形代数、ランダム化アルゴリズム、通信複雑性といった様々な手法を用いています。
関連論文リスト
- One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。
合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
論文 参考訳（メタデータ） (2023-06-06T22:35:16Z) - On the well-spread property and its relation to linear regression [4.619541348328937]
頑健な線形回帰モデルにおけるパラメータベクトルの一貫した回復は情報理論上不可能であることを示す。
与えられた$n$-by-d$行列が、周囲の次元で観測回数が二次的である場合、適切に証明できることが示される。
論文 参考訳（メタデータ） (2022-06-16T11:17:44Z) - Sign and Basis Invariant Networks for Spectral Graph Representation
Learning [75.18802152811539]
SignNetとBasisNetは、すべての必須対称性に不変な新しいニューラルアーキテクチャであり、したがって、原則化された方法で固有空間のコレクションを処理する。
我々のネットワークは理論的にはグラフ表現学習に強い -- 任意のスペクトルグラフ畳み込みを近似することができる。
実験により、スペクトルグラフフィルタの学習とグラフ位置エンコーディングの学習のためのネットワークの強みが示された。
論文 参考訳（メタデータ） (2022-02-25T23:11:59Z) - Improved analysis of randomized SVD for top-eigenvector approximation [16.905540623795467]
そこで本研究では,無作為なSVDアルゴリズムであるcitethalko2011finding を新たに解析し,興味のある場合の厳密な境界を導出する。
特に、これは任意の反復数を持つランダム化SVDに対して$R(hatmathbfu)$の非自明な境界を与える最初の作品である。
論文 参考訳（メタデータ） (2022-02-16T11:12:07Z) - On the query complexity of connectivity with global queries [0.2538209532048867]
グラフがグローバルクエリと結びついているかどうかを判断する際のクエリの複雑さについて検討する。
ゼロエラーランダム化アルゴリズムは接続性を解決するために,$Omega(n)$リニアクエリを生成する必要がある。
論文 参考訳（メタデータ） (2021-09-05T16:22:55Z) - Non-PSD Matrix Sketching with Applications to Regression and
Optimization [56.730993511802865]
非PSDおよび2乗根行列の次元削減法を提案する。
複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
論文 参考訳（メタデータ） (2021-06-16T04:07:48Z) - Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative
GLASSO and Projection [58.5350491065936]
グラフ Laplacian 行列 $L$ 上の構造的仮定を考える。
最初の$K$ eigenvectors of $L$は、例えばドメイン固有の基準に基づいて事前選択される。
本稿では,H_u+$$$$barC$で最も適切なグラフラプラシアン行列$L*を計算するために,効率的なハイブリッドグラフラッソ/投影アルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-10-25T18:12:50Z) - Recovery of sparse linear classifiers from mixture of responses [42.228977798395846]
双対応答列から超平面の集合を学習する方法を示す。
各応答はベクトルとのクエリの結果であり、クエリベクトルが属するコレクションからランダムに選択された超平面の側面を示す。
論文 参考訳（メタデータ） (2020-10-22T22:03:53Z) - Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。
我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-30T19:10:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。