# Complexity of low-rank matrix factorizations with rows in a simplex and outliers

Our goal is to obtain a matrix factorization in form of $$M = U V'$$, where $$U\in\mathbb{R}^{d\times r}, V \in\mathbb{R}^{N\times r}$$ and each row of $$V$$ satisfies $$\sum_{j}(V)_{ij}=1, (V)_{ij}\ge 0$$ for each $$i$$. Also, we have $$rank(U)=r$$ and $$N\gg r$$, which means that $$U$$ is the basis matrix and $$V$$ is the coefficient matrix.

We know that there exist methods including semi-nonnegative matrix factorization and convex nonnegative matrix factorization, but these methods do not guarantee convergence to the globally optimal solution. Moreover, we aim to make the algorithm robust to outliers. So we are wondering whether there is any method that solves this problem with theoretical guarantees or there is hardness characterization.

A much simpler equivalent formulation of this problem is: if we have a $$(r-1)$$-dimensional simplex with outliers, how do we find this simplex? Suppose that we have $$r$$ linearly independent basis $$\{b_j\}_{j=1}^r$$, and our observed data points are supposed to have the form of $$\sum_{j=1}^r \lambda_j b_j, \lambda_j \ge 0,\sum_j \lambda_j =1,$$ meaning that they lie on a simplex. However, due to corruption, some of these data points may not lie on the simplex, but still, lie in the linear space spanned by the $$r$$ basis, which means that they are outliers. The outliers still have the form of $$\sum_{j=1}^r \lambda_j b_j$$, but they do not satisfy $$\sum \lambda_j=1$$. Moreover, suppose that we have $$N$$ data points ($$N\gg r$$) of which $$f$$ points are outliers and we want $$f/N$$ to be as large as possible. Our question is how to develop a robust algorithm to detect the simplex and outliers.

• What are you optimizing? If I ignore the outliers issue for the moment, why can't I just take $U = M$ and $V = I$ (the identity)? The equivalent question is also unclear: how is the "simplex with outliers" given to you? – Sasho Nikolov Dec 17 '18 at 6:17
• @SashoNikolov This example doesn't fit this problem because this trivial solution of $U$ and $V$ does not fit the desired shape in our question. I added more details to the question so as to make it more clear. – Yufeng Zhang Dec 17 '18 at 23:41
• @SashoNikolov If I understand the OP correctly, it seems to be the rank constraint that rules out the trivial case. – Minkov Dec 21 '18 at 7:14
• Yes, that changed since my comment. I still have no idea what the "globally optimal solution" means given that there is no objective function. – Sasho Nikolov Dec 21 '18 at 15:40