論文の概要: Polynomial Complexity of Inversion of sequences and Local Inversion of Maps

• arxiv url: http://arxiv.org/abs/2406.19610v1
• Date: Fri, 28 Jun 2024 02:34:29 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-01 18:00:20.169863
• Title: Polynomial Complexity of Inversion of sequences and Local Inversion of Maps
• Title（参考訳）: 列の逆転の多項式複雑性と写像の局所逆転
• Authors: Virendra Sule,
• Abstract要約: 論文は、二項体上の有限列のエンプインバージョン問題に対する解を定義し、探求する。 RR を定義する固定次数の複素数の最小数(位数)は、その次数の列の EmphPolynomial と呼ばれる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This Paper defines and explores solution to the problem of \emph{Inversion of a finite Sequence} over the binary field, that of finding a prefix element of the sequence which confirms with a \emph{Recurrence Relation} (RR) rule defined by a polynomial and satisfied by the sequence. The minimum number of variables (order) in a polynomial of a fixed degree defining RRs is termed as the \emph{Polynomial Complexity} of the sequence at that degree, while the minimum number of variables of such polynomials at a fixed degree which also result in a unique prefix to the sequence and maximum rank of the matrix of evaluation of its monomials, is called \emph{Polynomial Complexity of Inversion} at the chosen degree. Solutions of this problems discovers solutions to the problem of \emph{Local Inversion} of a map $F:\ftwo^n\rightarrow\ftwo^n$ at a point $y$ in $\ftwo^n$, that of solving for $x$ in $\ftwo^n$ from the equation $y=F(x)$. Local inversion of maps has important applications which provide value to this theory. In previous work it was shown that minimal order \emph{Linear Recurrence Relations} (LRR) satisfied by the sequence known as the \emph{Linear Complexity} (LC) of the sequence, gives a unique solution to the inversion when the sequence is a part of a periodic sequence. This paper explores extension of this theory for solving the inversion problem by considering \emph{Non-linear Recurrence Relations} defined by a polynomials of a fixed degree $>1$ and satisfied by the sequence. The minimal order of polynomials satisfied by a sequence is well known as non-linear complexity (defining a Feedback Shift Register of smallest order which determines the sequences by RRs) and called as \emph{Maximal Order Complexity} (MOC) of the sequence. However unlike the LC there is no unique polynomial recurrence relation at any degree.
• Abstract（参考訳）: この論文は、二項体上の「有限列のemph{Inversion」問題、多項式によって定義され、その列によって満たされる「emph{Recurrence Relation} (RR)」規則で確認される列のプレフィックス要素を見つける問題に対する解を定義し、探求する。 RRs を定義する固定次数の多項式における変数(順序)の最小数は、その次数の列の \emph{Polynomial Complexity} と呼ばれ、一方、そのような多項式の変数の最小数は、その単項の評価の行列の列の唯一の接頭辞と最大階数となり、選択された次数の次数で \emph{Polynomial Complexity of Inversion} と呼ばれる。 この問題の解は、写像 $F:\ftwo^n\rightarrow\ftwo^n$ at a point $y$ in $\ftwo^n$, that of solve for $x$ in $\ftwo^n$ from the equation $y=F(x)$ である。 写像の局所反転は、この理論に価値を与える重要な応用である。 以前の研究で、列の \emph{Linear Complexity} (LC) と呼ばれる列で満たされる最小順序 \emph{Linear Recurrence Relations} (LRR) は、列が周期列の一部であるときの反転に対する一意の解を与えることを示した。 本稿では, 次数$>1$の多項式で定義され, 列で満たされた 'emph{Non-linear Recurrence Relations' を考えることにより, 逆問題を解決するためのこの理論の拡張について検討する。 列で満たされる多項式の最小順序は、非線形複雑性(RRによって列を決定する最小順序のフィードバックシフトレジスタを定義する)として知られ、その列の 'emph{Maximal Order Complexity} (MOC) と呼ばれる。 しかし、LCとは異なり、任意の程度に一意な多項式反復関係は存在しない。

関連論文リスト

• Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers [29.212403229351253]
  我々は、このマルコフ連鎖のほぼ最適な実装を示し、ステップごとの複雑さは、約$A$のゼロでないエントリの数であるのに対して、マルコフ連鎖のステップの数は同じである。 1) このダイキンウォークで生じる行列はゆっくりと変化すること,2) この遅い変化を利用した効率的な線形解法を展開し, 以前のステップで計算した情報を用いて行列の逆転を高速化すること,3) ランダム化されたテイラー級数に基づく推定器を用いてメトロポリスフィルタステップにおける行列項の計算を高速化すること,である。
  論文  参考訳（メタデータ） (2024-09-06T14:49:43Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の等方的ガウスデータの下で勾配降下学習の問題を考察する。 SGDアルゴリズムで最適化された2層ニューラルネットワークは、サンプル付き任意のリンク関数の$f_*$を学習し、実行時の複雑さは$n asymp T asymp C(q) cdot dであることを示す。
  論文  参考訳（メタデータ） (2024-06-03T17:56:58Z)
• Positive Moments Forever: Undecidable and Decidable Cases [1.3124513975412255]
  単純ユニタリ線形反復列に対する正の問題は決定可能であり、可換環上の線形反復列に対しては決定不能であることを示す。 副生成物として、ポリアの定理の自由版を証明する。
  論文  参考訳（メタデータ） (2024-04-23T13:53:37Z)
• Word Linear Complexity of sequences and Local Inversion of maps over finite fields [0.0]
  本稿では、有限体上のベクトル値列の概念を、そのアンサンブルの線形複素性$の拡張として展開する。 行列極小は、列が周期的であるとき、一意の局所逆の$x$ in $ffn$を解くために与えられた$ffn$ in $ffn$において、写像$F:ffnが反復的に生成したベクトルで使用できることを示す。
  論文  参考訳（メタデータ） (2023-11-11T14:06:23Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。 特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
  論文  参考訳（メタデータ） (2023-01-10T20:43:29Z)
• 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)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization [49.090785356633695]
  非対称な低ランク分解問題: [mathbbRm min d , mathbfU$ および MathV$ について検討する。
  論文  参考訳（メタデータ） (2021-06-27T17:25:24Z)
• Unique sparse decomposition of low rank matrices [17.037882881652617]
  低階行列Yin mathbbRrtimes n$ のユニークな分解が見つかる。 我々は、ある$Yin MathRrtimes n$が$Xin mathbbRrtimes n$のスパースワイズ分解であることを示す。
  論文  参考訳（メタデータ） (2021-06-14T20:05:59Z)

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

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