# Solving Linear Least Squares for polynomial fitting, ill-conditioned

In trying to fit polynomials to data, I have a tall and skinny matrix $$A$$, of size $$\simeq 250,000 \times 1000$$, that is quite ill-conditioned $$\kappa(A) \simeq 10^{78}$$.

I am solving it by pivoted QR, but the results get worse when adding more data points, and more polynomials.

I tried building the normal form $$A^TA$$, but the condition number is worse, and the smallest eigenvalue is around $$-10^3$$, which is strange for a symmetric positive matrix... I expect that this is due to floating point arithmetic, and it should not matter if the conditioning is better.

Could preconditioning help? I saw somewhere that rescaling the grid on which the polynomials live might make it better.

Any other ideas?

• Are you trying to fit your data (250k points) with polynomial of the order 1000? – Vasily Mitch Feb 12 at 11:54
• It is multidimensional data, and I have a bunch of polynomials of degree 6. In fact, each polynomial is multiplied by a gaussian centered at a different point, hence the number of parameters. – user288227 Feb 12 at 11:57

In case someone else is facing this particular issue: my matrix did not have full numerical rank, there was a bunch of singular values below $$10^{-16}$$, but none was exactly zero, hence the condition number blew up. However pivoted QR (in Julia) calculates this numerical rank, and the backslash operator solves the system by inverting with respect to the well-conditioned submatrix. My problem is somewhere else...