Mixed linear regression (MLR) is a powerful model for characterizing
nonlinear relationships by utilizing a mixture of linear regression sub-models.
The identification of MLR is a fundamental problem, where most of the existing
results focus on offline algorithms, rely on independent and identically
distributed (i.i.d) data assumptions, and provide local convergence results
only. This paper investigates the online identification and data clustering
problems for two basic classes of MLRs, by introducing two corresponding new
online identification algorithms based on the expectation-maximization (EM)
principle. It is shown that both algorithms will converge globally without
resorting to the traditional i.i.d data assumptions. The main challenge in our
investigation lies in the fact that the gradient of the maximum likelihood
function does not have a unique zero, and a key step in our analysis is to
establish the stability of the corresponding differential equation in order to
apply the celebrated Ljung's ODE method. It is also shown that the
within-cluster error and the probability that the new data is categorized into
the correct cluster are asymptotically the same as those in the case of known
parameters. Finally, numerical simulations are provided to verify the
effectiveness of our online algorithms.

本文研究了混合线性回归模型的在线识别和数据聚类问题，引入了两种基于期望最大化原理的相应的新的在线识别算法，证明了这两种算法都在不依赖传统的独立同分布数据假设的情况下全局收敛。在分析中的一个关键步骤是建立相应微分方程的稳定性以应用著名的 Ljung 的 ODE 方法，同时还证明了在已知参数的情况下，簇内误差和新数据被正确分类到簇中的概率渐近地与之前相同。最后，通过数值模拟验证了我们在线算法的有效性。

混合线性回归的全局在线识别收敛性

Global Convergence of Online Identification for Mixed Linear Regression

We study the problem of approximate social welfare maximization (without
money) in one-sided matching problems when agents have unrestricted cardinal
preferences over a finite set of items. Random priority is a very well-known
truthful-in-expectation mechanism for the problem. We prove that the
approximation ratio of random priority is Theta(n^{-1/2}) while no
truthful-in-expectation mechanism can achieve an approximation ratio better
than O(n^{-1/2}), where n is the number of agents and items. Furthermore, we
prove that the approximation ratio of all ordinal (not necessarily
truthful-in-expectation) mechanisms is upper bounded by O(n^{-1/2}), indicating
that random priority is asymptotically the best truthful-in-expectation
mechanism and the best ordinal mechanism for the problem.

研究了在代理人对有限物品具有不受限制的基数偏好时，近似社会福利最大化（无货币）的问题，在此问题中随机优先级是一个非常著名的期望真实机制，证明了随机优先级的近似比率是 Θ（n ^ {-1 / 2}），而没有期望真实机制可以实现比 O（n^{-1/2}）更好的近似比率。此外，证明了所有序数（不一定是期望真实的）机制的近似比率都是 O（n^{-1/2}），表明随机优先级是问题的渐近最好的期望真实机制和最好的序数机制。