# Probabilistic model to approach problem that is usually dealt with linear programming

I have the following problem. Let's say we have $x_{jk}$ it is an expression value of gene $j$ in a sample $k$. It is the average of expression levels across the cell types $s_{ij}$, weighted by respective proportions $a_{ki}$ ($i = 1 \cdots N$, $N$ is the disease type):

$$x_{jk} = \sum_{i=1}^{N} a_{ki}s_{ij}$$

Generally this can be expressed as matrix form

$$X = AS$$

What I want to do is to solve this equation

\begin{align} &\min_{A}\ || AS- X||^{2}\\ &\text{subject to } \left\{ \begin{array}{c l} \sum_{i} a_{ki} = 1\\ a_{ki} \ge0, \forall i \end{array}\right. \end{align}

Typically this is solved by using quadratic programming. The number of genes is large (e.g. ~30K).

I'm wandering if there is any good probabilistic model to deal such kind of problem?

• I cannot provide an answer, but your problem sounds like it may be Convex non-negative matrix factorization. If so, you might try searching on that term, or putting it in your question title and/or description. – GeoMatt22 Oct 27 '15 at 13:38
• @GeoMatt22: Note quite. In NMF both A and S is unknown. In my problem A is known. – neversaint Oct 27 '15 at 13:52
• You mean S is known? (A is the argument of the objective function) – GeoMatt22 Oct 27 '15 at 14:02
• @GeoMatt22: Oops you're right. S is known. – neversaint Oct 28 '15 at 0:30