論文の概要: A simple analysis of a quantum-inspired algorithm for solving low-rank linear systems
- arxiv url: http://arxiv.org/abs/2508.13108v1
- Date: Mon, 18 Aug 2025 17:14:35 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-19 14:49:11.506876
- Title: A simple analysis of a quantum-inspired algorithm for solving low-rank linear systems
- Title(参考訳): 低ランク線形システムを解くための量子インスピレーションアルゴリズムの簡単な解析
- Authors: Tyler Chen, Junhyung Lyle Kim, Archan Ray, Shouvanik Chakrabarti, Dylan Herman, Niraj Kumar,
- Abstract要約: 解 $mathbfx* := mathbfA+mathbfb$ から線形系への簡単なサンプリングアルゴリズムを解析する。
我々の分析は初等的で非漸近的で、完全に自己完結している。
- 参考スコア(独自算出の注目度): 4.17272639356083
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We describe and analyze a simple algorithm for sampling from the solution $\mathbf{x}^* := \mathbf{A}^+\mathbf{b}$ to a linear system $\mathbf{A}\mathbf{x} = \mathbf{b}$. We assume access to a sampler which allows us to draw indices proportional to the squared row/column-norms of $\mathbf{A}$. Our algorithm produces a compressed representation of some vector $\mathbf{x}$ for which $\|\mathbf{x}^* - \mathbf{x}\| < \varepsilon \|\mathbf{x}^* \|$ in $\widetilde{O}(\kappa_{\mathsf{F}}^4 \kappa^2 / \varepsilon^2)$ time, where $\kappa_{\mathsf{F}} := \|\mathbf{A}\|_{\mathsf{F}}\|\mathbf{A}^{+}\|$ and $\kappa := \|\mathbf{A}\|\|\mathbf{A}^{+}\|$. The representation of $\mathbf{x}$ allows us to query entries of $\mathbf{x}$ in $\widetilde{O}(\kappa_{\mathsf{F}}^2)$ time and sample proportional to the square entries of $\mathbf{x}$ in $\widetilde{O}(\kappa_{\mathsf{F}}^4 \kappa^6)$ time, assuming access to a sampler which allows us to draw indices proportional to the squared entries of any given row of $\mathbf{A}$. Our analysis, which is elementary, non-asymptotic, and fully self-contained, simplifies and clarifies several past analyses from literature including [Gily\'en, Song, and Tang; 2022, 2023] and [Shao and Montanaro; 2022].
- Abstract(参考訳): 解 $\mathbf{x}^* := \mathbf{A}^+\mathbf{b}$ から線形系 $\mathbf{A}\mathbf{x} = \mathbf{b}$ への簡単なサンプリングアルゴリズムを記述・解析する。
サンプルには$\mathbf{A}$の2乗行/カラムノルムに比例するインデックスを描画できる。
我々のアルゴリズムは、あるベクトル $\mathbf{x}$ の圧縮表現を生成する: $\|\mathbf{x}^* - \mathbf{x}\| < \varepsilon \|\mathbf{x}^* \|$ in $\widetilde{O}(\kappa_{\mathsf{F}}^4 \kappa^2 / \varepsilon^2)$time, where $\kappa_{\mathsf{F}} := \|\mathbf{A}\|_{\mathsf{F}}\|\mathbf{A}^{+}\|$ and $\kappa := \|\mathbf{A}\|\mathbf{A}^{+\|$。
$\mathbf{x}$の表現は、$\mathbf{x}$ in $\widetilde{O}(\kappa_{\mathsf{F}}^2)$時間とサンプルを$\mathbf{x}$ in $\widetilde{O}(\kappa_{\mathsf{F}}^4 \kappa^6)$時間に比例する。
我々の分析は, 初等・非漸近・完全自己完結型であり, [Gily\'en, Song, and Tang, 2022, 2023] や [Shao and Montanaro, 2022] などの文献からのいくつかの過去の分析を単純化し, 解明している。
関連論文リスト
- Matrix Product Sketching via Coordinated Sampling [15.820518033589705]
我々は、小さな空間スケッチに基づいて行列積 $mathbfATmathbfB$ を近似するというよく研究された問題を再考する。
我々は, $mathbfA$ と $mathbfB$ がスパースであることを証明する。
論文 参考訳(メタデータ) (2025-01-29T18:35:38Z) - Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳(メタデータ) (2024-06-07T08:26:31Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳(メタデータ) (2024-02-06T15:39:09Z) - Fast Partition-Based Cross-Validation With Centering and Scaling for $\mathbf{X}^\mathbf{T}\mathbf{X}$ and $\mathbf{X}^\mathbf{T}\mathbf{Y}$ [0.0]
機械学習モデルの分割に基づくクロスバリデーションを大幅に高速化するアルゴリズムを提案する。
我々のアルゴリズムは、例えば、主成分分析(PCA)、主成分回帰(PCR)、隆起回帰(RR)、通常最小二乗(OLS)、部分最小二乗(PLS)のモデル選択に応用できる。
文献に見られる代替手段とは異なり、前処理によるデータの漏洩を避ける。
論文 参考訳(メタデータ) (2024-01-24T02:16:03Z) - Quantum Oblivious LWE Sampling and Insecurity of Standard Model Lattice-Based SNARKs [4.130591018565202]
Learning Errors With Errors(mathsfLWE$)問題は$(mathbfAmathbfs+mathbfe$)という形式の入力から$mathbfs$を見つけるように要求する
私たちは$mathsfLWE$の解決ではなく、インスタンスをサンプリングするタスクに注力しています。
我々の主な成果は、よく分散された$mathsfLWE$インスタンスをサンプリングする量子時間アルゴリズムである。
論文 参考訳(メタデータ) (2024-01-08T10:55: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) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳(メタデータ) (2022-06-17T17:55:43Z) - Low-degree learning and the metric entropy of polynomials [44.99833362998488]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳(メタデータ) (2022-03-17T23:52:08Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳(メタデータ) (2021-10-21T18:43:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。