論文の概要: The Structural Complexity of Matrix-Vector Multiplication

• arxiv url: http://arxiv.org/abs/2502.21240v2
• Date: Thu, 06 Mar 2025 19:17:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-10 12:19:59.205059
• Title: The Structural Complexity of Matrix-Vector Multiplication
• Title（参考訳）: 行列ベクトル乗算の構造複雑性
• Authors: Emile Anand, Jan van den Brand, Rose McCarty,
• Abstract要約: 行列ベクトル乗算問題は$tildeO(n2)$プレプロセッシングと$tildeO(n2-1/d)$クエリ時間で解けることを示す。 我々の結果は、多くの応用において最初の非自明な上界が得られる。
• 参考スコア（独自算出の注目度）: 0.10485739694839669
• License:
• Abstract: We consider the problem of preprocessing an $n\times n$ matrix M, and supporting queries that, for any vector v, returns the matrix-vector product Mv. This problem has been extensively studied in both theory and practice: on one side, practitioners have developed algorithms that are highly efficient in practice, whereas theoreticians have proven that the problem cannot be solved faster than naive multiplication in the worst-case. This lower bound holds even in the average-case, implying that existing average-case analyses cannot explain this gap between theory and practice. Therefore, we study the problem for structured matrices. We show that for $n\times n$ matrices of VC-dimension d, the matrix-vector multiplication problem can be solved with $\tilde{O}(n^2)$ preprocessing and $\tilde O(n^{2-1/d})$ query time. Given the low constant VC-dimensions observed in most real-world data, our results posit an explanation for why the problem can be solved so much faster in practice. Moreover, our bounds hold even if the matrix does not have a low VC-dimension, but is obtained by (possibly adversarially) corrupting at most a subquadratic number of entries of any unknown low VC-dimension matrix. Our results yield the first non-trivial upper bounds for many applications. In previous works, the online matrix-vector hypothesis (conjecturing that quadratic time is needed per query) was used to prove many conditional lower bounds, showing that it is impossible to compute and maintain high-accuracy estimates for shortest paths, Laplacian solvers, effective resistance, and triangle detection in graphs subject to node insertions and deletions in subquadratic time. Yet, via a reduction to our matrix-vector-multiplication result, we show we can maintain the aforementioned problems efficiently if the input is structured, providing the first subquadratic upper bounds in the high-accuracy regime.
• Abstract（参考訳）: 我々は、$n\times n$ matrix M を前処理し、任意のベクトル v に対して行列ベクトル積 Mv を返すクエリをサポートする問題を考える。 この問題は、理論と実践の両方で広く研究されている:一方、実践者は、実践において非常に効率的なアルゴリズムを開発してきたが、理論家たちは、最悪の場合において、問題を単純な乗法よりも早く解けないことを証明している。 この下界は平均ケースにおいても成り立ち、既存の平均ケース解析では理論と実践の間のギャップを説明できないことを示唆している。 そこで, 構造行列の問題について検討した。 我々は,VC次元 d の n$ 行列に対して,行列ベクトル乗算問題を $\tilde{O}(n^2)$ 前処理と $\tilde O(n^{2-1/d})$クエリ時間で解くことができることを示した。 実世界のほとんどのデータで観測されるVC次元が低いことを考えると、我々の結果は、この問題が実際にこれほど早く解決できる理由を説明するものである。 さらに、行列が低VC次元を持っていなくても、未知の低VC次元行列の少なくとも二乗数で(逆向きに)崩壊することによって得られる境界は保持される。 我々の結果は、多くの応用において最初の非自明な上界が得られる。 従来の研究では、オンライン行列ベクトル仮説(クエリ毎に二次時間が必要であると仮定する)は条件付き下界の証明に用いられ、最短経路、ラプラシア解法、有効抵抗、四進時間におけるノード挿入や削除を受けるグラフの三角形検出の高精度な推定を計算および維持することは不可能であることを示した。 しかし, 行列ベクトル乗算結果の低減により, 入力が構造化された場合, 上記の問題を効率的に維持できることを示す。

関連論文リスト

• Quantum Time-Space Tradeoffs for Matrix Problems [0.5524804393257919]
  量子コンピュータが行列を含む様々な問題を解くのに必要な時間と空間を考察する。 ほぼ全ての行列$A$に対して、少なくとも$T$の入力クエリと$S$のメモリを持つ量子回路は$T=Omega(n2/S)$を必要とすることを証明している。 我々の下界の多くは時間と空間の複雑さで決定論的アルゴリズムと一致するため、量子コンピュータは任意の空間境界を持つこれらの問題に対していかなる利点も提供できないことを示す。
  論文  参考訳（メタデータ） (2024-01-10T18:38:43Z)
• One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
  行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。 合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
  論文  参考訳（メタデータ） (2023-06-06T22:35:16Z)
• Fast Matrix Multiplication Without Tears: A Constraint Programming Approach [8.52818380743467]
  $N倍のM$行列と$M倍のP$行列の乗算は、単純な$NMPアプローチが示しているよりも少ない乗算で実現できることが知られている。 これにより、高速行列乗法における制約満足度問題が発生する。 本稿では,高速行列乗算のための非可換アルゴリズムを見つけるための,シンプルながら新しい制約プログラミング手法を提案する。
  論文  参考訳（メタデータ） (2023-06-01T19:15:24Z)
• On the well-spread property and its relation to linear regression [4.619541348328937]
  頑健な線形回帰モデルにおけるパラメータベクトルの一貫した回復は情報理論上不可能であることを示す。 与えられた$n$-by-d$行列が、周囲の次元で観測回数が二次的である場合、適切に証明できることが示される。
  論文  参考訳（メタデータ） (2022-06-16T11:17:44Z)
• Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors [54.936314353063494]
  我々は,ロバストな1ビット圧縮センシングのための相関に基づく最適化アルゴリズムのリカバリ保証を提供する。 我々は,実用的な反復アルゴリズムを用いて,画像データセットの数値実験を行い,結果の相関付けを行う。
  論文  参考訳（メタデータ） (2021-08-08T05:28:06Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  非PSDおよび2乗根行列の次元削減法を提案する。 複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2021-06-16T04:07:48Z)
• What if Neural Networks had SVDs? [66.91160214071088]
  様々なニューラルネットワークでは、行列反転のような時間を要する行列演算を採用している。 本稿では,行列演算を高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-09-29T12:58:52Z)
• Ranky : An Approach to Solve Distributed SVD on Large Sparse Matrices [0.0]
  特異値分解(SVD)は、多くの分野や応用分野においてよく研究されている研究トピックである。 そこで我々は,大小行列のランク問題を分散的に解く手法であるRandyを提案する。
  論文  参考訳（メタデータ） (2020-09-21T11:36:28Z)
• Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems [58.83118651518438]
  ベクトル行列ベクトルクエリを用いて行列について学習する一般的な問題を考える。 これらのクエリは、固定フィールド上の$boldsymbolumathrmTboldsymbolMboldsymbolv$の値を提供する。 我々は、線形代数、統計、グラフにまたがる様々な問題に対して、新しい上界と下界を提供する。
  論文  参考訳（メタデータ） (2020-06-24T19:33:49Z)
• Sketching Transformed Matrices with Applications to Natural Language Processing [76.6222695417524]
  本稿では, 変換行列を用いて, 与えられた小さな行列の積を計算するための空間効率のよいスケッチアルゴリズムを提案する。 提案手法は誤差が小さく,空間と時間の両方で効率がよいことを示す。
  論文  参考訳（メタデータ） (2020-02-23T03:07:31Z)

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

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