論文の概要: Well-Conditioned Oblivious Perturbations in Linear Space

• arxiv url: http://arxiv.org/abs/2604.23193v1
• Date: Sat, 25 Apr 2026 07:54:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-28 17:12:07.201367
• Title: Well-Conditioned Oblivious Perturbations in Linear Space
• Title（参考訳）: 線形空間における曖昧な摂動
• Authors: Shabarish Chenakkod, Michał Dereziński, Xiaoyu Dong, Mark Rudelson,
• Abstract要約: ガウスノイズの小さい決定論的$n$次元行列の摂動は、アルゴリズムの滑らかな解析の基礎となる。 我々は、$O(log n)$の精度で$O(log n)$の乱数を生成し保存する必要がある摂動を提案する。 その結果、共役勾配アルゴリズムの複雑さが向上し、線形空間において$ntimes n$の線形系を任意に小さな定数逆誤差で解くことができることを示した。
• 参考スコア（独自算出の注目度）: 3.7042474403746706
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Perturbing a deterministic $n$-dimensional matrix with small Gaussian noise is a cornerstone of smoothed analysis of algorithms [Spielman and Teng, JACM 2004], as it reduces the condition number of the input to $O(n)$, and with it the complexity of many matrix algorithms. However, when deployed algorithmically, these perturbations are expensive due to the cost of generating and storing $n^2$ Gaussian random variables. We propose a perturbation that requires generating and storing $O(n)$ random numbers in $O(\log n)$ bits of precision, and reduces the condition number of any deterministic matrix to $O(n)$, matching Gaussian perturbations. Our result in particular implies a better complexity for the perturbed conjugate gradient algorithm, showing that we can solve an $n\times n$ linear system in linear space to within an arbitrarily small constant backward error using $O(n)$ matrix-vector products. In our construction, we introduce the concept of a pattern matrix, which is a dense deterministic matrix that maps all sparse vectors into dense vectors, and we combine it with a sparse perturbation whose entries are dependent and located in a non-uniform fashion. In order to analyze this construction, we develop new techniques for lower bounding the smallest singular value of a random matrix with dependent entries.
• Abstract（参考訳）: ガウス雑音が小さい決定論的$n$次元行列を摂動することは、入力の条件数を$O(n)$に減らし、多くの行列アルゴリズムの複雑さを減らし、アルゴリズム(Spielman and Teng, JACM 2004)の滑らかな解析の基盤となる。 しかし、アルゴリズム的に展開する場合、これらの摂動は、$n^2$ガウス確率変数の生成と保存のコストのため、高価である。 我々は、$O(n)$乱数を$O(\log n)$bitsの精度で生成・保存する必要がある摂動を提案し、任意の決定論的行列の条件数を$O(n)$に減らし、ガウス摂動に一致する。 我々の結果は特に摂動共役勾配アルゴリズムの複雑さを示唆しており、線型空間において$n\times n$線型系を$O(n)$行列ベクトル積を用いて任意に小さな定数逆誤差で解くことができることを示している。 本研究では,すべてのスパースベクトルを高密度ベクトルに写像する密度決定行列であるパターン行列の概念を導入し,成分が従属し一様でない方法で位置するスパース摂動と組み合わせる。 この構造を解析するために、従属成分を持つランダム行列の最小特異値を下界化するための新しい手法を開発した。

関連論文リスト

• Quantum Algorithms for Projection-Free Sparse Convex Optimization [32.34794896079469]
  ベクトル領域に対しては、$O(sqrtd/varepsilon)$のクエリ複雑性を持つ$varepsilon$-optimal解を求めるスパース制約に対する2つの量子アルゴリズムを提案する。 行列領域に対しては、時間複雑性を$tildeO(rd/varepsilon2)$と$tildeO(sqrtrd/varepsilon3)$に改善する2つの核ノルム制約の量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-07-11T12:43:58Z)
• Optimal Quantization for Matrix Multiplication [29.75700570685703]
  アルゴリズムにより,近似誤差を明確に保証したネスト格子に基づく普遍的量子化器を構築する。 我々の量子化器の実用的低複雑さバージョンは、非常に最適に近い性能を達成する。
  論文  参考訳（メタデータ） (2024-10-17T17:19:48Z)
• Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
  多くの機械学習タスクにおいて重要なボトルネックとなっているが、大規模な線形システムの解決コストは定量化が難しいことが証明されている。 低次元構造を示すアプリケーションによって動機づけられた線形システムの解法における複雑性の微妙な概念を考察する。 線形システム $Ax = b$, すなわち $|Abarx - b| le epsilon |b|$ であるような $barx$ を求める。
  論文  参考訳（メタデータ） (2024-05-09T14:56:49Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Householder Dice: A Matrix-Free Algorithm for Simulating Dynamics on Gaussian and Random Orthogonal Ensembles [12.005731086591139]
  Householder Dice (HD) は、高密度ランダム行列アンサンブルのダイナミクスを翻訳不変特性でシミュレートするアルゴリズムである。 HDアルゴリズムのメモリとコストはそれぞれ$mathcalO(nT)$と$mathcalO(nT2)$である。 数値結果は、高次元ランダムシステムの研究における新しい計算ツールとしてのHDアルゴリズムの約束を示しています。
  論文  参考訳（メタデータ） (2021-01-19T04:50:53Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• 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)

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

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