3
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.