Decomposability of positive maps By results of Størmer and Woronowicz, every positive map $\Phi \colon \mathcal{M}_{d \times d} \rightarrow \mathcal{M}_{d' \times d'}$ for $dd' \leq 6$  can be decomposed as a convex combination
$$\Phi = p \phi + (1-p) ~ T \circ \psi$$
where $\phi$, $\psi$ are completely positive maps and $T$ is the transposition map.
For higher dimensions, this is in general false.
Does there however (for fixed $d$, $d'$) exist a finite set of positive maps $(P_i)$ such that every general positive map $\Phi$ is a convex combination
$$\Phi = \sum p_i P_i \circ \phi_i$$
where the $\phi_i$ are suitably chosen completely positive maps?
 A: I'm quite late answering this question, but I figured it still deserves an answer. The answer to your question is "no": when $d,d^\prime \geq 3$ there does not exist such a finite (or even countable) set of positive maps.
In arXiv:1209.0437, we considered the following problem: given a set of positive maps $\mathcal{Q}$ from $\mathcal{M}_d$ to $\mathcal{M}_{d^\prime}$, what is the set
$$\mathcal{C}_\mathcal{Q} \stackrel{\text{def}}{=} \{\sum_i \psi_i \circ P_i \circ \phi_i : P_i \in \mathcal{Q}, \psi_i \text{ and } \phi_i \text{ are completely positive for all $i$}\}?$$
As you noted, Størmer and Woronowicz showed that if $\mathcal{Q} = \{T\}$ (where $T$ is the transpose map) and $dd^\prime \leq 6$, then $\mathcal{C}_\mathcal{Q}$ is the set of all positive maps.
We didn't prove it in the paper, but as an offshoot Łukasz Skowronek proved in the $d,d^\prime\geq 3$ case that if $\mathcal{C}_\mathcal{Q}$ is the set of all positive maps then $\mathcal{Q}$ must be uncountable. I don't believe he ever did end up formally writing up the result, but he at least gave a talk about it (slides available here).
The slides go through the proof in pretty good detail: the rough idea is that there is a known uncountably infinite set of positive maps on $\mathcal{M}_3$ that are each exposed in the set of positive maps and are all indecomposable (i.e., can not be written in the form $\phi_1 + T \circ \phi_2$ for some completely positive $\phi_1,\phi_2$) due to Ha and Kye (see arXiv:1108.0130). Łukasz showed that there is no countable set $\mathcal{Q}$ such that $\mathcal{C}_\mathcal{Q}$ contains even just this particular (relatively small) set of positive maps.
Update [May 23, 2016]: It seems that Łukasz finally got around to formally writing up this result, and it is now proved explicitly in this new paper).
