BIGDATA: F: DKA: Learning a Union of Subspaces from Big and Corrupted Data

本计画主要研究在高维资料中自动发现多重低维结构的理论与演算法，并评估这些演算法在影像丛集的应用。开发的技术增强了我们处理来自多个来源和模式的大数据问题的能力，并提高了如何解释大量复杂高维数据的知识。在这个项目中开发的技术可以显着拓宽稀疏表示理论中现有结果对子空间聚类问题的适用性，这些问题在图像处理中得到了广泛的应用（例如，图像去噪、压缩、表示和分割），计算机视觉（例如，运动分割和面部聚类）和动态系统（例如，混合系统识别）。这项研究开发了可证明正确和可扩展的算法，用于从大数据和损坏的数据中学习低维子空间的并集。这些算法是基于所谓的数据的自我表达属性，它指出，一个未损坏的数据点可以很好地近似于其他未损坏的数据点的仿射组合。这项研究表明，通过对系数施加结构化的稀疏和低秩先验，可以发现数据中的多个结构。在未损坏数据的情况下，研究小组研究了数据的条件，在这些条件下，完美的聚类是可能的。在数据被离群值破坏的情况下，研究小组研究了完美聚类和离群值拒绝可能的条件。在缺少条目的数据的情况下，研究小组研究了完美聚类和数据完成的条件。该项目还开发了高效和可扩展的算法，这些算法受益于分布式和高性能计算，用于解决各种子空间聚类问题。这些算法能够解决计算机视觉中的大规模问题，包括图像聚类。

This project develops theory and algorithms for automatically discovering multiple low-dimensional structures in high-dimensional data, and evaluates these algorithms in image clustering applications. The developed techniques enhance our ability to handle big data problems from multiple sources and modalities, and advance the knowledge on how to interpret massive amounts of complex high-dimensional data. The techniques developed in this project can significantly broaden the applicability of existing results in sparse representation theory to subspace clustering problems, which have found widespread applications in image processing (e.g., image denoising, compression, representation, and segmentation), computer vision (e.g., motion segmentation and face clustering) and dynamical systems (e.g., hybrid system identification). This research develops provably correct and scalable algorithms for learning a union of low-dimensional subspaces from big and corrupted data. The algorithms are based on the so-called self-expressiveness property of the data, which states that an uncorrupted data point can be well approximated by an affine combination of other uncorrupted data points. This research shows that by imposing a structured sparse and low-rank prior on the coefficients, one can discover multiple structures in the data. In the case of uncorrupted data, the research team studies conditions on the data under which a perfect clustering is possible. In the case of data corrupted by outliers, the research team studies conditions under which perfect clustering and outlier rejection are possible. In the case of data with missing entries, the research team studies conditions under which perfect clustering and data completion are possible. The project also develops efficient and scalable algorithms that benefit from distributed and high-performance computing for solving the various subspace clustering problems. These algorithms enable solving large-scale problems in computer vision, including image clustering.