Emil- I'm willing to bet that if you add the time to program any specialized algorithm to the time to solve the problem it will end up being longer than the time to setup and solve the LP. Unless you have a lot of instances of the problem to solve, it's probably not worth investing the human time in programming something for this particular problem.

The LP can be solved in polynomial time, although you won't get this done in linear or quadratic time.

A copy of the Hager paper can be found at: math.ufl.edu/~hager/papers/Regular/sphere.pdf

@Suvrit- I agree that the TRS problem has been studied for a long time. I didn't mean to imply that this was the first paper on the topic, but rather cited this paper because I think it gives the simplest answer to this question. The original poster has many instances of a very scale version of the problem with a fixed $A$ matrix and many different $b$ vectors, so simply using the eigenvalue-eigenvector decomposition of $A$ is the way to go here rather than using something like LSTRS.

I first learned about this stuff in a course that used "Functional Analysis" by Bachman and Narici as the text. The spectral theorem for bounded normal operators is covered in chapter 28. This book is available in an inexpensive reprint edition from Dover.

It's worth mentioning that there's a concept in numerical linear algebra called the "Generalized Singular Value Decomposition (GSVD)" that still has to do with matrices and doesn't have anything to do with Hilbert space.

I have to agree that reading and understanding the ROF paper is a good idea here- that paper is a very widely cited and important source and it includes some more sophisticated ideas than the ones in the first paper that you linked to.