ON STATISTICAL LEARNING OF SIMPLICES: UNMIXING PROBLEM REVISITED

• 成果类型: Article
• 署名作者: Najafi, Amir; Ilchi, Saeed; Saberi, Amir Hossein; Motahari, Seyed Abolfazl; Khalaj, Babak H.; Rabiee, Hamid R.
• 署名单位: Sharif University of Technology; Sharif University of Technology; Sharif University of Technology
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/20-AOS2016
• 发表日期: 2021
• 页码: 1626-1655
• 关键词: convex; algorithm; polytope; volume; Identifiability

摘要

We study the sample complexity of learning a high-dimensional simplex from a set of points uniformly sampled from its interior. Learning of simplices is a long studied problem in computer science and has applications in computational biology and remote sensing, mostly under the name of spectral unmixing. We theoretically show that a sufficient sample complexity for reliable learning of a K-dimensional simplex up to a total-variation error of is an element of is O(K-2/epsilon log K/epsilon), which yields a substantial improvement over existing bounds. Based on our new theoretical framework, we also propose a heuristic approach for the inference of simplices. Experimental results on synthetic and real-world datasets demonstrate a comparable performance for our method on noiseless samples, while we outperform the state-of-the-art in noisy cases.