Consider a bounded linear operator $A : U \to V$ where $U$ is finite dimensional and where $V$ is a separable Hilbert space, or with large dimension such that $A$ cannot be stored explicitly, being instead available as an algorithm for computing $y \mapsto Ay$. Let $f \in V$ and consider the standard least-squares problem: Find $x \in U$ such that $\|Ax-f\|=\text{min}!$. We assume that inner products of columns of $A$, i.e., the matrix elements of $M = A^*A$, can be computed efficiently, and similarly $A^*f$ can be computed efficiently. However, we also assume that that $M = A^*A$ is ill-conditioned.
Are there efficient algorithms for the solution of this least-squares problem that avoids the ill-conditioning of $A$?