論文の概要: Wedge Sampling: Efficient Tensor Completion with Nearly-Linear Sample Complexity

• arxiv url: http://arxiv.org/abs/2602.05869v1
• Date: Thu, 05 Feb 2026 16:47:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-06 18:49:09.055384
• Title: Wedge Sampling: Efficient Tensor Completion with Nearly-Linear Sample Complexity
• Title（参考訳）: Wedge Smpling: ほぼLinearサンプル複合体を用いた高効率テンソル補修法
• Authors: Hengrui Luo, Anna Ma, Ludovic Stephan, Yizhe Zhu,
• Abstract要約: 低ランクテンソル補完のための新しい非適応サンプリングスキームであるウェッジサンプリングを導入する。 次数$kの低ランクテンソルの次元$n倍の倍数n$を、そのエントリのサブセットから復元する。
• 参考スコア（独自算出の注目度）: 9.42598427201735
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We introduce Wedge Sampling, a new non-adaptive sampling scheme for low-rank tensor completion. We study recovery of an order-$k$ low-rank tensor of dimension $n \times \cdots \times n$ from a subset of its entries. Unlike the standard uniform entry model (i.e., i.i.d. samples from $[n]^k$), wedge sampling allocates observations to structured length-two patterns (wedges) in an associated bipartite sampling graph. By directly promoting these length-two connections, the sampling design strengthens the spectral signal that underlies efficient initialization, in regimes where uniform sampling is too sparse to generate enough informative correlations. Our main result shows that this change in sampling paradigm enables polynomial-time algorithms to achieve both weak and exact recovery with nearly linear sample complexity in $n$. The approach is also plug-and-play: wedge-sampling-based spectral initialization can be combined with existing refinement procedures (e.g., spectral or gradient-based methods) using only an additional $\tilde{O}(n)$ uniformly sampled entries, substantially improving over the $\tilde{O}(n^{k/2})$ sample complexity typically required under uniform entry sampling for efficient methods. Overall, our results suggest that the statistical-to-computational gap highlighted in Barak and Moitra (2022) is, to a large extent, a consequence of the uniform entry sampling model for tensor completion, and that alternative non-adaptive measurement designs that guarantee a strong initialization can overcome this barrier.
• Abstract（参考訳）: 低ランクテンソル補完のための新しい非適応サンプリングスキームであるウェッジサンプリングを導入する。 次数-k$ 次元 $n \times \cdots \times \times n$ の低ランクテンソルをその部分集合から復元する。 標準的な一様エントリーモデル(すなわち$[n]^k$のサンプル)とは異なり、ウェッジサンプリングは関連する二部サンプリンググラフの2つの構造化パターン(ウェッジ)に観測を割り当てる。 これらの長い2つの接続を直接促進することにより、サンプリング設計は、一様サンプリングが不十分で十分な情報相関を生成できない状況において、効率的な初期化の基盤となるスペクトル信号を強化する。 本研究の主な成果は、このサンプリングパラダイムの変更により、多項式時間アルゴリズムが、ほぼ線形なサンプルの複雑さを$n$で、弱さと正確なリカバリを両立させることができることを示している。 wedge-sampling-based spectrum initialization は既存の精細化手順(例えばスペクトル法や勾配法)と組み合わせて、$\tilde{O}(n)$一様にサンプリングされたエントリのみを加算し、$\tilde{O}(n^{k/2})$サンプルの複雑さを、効率的な方法で一様エントリーサンプリングで必要とされるのが一般的である。 以上の結果から,Barak と Moitra (2022) で強調された統計的・計算的ギャップは,テンソル完備化のための一様エントリーサンプリングモデルの結果であり,強い初期化を保証するような代替の非適応測定設計は,この障壁を克服できる可能性が示唆された。

関連論文リスト

• Parallel Simulation for Log-concave Sampling and Score-based Diffusion Models [55.07411490538404]
  本稿では,次元$d$の適応的複雑性依存性を改善する並列サンプリング手法を提案する。 我々の手法は科学計算による並列シミュレーション技術に基づいている。
  論文  参考訳（メタデータ） (2024-12-10T11:50:46Z)
• Improving Gradient-guided Nested Sampling for Posterior Inference [47.08481529384556]
  本稿では,パフォーマンス,汎用的勾配誘導型ネストサンプリングアルゴリズム,$tt GGNS$を提案する。 後部分布から大量の高品質なサンプルを得るために,ネストサンプリングと生成フローネットワークを組み合わせる可能性を示す。
  論文  参考訳（メタデータ） (2023-12-06T21:09:18Z)
• Model-adapted Fourier sampling for generative compressed sensing [7.130302992490975]
  測定行列が一意行列からランダムにサブサンプリングされたとき, 生成的圧縮センシングについて検討した。 我々は,textitO(kd| boldsymbolalpha|_22)$の測定精度を改良したモデル適応サンプリング戦略を構築した。
  論文  参考訳（メタデータ） (2023-10-08T03:13:16Z)
• Improved Active Learning via Dependent Leverage Score Sampling [8.400581768343804]
  本研究では,非依存的(逆方向雑音)環境下での能動学習手法の改善方法について述べる。 エンフェボタルサンプリングアルゴリズムに基づく簡単な実装法を提案する。 独立サンプリングと比較して,本手法は,所定の目標精度に到達するために必要なサンプル数を最大50%削減する。
  論文  参考訳（メタデータ） (2023-10-08T01:51:30Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。 これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。 アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
  論文  参考訳（メタデータ） (2022-10-22T19:07:26Z)
• Adaptive Sketches for Robust Regression with Importance Sampling [64.75899469557272]
  我々は、勾配降下(SGD)による頑健な回帰を解くためのデータ構造を導入する。 我々のアルゴリズムは、サブ線形空間を使用し、データに1回パスするだけで、SGDの$T$ステップを重要サンプリングで効果的に実行します。
  論文  参考訳（メタデータ） (2022-07-16T03:09:30Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。 この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
  論文  参考訳（メタデータ） (2021-06-29T12:49:54Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。 我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
  論文  参考訳（メタデータ） (2020-04-23T05:00:21Z)

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

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