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.

  • $\begingroup$ Thanks for this. Still looking for some info that applies when $m\neq n$ $\endgroup$ – Eric Auld Aug 13 '18 at 9:01
  • $\begingroup$ I'll attempt to find something. $\endgroup$ – Shogun Aug 13 '18 at 10:22
  • 1
    $\begingroup$ edited, see the link $\endgroup$ – Shogun Aug 13 '18 at 20:34
  • $\begingroup$ 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.) $\endgroup$ – Eric Auld Aug 13 '18 at 23:44
  • $\begingroup$ 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. $\endgroup$ – Shogun Aug 14 '18 at 0:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.