We present a method for computing an approximate Riemannian barycenter of a collection of points lying on a Riemannian manifold. Our approach relies on the use of theoretically proven under- and over-approximations of the Riemannian distance function. We compare it to Riemannian steepest descent on the exact objective function of the Riemannian barycenter and to an approach that approximates the Riemannian logarithm using lifting maps. Experiments are conducted on the Stiefel manifold.