从数据中学习切换线性动态的算法

我们提出了一种算法，用于从系统的完整状态或输出的噪声观察中学习离散时间的切换线性动态系统。切换线性系统使用多个线性动态模式来适应在某些期望容差范围内的数据。它们在机器人技术和网络物理系统的应用中自然而然地出现。从数据中学习切换系统是一个 NP-hard 问题，几乎与将 k > 1 线性模型拟合到数据的 k-线性回归问题相同。直接的混合整数线性规划（MILP）方法会导致与数据点数量呈指数级的时间复杂度。本文中，我们修改了问题的公式，以产生一个在数据规模上呈线性而在状态变量数量和期望模式数量上仍为指数级的算法。为此，我们结合了处理凸优化问题的椭球方法中的经典思想，以及非光滑优化中的知名oracle分离结果。我们在一组微基准和几个有趣的实际问题上展示了我们的方法。我们的评估表明，即使面对经过高度优化的现成MILP求解器，这种算法的优势也能够实际应用。