論文の概要: Structure and Exact Certification of Nonnegative Tensor Decompositions

• arxiv url: http://arxiv.org/abs/2610.32787v1
• Date: Fri, 23 Oct 2026 15:35:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-27 01:38:06.594846
• Title: Structure and Exact Certification of Nonnegative Tensor Decompositions
• Title（参考訳）: 非負のテンソル分解の構造と厳密な証明
• Abstract要約: 有理因子行列によって供給される非負のテンソル分解の構造と正確な証明について検討する。 入力ビット長$L$に対して、非負のランクと正確な最小長分解を計算する決定論的$G(R)LO(R2)$-timeアルゴリズムを与える。 いくつかの有理長さ-$R$入力は、任意の最小長出力に対して少なくとも$lfloor R/2rfloor!
• 参考スコア（独自算出の注目度）: 4.894024268234817
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the structure and exact certification of nonnegative tensor decompositions supplied through rational factor matrices. Every failure of minimality or essential uniqueness contains an irreducible positive exchange between $p$ supplied terms and $q$ competing terms. A dimension count based on the Lovitz--Petrov splitting theorem bounds the effective order of such an exchange, the sum over the modes of the joint factor-span dimension minus one, by $p+q-2$, and this bound is attained at every supplied length $R\ge2$. After eliminating ambient-row variables by the Farkas lemma, the resulting semialgebraic systems have fewer than $2R^2$ real variables. For input bit length $L$, this gives a deterministic $G(R)L^{O(R^2)}$-time algorithm that computes the nonnegative rank and an exact minimum-length decomposition, decides minimality and essential uniqueness, and returns exact witnesses when either property fails. The exponent is independent of the tensor order and the mode dimensions. For Lebesgue moment tensors, positive quadrature determines the nonnegative rank and the uniqueness behavior, and some rational length-$R$ inputs force a common field of degree at least $\lfloor R/2\rfloor!$ for any exact minimum-length output. As an illustration, an implementation resolves all 114 instances left inconclusive by earlier positive-scattering criteria, of which 95 are minimal and essentially unique and 19 are minimal but nonunique.
• Abstract（参考訳）: 有理因子行列によって供給される非負のテンソル分解の構造と正確な証明について検討する。 極小性または本質的一意性のすべての失敗は、$p$供給項と$q$競合項の間の既約正の交換を含む。 ロヴィッツ-ペトロフ分割定理に基づく次元カウントは、そのような交換の有効順序、結合係数-スパン次元のモードの和を1、$p+q-2$で制限し、この境界は供給された全ての長さ$R\ge2$で達成される。 ファーカス補題によって周囲のロー変数を排除した後、結果として生じる半代数系は2R^2$実変数より少ない。 入力ビット長$L$の場合、決定論的$G(R)L^{O(R^2)}$-timeアルゴリズムが与えられ、非負階数と正確な最小長分解を計算し、極小性と本質的な一意性を決定し、どちらの特性が失敗しても正確な証人を返す。 指数はテンソル次数とモード次元とは独立である。 ルベーグのモーメントテンソルの場合、正の次数は非負ランクと一意性行動を決定し、いくつかの有理長-R$入力は少なくとも$\lfloor R/2\rfloor! 任意の最小限の出力に対して$。 例示として、実装は、初期の正の散乱基準によって決定的に残っていた114のインスタンスをすべて解決し、95は最小で本質的に一意であり、19は最小だが非特異である。

関連論文リスト

• Strictly Replicable Realizable Learning: Unknown Marginals, Finite-Class Interpolation, and the Cost of Shared Randomness [0.0]
  本研究では,未知の,未知の,未知の,未知の事例の残差に基づく実存可能なブール学習について検討する。 決定論的学習、任意の有限類に対する極小$$レギュレーション、VC 1 の有限類に対するすべての濃度-再現性レギュレーションを特徴付ける。
  論文  参考訳（メタデータ） (2026-10-18T05:17:14Z)
• Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization [55.29259818039367]
  凸閉集合上の逆オンライン非負の非単調DR-部分モジュラ函数について検討する。 学習者は、目的を観察する前に各アクションを学習し、後から最高の固定アクションと競合する。 定数対物列は、最適に多くの1次クエリでオフラインの$(4/9-varepsilon)$近似を生成する。
  論文  参考訳（メタデータ） (2026-09-30T18:26:29Z)
• Scalable Minimum-Volume Simplex Estimation with Non-asymptotic Analysis [3.008906408145323]
  既存の推定器は、サンプルごとの立方体処理か、または$O(NK)$ストレージを必要とする。 DeepMVSAは神経暗黙の形で最小限の原理を再表現する。 最大$N=108$の合成観測実験は、予測された精度とスケーリングと一致している。
  論文  参考訳（メタデータ） (2026-09-22T02:13:14Z)
• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
  論文  参考訳（メタデータ） (2026-09-09T10:13:43Z)
• Deterministic Minimum-Output-Entropy Nonadditivity via Haagerup's Inequality and Near-Free Permutation Representations [6.9022592726569085]
  コリンズの最小出力エントロピー非付加性の混合単位証明に基づく有限次元二次証明を実現する。
  論文  参考訳（メタデータ） (2026-08-31T16:53:42Z)
• Non-Asymptotic Variational Learning for Monotone Nonlinear Multiscale Elliptic Equations: Scale-Robust Primal-Dual Bounds and Strong-Form Statistical Ill-Conditioning [0.0]
  我々は、一様非線形多スケール楕円型方程式の変分物理学インフォームド近似に対する非漸近近似、サンプリング、有限点最適化理論を開発した。 境界整合性ニューロ特徴クラスでは、集団誤差は近似、経験的四分法、投影的次数項に分けられ、全ての非近似定数は顕微鏡スケール(ヴァレプシロン)で均一である。
  論文  参考訳（メタデータ） (2026-07-17T07:26:29Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。 これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
  論文  参考訳（メタデータ） (2026-05-22T15:05:33Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。 1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。 テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
  論文  参考訳（メタデータ） (2022-11-10T00:40:37Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)

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

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