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

<p>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. </p>

<p>A much simpler equivalent formulation of this problem is: if we have a <span class="math-container">$(r-1)$</span>-dimensional simplex with outliers, how do we find this simplex? Suppose that we have <span class="math-container">$r$</span> linearly independent basis <span class="math-container">$\{b_j\}_{j=1}^r$</span>, and our observed data points are supposed to have the form of <span class="math-container">$$\sum_{j=1}^r \lambda_j b_j, \lambda_j \ge 0,\sum_j \lambda_j =1,$$</span> 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 <span class="math-container">$r$</span> basis, which means that they are outliers. The outliers still have the form of  <span class="math-container">$\sum_{j=1}^r \lambda_j b_j$</span>, but they do not satisfy <span class="math-container">$\sum \lambda_j=1$</span>. Moreover, suppose that we have <span class="math-container">$N$</span> data points (<span class="math-container">$N\gg r$</span>) of which <span class="math-container">$f$</span> points are outliers and we want <span class="math-container">$f/N$</span> to be as large as possible. Our question is how to develop a robust algorithm to detect the simplex and outliers. </p>

CC BY-SA 4.0
2018-12-17T06:17:13.803Z
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
CC BY-SA 4.0
2018-12-17T23:41:27.183Z
@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
CC BY-SA 4.0
2018-12-21T07:14:44.567Z
@SashoNikolov If I understand the OP correctly, it seems to be the rank constraint that rules out the trivial case.
Minkov
CC BY-SA 4.0
2018-12-21T15:40:18.160Z
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
<machine-learning><matrices><na.numerical-analysis>
Complexity of low-rank matrix factorizations with rows in a simplex and outliers
Yufeng Zhang
# Complexity of low-rank matrix factorizations with rows in a simplex and outliers

(Asked by: username_0 on 2018-12-17)

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.

**Tags:** machine-learning, matrices, na.numerical-analysis
> **Comments:**
> **username_1**: 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?  
> **username_0**: @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.  
> **username_2**: @SashoNikolov If I understand the OP correctly, it seems to be the rank constraint that rules out the trivial case.  
> **username_1**: Yes, that changed since my comment. I still have no idea what the "globally optimal solution" means given that there is no objective function.  

---

## 0 answers

