  Consider a channel $W$ along with a given input distribution $P_X$. In
certain settings, such as in the construction of polar codes, the output
alphabet of $W$ is `too large', and hence we replace $W$ by a channel $Q$
having a smaller output alphabet. We say that $Q$ is upgraded with respect to
$W$ if $W$ is obtained from $Q$ by processing its output. In this case, the
mutual information $I(P_X,W)$ between the input and output of $W$ is
upper-bounded by the mutual information $I(P_X,Q)$ between the input and output
of $Q$. In this paper, we present an algorithm that produces an upgraded
channel $Q$ from $W$, as a function of $P_X$ and the required output alphabet
size of $Q$, denoted $L$. We show that the difference in mutual informations is
`small'. Namely, it is $O(L^{-2/(|\mathcal{X}|-1)})$, where $|\mathcal{X}|$ is
the size of the input alphabet. This power law of $L$ is optimal. We complement
our analysis with numerical experiments which show that the developed algorithm
improves upon the existing state-of-the-art algorithms also in non-asymptotic
setups.
