Finding k in Latent k-polytope

The recently introduced Latent k Polytope(LkP) encompasses several stochastic Mixed Member ship models including Topic Models. The problem of finding k, the number of extreme points of LkP, is a fundamental challenge and includes several important open problems such as determination of number of components in Ad-mixtures. This paper addresses this challenge by introducing Interpolative Convex Rank(ICR) of a matrix defined as the minimum number of its columns whose convex hull is within Hausdorff distance of the convex hull of all columns. The first important contribution of this paper is to show that under standard assumptions k equals the ICR of a subset smoothed data matrix defined from Data generated from an LkP. The second important contribution of the paper is a polynomial time algorithm for finding k under standard assumptions. An immediate corollary is the first polynomial time algorithm for finding the inner dimension in Non-negative matrix factorisation (NMF) with assumptions which are qualitatively different than existing ones such as Separability.