Redshift determination through weighted phase correlation: a linearithmic implementation

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 at best in a weighted chi-squared sense. The proposed implementation is based on an orthogonalization algorithm and thus also benefits from a high numerical stability. We successfully apply this method to the redshift determination of quasars from the twelfth Sloan Digital Sky Survey (SDSS) quasar catalog and derive the proper spectral reduction and redshift selection methods. Also provided are the derivations of the redshift uncertainty and of the associated confidence. Results of this application are comparable to the performances of the SDSS pipeline while not having a quadratic time dependency.