Gram-Schmidt with a Weighted Inner Product

Why the Inner Product Changes the Calculation

Gram–Schmidt turns an independent list of vectors into an orthogonal list by subtracting projections onto vectors already constructed. The projection coefficients depend on the inner product: changing how lengths and angles are measured changes the residuals as well. With a weighted inner product, ordinary dot products and ordinary lengths must therefore be replaced consistently at every step. The method is still familiar, but each coefficient and normalization must use the specified weights.

Throughout, vectors are columns in \(\mathbb{R}^n\). Let \(\mathbf{W}\in\mathbb{R}^{n\times n}\) be symmetric and positive definite, meaning \(\mathbf{W}^{\top}=\mathbf{W}\) and \(\mathbf{x}^{\top}\mathbf{W}\mathbf{x}>0\) for every nonzero \(\mathbf{x}\in\mathbb{R}^n\). The corresponding weighted inner product and norm are defined as follows.

A common special case is a diagonal weight matrix \(\mathbf{W}=\operatorname{diag}(w_1,\dots,w_n)\), where every \(w_i>0\). Then \(\langle\mathbf{x},\mathbf{y}\rangle_{\mathbf{W}}=\sum_{i=1}^n w_i x_i y_i\): coordinates with larger weights contribute more to inner products and squared lengths. A weight matrix need not be diagonal, however, as long as it is symmetric and positive definite.

Projection Coefficients with Weights

Suppose \(\mathbf{u}\ne\mathbf{0}\). A multiple \(c\mathbf{u}\) is the weighted projection of \(\mathbf{v}\) onto the line through \(\mathbf{u}\) when the residual \(\mathbf{v}-c\mathbf{u}\) is weighted-orthogonal to \(\mathbf{u}\). This condition determines \(c\), because

The denominator \(\langle\mathbf{u},\mathbf{u}\rangle_{\mathbf{W}}\) is positive: \(\mathbf{u}\ne\mathbf{0}\) and \(\mathbf{W}\) is positive definite. Thus the coefficient is defined and unique.

Proof. Set \(c=\langle\mathbf{v},\mathbf{u}\rangle_{\mathbf{W}}/\langle\mathbf{u},\mathbf{u}\rangle_{\mathbf{W}}\). Substitution gives \(\langle\mathbf{v}-c\mathbf{u},\mathbf{u}\rangle_{\mathbf{W}}=\langle\mathbf{v},\mathbf{u}\rangle_{\mathbf{W}}-c\langle\mathbf{u},\mathbf{u}\rangle_{\mathbf{W}}=0\). Conversely, if \(c\mathbf{u}\) has a residual orthogonal to \(\mathbf{u}\), then this same equality must be zero. Since the denominator is positive, solving for \(c\) gives the stated value, so no other coefficient has this property. \(\square\)

This formula gives the Gram–Schmidt steps. Starting with \(\mathbf{v}_1,\dots,\mathbf{v}_p\), first set \(\mathbf{u}_1=\mathbf{v}_1\). At step \(j\), subtract the weighted projections onto all previously constructed orthogonal vectors:

The residual formula requires each earlier \(\mathbf{u}_i\) to be nonzero; the normalization also requires \(\mathbf{u}_j\ne\mathbf{0}\). In particular, when the input vectors are linearly independent, every residual is nonzero. The next result justifies the procedure and its conditions.

Proof. We use induction on \(j\). At the first step, \(\mathbf{u}_1=\mathbf{v}_1\ne\mathbf{0}\), and its one-vector span agrees with that of \(\mathbf{v}_1\). Suppose the recursion has produced nonzero, pairwise weighted-orthogonal residuals through step \(j-1\), and that their initial segment spans the same vectors as the corresponding initial segment of the input. The formula for \(\mathbf{u}_j\) is defined because every denominator \(\langle\mathbf{u}_i,\mathbf{u}_i\rangle_{\mathbf{W}}\) is positive. For each \(k<j\), take its weighted inner product with \(\mathbf{u}_k\). In the sum, every term with \(i\ne k\) has inner product zero by the induction hypothesis, while the term with \(i=k\) cancels \(\langle\mathbf{v}_j,\mathbf{u}_k\rangle_{\mathbf{W}}\). Thus \(\langle\mathbf{u}_j,\mathbf{u}_k\rangle_{\mathbf{W}}=0\).

Rearranging the recursion expresses \(\mathbf{v}_j\) as \(\mathbf{u}_j\) plus a linear combination of earlier residuals. Therefore the first \(j\) input vectors and the first \(j\) residuals span the same vectors. If \(\mathbf{u}_j=\mathbf{0}\), this rearrangement would express \(\mathbf{v}_j\) as a combination of \(\mathbf{u}_1,\dots,\mathbf{u}_{j-1}\), hence as a combination of \(\mathbf{v}_1,\dots,\mathbf{v}_{j-1}\). That contradicts independence of the input list. So \(\mathbf{u}_j\ne\mathbf{0}\). Finally, division by its positive weighted norm gives \(\langle\mathbf{q}_j,\mathbf{q}_j\rangle_{\mathbf{W}}=1\); orthogonality is preserved by scaling, so the normalized list is orthonormal. \(\square\)

Worked Calculations

Common Mistake: Mixing Two Inner Products

A frequent error is to use an ordinary dot product for the projection coefficient, then use the weighted norm for normalization. In the first example, that mistake gives \(\mathbf{v}_2\cdot\mathbf{u}_1=1\) and \(\mathbf{u}_1\cdot\mathbf{u}_1=2\), so it uses the incorrect coefficient \(1/2\). The resulting residual would be \((1/2,-1/2)^{\top}\). But its weighted inner product with \(\mathbf{u}_1\) is \(1/2+4(-1/2)=-3/2\ne0\), so it is not orthogonal in the specified inner product. The correction is to use the weighted coefficient \(1/5\), which gives the residual \((4/5,-1/5)^{\top}\) and weighted inner product \(4/5-4/5=0\).

The weights must be used both when finding each projection and when computing each length. With a positive-definite weight matrix, the denominator for a nonzero residual is positive, so normalization is valid. If a residual is zero, however, division by its norm is not permitted; the inputs have failed the independence condition needed for the theorem above.