On Statistical Learning of Simplices: Unmixing Problem Revisited
This work addresses the simplex learning problem, which has applications in computational biology and remote sensing, offering a theoretical improvement and practical method, though it is incremental as it builds on existing spectral unmixing research.
The paper tackles the problem of learning a high-dimensional simplex from uniformly sampled interior points, improving the sample complexity bound to O(K^2/ε log(K/ε)) for total-variation error ε, and proposes a heuristic method that matches state-of-the-art on noiseless data and outperforms it in noisy cases.
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 $O\left(\frac{K^2}ε\log\frac{K}ε\right)$, 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.