Positive definite Hermitian matrices form a Cartan-Hadamard manifold and the explicite expressions of geodesics in this manifold are known (see R. Bhatia's book "Positive definite matrices"), so that your problem can be solved by the subgradient algorithm in the following article:

Riemannian median and its estimation, LMS J.Comput. Math. 13(2010), 461-479

Moreover, stochatic algorithms for finding p-means (p=1 for medians and p=2 for barycenters) in Riemannian manifolds can be found in the article:

Stochastic algorithms for computing means of probability measures, Stochastic Processes and their Applications, Volume 122, Issue 4, April 2012, Pages 1437–1455

Deterministic algorithms for computing p-means can be found in Chpter 4 of the thesis (French title but English contents):

http://tel.archives-ouvertes.fr/tel-00664188

Positive definite Hermitian matrices form a Cartan-Hadamard manifold the Riemannian distance and the explicite expressions of geodesics in this manifold are known (see R. Bhatia's book "Positive definite matrices"), so that your problem can be solved by the subgradient algorithm in the following article:

Riemannian median and its estimation, LMS J.Comput. Math. 13(2010), 461-479

Moreover, stochatic algorithms for finding p-means (p=1 for medians and p=2 for barycenters) in Riemannian manifolds can be found in the article:

Stochastic algorithms for computing means of probability measures, Stochastic Processes and their Applications, Volume 122, Issue 4, April 2012, Pages 1437–1455

Deterministic algorithms for computing p-means can be found in Chpter 4 of the thesis (French title but English contents):

http://tel.archives-ouvertes.fr/tel-00664188