Better alternative to solve quadratic programming for large matrices

Question

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.

Answer 1

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", for example.