Title: Redshift determination through weighted phase correlation: a linearithmic implementation,
Abstract: We present a new algorithm having a time complexity of O(N log N) and
designed to retrieve the phase at which an input signal and a set of not
necessarily orthogonal templates match best in a weighted chi-squared sense.
The proposed implementation is based on an orthogonalization algorithm and thus
also benefits from high numerical stability. We apply this method successfully
to the redshift determination of quasars from the twelfth Sloan Digital Sky
Survey (SDSS) quasar catalogue and derive the proper spectral reduction and
redshift selection methods. Derivations of the redshift uncertainty and the
associated confidence are also provided. The results of this application are
comparable to the performance of the SDSS pipeline, while not having a
quadratic time dependence.