論文の概要: Unbiased Low-Rank Approximation for Repeated Matrix-Vector Multiplication: Stability and Optimal Sampling

• arxiv url: http://arxiv.org/abs/2611.00787v1
• Date: Sat, 31 Oct 2026 09:59:25 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-11-03 19:20:55.431826
• Title: Unbiased Low-Rank Approximation for Repeated Matrix-Vector Multiplication: Stability and Optimal Sampling
• Title（参考訳）: 繰り返し行列ベクトル乗算に対する非バイアス低ランク近似:安定性と最適サンプリング
• Abstract要約: 本研究では,各ステップで個別にサンプリングする場合に,この成長を最小限に抑えるために,ランダム行列の分布を選択する方法について検討する。 最適成長係数の正確な公式を導出し、期待される平方ノルムが 0 に収束するかどうかを決定するためにそれを用いる。 これらの結果は、安定性に必要な最小ランクを決定し、所定のランク制約の下で最適なサンプリング設計を提供する。
• 参考スコア（独自算出の注目度）: 9.838557162303582
• License:
• Abstract: Replacing the matrix in an iteration with random low-rank matrices can reduce the cost of matrix-vector multiplication. However, even if the sampled matrices equal the original matrix in expectation, the expected squared norm of the random iterates may grow while the original iteration converges. Under a fixed rank bound, we study how to choose the distribution of these random matrices to minimize this growth when sampling independently at each step. We derive an exact formula for the optimal asymptotic growth factor and use it to determine when the expected squared norm can converge to zero. We then characterize precisely when a fixed sampling distribution achieves this optimal factor and construct finite-support optimal distributions in every attainable case. These results determine the minimum rank required for stability and provide optimal sampling designs under the prescribed rank constraint.
• Abstract（参考訳）: 行列をランダムな低ランク行列に置き換えることで、行列ベクトル乗算のコストを削減できる。 しかし、サンプリングされた行列が期待されたときに元の行列と等しいとしても、元の反復が収束している間に、ランダムな反復の期待される二乗ノルムが増大する。 固定階数境界の下で、各ステップで独立にサンプリングする場合に、この成長を最小限に抑えるために、これらのランダム行列の分布を選択する方法を検討する。 最適漸近成長係数の正確な式を導出し、期待される2乗ノルムが 0 に収束するかどうかを決定するためにそれを用いる。 そして、固定サンプリング分布がこの最適因子を達成し、到達可能なすべてのケースで有限対応な最適分布を構成するとき、正確に特徴付ける。 これらの結果は、安定性に必要な最小ランクを決定し、所定のランク制約の下で最適なサンプリング設計を提供する。

関連論文リスト

• Symmetric Matrix Completion with ReLU Sampling [15.095194065320987]
  エントリー依存サンプリングによる対称正半定値低ランク行列補完(MC)の問題について検討する。 特に、静止点のみを観測する修正線形単位(ReLU)サンプリングについて検討する。
  論文  参考訳（メタデータ） (2024-06-09T15:14:53Z)
• Disjunctive Branch-And-Bound for Certifiably Optimal Low-Rank Matrix Completion [6.537257913467247]
  2つの未成年者の和として低ランク行列を分解することにより、新しく、しばしばほぼ一致する凸緩和のクラスを提示する。 数値実験では、新しい凸緩和は、$max m, n q$ および $r leq$ の最適性またはほぼ最適性を減少させる。
  論文  参考訳（メタデータ） (2023-05-20T22:04:34Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  本稿では,初期監視情報を同時に拡張し,識別親和性行列を構築することのできる,新しい半教師付きサブスペースクラスタリング手法を提案する。 6つの一般的なベンチマークデータセットの総合的な実験結果から,本手法が最先端手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-21T01:47:17Z)
• Near optimal sample complexity for matrix and tensor normal models via geodesic convexity [4.808993240491135]
  行列およびテンソル正規モデルにおける共分散行列のクロネッカー因子の推定について検討した。 我々の結果は、十分に条件が整った、あるいは疎い要因に頼らず、また、十分に正確な初期推定を仮定する必要もない。 サンプルの複雑性境界と同じ状況下では,MLEを計算するための実用的で広く用いられている反復的手法であるフリップフロップアルゴリズムが,高い確率で線形に収束することを示す。
  論文  参考訳（メタデータ） (2021-10-14T17:47:00Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
  1次モーメントに対する大きな運動量パラメータの増大は適応的スケーリングに十分であることを示す。 また,段階的に減少するステップサイズに応じて,段階的に運動量を増加させるための洞察を与える。
  論文  参考訳（メタデータ） (2021-04-30T08:50:24Z)
• 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)
• Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion [101.83262280224729]
  我々は、原子核ノルム正規化行列補完に対する相対誤差を開発する。 未知行列の最適低ランク近似を回復するための相対上界を導出する。
  論文  参考訳（メタデータ） (2015-04-26T13:12:16Z)

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

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