What about x^k+x^l where l<k? How could you get the triangle for x^k+x^l given the triangles for x^l and x^k seperately?
Have you tried to reconstruct your polynomial given this left diagonal?
You can't really do any better than just storing the coefficients. "Randomish" data isn't likely to fit on a polynomial of lower degree to make compression possible.
You may know this, but given any sequence of numbers x(1),..,x(n) you can find a degree n-1 polynomial where f(i)=x(i). So when you are saying this sequence (or others) can't be a polynomial, what do you mean exactly? Some conditions on the degree? You will be able to say something about the minimum degree required from the difference table.