論文の概要: Fast Length-Squared Sampling for Positive-Semidefinite Matrices
- arxiv url: http://arxiv.org/abs/2608.12503v1
- Date: Wed, 12 Aug 2026 18:33:22 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-14 18:29:38.303109
- Title: Fast Length-Squared Sampling for Positive-Semidefinite Matrices
- Title（参考訳）: 正定値行列に対する高速長方形サンプリング
- Abstract要約: 本稿では,行列上で長二乗サンプリングを行うための単純なリジェクションサンプリングに基づくアルゴリズムについて述べる。
このアルゴリズムは$On)$ expected timeで実行され、入力サイズは著しくサブ線形である。
- 参考スコア（独自算出の注目度）: 15.092552206493544
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We describe a simple rejection-sampling-based algorithm to perform length-squared sampling on an $n \times n$ positive-semidefinite (psd) matrix: that is, to sample a column with probability proportional to its squared $\ell_2$-norm. The algorithm runs in just $O(n)$ expected time, which is significantly sublinear in the input matrix size. The runtime is optimal, even when the input is assumed to be diagonal. Our result has several applications. Length-squared sampling is used by a number of sublinear time algorithms for matrix problems, like low-rank approximation and eigenvalue approximation. Often, it is assumed that the algorithm is given access to the matrix column norms, and thus can perform length-squared sampling efficiently. Our result shows that, at least for psd matrices, we can remove this assumption. We also discuss an application to an asymptotically optimal algorithm for estimating the Frobenius norm of a psd matrix to relative error. Finally, we show that our sampling algorithm yields a very simple sublinear time algorithm for the robust psd low-rank approximation problem introduced by Bakshi et al. (FOCS, 2020), which nearly matches the more complex method developed there.
- Abstract（参考訳）: 提案手法では, 正の正の正定値 (psd) 行列を$n \times n$で2乗サンプリングし, 正の正の正定値 (psd) 行列で2乗サンプリングを行う。
このアルゴリズムはたったの$O(n)$期待時間で実行され、入力行列サイズは著しくサブ線形である。
入力が対角的であると仮定しても、ランタイムは最適である。
我々の結果にはいくつかの応用がある。
長さ2乗サンプリングは、低ランク近似や固有値近似のような行列問題に対する多くのサブ線形時間アルゴリズムによって用いられる。
しばしば、アルゴリズムは行列列ノルムへのアクセスを与えられるため、効率的に長二乗サンプリングを行うことができると仮定される。
我々の結果は、少なくとも psd 行列の場合、この仮定を除去できることを示している。
psd行列のフロベニウスノルムを相対誤差に推定するための漸近的最適アルゴリズムの適用についても論じる。
最後に,本アルゴリズムは,Bakshi et al (FOCS, 2020) が導入したロバストなpsd低ランク近似問題に対して,より複雑な手法とほぼ一致する,非常に単純なサブ線形時間アルゴリズムを導出することを示す。
関連論文リスト
- Improving Algorithmic Efficiency using Cryptography [11.496343300483904]
計算問題を解く際の時間的複雑さを改善するために暗号を用いる方法を示す。
標準的な暗号仮定の下では、既存のアルゴリズムよりも決定的に高速なアルゴリズムを設計できることを示す。
論文 参考訳（メタデータ） (2025-02-18T17:08:59Z) - Randomized Algorithms for Symmetric Nonnegative Matrix Factorization [1.991322361612643]
対称非負行列因子化(SymNMF)は、データ解析と機械学習における技術である。
計算のためのランダム化アルゴリズムを2つ開発した。
提案手法は, 解法の品質を概ね維持し, 大規模疎水化問題と大規模疎水化問題の両方に対して, 大幅な高速化を実現する。
論文 参考訳（メタデータ） (2024-02-13T00:02:05Z) - Fast Minimization of Expected Logarithmic Loss via Stochastic Dual
Averaging [8.990961435218544]
本稿では,対数障壁を用いたB$-sample双対平均化法を提案する。
Poisson逆問題に対して、我々のアルゴリズムは$smashtildeO(d3/varepsilon2)$ timeで$varepsilon$解を得る。
量子状態トモグラフィーの最大線量推定を計算するとき、我々のアルゴリズムは $smashtildeO(d3/varepsilon2)$ time で $varepsilon$-optimal Solution を得る。
論文 参考訳（メタデータ） (2023-11-05T03:33:44Z) - Learning the Positions in CountSketch [49.57951567374372]
本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。
本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-11T07:28:35Z) - 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) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z) - Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。
我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
論文 参考訳（メタデータ） (2020-04-23T05:00:21Z) - Optimal Iterative Sketching with the Subsampled Randomized Hadamard
Transform [64.90148466525754]
最小二乗問題に対する反復スケッチの性能について検討する。
本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。
これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
論文 参考訳（メタデータ） (2020-02-03T16:17:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。