作者：云雯 经济管理学院

指导老师：王纯 经济管理学院

关键词：聚类、随机图、高维统计、计算机理论、样本复杂度

摘要

一、回归的数据特征

1.多个因变量；2.部分自变量对应单个因变量；3.单个因变量或与其他因变量对应的自变量相关；4.特征3中相关性未知，因变量“联动”呈块状结构。

二、数学模型

总的自变量可能较多(所有因变量对应的自变量)，容易出现高维问题，但高维的参数稀疏/低秩假设不成立；且若根据样本协方差矩阵构建图，图中边不独立，这和常用随机图模型不符。所以，我们提出数学模型：有块状结构且为随机矩阵(average-case analysis)。

三、算法

我们“先聚类后回归”算法如图1。在样本量不变的情况下，该算法减少估计参数的个数，缓解高维的问题。 对于图1中Step 1，我们先根据的样本协方差矩阵绝对值和硬阈值建立无向图；由于样本较少，图中的边随机性较大，我们不用局部信息(单条边)，而用全局信息(共同邻居数量是否超过阈值)来；与常用的最小化MSE+凸的惩罚项(如Lasso回归)不同，该算法借用图的全局信息考虑高维问题中特殊的块状结构来添加惩罚项。

     图1 算法简介

四、理论结构和拓展

我们证明该算法样本复杂度与最大块维数同量级，并且是最优的。我们还把理论和算法拓展到有更复杂块状结构和条状(band)结构的情况。