In the literature, "sparse least-squares" refer to the problem of minimising $\|Ax-b\|_2^2$ when the design matrix $A$ is sparse. But are there efficient and robust methods for the case when $A$ is full but the normal matrix $A^TA$ is sparse? Obviously one could perform a sparse Cholesky decomposition $A^TA=R^TR$ where $R$ is upper triangular, and sparse. However computing $A^TA$ squares the condition number of $A$, which is sometimes not acceptable.
Thus would there be some clever way to compute $R$, e.g. with a $QR$ decomposition of $A$, that would dramatically reduce the amount of work based on the known sparsity pattern of $R$? For the application I have in mind, the sparsity pattern of $A^TA$ is indeed known ahead of time without the need to compute the actual matrix elements (otherwise my question would not make much sense!). From that, a "symbolic" Cholesky can be used to determine the sparsity pattern of $R$.