CIF: Small: Learning Mixed Membership Models with a Separable Latent Structure: theory, provably efficient algorithms, and applications

在包括高光谱成像、基因表达分析和代谢网络在内的科学和工程领域的广泛问题中，观察到的数据是高维的，并且来自于一小部分未知共享潜在（隐藏）原因的未知随机混合。能够成功有效地从观测数据中识别潜在原因不仅对科学理解很重要，而且对有效的数据表示和决策也很重要。这类问题的流行算法利用近似和计算易处理性。 因此，这种算法的一致性或效率保证要么非常弱，要么不存在。这项研究涉及的算法的发展，学习潜在的原因模型，从高维数据与可证明的统计和计算效率guarantee.The关键的这项研究是一个自然的分离属性的共享潜在的因素？每个潜在因素的特征成分的存在？这是近似满足由流行的方法产生的估计。本研究的目的是建立，近似可分性不仅是一个自然和方便的混合隶属潜在因素模型的结构属性，但事实上，高维的必然结果。本研究还涉及开发一套可证明一致的，统计和计算效率高的算法，通过适当地利用几何形状引起的签名组件的混合成员的潜在因素的问题。关键的洞察力是将每个潜在因素的签名部分识别为合适空间中的极值点。这可以通过适当定义的随机投影有效地完成。基于随机投影的算法自然适合于低通信成本的分布式实现，这对于网络规模的分布式数据挖掘应用程序是有吸引力的。

In a wide spectrum of problems in science and engineering that includes hyperspectral imaging, gene expression analysis, and metabolic networks, the observed data is high-dimensional and arises from an unknown random mixture of a small set of unknown shared latent (hidden) causes. Being able to successfully and efficiently identify the latent causes from the observed data is important not only for scientific understanding, but also for efficient data representation and decision making. Popular algorithms for such problems make use of approximations and heuristics for computational tractability. As a consequence, consistency or efficiency guarantees for such algorithms are either very weak or nonexistent. This research involves the development of algorithms for learning latent-cause models from high-dimensional data with provable statistical and computational efficiency guarantees.The linchpin of this research is a natural separability property of the shared latent factors ? the presence of a signature component for each latent factor ? that is approximately satisfied by the estimates produced by popular approaches. This research aims to establish that approximate separability is not only a natural and convenient structural property of mixed-membership latent-factor models, but is, in fact, an inevitable consequence of high-dimensionality. This research also involves the development of a suite of provably consistent and statistically and computationally efficient algorithms for a diverse set of mixed-membership latent-factor problems by suitably leveraging the geometry induced by the signature components. The key insight is to identify the signature parts of each latent factor as extreme points in a suitable space. This can be done efficiently through appropriately defined random projections. The random-projections-based algorithm is naturally amenable to a low-communication-cost distributed implementation that is attractive for web-scale distributed data-mining applications.