論文の概要: Approximating Uniform Random Rotations by Two-Block Structured Hadamard Rotations in High Dimensions
- arxiv url: http://arxiv.org/abs/2604.23418v1
- Date: Sat, 25 Apr 2026 19:22:42 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-28 17:12:07.325319
- Title: Approximating Uniform Random Rotations by Two-Block Structured Hadamard Rotations in High Dimensions
- Title（参考訳）: 高次元2ブロック構造アダマール回転による一様ランダム回転の近似
- Authors: Tomer Zilca, Gal Mendelson,
- Abstract要約: 一様ランダムローテーションは、高速なJohnson-Lindenstrauss埋め込み、カーネル近似、通信効率の学習、最近のAI圧縮パイプラインなどのアプリケーションで有用なプリミティブである。
一般的な実践的な置き換えは、ウォルシュ・ハダマール変換とランダムサインから構築された繰り返し構造化されたランダムな回転である。
構造化ランダム回転を2回適用することは実証的に有用であることが示されているが、支持理論はまだ限られている。
- 参考スコア（独自算出の注目度）: 0.8307668828380427
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Uniform random rotations are a useful primitive in applications such as fast Johnson-Lindenstrauss embeddings, kernel approximation, communication-efficient learning, and recent AI compression pipelines, but they are computationally expensive to generate and apply in high dimensions. A common practical replacement is repeated structured random rotations built from Walsh-Hadamard transforms and random sign diagonals. Applying the structured random rotation twice has been shown empirically to be useful, but the supporting theory is still limited. In this paper we study the approximation quality achieved when using this two-block structured Hadamard rotation. Our results are both positive and negative. On the positive side, we prove that every fixed coordinate of the two-block transform converges uniformly, over all inputs, to the corresponding coordinate of a uniformly rotated vector, with an explicit Kolmogorov-distance bound of order $d^{-1/5}$. On the negative side, we prove an explicit lower bound on the Wasserstein distance between the full vector distributions, showing that the two-block transform is not a globally accurate surrogate for a uniform random rotation in the worst case. For the extremal input used in the lower bound, we also prove a matching asymptotic upper bound, showing that the lower-bound scale is sharp for that input. Taken together, the results identify a clear separation between one-dimensional marginal behavior, where approximation improves with dimension, and full high-dimensional geometry, where a nonvanishing discrepancy remains. This provides a partial theoretical explanation for the empirical success of structured Hadamard rotations in some algorithms, while also clarifying the limitations of treating them as drop-in replacements for true uniform random rotations.
- Abstract（参考訳）: 一様ランダムローテーションは、高速なジョンソン-リンデンシュトラウス埋め込み、カーネル近似、通信効率のよい学習、最近のAI圧縮パイプラインなどのアプリケーションで有用なプリミティブであるが、高次元で生成および適用するのに計算コストがかかる。
一般的な実践的な置き換えは、ウォルシュ・ハダマール変換とランダムサイン対角線から構築された繰り返し構成されたランダム回転である。
構造化ランダム回転を2回適用することは実証的に有用であることが示されているが、支持理論はまだ限られている。
本稿では,この2ブロック構造のアダマール回転を用いた場合の近似精度について検討する。
私たちの結果は肯定的かつ否定的です。
正の面において、2ブロック変換のすべての固定座標が、すべての入力に対して一様回転ベクトルの対応する座標に一様収束することを証明し、次数$d^{-1/5}$の明示的にコルモゴロフ距離境界を持つ。
負側では、全ベクトル分布間のワッサーシュタイン距離の明示的な下界を証明し、2ブロック変換が最悪の場合における一様ランダム回転に対する大域的精度の代理ではないことを示す。
また, 下界で使用する極端入力についても, 一致した漸近上界を証明し, その入力に対して下界スケールが鋭いことを示す。
まとめると、結果は、近似が次元によって改善される1次元の辺りの挙動と、消滅しない相違が残る完全な高次元幾何学とを明確に区別する。
これは、いくつかのアルゴリズムにおける構造化アダマール回転の経験的成功を部分的に理論的に説明し、真の均一なランダム回転に対するドロップイン置換として扱うという制限を明らかにした。
関連論文リスト
- Two-Sided Bounds for Entropic Optimal Transport via a Rate-Distortion Integral [17.319855487817257]
ランダムベクトルと標準正規ベクトルの間の最大予測内積は、速度歪関数を含む切り込み積分と等価であることを示す。
この証明は、情報理論の不等式に関わる確率分布の型クラスのランダムな部分集合によってインデックス付けされたガウス過程を構成するリフト法に基づいている。
論文 参考訳（メタデータ） (2026-04-15T16:37:00Z) - Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。
一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。
グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
論文 参考訳（メタデータ） (2026-02-26T15:27:53Z) - Relative Wasserstein Angle and the Problem of the $W_2$-Nearest Gaussian Distribution [4.042425236692822]
本研究では, 最適輸送の枠組みの下で, 経験的分布がガウス性からどこまで逸脱するかを定量化する問題について検討する。
相対変換不変な二次ワッサーシュタイン空間の錐幾何学を利用して、2つの新しい幾何学量を導入する。
この空間の任意の2光線によって生成される充填円錐は平坦であり、角度、射影、内部積が厳密に明確に定義されていることを証明する。
論文 参考訳（メタデータ） (2026-01-29T22:03:10Z) - Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations [57.179679246370114]
乱摂動の分布は, 摂動段差がゼロになる傾向にあるため, 推定子の分散を最小限に抑える。
以上の結果から, 一定の長さを維持するのではなく, 真の勾配に方向を合わせることが可能であることが示唆された。
論文 参考訳（メタデータ） (2025-10-22T19:06:39Z) - Randomized Coordinate Subgradient Method for Nonsmooth Composite
Optimization [11.017632675093628]
非滑らかな問題に対処するコーディネート型劣階法は、リプシッツ型仮定の性質のセットのため、比較的過小評価されている。
論文 参考訳（メタデータ） (2022-06-30T02:17:11Z) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。
次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
論文 参考訳（メタデータ） (2021-05-03T16:36:27Z) - Fused-Lasso Regularized Cholesky Factors of Large Nonstationary
Covariance Matrices of Longitudinal Data [0.0]
大きな共分散行列のコレスキー因子のサブ対角線の滑らかさは、時系列および長手データに対する自己回帰モデルの非定常度の度合いと密接に関連している。
行ごとに分離するColesky因子のスパース推定アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-07-22T02:38:16Z) - Debiased Sinkhorn barycenters [110.79706180350507]
最適輸送(OT)におけるエントロピー正則化(Entropy regularization)は、機械学習におけるWassersteinメトリクスやバリセンタに対する近年の関心の原動力となっている。
このバイアスがエントロピー正則化器を定義する基準測度とどのように密接に関連しているかを示す。
両世界の長所を保ち、エントロピーを滑らかにしないシンクホーン様の高速な反復をデバイアスド・ワッサースタインのバリセンタとして提案する。
論文 参考訳（メタデータ） (2020-06-03T23:06:02Z) - Explicit Regularization of Stochastic Gradient Methods through Duality [9.131027490864938]
ランダム化された双対座標の上昇に基づくランダム化されたDykstraスタイルのアルゴリズムを提案する。
座標降下を高速化するために、補間系における既存の勾配法よりも収束特性がよい新しいアルゴリズムを得る。
論文 参考訳（メタデータ） (2020-03-30T20:44:56Z) - Optimal Iterative Sketching with the Subsampled Randomized Hadamard
Transform [64.90148466525754]
最小二乗問題に対する反復スケッチの性能について検討する。
本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。
これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
論文 参考訳（メタデータ） (2020-02-03T16:17:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。