What is the best known complexity for finding a vector $x \in \mathbb{R}^n$ to minimize $||Ax - b||^2$ and/or to solve (when possible) the system of linear equations $Ax=b$?

I am interested in approximation methods that produce $\epsilon$-approximations for arbitrarily small $\epsilon>0$. Specifically, if $A$ is a real-valued $m \times n$ matrix and $b$ a column vector of size $m$, if I can get an answer within $\epsilon$ of optimality via an algorithm that has total complexity $O(mn \log(mn/\epsilon))$, is that good? Or known?

Any related thoughts or references are appreciated.

Some basic comparisons:

i) $O(mn \log(mn/\epsilon))$ seems to be better than Gaussian elimination, which can have higher complexity and has “divide by small number” issues.

ii) The least-square problem of minimizing $||Ax-b||^2$ is the same as finding a vector $x$ to solve the orthogonality equations $A^TAx = A^Tb$, and these orthogonality equations always have (possibly many) solutions $x \in \mathbb{R}^n$. Yet, computing $A^TA$ requires $mn^2$ computations, which is already larger than $O(mn\log(mn/\epsilon))$ (assuming we overlook the log() factors).

iii) Gauss-Seidel iterative methods seem nice but I think (I am not sure) these methods need matrices to be square and to have special structure.