論文の概要: The Communication Complexity of Approximating Matrix Rank

• arxiv url: http://arxiv.org/abs/2410.20094v1
• Date: Sat, 26 Oct 2024 06:21:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-29 12:21:15.438556
• Title: The Communication Complexity of Approximating Matrix Rank
• Title（参考訳）: 行列ランク近似の通信複雑性
• Authors: Alexander A. Sherstov, Andrey A. Storozhenko,
• Abstract要約: この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
• 参考スコア（独自算出の注目度）: 50.6867896228563
• License:
• Abstract: We fully determine the communication complexity of approximating matrix rank, over any finite field $\mathbb{F}$. We study the most general version of this problem, where $0\leq r<R\leq n$ are given integers, Alice and Bob's inputs are matrices $A,B\in\mathbb{F}^{n\times n}$, respectively, and they need to distinguish between the cases $\mathrm{rk}(A+B)=r$ and $\mathrm{rk}(A+B)=R$. We show that this problem has randomized communication complexity $\Omega(1+r^{2}\log|\mathbb{F}|)$. This is optimal in a strong sense because $O(1+r^{2}\log|\mathbb{F}|)$ communication is sufficient to determine, for arbitrary $A,B$, whether $\mathrm{rk}(A+B)\leq r$. Prior to our work, lower bounds were known only for consecutive integers $r$ and $R$, with no implication for the approximation of matrix rank. Our lower bound holds even for quantum protocols and even for error probability $\frac{1}{2}-\frac{1}{4}|\mathbb{F}|^{-r/3}$, which too is virtually optimal because the problem has a two-bit classical protocol with error $\frac{1}{2}-\Theta(|\mathbb{F}|^{-r})$. As an application, we obtain an $\Omega(\frac{1}{k}\cdot n^{2}\log|\mathbb{F}|)$ space lower bound for any streaming algorithm with $k$ passes that approximates the rank of an input matrix $M\in\mathbb{F}^{n\times n}$ within a factor of $\sqrt{2}-\delta$, for any $\delta>0$. Our result is an exponential improvement in $k$ over previous work. We also settle the randomized and quantum communication complexity of several other linear-algebraic problems, for all settings of parameters. This includes the determinant problem (given matrices $A$ and $B$, distinguish between the cases $\mathrm{det}(A+B)=a$ and $\mathrm{det}(A+B)=b$, for fixed field elements $a\ne b)$ and the subspace sum and subspace intersection problem (given subspaces $S$ and $T$ of known dimensions $m$ and $\ell$, respectively, approximate the dimensions of $S+T$ and $S\cap T$).
• Abstract（参考訳）: 任意の有限体 $\mathbb{F}$ 上で、行列階数近似の通信複雑性を完全に決定する。 この問題の最も一般的なバージョンについて研究し、$0\leq r<R\leq n$ を整数とし、Alice と Bob の入力をそれぞれ行列 $A,B\in\mathbb{F}^{n\times n}$ とし、それぞれ $\mathrm{rk}(A+B)=r$ と $\mathrm{rk}(A+B)=R$ を区別する必要がある。 この問題はランダムな通信複雑性$\Omega(1+r^{2}\log|\mathbb{F}|)$であることを示す。 これは強い意味で最適である:$O(1+r^{2}\log|\mathbb{F}|)$通信は任意の$A,B$に対して$\mathrm{rk}(A+B)\leq r$を決定するのに十分である。 我々の研究以前には、下位境界は連続整数$r$と$R$でしか知られていなかったが、行列ランクの近似には影響しなかった。 我々の下界は、量子プロトコルに対しても、誤差確率$\frac{1}{2}-\frac{1}{4}|\mathbb{F}|^{-r/3}$に対しても成り立つが、この問題は、誤差$\frac{1}{2}-\Theta(|\mathbb{F}|^{-r})$を持つ2ビット古典的プロトコルを持つため、実質的に最適である。 アプリケーションとして、$\Omega(\frac{1}{k}\cdot n^{2}\log|\mathbb{F}|)$ space lower bound for any streaming algorithm with $k$ pass that almosts the rank of a input matrix $M\in\mathbb{F}^{n\times n}$ in a factor of $\sqrt{2}-\delta$ for any $\delta>0$。 私たちの成果は、以前の作業よりも400ドルの指数関数的な改善です。 また、パラメータの全ての設定に対して、他の線形代数問題に対するランダム化および量子化通信の複雑さを解決した。 これには、行列式問題(行列式$A$と$B$)と、固定体要素$a\ne b)$に対する$\mathrm{det}(A+B)=a$と$\mathrm{det}(A+B)=b$、および部分空間和と部分空間交叉問題(既知の次元の$m$と$T$はそれぞれ$S+T$と$S\cap T$)とを区別する。

関連論文リスト

• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Quantum and classical query complexities of functions of matrices [0.0]
  任意の連続関数 $f(x):[-1,1]rightarrow [-1,1]$ に対して、計算の量子クエリ複雑性 $brai f(A) ketjpm varepsilon/4$ は$Omega(widetildedeg_varepsilon(f))$ で制限される。
  論文  参考訳（メタデータ） (2023-11-13T00:45:41Z)
• Optimal Estimator for Linear Regression with Shuffled Labels [17.99906229036223]
  本稿では,シャッフルラベルを用いた線形回帰の課題について考察する。 mathbb Rntimes m の $mathbf Y、mathbb Rntimes p の mathbf Pi、mathbb Rptimes m$ の mathbf B、mathbb Rntimes m$ の $mathbf Win mathbb Rntimes m$ である。
  論文  参考訳（メタデータ） (2023-10-02T16:44:47Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension [18.57735939471469]
  我々は注意問題のスパシフィケーションを考慮する。 超大規模特徴量の場合、文の長さをほぼ線形に縮めることができる。
  論文  参考訳（メタデータ） (2023-04-10T05:52:38Z)
• A Nearly-Optimal Bound for Fast Regression with $\ell_\infty$ Guarantee [16.409210914237086]
  行列 $Ain mathbbRntimes d$ とテンソル $bin mathbbRn$ が与えられたとき、 $ell_infty$ の回帰問題を考える。 このような$ell_infty$レグレッションの保証を得るためには、濃密なスケッチ行列を使わなければならない。 我々はまた、OCE(Oblivious Coordinate-wise Embedding)特性を利用した $ell_infty$ guarantee regression のための新しい分析フレームワークを開発した。
  論文  参考訳（メタデータ） (2023-02-01T05:22:40Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
  論文  参考訳（メタデータ） (2021-09-06T14:21:43Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Locally Private $k$-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error [10.632986841188]
  2つの新しいアルゴリズムで加算誤差の上と下の境界における$n$の指数のギャップを埋める。 局所的にプライベートな$k$-meansの問題を、定数係数乗算近似を持つ一定数のラウンドで解くことができる。
  論文  参考訳（メタデータ） (2021-05-31T14:41:40Z)

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

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