  In this paper, we present perturbation analysis and randomized algorithms for
the total least squares (TLS) problems. We derive the perturbation bound and
check its sharpness by numerical experiments. Motivated by the recently popular
probabilistic algorithms for low-rank approximations, we develop randomized
algorithms for the TLS and the truncated total least squares (TTLS) solutions
of large-scale discrete ill-posed problems, which can greatly reduce the
computational time and still keep good accuracy.
