論文の概要: Learning Transition Operators From Sparse Space-Time Samples
- arxiv url: http://arxiv.org/abs/2212.00746v1
- Date: Thu, 1 Dec 2022 18:33:59 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-02 15:48:52.779706
- Title: Learning Transition Operators From Sparse Space-Time Samples
- Title（参考訳）: スパース時空サンプルからの遷移演算子学習
- Authors: Christian K\"ummerle, Mauro Maggioni, Sui Tang
- Abstract要約: 遷移作用素$mathbfA$を異なる時間における部分的な観測から学習する非線形問題を考察する。
我々は、$mathcalOrn log(nT)$ space-time sample が、ランク=r$演算子の正確な回復を保証するのに十分であることを示す。
- 参考スコア（独自算出の注目度）: 11.859913430860335
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the nonlinear inverse problem of learning a transition operator
$\mathbf{A}$ from partial observations at different times, in particular from
sparse observations of entries of its powers
$\mathbf{A},\mathbf{A}^2,\cdots,\mathbf{A}^{T}$. This Spatio-Temporal
Transition Operator Recovery problem is motivated by the recent interest in
learning time-varying graph signals that are driven by graph operators
depending on the underlying graph topology. We address the nonlinearity of the
problem by embedding it into a higher-dimensional space of suitable
block-Hankel matrices, where it becomes a low-rank matrix completion problem,
even if $\mathbf{A}$ is of full rank. For both a uniform and an adaptive random
space-time sampling model, we quantify the recoverability of the transition
operator via suitable measures of incoherence of these block-Hankel embedding
matrices. For graph transition operators these measures of incoherence depend
on the interplay between the dynamics and the graph topology. We develop a
suitable non-convex iterative reweighted least squares (IRLS) algorithm,
establish its quadratic local convergence, and show that, in optimal scenarios,
no more than $\mathcal{O}(rn \log(nT))$ space-time samples are sufficient to
ensure accurate recovery of a rank-$r$ operator $\mathbf{A}$ of size $n \times
n$. This establishes that spatial samples can be substituted by a comparable
number of space-time samples. We provide an efficient implementation of the
proposed IRLS algorithm with space complexity of order $O(r n T)$ and
per-iteration time complexity linear in $n$. Numerical experiments for
transition operators based on several graph models confirm that the theoretical
findings accurately track empirical phase transitions, and illustrate the
applicability and scalability of the proposed algorithm.
- Abstract（参考訳）: 我々は、遷移作用素 $\mathbf{a}$ を異なる時間における部分的観測から学習する非線形逆問題、特にそのパワーの成分のスパース観測 $\mathbf{a},\mathbf{a}^2,\cdots,\mathbf{a}^{t}$ を考える。
この時空間遷移演算子回復問題は、グラフトポロジに依存するグラフ演算子によって駆動される時間変化グラフ信号の学習に対する近年の関心に動機付けられている。
適切なブロック・ハンケル行列の高次元空間に埋め込むことで問題の非線形性に対処し、$\mathbf{A}$ がフルランクであっても、低ランク行列完備問題となる。
一様および適応的ランダム時空サンプリングモデルにおいて、これらのブロック・ハンケル埋め込み行列の不整合の適切な尺度を用いて遷移作用素の回復性を定量化する。
グラフ遷移作用素の場合、これらの非コヒーレンスの測定は力学とグラフトポロジーの間の相互作用に依存する。
我々は、適切な非凸反復再重み付き最小二乗法(IRLS)アルゴリズムを開発し、その二次局所収束を確立し、最適なシナリオでは、$\mathcal{O}(rn \log(nT))$ 時空間サンプルが、階数-r$演算子$\mathbf{A}$ サイズ$n \times n$ の正確な回復を保証するのに十分であることを示す。
これにより、空間サンプルは、同じ数の時空サンプルで置き換えることができる。
提案したIRLSアルゴリズムを,次数$O(r n T)$の空間複雑性と,次数$n$の時間単位の複雑性を線形に実装する。
複数のグラフモデルに基づく遷移作用素の数値実験により、理論的知見は経験的相転移を正確に追跡し、提案するアルゴリズムの適用性と拡張性を示す。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳（メタデータ） (2024-03-08T18:50:19Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - A Finite Expression Method for Solving High-Dimensional Committor Problems [5.748690310135373]
有限表現法(FEX)をコミッタの計算ツールとして検討する。
FEXベースのコミッタソルバは、いくつかの高次元ベンチマーク問題でテストされる。
論文 参考訳（メタデータ） (2023-06-21T13:43:59Z) - Orthogonal Directions Constrained Gradient Method: from non-linear
equality constraints to Stiefel manifold [16.099883128428054]
直交方向制約法(ODCGM)という新しいアルゴリズムを提案する。
ODCGMはベクトル空間へのプロジェクションのみを必要とする。
以上より, ODCGMは, ほぼ最適のオラクル複合体を呈することを示した。
論文 参考訳（メタデータ） (2023-03-16T12:25:53Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Optimal Randomized Approximations for Matrix based Renyi's Entropy [16.651155375441796]
整数次数$alpha$の場合のランダム近似と非整数$alpha$の場合の直列近似を開発する。
大規模シミュレーションと実世界の応用は、開発した近似の有効性を検証する。
論文 参考訳（メタデータ） (2022-05-16T02:24:52Z) - Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and
Costs [45.87981728307819]
異種空間に居住する関連するデータセットを比較して整列する能力は、機械学習においてますます重要な役割を担っている。
グロモフ・ワッサーシュタイン (Gromov-Wasserstein, GW) 形式主義はこの問題に対処するのに役立つ。
論文 参考訳（メタデータ） (2021-06-02T12:50:56Z) - Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。
我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-30T19:10:32Z) - Phase retrieval in high dimensions: Statistical and computational phase
transitions [27.437775143419987]
我々は$mathbfXstar$を$m$(おそらくノイズの多い)観測から再構成する問題を考察する。
特に、フルランク行列に対する情報理論上の完全回復への遷移は、$alpha=1$と$alpha=2$である。
我々の研究は、高次元位相探索における統計的およびアルゴリズム的しきい値の広範な分類を提供する。
論文 参考訳（メタデータ） (2020-06-09T13:03:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。