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


$$
min\_{A}(|| AS- X||^{2}), s.t. \left\{
\begin{array}{c l} 
 \sum\_{i} a\_{ki} = 1\\
 a\_{ki} \ge0, \forall i
\end{array}\right.
$$


Typically this is solved by using quadratic programming. But since the number of genes is so large (e.g. ~30K). The method could be too slow. What's the better alternative to it?


I'm also wandering if there is alternative to linear-programming like approach to this kind of problem.



Better alternative to solve quadratic programming for large matrices
Your problem is also convex. Hence, a whole bunch of methods for convex optimization are available. Since projecting onto the constraints is not too difficult (project each row of $A$ onto the simplex), you could use projected gradient descent (many variants are available: you could use over- or under-relaxation or Nesterovs accelerated methods, or Barzilai-Borwein stepsizes…). A place to start to look for methods could be Boyd and Vandenberghes "[Convex Optimization](http://stanford.edu/~boyd/cvxbook/)", for example.


