In this paper we develop a randomized block-coordinate descent method for
minimizing the sum of a smooth and a simple nonsmooth block-separable convex
function and prove that it obtains an $\epsilon$-accurate solution with
probability at least $1-\rho$ in at most $O(\tfrac{n}{\epsilon} \log
\tfrac{1}{\rho})$ iterations, where $n$ is the number of blocks. For strongly
convex functions the method converges linearly.