# Condition number of $AA^T$ when $A$ is polynomial Vandermonde

Suppose I'm doing polynomial regression of degree $m$

$$p(x, \mathbf{w}) = w_0 + w_1x + \dotsb + w_mx^m$$

given training data $(x_1, t_1), \dotsc, (x_N, t_N)$. Suppose I'm using the loss function

$$L(\mathbf{w}) = \frac12 \sum_{j=1}^N \big( p(x_j, \mathbf{w}) - t_j \big)^2$$

The Hessian of the loss function is $AA^T$, where $A_{ij} = {x_{(i)}}^{j-1}$. What can be said about the eigenvalues of the positive definite matrix $AA^T$, as we vary which $x_{i}$ we choose? Specifically its condition number?

There are estimates on the condition number of Vandermonde matrices . There is generally some theory there are "knots" in them. It states the condition number is exponential in $n$. Note then you are squaring the condition number because you took covariance matrix of $A$. On page 9, here

$$\kappa(V_{s})\geq \eta^{\rho}(\eta-1)r(\sqrt{n}/2)$$

You'd have look through this paper more but the main constraints are that this is an $n\times n$ vandermonde matrix. $\eta$ appears to be in a disc.

Note the relationship between the condition number and the eigenvalues is

$$\kappa(A) = \frac{|\lambda_{max}(A) |}{|\lambda_{min}(A)|}$$

The estimate for the conditioning of rectangular vandermonde matrices can be found here. Page 684 Theorem 6 there is a theorem that bounds that condition number. The theorem states the following.

Theorem 6: Let $W_{n}$ be the $n \times N$ Vandermonde matrix with nodes $z_{j}$ in the unit disk. Define $\alpha = max_{j} |z_{j}| \beta = min_{j} |z_{j}|$ and $\delta = min_{j,k}|z_{j}-z_{k}| , j \neq k$ also let $D_{N}$ be the departure from normality of the matrix $F_{N}$ defined in (2.3)that is $D_{N}^{2} = D^{2}(F_{N}) = \| F_{N} \|_{N}^{2} -( |z_{1}|^{2} + \cdots + |z_{n}|^{2}$ then for $N > n \geq 2$ the $2$ norm condition number of $W_{N}$ satisfies.

$$\tag{3.4} \frac{\sigma_{1}(F_{N})}{\alpha} \leq \kappa_{2}(W_{N})\leq \frac{1}{2}\left( \eta + \sqrt{\eta^{2} - 4} \right)$$

where $\eta = \rho - n +2$

$$\tag{3.5} \rho = n \bigg[ 1 + \frac{D_{N}^{2}}{(n-1)\delta^{2}}\bigg]^{\frac{n-1}{2}} \phi_{N}(\alpha,\beta)$$

$$\tag{3.6} \phi(\alpha,\beta) = \sqrt{\frac{1+\alpha^{2}+\alpha^{4}+\cdots+\alpha^{2(N-1)}}{1+\beta^{2}+\beta^{4}+\cdots+\beta^{2(N-1)}}}$$

The proof of the theorem is found beneath it.

• Thanks for this. Still looking for some info that applies when $m\neq n$ – Eric Auld Aug 13 '18 at 9:01
• I'll attempt to find something. – Shogun Aug 13 '18 at 10:22
• edited, see the link – Shogun Aug 13 '18 at 20:34
• Thanks. How did you go about searching for it? I have some things to learn about finding references. (We could continue in chat or whatever.) – Eric Auld Aug 13 '18 at 23:44
• I did a search on google scholar for the condition number of vandermonde matrices. searched a little went back to google, searched "condition number of nonsquare vandermonde matrices". it is the second one down. It was pay walled and I used sci hub. – Shogun Aug 14 '18 at 0:58