Blog

Quadratic Forms

A quadratic form is a polynomial in which every term has degree two. In two variables it looks like \[f(x_1,x_2)=a_{11}x_1^2+a_{22}x_2^2+2a_{12}x_1x_2.\] With \(n\) variables, a quadratic form can always be written in matrix form, and the matrix \(\mA\) can be chosen to be symmetric:

Definition A quadratic form is called a canonical quadratic form if it has no cross terms, that is, if its matrix is diagonal: \[f(x_1,\ldots,x_n)=\xx^T\mD\xx,\quad\mD\text{ is diagonal}.\]

Theorem 11.6.1

Every quadratic form can be brought to canonical form by a change of variables.

Proof Let \(f(x_1,\ldots,x_n)=\xx^T\mA\xx\) with \(\mA\) symmetric. A symmetric matrix can be diagonalized by an orthogonal matrix \(\mQ\) whose columns are unit-norm eigenvectors: \[\mQ^T\mA\mQ=\mLambda,\qquad\text{so}\qquad\mA=\mQ\mLambda\mQ^T.\] Then, introducing the new variables \(\widetilde{\xx}=\mQ^T\xx\) (equivalently \(\xx=\mQ\widetilde{\xx}\)), \begin{align*} \underbrace{f(x_1,\ldots,x_n)}_{f(\xx)}&=\xx^T\mQ\mLambda\mQ^T\xx\\ &=(\mQ^T\xx)^T\mLambda(\mQ^T\xx)\\ &=\widetilde{\xx}^{\,T}\mLambda\widetilde{\xx}. \end{align*} Thus \(f(\mQ\widetilde{\xx})=\widetilde{\xx}^{\,T}\mLambda\widetilde{\xx}\), which has no cross terms, so the form is in canonical form in the new variables. \(\blacksquare\)

Definition A quadratic form \(\xx^T\mA\xx\) is positive definite if \(\xx^T\mA\xx>0\) for all \(\xx\ne\nul\), and negative definite if \(\xx^T\mA\xx<0\) for all \(\xx\ne\nul\). A symmetric matrix \(\mA\) is called positive (negative) definite if its quadratic form is.

Theorem 11.6.2

The eigenvalues tell us the sign of the form.

Proof Let \(\mQ\) have unit-norm eigenvectors as its columns, so that \(\mA=\mQ\mLambda\mQ^T\). Then, with \(\widetilde{\xx}=\mQ^T\xx\), \begin{align*} \xx^T\mA\xx&=\xx^T(\mQ\mLambda\mQ^T)\xx\\ &=(\mQ^T\xx)^T\mLambda(\mQ^T\xx)\\ &=\widetilde{\xx}^{\,T}\mLambda\widetilde{\xx}\\ &=\sum_{i=1}^n\lambda_i\widetilde{x}_i^2\quad\begin{cases}>0&\text{if all }\lambda_i>0\\<0&\text{if all }\lambda_i<0.\end{cases} \end{align*} Here \(\widetilde{\xx}\ne\nul\) whenever \(\xx\ne\nul\), so at least one term is non-zero and the sign of the sum is the common sign of the eigenvalues. Conversely, if \(\mA\) is positive definite and \((\lambda,\xx)\) is an eigenpair with \(\xx^T\xx=1\), then \(\lambda=\lambda\xx^T\xx=\xx^T\mA\xx>0\); the negative definite case is the same. \(\blacksquare\)

Curve Fitting

In many applications we are given a set of measurements \((x_i,y_i)\), \(1\le i\le N\), where \(x_i\) may be the time or the position of the \(i^{\mathrm{th}}\) measurement.

The relationship between \(x\) and \(y\) is usually assumed to be a parametric function, with a vector \(\vc{\theta}\) of parameters: \[y=f(x;\underbrace{\vc{\theta}}_{\text{the parameters, in vector form}}).\] We then choose the parameters that fit the measurements best. A common choice is the parameters that minimize the sum of the squared errors: \[\sum_{i=1}^N(y_i-f(x_i;\vc{\theta}))^2,\quad\text{or}\quad\vc{\theta}^{\,*}=\operatorname*{arg\,min}_{\vc{\theta}}\sum_{i=1}^N(y_i-f(x_i;\vc{\theta}))^2.\] In general this is solved with numerical optimization tools, such as those available in MATLAB. But in some cases it reduces to linear algebra. This happens when \(f\) is a polynomial in \(x\): \[f(x;\vc{\theta})=\theta_nx^n+\theta_{n-1}x^{n-1}+\cdots+\theta_1x+\theta_0.\] Let \(e_i\) be the error at the point \(x_i\): \[e_i=y_i-(\theta_nx_i^n+\theta_{n-1}x_i^{n-1}+\cdots+\theta_1x_i+\theta_0).\] Collecting all the errors in a vector gives a matrix equation, where \(\mX\) has one row \([1,\ x_i,\ x_i^2,\ \ldots,\ x_i^n]\) per measurement: \[\underbrace{\col{e_1\\\vdots\\e_N}}_{\ev}=\underbrace{\col{y_1\\\vdots\\y_N}}_{\yy}-\underbrace{\col{1&x_1&\cdots&x_1^n\\\vdots&&&\vdots\\1&x_N&\cdots&x_N^n}}_{\mX}\underbrace{\col{\theta_0\\\vdots\\\theta_n}}_{\vc{\theta}}.\]

So the optimization problem is to choose \(\vc{\theta}\) to make the error vector as short as possible: \[\min_{\vc{\theta}}\|\ev\|^2=\min_{\vc{\theta}}\|\yy-\mX\vc{\theta}\|^2.\] This is a best-approximation problem like the one we solved earlier: we look for the vector \(\mX\vc{\theta}\) in the column space of \(\mX\) that is closest to \(\yy\). The answer is characterized by orthogonality: at the optimal \(\vc{\theta}\) the error \(\ev\) must be orthogonal to the column space of \(\mX\), that is, \(\mX^T\ev=\nul\). Substituting \(\ev=\yy-\mX\vc{\theta}\):

The normal equations are always consistent, because the closest point to \(\yy\) in the column space of \(\mX\) always exists (it is the orthogonal projection of \(\yy\)), and it has the form \(\mX\vc{\theta}\) for some \(\vc{\theta}\). So they can be solved for the optimal parameters.

Example Fit a second-order polynomial to the data \(\yy=\col{1\\-1\\3\\2}\) measured at \(x_1=0\), \(x_2=1\), \(x_3=2\), \(x_4=3\). There are three parameters \(\theta_0,\theta_1,\theta_2\), and the normal equations are \[\underbrace{\col{1&0&0\\1&1&1\\1&2&4\\1&3&9}^T}_{\mX^T}\underbrace{\col{1&0&0\\1&1&1\\1&2&4\\1&3&9}}_{\mX}\underbrace{\col{\theta_0\\\theta_1\\\theta_2}}_{\vc{\theta}}=\underbrace{\col{1&0&0\\1&1&1\\1&2&4\\1&3&9}^T}_{\mX^T}\underbrace{\col{1\\-1\\3\\2}}_{\yy}\] Multiplying out, \[\col{4&6&14\\6&14&36\\14&36&98}\col{\theta_0\\\theta_1\\\theta_2}=\col{5\\11\\29}.\] Solving this system gives the best-fit parameters \[\vc{\theta}=\col{9/20\\-1/20\\1/4}.\]