论文标题
从稀疏时空样品中学习过渡操作员
Learning Transition Operators From Sparse Space-Time Samples
论文作者
论文摘要
我们考虑从不同时间的部分观察结果，特别是从稀疏观察到其权力的条目$ \ mathbf {a}，\ mathbf {a}^2，\ cdots，\ cdots，\ mathbf {a a a} $。这个时空过渡操作员恢复问题是由最近学习随时间变化的图形信号的兴趣所激发的，这些图形信号是由图形运算符驱动的，具体取决于基础图形拓扑。我们通过将问题嵌入合适的块矩阵的高维空间中来解决该问题的非线性，即使$ \ mathbf {a} $是完整的排名，它也会成为低级别矩阵完成问题。对于均匀的和自适应的随机时空抽样模型，我们通过适当的衡量这些嵌入式嵌入矩阵的不一致的量度来量化过渡算子的可恢复性。对于图形过渡算子，这些不一致的度量取决于动力学和图形拓扑之间的相互作用。 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 $。这就确定了空间样品可以用可比数量的时空样本代替。我们提供有效的IRLS算法的有效实现，并具有$ O（r n t）$的空间复杂性，并且在$ n $中的每卷时间复杂性线性线性。基于多个图形模型的过渡运算符的数值实验证实，理论发现准确地跟踪了经验相变，并说明了所提出算法的适用性和可扩展性。
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.
