  Notions of depth in regression have been introduced and studied in the
literature. The most famous example is Regression Depth (RD), which is a direct
extension of location depth to regression. The projection regression depth
(PRD) is the extension of another prevailing location depth, the projection
depth, to regression. The computation issues of the RD have been discussed in
the literature. The computation issues of the PRD have never been dealt with
before. The computation issues of the PRD and its induced median (maximum depth
estimator) in a regression setting are addressed now. For a given
$\bs{\beta}\in\R^p$ exact algorithms for the PRD with cost $O(n^2\log n)$
($p=2$) and $O(N(n, p)(p^{3}+n\log n+np^{1.5}+npN_{Iter}))$ ($p>2$) and
approximate algorithms for the PRD and its induced median with cost
respectively $O(N_{\mb{v}}np)$ and $O(Rp
N_{\bs{\beta}}(p^2+nN_{\mb{v}}N_{Iter}))$ are proposed. Here $N(n, p)$ is a
number defined based on the total number of $(p-1)$ dimensional hyperplanes
formed by points induced from sample points and the $\bs{\beta}$; $N_{\mb{v}}$
is the total number of unit directions $\mb{v}$ utilized; $N_{\bs{\beta}}$ is
the total number of candidate regression parameters $\bs{\beta}$ employed;
$N_{Iter}$ is the total number of iterations carried out in an optimization
algorithm; $R$ is the total number of replications. Furthermore, as the second
major contribution, three PRD induced estimators, which can be computed up to
30 times faster than that of the PRD induced median while maintaining a similar
level of accuracy are introduced. Examples and simulation studies reveal that
the depth median induced from the PRD is favorable in terms of robustness and
efficiency, compared to the maximum depth estimator induced from the RD, which
is the current leading regression median.
