Abstract:
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(\INR)
of a matrix defined as the minimum number of its columns whose convex hull is
within Hausdorff distance $\varepsilon$ of the convex hull of all columns. The first important contribution of this paper is to show that under \emph{standard assumptions} $k$ equals the \INR of a \emph{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 \emph{inner dimension} in Non-negative matrix factorisation(NMF) with
assumptions which are qualitatively different than existing ones such as \emph{Separability}.
%An immediate corollary is the first polynomial time algorithm for finding the \emph{inner dimension} in Non-negative matrix factorisation(NMF) with assumptions considerably weaker than \emph{Separability}.
