Finding k in Latent k- polytope

The recently introduced Latent k-Polytope(LkP) encompasses several stochastic Mixed Membership 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. Contributions: This paper addresses some of these challenges and a summary of contributions are listed below. • The paper introduces the notion of Interpolative Convex Rank(ICR) of a matrix, and shows that k = ICR of a subset smoothed data matrix where k is the number of vertices in LkP (see details in Theorem 1). The notion of ICR should be of independent interest. • The paper introduces new techniques based on the hy-