  We consider the problem of solving linear least squares problems in a
framework where only evaluations of the linear map are possible. We derive
randomized methods that do not need any other matrix operations than forward
evaluations, especially no evaluation of the adjoint map is needed. Our method
is motivated by the simple observation that one can get an unbiased estimate of
the application of the adjoint. We show convergence of the method and then
derive a more efficient method that uses an exact linesearch. This method,
called random descent, resembles known methods in other context and has the
randomized coordinate descent method as special case. We provide convergence
analysis of the random descent method emphasizing the dependence on the
underlying distribution of the random vectors. Furthermore we investigate the
applicability of the method in the context of ill-posed inverse problems and
show that the method can have beneficial properties when the unknown solution
is rough. We illustrate the theoretical findings in numerical examples. One
particular result is that the random descent method actually outperforms
established transposed-free methods (TFQMR and CGS) in examples.
