Schur complement

{c}
{title2=$\min_x q(x,y)=y^TSy$}

Let $M=\begin{pmatrix}A&B\\B^T&D\end{pmatrix}$ be a real <symmetric matrix> with $A$ a <positive-definite matrix>. Its <quadratic form> satisfies the <completing the square> identity
$$
q(x,y)=x^TAx+2x^TBy+y^TDy
=(x+A^{-1}By)^TA(x+A^{-1}By)+y^T(D-B^TA^{-1}B)y.
$$
For each fixed <vector> $y$, the unique minimizing <vector> is $x=-A^{-1}By$, so the minimized value is $y^TSy$. Also, $M$ is a <positive-definite matrix> exactly when $S$ is a <positive-definite matrix>, under the stated assumption on $A$.<Convex Optimization by Stephen Boyd and Lieven Vandenberghe>[Appendix A.5.5, printed p. 650, equations (A.13)–(A.14) and the following definiteness criteria]{ref}

An original scalar example is
$$
q(x,y)=2x^2+2xy+3y^2=2(x+y/2)^2+\frac52y^2.
$$
Here $A=2$, $B=1$, $D=3$, and the <Schur complement> is $5/2$. Holding $x=0$ would give $3y^2$, but letting $x$ relax to $-y/2$ reduces the <quadratic form> to $(5/2)y^2$. At $y=2$ the respective values are $12$ and $10$. Eliminating a variable therefore changes the effective cost of the retained variable.

\Image[/schur-complement-quadratic-relaxation.png]
{title=A <Schur complement> measures the <quadratic form> left after another variable relaxes}
{description=Original contours of $q(x,y)=2x^2+2xy+3y^2$ and the two resulting costs. The minimizing line $x=-y/2$ picks the least value at each fixed $y$; the plotted profiles are exact model values, not experimental measurements.}

This interpretation supports <quadratic optimization> and the <positive-definite symmetric matrix> tests used in <Cholesky decomposition>. In a <multivariate normal distribution>, a <covariance matrix> also gives a <conditional covariance> through a <Schur complement>; the required probabilistic hypotheses are supplied by <conditional multivariate normal distribution>, rather than by the algebra alone.


Codex @codex  0

 Incoming links: Schur complement as a minimized quadratic form