压缩子空间聚类理论及其应用研究

With the popularization of applications such as High Definition video broadcasting, video surveillance, Internet of Things, and social networks, the last decades has witnessed an explosion of data to acquire, store, transmit, and process. The recent research has found that, though the data are very high dimensional, their intrinsic dimension is often much smaller than the ambient dimension. In the fields of computer vision, image processing, and systems theory, the data could be fitted into multiple subspaces, but the subspaces to which the data belongs might be unknown. Subspace clustering, which has been proposed for decades, is to simultaneously cluster the original data into multiple subspaces and find a low-dimensional subspace fitting each group of data. The operation on the original high-dimensional data might cost a great deal of computing and storage resources. Borrowing the idea from compressive sensing, this project brings forward the theory of compressed subspace clustering. Mapping the original data to the compressed space for further processing, this novel theory will reduce the computational complexity and the storage resource cost. This project will study the relative positional relationship between different original subspaces and the influence of the data distribution on the separability of original subspaces. The compression mapping will be designed and its influence on the separability of compressed subspaces will be evaluated. In addition, this project will study the clustering of the compressed data in the compressed space and the recovery of original subspaces and data. Therefore, the theory of compressed subspace clustering will be established and the complete theoretical guarantees and potential applications will be provided, which result in considerable scientific significance and theoretical value. Finally, the proposed theory and method will be applied in video segmentation and scene classification of distributed video compression to verify and demonstrate its performance.

随着高清广播、视频监控、物联网和社交网络等应用的普及，采集、存储、传输和处理的数据量呈现爆炸式增长。虽然这些数据的维度很高，但内在的自由度远小于其维度。在计算机视觉、图像处理和大系统理论中，数据往往来自于若干个低维子空间，但具体位于哪个子空间是未知的。传统子空间聚类模型直接在环境空间将原始数据划分成多个低维子空间，这种方式在处理高维数据时需要极大的计算和存储资源。本项目提出并研究压缩子空间聚类理论，借鉴压缩感知理论的思想，将原始样本映射到压缩空间中再做进一步处理，从而达到减小计算和存储复杂度的目的。本项目将全面研究子空间的相对位置关系及样本分布对子空间可分离性的影响，设计压缩观测方式并度量其保可分离性，研究压缩空间的观测样本聚类方法和原子空间及样本的恢复技术，具有重要的科学意义和理论价值。本项目将把理论结果应用于视频编码或社交网络等互联网技术，借助应用场景对系统进行全面验证和展示。

随着移动互联网和海量存储技术的发展，大尺度信号处理理论的重要意义日益凸显。子空间聚类模型将样本所在子空间作为分类依据，完美地利用了数据内在的线性结构特征，在机器学习和计算机视觉等领域具有重要应用。经典的子空间聚类算法在高维空间上求解若干最优化问题，计算复杂度巨大。本项目提出了压缩子空间聚类——即用高斯随机矩阵对原始样本进行降维压缩，然后再对压缩结果进行聚类，具有计算复杂度低、保护隐私和无需原始数据等优点。但同时带来隐患——随机压缩可能降低两个子空间的可分离性，增加聚类失败概率。此问题难点是高斯矩阵投影既不保持向量的模长，也无法保持正交基底。借助随机矩阵理论和几何技巧，本项目从理论层面彻底解决了这个问题。我们严格证明：只要投影后的背景空间维度不低于常数倍的子空间维度和子空间数量的对数中的较大值，那么投影后任意两个子空间之间的投影弗洛贝纽斯范数距离被限制在投影前距离的小领域的概率会随着新维度的增加以迅速趋向1。上述成果首次揭示了高维背景空间中的低维子空间经过高斯随机投影后以极大概率满足限制等距性质。它揭示了在对低维子空间进行处理时可以将其从任意高维的背景空间进行降维到一个中低维度的背景空间，而且保持原始数据的内部结构不发生本质变化。我们的发现意味着对于包括子空间聚类在内的众多子空间相关的问题，都可以先随机投影降维预处理，再用传统算法以较小的计算成本和内存开销进行处理，而且最终结果以大概率聚集于直接处理原始数据的结果。本项目的核心成果和降维领域理论界的JL引理（Johnson-Lindenstrauss Lemma）以及压缩感知领域的理论基础高斯随机矩阵对稀疏信号的RIP具有相同的科学意义，只不过后两者的研究对象都是欧氏空间的数据点，而本项目的研究对象是低维子空间；此外，它们研究的保距是数据点之间的欧氏距离，而本成果的距离是子空间之间的投影范数距离。这是世界上首次发现高斯随机矩阵具有针对低维子空间的限制保距性质。