  Non-Euclidean data that are indexed with a scalar predictor such as time are
increasingly encountered in data applications, while statistical methodology
and theory for such random objects are not well developed yet. To address the
need for new methodology in this area, we develop a total variation
regularization technique for nonparametric Fr\'echet regression, which refers
to a regression setting where a response residing in a metric space is paired
with a scalar predictor and the target is a conditional Fr\'echet mean.
Specifically, we seek to approximate an unknown metric-space valued function by
an estimator that minimizes the Fr\'echet version of least squares and at the
same time has small total variation, appropriately defined for metric-space
valued objects. We show that the resulting estimator is representable by a
piece-wise constant function and establish the minimax convergence rate of the
proposed estimator for metric data objects that reside in Hadamard spaces. We
illustrate the numerical performance of the proposed method for both simulated
and real data, including metric spaces of symmetric positive-definite matrices
with the affine-invariant distance, of probability distributions on the real
line with the Wasserstein distance, and of phylogenetic trees with the
Billera--Holmes--Vogtmann metric.
