How can auto-encoders compute the reconstruction error for the new data?
It is computed just like in training. You take an MSE or something along these lines between the input and the output. You set a threshold for it. If new data's reconstruction error is higher than your threshold, then it is anomalous otherwise it isn't.